TY - GEN
T1 - Parallel machine scheduling through column generation
T2 - 14th Annual European Symposium on Algorithms, ESA 2006
AU - Van Den Akker, J. M.
AU - Hoogeveen, J. A.
AU - Van Kempen, J. W.
PY - 2006
Y1 - 2006
N2 - In this paper we consider one of the basic problems in scheduling and project management: scheduling on parallel identical machines. We present a solution framework for a number of scheduling problems in which the goal is to find a feasible schedule that minimizes some objective function of the minimax type on a set of parallel, identical machines, subject to release dates, deadlines, and/or generalized precedence constraints. Our framework is based on column generation. Although column generation has been successfully applied to many parallel machine scheduling problems with objective functions of the minsum type, the number of applications for minimax objective functions is still small. We determine a lower bound on the objective function in the following way. We first turn the minimization problem into a decision problem by bounding the outcome value. We then ask ourselves 'Are m machines enough to feasibly accommodate all jobs?'. We formulate this as an integer linear programming problem and we determine a high quality lower bound by applying column generation to the LP-relaxation; if this lower bound is more than m, then we can conclude infeasibility. To speed up the process, we compute an intermediate lower bound based on the outcome of the pricing problem. As the pricing problem is intractable for many variants of the original scheduling problem, we mostly solve it approximately by applying local search, but once in every 50 iterations or when local search fails, we use a time-indexed integer linear programming formulation to solve the pricing problem. After having derived the lower bound on the objective function of the original scheduling problem, we try to find a matching upper bound by identifying a feasible schedule with objective function value equal to this lower bound. Our computational results show that our lower bound is so strong that this almost always succeeds. We are able to solve problems with up to 160 jobs and 10 machines in 10 minutes on average.
AB - In this paper we consider one of the basic problems in scheduling and project management: scheduling on parallel identical machines. We present a solution framework for a number of scheduling problems in which the goal is to find a feasible schedule that minimizes some objective function of the minimax type on a set of parallel, identical machines, subject to release dates, deadlines, and/or generalized precedence constraints. Our framework is based on column generation. Although column generation has been successfully applied to many parallel machine scheduling problems with objective functions of the minsum type, the number of applications for minimax objective functions is still small. We determine a lower bound on the objective function in the following way. We first turn the minimization problem into a decision problem by bounding the outcome value. We then ask ourselves 'Are m machines enough to feasibly accommodate all jobs?'. We formulate this as an integer linear programming problem and we determine a high quality lower bound by applying column generation to the LP-relaxation; if this lower bound is more than m, then we can conclude infeasibility. To speed up the process, we compute an intermediate lower bound based on the outcome of the pricing problem. As the pricing problem is intractable for many variants of the original scheduling problem, we mostly solve it approximately by applying local search, but once in every 50 iterations or when local search fails, we use a time-indexed integer linear programming formulation to solve the pricing problem. After having derived the lower bound on the objective function of the original scheduling problem, we try to find a matching upper bound by identifying a feasible schedule with objective function value equal to this lower bound. Our computational results show that our lower bound is so strong that this almost always succeeds. We are able to solve problems with up to 160 jobs and 10 machines in 10 minutes on average.
KW - Column generation
KW - Intermediate lower bounds
KW - Linear programming
KW - Maximum lateness
KW - Parallel machine scheduling
KW - Precedence constraints
KW - Release dates
KW - Set covering formulation
KW - Time-indexed formulation
UR - http://www.scopus.com/inward/record.url?scp=33750695647&partnerID=8YFLogxK
U2 - 10.1007/11841036_58
DO - 10.1007/11841036_58
M3 - Conference contribution
AN - SCOPUS:33750695647
SN - 3540388753
SN - 9783540388753
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 648
EP - 659
BT - Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
PB - Springer
Y2 - 11 September 2006 through 13 September 2006
ER -