An Efficient Heuristic for Scheduling a Flowshop to Minimize the Makespan Criterion

The main aim of this paper deals with the problem of sequencing n jobs over m machines in a flow shop without constraints. The scheduling is based on the maximum completion time. A heuristic based on a branch and bound technique is proposed to solve the problem. Though, the idea of our algorithm is in some way similar to Bertolissi’s one, the fact that we minimize the makespan instead of the sum of the total flow times, makes them different. In order to show the effectiveness of our heuristic, we compared it to that proposed by Nawaz et al. The numerical evaluation of the two approaches shows that our heuristic is good in term of quality of the solutions, computing times and simplicity of implementation.