A new set of high-performing heuristics to minimise flowtime in permutation flowshops

This paper addresses the problem of scheduling jobs in a permutation flowshop with the objective of total completion time minimisation. Since this problem is known to be NP-hard, most research has focussed on obtaining procedures – heuristics – able to provide good, but not necessarily optimal, solutions with a reasonable computational effort. Therefore, a full set of heuristics efficiently balancing both aspects (quality of solutions and computational effort) has been developed. 12 out of these 14 efficient procedures are composite heuristics based on the LR   heuristic by Liu and Reeves (2001), which is of complexity n3mn3m. In our paper, we propose a new heuristic of complexity n2mn2m for the problem, which turns out to produce better results than LR. Furthermore, by replacing the heuristic LR by our proposal in the aforementioned composite heuristics, we obtain a new set of 17 efficient heuristics for the problem, with 15 of them incorporating our proposal. Additionally, we also discuss some issues related to the evaluation of efficient heuristics for the problem and propose an alternative indicator.