Optimal Solution to the Two-Stage Hybrid Flow Shop Scheduling Problem with Removal and Transportation Times

Abstract

The two-stage hybrid flow shop scheduling problem with removal and transportation times is addressed in this paper. The maximum completion time is the objective function to be minimized. This scheduling problem is modeling real-life situations encountered in manufacturing and industrial areas. On the other hand, the studied problem is a challenging one from a theoretical point of view since it is NP-Hard in a strong sense. In addition, the problem is symmetric in the following sense. Scheduling from the second stage to the first provides the same optimal solution as the studied problem. This propriety allows extending all the proposed procedures to the symmetric problem in order to improve the quality of the obtained solution. Based on the existing literature and to the best of our knowledge, this study is the first one addressing the removal time and the transportation time in the hybrid flow shop environment simultaneously. In order to solve the studied problem optimally, a heuristic composed of two phases is proposed, and a new family of lower bounds is developed. In addition, an exact Branch and Bound algorithm is presented to solve the hard test problems. These hard instances are unsolved by the proposed heuristic. In order to evaluate the performance of the proposed procedures, an extensive experimental study is carried out over benchmark test problems with a size of up to 200 jobs. The obtained computational results provide strong evidence that the presented procedures are very effective since 90% of test problems are solved optimally within a moderate time of 47.44 s. Furthermore, the unsolved test problems present a relative gap of only 2.4%.

Keywords

• hybrid flow shop
• removal times
• transportation times
• lower bound
• heuristic
• branch and bound