TY - GEN
T1 - Column generation for sequence dependent flowshop scheduling to minimize the total weighted tardiness
AU - Nishi, Tatsushi
AU - Isoya, Yukinori
AU - Inuiguchi, Masahiro
PY - 2011
Y1 - 2011
N2 - We propose a column generation algorithm for solving sequence dependent flowshop scheduling problems (SDST flowshop) to minimize the total weighted tardiness. The continuous relaxation of the set partitioning formulation of the Dantzig-Wolfe decomposition for SDST flowshop is solved by the column generation. The pricing subproblem for the column generation is decomposed into each job-level subproblem. In order to strengthen the lower bound, the additional constraints are imposed to the pricing problems in the proposed algorithm. The cut generation algorithm is developed for the column generation. Computational experiments show that the proposed method can derive the solutions with a smaller duality gap compared with those of the conventional algorithm of ordinary column generation and Lagrangian relaxation with cuts.
AB - We propose a column generation algorithm for solving sequence dependent flowshop scheduling problems (SDST flowshop) to minimize the total weighted tardiness. The continuous relaxation of the set partitioning formulation of the Dantzig-Wolfe decomposition for SDST flowshop is solved by the column generation. The pricing subproblem for the column generation is decomposed into each job-level subproblem. In order to strengthen the lower bound, the additional constraints are imposed to the pricing problems in the proposed algorithm. The cut generation algorithm is developed for the column generation. Computational experiments show that the proposed method can derive the solutions with a smaller duality gap compared with those of the conventional algorithm of ordinary column generation and Lagrangian relaxation with cuts.
KW - column generation
KW - cut generation
KW - scheduling
KW - sequence dependent setup
UR - http://www.scopus.com/inward/record.url?scp=83755195272&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=83755195272&partnerID=8YFLogxK
U2 - 10.1109/ICSMC.2011.6083859
DO - 10.1109/ICSMC.2011.6083859
M3 - Conference contribution
AN - SCOPUS:83755195272
SN - 9781457706523
T3 - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
SP - 1187
EP - 1192
BT - 2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Conference Digest
T2 - 2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011
Y2 - 9 October 2011 through 12 October 2011
ER -