Single machine batch scheduling problem with family setup times and release dates to minimize makespan

Single machine batch scheduling problem with family setup times and release dates to minimize makespan

0.00 Avg rating0 Votes
Article ID: iaor20081247
Country: United Kingdom
Volume: 9
Issue: 6
Start Page Number: 499
End Page Number: 513
Publication Date: Dec 2006
Journal: Journal of Scheduling
Authors: , , ,
Keywords: heuristics, programming: dynamic
Abstract:

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((n/m) + 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.

Reviews

Required fields are marked *. Your email address will not be published.