Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/6036
DC Field | Value | Language |
---|---|---|
dc.contributor | Department of Logistics and Maritime Studies | - |
dc.creator | Cheng, TCE | - |
dc.creator | Kovalyov, MY | - |
dc.creator | Lin, BM | - |
dc.date.accessioned | 2014-12-11T08:28:07Z | - |
dc.date.available | 2014-12-11T08:28:07Z | - |
dc.identifier.issn | 1052-6234 | - |
dc.identifier.uri | http://hdl.handle.net/10397/6036 | - |
dc.language.iso | en | en_US |
dc.publisher | Society for Industrial and Applied Mathematics | en_US |
dc.rights | © 1997 Society for Industrial and Applied Mathematics | en_US |
dc.subject | Single machine scheduling | en_US |
dc.subject | Batch scheduling | en_US |
dc.subject | NP-hardness | en_US |
dc.subject | Dynamic programming | en_US |
dc.subject | Polynomial algorithms | en_US |
dc.title | Single machine scheduling to minimize batch delivery and job earliness penalties | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.spage | 547 | - |
dc.identifier.epage | 559 | - |
dc.identifier.volume | 7 | - |
dc.identifier.issue | 2 | - |
dc.identifier.doi | 10.1137/S1052623494269540 | - |
dcterms.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. | - |
dcterms.accessRights | open access | en_US |
dcterms.bibliographicCitation | SIAM journal on optimization, May 1997, v. 7, no. 2, p. 547-559 | - |
dcterms.isPartOf | SIAM Journal on optimization | - |
dcterms.issued | 1997-05 | - |
dc.identifier.isi | WOS:A1997WW81700016 | - |
dc.identifier.scopus | 2-s2.0-0031493530 | - |
dc.identifier.eissn | 1095-7189 | - |
dc.description.oa | Version of Record | en_US |
dc.identifier.FolderNumber | OA_IR/PIRA | en_US |
dc.description.pubStatus | Published | en_US |
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.