An efficient constructive heuristic for flowtime minimisation in permutation flow shops

In this paper, we propose a heuristic for mean/total flowtime minimisation in permutation flow shops. The heuristic exploits the idea of 'optimising' partial schedules, already present in the NEH-heuristic (Omega 11 (1983) 91) with respect to makespan minimisation. We compare the proposed heuristic against the ones by Rajendran and Ziegler (Eur. J. Oper. Res. 32 (1994) 2541), and Woo and Yim (Comput. Oper. Res. 25 (1998) 175), which are considered the best constructive heuristics for flowtime minimisation so far. The computational experiments carried out show that our proposal outperforms both heuristics with respect to the quality of the solutions. Moreover, our heuristic can be embedded in an improvement scheme to build a composite heuristic in the manner suggested by Allahverdi and Aldowaisan (Int. J. Prod. Econom. 77 (2002) 71) for the flowtime minimisation problem. The so-constructed composite heuristic also improves the best results obtained by the original composite heuristics by Allahverdi and Aldowaisan.