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 |
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
100
Last Week
1
1
Last month
Citations as of May 28, 2023
Downloads
157
Citations as of May 28, 2023
SCOPUSTM
Citations
34
Last Week
0
0
Last month
1
1
Citations as of May 25, 2023
WEB OF SCIENCETM
Citations
31
Last Week
0
0
Last month
0
0
Citations as of May 25, 2023

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