Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/6036
PIRA download icon_1.1View/Download Full Text
DC FieldValueLanguage
dc.contributorDepartment of Logistics and Maritime Studies-
dc.creatorCheng, TCE-
dc.creatorKovalyov, MY-
dc.creatorLin, BM-
dc.date.accessioned2014-12-11T08:28:07Z-
dc.date.available2014-12-11T08:28:07Z-
dc.identifier.issn1052-6234-
dc.identifier.urihttp://hdl.handle.net/10397/6036-
dc.language.isoenen_US
dc.publisherSociety for Industrial and Applied Mathematicsen_US
dc.rights© 1997 Society for Industrial and Applied Mathematicsen_US
dc.subjectSingle machine schedulingen_US
dc.subjectBatch schedulingen_US
dc.subjectNP-hardnessen_US
dc.subjectDynamic programmingen_US
dc.subjectPolynomial algorithmsen_US
dc.titleSingle machine scheduling to minimize batch delivery and job earliness penaltiesen_US
dc.typeJournal/Magazine Articleen_US
dc.identifier.spage547-
dc.identifier.epage559-
dc.identifier.volume7-
dc.identifier.issue2-
dc.identifier.doi10.1137/S1052623494269540-
dcterms.abstractWe 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.accessRightsopen accessen_US
dcterms.bibliographicCitationSIAM journal on optimization, May 1997, v. 7, no. 2, p. 547-559-
dcterms.isPartOfSIAM Journal on optimization-
dcterms.issued1997-05-
dc.identifier.isiWOS:A1997WW81700016-
dc.identifier.scopus2-s2.0-0031493530-
dc.identifier.eissn1095-7189-
dc.description.oaVersion of Recorden_US
dc.identifier.FolderNumberOA_IR/PIRAen_US
dc.description.pubStatusPublisheden_US
Appears in Collections:Journal/Magazine Article
Files in This Item:
File Description SizeFormat 
Cheng_Single_Machine_Batch.pdf311.07 kBAdobe PDFView/Open
Open Access Information
Status open access
File Version Version of Record
Access
View full-text via PolyU eLinks SFX Query
Show simple item record

Page views

97
Last Week
1
Last month
Citations as of Mar 24, 2024

Downloads

182
Citations as of Mar 24, 2024

SCOPUSTM   
Citations

31
Last Week
0
Last month
0
Citations as of Mar 28, 2024

WEB OF SCIENCETM
Citations

25
Last Week
0
Last month
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.