Optimal Results and Numerical Simulations for Flow Shop Scheduling Problems

Abstract EN

This paper considers the m-machine flow shop problem with two objectives: makespan with release dates and total quadratic completion time, respectively.

For Fm|rj|Cmax, we prove the asymptotic optimality for any dense scheduling when the problem scale is large enough.

For Fm∥ΣCj2, improvement strategy with local search is presented to promote the performance of the classical SPT heuristic.

At the end of the paper, simulations show the effectiveness of the improvement strategy.