An integrated column generation and lagrangian relaxation for solving flowshop problems to minimize the total weighted tardiness

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, the initial columns are generated by using near-optimal dual variables for linear programming relaxation of Dantzig-Wolfe decomposition derived by the Lagrangian relaxation method. The column generation is executed just after the generation of base columns generated by near-optimal Lagrange multipliers. Computational results demonstrate that the integration of column generation and Lagrangian relaxation can drastically speed up the conventional column generation.