Composite heuristic algorithm for permutation flowshop scheduling problems with total flowtime minimization

In this paper, a composite heuristic algorithm is proposed for permutation flowshop scheduling problems (PFSP) with total flowtime minimization, which are well known NP-hard. Besides initialized by LR(n/m), solution of the proposal is developed by iteration of FPE or BPE alternatively. Perturbation is applied to escape from the local optimization when no improvement can be obtained during the development procedure. Good structures in the sequence can be kept during the perturbation. Ties with no improvement can be broken up during the perturbation. Experimental results show that the proposal is rather suitable for large-sized problems and outperforms the other recent and effective algorithms considered on benchmark instances on average.