Heuristic algorithms for large flowshop scheduling problems

To meet the requirements on time and to minimize the makespan performance of large flowshop scheduling problems, partial enumeration method (PEM) is presented, which is a polynomial algorithm with a job sequence resulted from an algorithm or a rule as input and result in another job sequence. The PEM runs in short time and can be easily combined with other algorithms or rules to improve performance. Two priority rules, variance method and variance-mean method, are developed. Integrating PEM with the two rules respectively, the PE-V (PE method based on variance) and PE-VM (PE method based on variance-mean) heuristics are described. The algorithms are performed on 120 benchmark instances. Computational results show that PE-V is almost as good as NEH in performance but its runtime is nearly 50% of that of NEH, PE-VM outperforms NEH, PE-V and a simulated annealing algorithm. The makespan of PE-VM is near to or even better than that of tabu search.