Optimal results and numerical simulations for flow shop scheduling problems (Q410955)

Summary: This paper considers the m-machine flow shop problem with two objectives: makespan with release dates and total quadratic completion time, respectively. For \({\text F}m|r_j|C_{\max}\), we prove the asymptotic optimality for any dense scheduling when the problem scale is large enough. For \({\text F}m||\Sigma C^2_j\), 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.