Improved solution for minimizing makespan in permutation flow shop

Flow shop is one of the scheduling systems in which the jobs are processed on different machines in a fixed order so as to optimize certain scheduling criteria. The general flow shop problem is shown to be NP-complete. In this paper, a simple constructive heuristic algorithm is proposed for optimizing flow shop scheduling problem with the objective to minimize the makespan. Experimental results show the superiority of the proposed algorithm over well-known heuristics when tested on existing benchmark problems in scheduling literature. Based upon the concept of CL-heuristic [a high-performing constructive heuristic for minimizing makespan in permutation flowshops, Journal of Industrial and Production Engineering, 2013; 30(6): 355–362], we propose a new tie-breaking rule in the proposed approach. An illustrative example is given in the paper to explain the working of the proposed procedure. Statistical tests are performed to establish the effectiveness of the proposed heuristic.