TY - JOUR
T1 - Column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem
AU - Chen, Zhi Long
AU - Powell, Warren Buckler
N1 - Funding Information:
The first author was supported in part by the University of Pennsylvania Research Foundation Award. The second author was supported in part by grant AFOSR-F49620-93-1-0098 from the Air Force Office of Scientific Research.
PY - 1999/7/1
Y1 - 1999/7/1
N2 - We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig-Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.
AB - We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig-Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.
UR - http://www.scopus.com/inward/record.url?scp=0032641373&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032641373&partnerID=8YFLogxK
U2 - 10.1016/S0377-2217(98)00136-2
DO - 10.1016/S0377-2217(98)00136-2
M3 - Article
AN - SCOPUS:0032641373
SN - 0377-2217
VL - 116
SP - 220
EP - 232
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -