Optimal results and numerical simulations for flow shop scheduling problems. (English) Zbl 1235.90066

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.


90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] B. Chen, C. N. Potts, and G. J. Woeginger, “A review of machine scheduling: complexity, algorithms and approximability,” in Handbook of Combinatorial Optimization, Vol. 3, D.-Z. Du and P. Pardalos, Eds., pp. 21-169, Kluwer Academic Publishers, Boston, Mass, USA, 1998. · Zbl 0944.90022
[2] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, “Optimization and approximation in deterministic sequencing and scheduling: a survey,” Annals of Discrete Mathematics, vol. 5, pp. 287-326, 1979. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[3] J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Brucker, “Complexity of machine scheduling problems,” Annals of Operations Research, vol. 1, pp. 343-362, 1977. · Zbl 0353.68067
[4] C. N. Potts, “Analysis of heuristics for two-machine flow-shop sequencing subject to release dates,” Mathematics of Operations Research, vol. 10, no. 4, pp. 576-584, 1985. · Zbl 0582.90055 · doi:10.1287/moor.10.4.576
[5] L. A. Hall, “Approximability of flow shop scheduling,” Mathematical Programming, vol. 82, no. 1-2, pp. 175-190, 1998. · Zbl 0920.90073 · doi:10.1007/BF01585870
[6] T. C.E. Cheng and Z. Liu, “Parallel machine scheduling to minimize the sum of quadratic completion times,” IIE Transactions, vol. 36, no. 1, pp. 11-17, 2004. · doi:10.1080/07408170490257844
[7] C. Koulamas and G. Kyparisis, “Algorithms with performance guarantees for flow shops with regular objective functions,” IIE Transactions, vol. 37, no. 12, pp. 1107-1111, 2005. · doi:10.1080/07408170500288067
[8] N. M. Matsveichuk, Y. N. Sotskov, N. G. Egorova, and T.-C. Lai, “Schedule execution for two-machine flow-shop with interval processing times,” Mathematical and Computer Modelling, vol. 49, no. 5-6, pp. 991-1011, 2009. · Zbl 1165.90464 · doi:10.1016/j.mcm.2008.02.004
[9] C. T. Ng, N. M. Matsveichuk, Y. N. Sotskov, and T. C. E. Cheng, “Two-machine flow-shop minimum-length scheduling with interval processing times,” Asia-Pacific Journal of Operational Research, vol. 26, no. 6, pp. 715-734, 2009. · Zbl 1180.90134 · doi:10.1142/S0217595909002432
[10] D. Bai and L. Tang, “Two asymptotically optimal lower bounds for flow shop problem,” Chinese Journal of Electronics, vol. 18, no. 4, pp. 625-629, 2009.
[11] D. Bai and L. Tang, “New heuristics for flow shop problem to minimize makespan,” Journal of the Operational Research Society, vol. 61, no. 6, pp. 1032-1040, 2010. · Zbl 1196.90045 · doi:10.1057/jors.2009.44
[12] I. Bárány and T. Fiala, “Nearly optimum solution of multimachine scheduling problems,” Szigma, vol. 15, no. 3, pp. 177-191, 1982 (Hungarian). · Zbl 0506.90036
[13] B. Chen and W. Yu, “How good is a dense shop schedule?” Acta Mathematicae Applicatae Sinica, vol. 17, no. 1, pp. 121-128, 2001. · Zbl 0964.90017 · doi:10.1007/BF02669692
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.