Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/630
PIRA download icon_1.1View/Download Full Text
DC FieldValueLanguage
dc.contributorDepartment of Logistics and Maritime Studies-
dc.creatorYuan, JJ-
dc.creatorLiu, Z-
dc.creatorNg, CTD-
dc.creatorCheng, TCE-
dc.date.accessioned2014-12-11T08:24:42Z-
dc.date.available2014-12-11T08:24:42Z-
dc.identifier.issn0304-3975-
dc.identifier.urihttp://hdl.handle.net/10397/630-
dc.language.isoenen_US
dc.publisherElsevieren_US
dc.rightsTheoretical Computer Science © 2004 Elsevier B.V. The journal web site is located at http://www.sciencedirect.com.en_US
dc.subjectSchedulingen_US
dc.subjectFamilyen_US
dc.subjectBatchingen_US
dc.subjectMakespanen_US
dc.titleThe unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespanen_US
dc.typeJournal/Magazine Articleen_US
dc.description.otherinformationAuthor name used in this publication: Z. H. Liuen_US
dc.description.otherinformationAuthor name used in this publication: T. C. E. Chengen_US
dc.identifier.spage199-
dc.identifier.epage212-
dc.identifier.volume320-
dc.identifier.issue2-3-
dc.identifier.doi10.1016/j.tcs.2004.01.038-
dcterms.abstractIn this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n(n/m+1)[sup m]) time dynamic programming algorithm and an O(mk[sup k+1]P[sup 2k−1]) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem.-
dcterms.accessRightsopen accessen_US
dcterms.bibliographicCitationTheoretical computer science, 14 June 2004, v. 320. no. 2-3, p. 199-212-
dcterms.isPartOfTheoretical computer science-
dcterms.issued2004-06-14-
dc.identifier.isiWOS:000221936000004-
dc.identifier.scopus2-s2.0-2442684605-
dc.identifier.rosgroupidr17579-
dc.description.ros2003-2004 > Academic research: refereed > Publication in refereed journal-
dc.description.oaAccepted Manuscripten_US
dc.identifier.FolderNumberOA_IR/PIRAen_US
dc.description.pubStatusPublisheden_US
Appears in Collections:Journal/Magazine Article
Files in This Item:
File Description SizeFormat 
p-batch-family-makespan_Revised(TCSA2205).pdfPre-published version191.92 kBAdobe PDFView/Open
Open Access Information
Status open access
File Version Final Accepted Manuscript
Access
View full-text via PolyU eLinks SFX Query
Show simple item record

Page views

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

Downloads

170
Citations as of Mar 24, 2024

SCOPUSTM   
Citations

33
Last Week
0
Last month
1
Citations as of Mar 28, 2024

WEB OF SCIENCETM
Citations

31
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.