Heuristic approach to solve hybrid flow shop scheduling problem with unrelated parallel machines

Abstract

In hybrid flow shop scheduling problem (HFS) with unrelated parallel machines, a set of n jobs are processed on k machines. A mixed integer linear programming (MILP) model for the HFS scheduling problems with unrelated parallel machines has been proposed to minimize the maximum completion time (makespan). Since the problem is shown to be NP-complete, it is necessary to use heuristic methods to tackle the moderate to large scale problems. This article presents a new bottleneck-based heuristic to solve the problem. To improve the performance of the heuristic method, a local search approach is embedded in the structure of the heuristic method. To evaluate the performance of the proposed heuristic method, a new lower bound is developed based on Kurz and Askin [1] lower bound. For evaluation purposes, two series of test problems, small and large size problems, are generated under different production scenarios.  The empirical results show that average difference between lower bound and optimal solution as well as lower bound and heuristic method are equal to 2.56% and 5.23%, respectively. For more investigation, the proposed heuristic method is compared by other well-known heuristics in the literature. The results verify the efficiency of the proposed heuristic method in term of number of best solution.

Keywords

• bottleneck-based heuristic
• lower bound
• hybrid flow shop
• makespan