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)m) time dynamic programming algorithm and an O(mkk+1P2k-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.
| Original language | English |
|---|---|
| Pages (from-to) | 199-212 |
| Number of pages | 14 |
| Journal | Theoretical Computer Science |
| Volume | 320 |
| Issue number | 2-3 |
| DOIs | |
| Publication status | Published - 14 Jun 2004 |
Keywords
- Batching
- Family
- Makespan
- Scheduling
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
Fingerprint
Dive into the research topics of 'The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan'. Together they form a unique fingerprint.Prizes
-
Outstanding Natural Sciences Paper Award
Yuan, J. J. (Recipient), Liu, Z. H. (Recipient), Ng, C. T. (Recipient) & Cheng, E. T. C. (Recipient), Jul 2006
Prize: Prize (research)
-
Outstanding Science and Technology Paper Award
Yuan, J. J. (Recipient), Liu, Z. H. (Recipient), Ng, C. T. (Recipient) & Cheng, E. T. C. (Recipient), Aug 2006
Prize: Prize (research)