Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/630
DC Field | Value | Language |
---|---|---|
dc.contributor | Department of Logistics and Maritime Studies | - |
dc.creator | Yuan, JJ | - |
dc.creator | Liu, Z | - |
dc.creator | Ng, CTD | - |
dc.creator | Cheng, TCE | - |
dc.date.accessioned | 2014-12-11T08:24:42Z | - |
dc.date.available | 2014-12-11T08:24:42Z | - |
dc.identifier.issn | 0304-3975 | - |
dc.identifier.uri | http://hdl.handle.net/10397/630 | - |
dc.language.iso | en | en_US |
dc.publisher | Elsevier | en_US |
dc.rights | Theoretical Computer Science © 2004 Elsevier B.V. The journal web site is located at http://www.sciencedirect.com. | en_US |
dc.subject | Scheduling | en_US |
dc.subject | Family | en_US |
dc.subject | Batching | en_US |
dc.subject | Makespan | en_US |
dc.title | The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.description.otherinformation | Author name used in this publication: Z. H. Liu | en_US |
dc.description.otherinformation | Author name used in this publication: T. C. E. Cheng | en_US |
dc.identifier.spage | 199 | - |
dc.identifier.epage | 212 | - |
dc.identifier.volume | 320 | - |
dc.identifier.issue | 2-3 | - |
dc.identifier.doi | 10.1016/j.tcs.2004.01.038 | - |
dcterms.abstract | In 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.accessRights | open access | en_US |
dcterms.bibliographicCitation | Theoretical computer science, 14 June 2004, v. 320. no. 2-3, p. 199-212 | - |
dcterms.isPartOf | Theoretical computer science | - |
dcterms.issued | 2004-06-14 | - |
dc.identifier.isi | WOS:000221936000004 | - |
dc.identifier.scopus | 2-s2.0-2442684605 | - |
dc.identifier.rosgroupid | r17579 | - |
dc.description.ros | 2003-2004 > Academic research: refereed > Publication in refereed journal | - |
dc.description.oa | Accepted Manuscript | 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 | |
---|---|---|---|---|
p-batch-family-makespan_Revised(TCSA2205).pdf | Pre-published version | 191.92 kB | Adobe PDF | View/Open |
Page views
124
Last Week
1
1
Last month
Citations as of Mar 24, 2024
Downloads
170
Citations as of Mar 24, 2024
SCOPUSTM
Citations
33
Last Week
0
0
Last month
1
1
Citations as of Mar 28, 2024
WEB OF SCIENCETM
Citations
31
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.