A new constructive heuristic for the flowshop scheduling problem

This paper presents a simple constructive heuristic (HFC) for the flowshop makespan problem which is capable of producing non-permutation schedules when it deems it appropriate. HFC determines the order of any two jobs in the final schedule based on their order in all two-machine problems embedded in the problem. Computational experiments indicate that HFC performs as well as NEH, which is the currently best available constructive heuristic on problems where a permutation schedule is expected to be optimal. However, HFC outperforms NEH on problems where a non-permutation schedule may be optimal.