Abstract

Flow shop problem has been addressed by many researchers around the world. Different heuristic methods has been developed to deal with this kind of problems. Nevertheless, it is necessary to explore the impact that the bottleneck machine has on the performance of each heuristic. In this article an F6 || Cmax (Makespan) flow shop is tackled with different well-known heuristics in open literature, such as Palmer, Johnson, Gupta, CDS, NEH and PAS and their impact on Cmax was measure. The methodology used seeks to find the possible relationship between the different bottleneck machines and the result obtained from each of the heuristics. For this experiment, there were 302 scenarios with six machines in series, in which each machine had a parity number of scenarios in which it was the bottleneck. The values of Cmax obtained for each heuristic were compared against the result of corresponding MILP (Mixed Integer Liner Problem) problem. The results show that the performance of the NEH heuristic is superior in each scenario, regardless of the bottleneck, but also shows a variable behavior in each heuristic, taking into account the bottleneck machine.