Using Lagrangian Relaxation Approach to Generate a Lower Bound for No-wait Flow Shop Problem

摘要

No wait flow shop scheduling problem (NWFSP) by minimizing make-span is an NP-hard problem with various applications in the industry. In this paper a new lower bound for NWFSP is presented. For this, the MIP model of the problem is relaxed and dived into two separate problems with polynomial solution. Then by applying Lagrangian relaxation method an algorithm is present to obtain a lower-bound. Computational result show the efficiency of proposed algorithm.