Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/9364
Title: Single machine batch scheduling with sequential job processing
Authors: Cheng, TCE 
Kovalyov, MY
Issue Date: 2001
Source: IIE transactions, 2001, v. 33, no. 5, p. 413-420
Abstract: The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both the bounded and unbounded problems in which all due dates and/or processing times are equal. Several special cases of the bounded problem are shown to be NP-hard. Thus, a comprehensive classification of the computational complexities of the special cases is provided.
Publisher: Taylor & Francis
Journal: IIE transactions 
ISSN: 0740-817X
EISSN: 1545-8830
DOI: 10.1023/A:1011005314354
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

32
Last Week
0
Last month
0
Citations as of Sep 6, 2020

WEB OF SCIENCETM
Citations

27
Last Week
0
Last month
0
Citations as of Sep 17, 2020

Page view(s)

145
Last Week
0
Last month
Citations as of Sep 13, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.