In this paper we consider the single machine batch scheduling problem with family setup times and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n (m-n+1)m) time dynamic programming algorithm and an O(mkkP2k-1) time dynamic programming algorithm for the problem, 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 setup times of all the families and the processing times of all the jobs. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme (PTAS) for the problem.
- Release dates
ASJC Scopus subject areas
- Management Science and Operations Research
- Artificial Intelligence