Please use this identifier to cite or link to this item:
Title: Single machine scheduling to minimize batch delivery and job earliness penalties
Authors: Cheng, TCE 
Kovalyov, MY
Lin, BM
Keywords: Single machine scheduling
Batch scheduling
Dynamic programming
Polynomial algorithms
Issue Date: May-1997
Publisher: Society for Industrial and Applied Mathematics
Source: SIAM journal on optimization, May 1997, v. 7, no. 2, p. 547-559 How to cite?
Journal: SIAM Journal on optimization 
Abstract: We study a problem in which a set of n jobs has to be batched as well as scheduled for processing on a single machine. A constant machine set-up time is required before the first job of each batch is processed. A schedule specifies the sequence of batches, where each batch comprises a sequence of jobs. The batch delivery time is defined as the completion time of the last job in a batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and the job completion time. The objective is to find a number B of batches and a schedule so as to minimize the sum of the total weighted job earliness and mean batch delivery time. The problem is shown to be strongly NP-hard. It remains strongly NP-hard if the set-up time is zero and B ≤ U for any variable U ≥ 2 or if B ≥ U for any constant U ≥ 2. The problem is proved to be ordinary NP-hard even if the set-up time is zero and B ≤ 2. For the case B ≤ U, a dynamic programming algorithm is presented, which is pseudopolynomial for any constant U ≥ 2. Algorithms with O(n²) running times are derived for the cases when all weights are equal or all processing times are equal. For the general problem, a family of heuristics is suggested. Computational experiments on the proposed heuristic algorithm are conducted. The results suggest that the heuristics are effective in generating near-optimal solutions quickly.
ISSN: 1052-6234
EISSN: 1095-7189
DOI: 10.1137/S1052623494269540
Rights: © 1997 Society for Industrial and Applied Mathematics
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
Cheng_Single_Machine_Batch.pdf311.07 kBAdobe PDFView/Open
View full-text via PolyU eLinks SFX Query
Show full item record
PIRA download icon_1.1View/Download Contents


Last Week
Last month
Citations as of Oct 4, 2018


Last Week
Last month
Citations as of Oct 10, 2018

Page view(s)

Last Week
Last month
Citations as of Oct 14, 2018


Citations as of Oct 14, 2018

Google ScholarTM



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