a heuristic approach to solve hybrid flow shop scheduling Problem with Unrelated Parallel Machines

In hybrid flow-shop scheduling problem (HFS) with unrelated parallel machines, a set of n jobs is 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-sized problems, are generated under different production scenarios. The empirical results show that the average differences 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 with other well-known heuristics in the literature. The results verify the efficiency of the proposed heuristic method in terms of the number of best solutions

کلیدواژه ها:

Bottleneck-based Heuristic ، Lower bound ، Hybrid flow shop ، Makespan