Systems, Man, and Cybernetics

 

Home

• [P458] An Integrated Column Generation and Lagrangian Relaxation for Flowshop Scheduling Problems
  Author(s): Nishi Tatsushi, Isoya Yukinori, Inuiguchi Masahiro
  
  

  Abstract
  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.

  
   

Full Text (PDF)