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
Publisher: Taylor & Francis
Source: IIE transactions, 2001, v. 33, no. 5, p. 413-420 How to cite?
Journal: IIE transactions 
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.
URI: http://hdl.handle.net/10397/9364
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

28
Last Week
0
Last month
0
Citations as of Nov 23, 2017

WEB OF SCIENCETM
Citations

24
Last Week
0
Last month
0
Citations as of Nov 16, 2017

Page view(s)

54
Last Week
2
Last month
Checked on Nov 20, 2017

Google ScholarTM

Check

Altmetric



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