Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/6036
Title: | Single machine scheduling to minimize batch delivery and job earliness penalties | Authors: | Cheng, TCE Kovalyov, MY Lin, BM |
Issue Date: | May-1997 | Source: | SIAM journal on optimization, May 1997, v. 7, no. 2, p. 547-559 | 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. | Keywords: | Single machine scheduling Batch scheduling NP-hardness Dynamic programming Polynomial algorithms |
Publisher: | Society for Industrial and Applied Mathematics | Journal: | SIAM Journal on optimization | 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 | Size | Format | |
---|---|---|---|---|
Cheng_Single_Machine_Batch.pdf | 311.07 kB | Adobe PDF | View/Open |
Page views
97
Last Week
1
1
Last month
Citations as of Mar 24, 2024
Downloads
182
Citations as of Mar 24, 2024
SCOPUSTM
Citations
31
Last Week
0
0
Last month
0
0
Citations as of Mar 28, 2024
WEB OF SCIENCETM
Citations
25
Last Week
0
0
Last month
0
0
Citations as of Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.