Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/630
Title: The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan
Authors: Yuan, JJ
Liu, Z
Ng, CTD 
Cheng, TCE 
Keywords: Scheduling
Family
Batching
Makespan
Issue Date: 14-Jun-2004
Publisher: Elsevier B.V.
Source: Theoretical computer science, 14 June 2004, v. 320. no. 2-3, p. 199-212 How to cite?
Journal: Theoretical computer science 
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.
URI: http://hdl.handle.net/10397/630
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2004.01.038
Rights: Theoretical Computer Science © 2004 Elsevier B.V. The journal web site is located at http://www.sciencedirect.com.
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
Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

29
Last Week
0
Last month
1
Citations as of Jun 4, 2016

WEB OF SCIENCETM
Citations

25
Last Week
0
Last month
0
Citations as of Dec 7, 2016

Page view(s)

516
Last Week
1
Last month
Checked on Dec 4, 2016

Download(s)

646
Checked on Dec 4, 2016

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.