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 n3m n 3 m . In our paper, we propose a new heuristic of complexity n2m n 2 m 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.
heuristics flowtime flowshop scheduling