The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan

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
Issue Date:	14-Jun-2004
Source:	Theoretical computer science, 14 June 2004, v. 320. no. 2-3, p. 199-212
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.
Keywords:	Scheduling Family Batching Makespan
Publisher:	Elsevier
Journal:	Theoretical computer science
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

File	Description	Size	Format
p-batch-family-makespan_Revised(TCSA2205).pdf	Pre-published version	191.92 kB	Adobe PDF	View/Open

Status	open access
File Version	Final Accepted Manuscript

View full-text via PolyU eLinks

100

Last Week
1

Last month

Citations as of May 28, 2023

157

Citations as of May 28, 2023

34

Last Week
0

Last month
1

Citations as of May 25, 2023

31

Last Week
0

Last month
0

Citations as of May 25, 2023

Check