A Successive Lagrangian Relaxation Method for Solving Flowshop Scheduling Problems with Total Weighted Tardiness

Lagrangian relaxation technique has been used for solving a wide variety of scheduling problems to obtain near optimal solutions. The approach has been successfully applied to jobshop scheduling problems by relaxing the capacity constraints on machines by using Lagrange multipliers. The relaxed problem can be decomposed into independent job-level subproblems which can be solved by dynamic programming. By extending the technique, in this paper, we propose a successive Lagrangian relaxation method for solving flowshop scheduling problems with total weighted tardiness. In the proposed method, the quality of lower bound is improved by successively solving the Lagrangian dual problem embedding cuts into the Lagrangian relaxation problem. The state space reduction for dynamic programming is also incorporated. The effectiveness of the proposed method is demonstrated from numerical experiments.