TY - GEN
T1 - An integrated column generation and Lagrangian relaxation for flowshop scheduling problems
AU - Nishi, Tatsushi
AU - Isoya, Yukinori
AU - Inuiguchi, Masahiro
PY - 2009
Y1 - 2009
N2 - In this paper, we address a new integration of column generation and Lagrangian relaxation for solving flowshop scheduling problems to minimize the total weighted tardiness. In the proposed method, initial columns are generated by using near-optimal dual solution using the Lagrange multipliers derived by Lagrangian relaxation method. After the generation of base columns, the column generation is executed. Computational results demonstrate that the integrated column generation and Lagrangian relaxation can drastically speed up the conventional column generation.
AB - In this paper, we address a new integration of column generation and Lagrangian relaxation for solving flowshop scheduling problems to minimize the total weighted tardiness. In the proposed method, initial columns are generated by using near-optimal dual solution using the Lagrange multipliers derived by Lagrangian relaxation method. After the generation of base columns, the column generation is executed. Computational results demonstrate that the integrated column generation and Lagrangian relaxation can drastically speed up the conventional column generation.
KW - Column generation
KW - Flowshop
KW - Lagrangian relaxation
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=74849096536&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=74849096536&partnerID=8YFLogxK
U2 - 10.1109/ICSMC.2009.5346159
DO - 10.1109/ICSMC.2009.5346159
M3 - Conference contribution
AN - SCOPUS:74849096536
SN - 9781424427949
T3 - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
SP - 299
EP - 304
BT - Proceedings 2009 IEEE International Conference on Systems, Man and Cybernetics, SMC 2009
T2 - 2009 IEEE International Conference on Systems, Man and Cybernetics, SMC 2009
Y2 - 11 October 2009 through 14 October 2009
ER -