Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times. (English) Zbl 1476.90139
Summary: We address a two-machine no-wait flowshop scheduling problem with respect to the performance measure of total completion time. Minimizing total completion time is important when inventory cost is of concern. Setup times are treated separately from processing times. Furthermore, setup times are uncertain with unknown distributions and are within some lower and upper bounds. We develop a dominance relation and propose eight algorithms to solve the problem. The proposed algorithms, which assign different weights to the processing and setup times on both machines, convert the two-machine problem into a single-machine one for which an optimal solution is known. We conduct computational experiments to evaluate the proposed algorithms. Computational experiments reveal that one of the proposed algorithms, which assigns the same weight to setup and processing times, is superior to the rest of the algorithms. The results are statistically verified by constructing confidence intervals and test of hypothesis.
MSC:
| 90B36 | Stochastic scheduling theory in operations research |
References:
| [1] | A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs, European Journal of Operational Research, 246, 345-378 (2015) · Zbl 1347.90031 · doi:10.1016/j.ejor.2015.04.004 |
| [2] | A. Allahverdi, A survey of scheduling problems with no-wait in process, European Journal of Operational Research, 255, 665-686 (2016) · Zbl 1394.90002 · doi:10.1016/j.ejor.2016.05.036 |
| [3] | A. Allahverdi, Two-machine flowshop scheduling problem to minimize makespan with bounded setup and processing times, Int. Journal of Agile Manufacturing, 8, 145-153 (2005) |
| [4] | A. Allahverdi, Two-machine flowshop scheduling problem to minimize total completion time with bounded setup and processing times, Int. Journal of Production Economics, 103, 386-400 (2006a) |
| [5] | A. Allahverdi, Two-machine flowshop scheduling problem to minimize maximum lateness with bounded setup and processing times, Kuwait Journal of Science and Engineering, 33, 233-251 (2006) |
| [6] | A. Allahverdi; T. Aldowaisan; Y. N. Sotskov, Two-machine flowshop scheduling problem to minimize makespan or total completion time with random and bounded setup times, Int. Journal of Mathematics and Mathematical Sciences, 39, 2475-2486 (2003) · Zbl 1041.90020 · doi:10.1155/S016117120321019X |
| [7] | A. Allahverdi; M. Allahverdi, Two-machine no-wait flowshop scheduling problem with uncertain setup times to minimize maximum lateness, Computational and Applied Mathematics, 37, 6774-6794 (2018) · Zbl 1413.90104 · doi:10.1007/s40314-018-0694-3 |
| [8] | A. Allahverdi; H. Aydilek, Heuristics for two-machine flowshop scheduling problem to minimize maximum lateness with bounded processing times, Computers and Mathematics with Applications, 60, 1374-1384 (2010) · Zbl 1201.90070 · doi:10.1016/j.camwa.2010.06.019 |
| [9] | A. Aydilek; H. Aydilek; A. Allahverdi, Increasing the profitability and competitiveness in a production environment with random and bounded setup times, Int. Journal of Production Research, 51, 106-117 (2013) · doi:10.1080/00207543.2011.652263 |
| [10] | A. Aydilek; H. Aydilek; A. Allahverdi, Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan, Int. Journal of Production Research, 53, 2803-2819 (2015) · doi:10.1080/00207543.2014.997403 |
| [11] | A. Aydilek; H. Aydilek; A. Allahverdi, Algorithms for minimizing the number of tardy jobs for reducing production cost with uncertain processing times, Applied Mathematical Modelling, 45, 982-996 (2017) · Zbl 1446.90005 · doi:10.1016/j.apm.2017.01.039 |
| [12] | O. Braun; T. C. Lai; G. Schmidt; Y. N. Sotskov, Stability of Johnson’s schedule with respect to limited machine availability, Int. Journal of Production Research, 40, 4381-4400 (2002) · Zbl 1064.90543 |
| [13] | A. A. Cunningham; S. K. Dutta, Scheduling jobs with exponentially distributed processing times on two machines of a flow shop, Naval Research Logistics Quarterly, 20, 69-81 (1973) · Zbl 0254.90021 · doi:10.1002/nav.3800200107 |
| [14] | O. Engin; A. Güçlü, A new hybrid ant colony optimization algorithm for solving the no-wait flow shop scheduling problems, Applied Soft Computing Journal, 72, 166-176 (2018) · doi:10.1016/j.asoc.2018.08.002 |
| [15] | O. Engin; C. Günaydin, An adaptive learning approach for no-wait flowshop scheduling problems to minimize makespan, International Journal of Computational Intelligence Systems, 4, 521-529 (2011) · doi:10.1080/18756891.2011.9727810 |
| [16] | E. M. Gonzalez-Neira; D. Ferone; S. Hatami; A. A. Juan, A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times, Simulation Modelling Practice and Theory, 79, 23-36 (2017) · doi:10.1016/j.simpat.2017.09.001 |
| [17] | N. G. Hall; C. Sriskandarajah, A survey of machine scheduling problems with blocking and no-wait in process, Operations Research, 44, 510-525 (1996) · Zbl 0864.90060 · doi:10.1287/opre.44.3.510 |
| [18] | P. J. Kalczynski; J. Kamburowski, A heuristic for minimizing the expected makespan in two-machine flowshops with consistent coefficients of variation, European Journal of Operational Research, 169, 742-750 (2006) · Zbl 1079.90070 · doi:10.1016/j.ejor.2004.08.045 |
| [19] | I. H. Karacizmeli; S. N. Ogulata, Energy consumption management in textile finishing plants: A cost effective and sequence dependent scheduling model, Textile and Apparel, 27, 145-152 (2017) |
| [20] | S. C. Kim; P. M. Bobrowski, Scheduling jobs with uncertain setup times and sequence dependency, Omega Int. Journal of Management Science, 25, 437-447 (1997) · doi:10.1016/S0305-0483(97)00013-3 |
| [21] | G. M. Kopanos; J. Miguel Lainez; L. Puigjaner, An efficient mixed-integer linear programming scheduling framework for addressing sequence-dependent setup issues in batch plants, Industrial & Engineering Chemistry Research, 48, 6346-6357 (2009) · doi:10.1021/ie801127t |
| [22] | P. S. Ku; S. C. Niu, On Johnson’s two-machine flow shop with random processing times, Operations Research, 34, 130-136 (1986) · Zbl 0595.90044 · doi:10.1287/opre.34.1.130 |
| [23] | T. C. Lai; Y. N. Sotskov; N. Y. Sotskova; F. Werner, Optimal makespan scheduling with given bounds of processing times, Mathematical and Computer Modelling, 26, 67-86 (1997) · Zbl 0895.90118 · doi:10.1016/S0895-7177(97)00132-5 |
| [24] | X. Li, Z. Yang, R. Ruiz, T. Chen and S. Sui, An iterated greedy heuristic for no-wait flow shops with sequence dependent setup times, learning and forgetting effects, Information Sciences, 453 (2018), 408-425. · Zbl 1440.90010 |
| [25] | R. Macchiaroli; S. Molè; S. Riemma, Modelling and optimization of industrial manufacturing processes subject to no-wait constraints, Int. Journal of Production Research, 37, 2585-2607 (1999) · Zbl 0949.90563 · doi:10.1080/002075499190671 |
| [26] | N. M. Matsveichuk; Y. N. Sotskov; N. G. Egorova; T. C. Lai, Schedule execution for two-machine flow-shop with interval processing times, Mathematical and Computer Modelling, 49, 991-1011 (2009) · Zbl 1165.90464 · doi:10.1016/j.mcm.2008.02.004 |
| [27] | N. M. Matsveichuk; Y. N. Sotskov; F. Werner, Partial job order for solving the two-machine flow-shop minimum-length problem with uncertain processing times, Optimization, 60, 1493-1517 (2011) · Zbl 1233.90166 · doi:10.1080/02331931003657691 |
| [28] | M. Pinedo, Stochastic scheduling with release dates and due dates, Operations Research, 31, 559-572 (1983) · Zbl 0523.90046 · doi:10.1287/opre.31.3.559 |
| [29] | M. Pinedo, Scheduling Theory, Algorithms, and Systems, Prentice Hall, Englewood Cliffs, New Jersey, Page 349, 1995. · Zbl 1145.90393 |
| [30] | V. Portougal; D. Trietsch, Johnson’s problem with stochastic processing times and optimal service level, European Journal of Operational Research, 169, 751-760 (2006) · Zbl 1079.90071 · doi:10.1016/j.ejor.2004.09.056 |
| [31] | V. Riahi; M. Kazemi, A new hybrid ant colony algorithm for scheduling of no-wait flowshop, Operational Research, 18, 55-74 (2018) · doi:10.1007/s12351-016-0253-x |
| [32] | D. K. Seo; C. M. Klein; W. Jang, Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models, Computers and Industrial Engineering, 48, 153-161 (2005) · doi:10.1016/j.cie.2005.01.002 |
| [33] | H. M. Soroush, Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs, European Journal of Operational Research, 113, 450-468 (1999) · Zbl 0938.90033 |
| [34] | H. M. Soroush, Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem., European Journal of Operational Research, 181, 266-287 (2007) · Zbl 1121.90064 · doi:10.1016/j.ejor.2006.05.036 |
| [35] | Y. N. Sotskov; N. M. Matsveichuk, Uncertainty measure for the Bellman-Johnson problem with interval processing times, Cybernetics and System Analysis, 48, 641-652 (2012) · Zbl 1288.90016 · doi:10.1007/s10559-012-9445-4 |
| [36] | Y. N. Sotskov; N. G. Egorova; T. C. Lai, Minimizing total weighted flow time of a set of jobs with interval processing times, Mathematical and Computer Modelling, 50, 556-573 (2009) · Zbl 1185.90094 · doi:10.1016/j.mcm.2009.03.006 |
| [37] | Y. N. Sotskov; T. C. Lai, Minimizing total weighted flow under uncertainty using dominance and a stability box, Computers and Operations Research, 39, 1271-1289 (2012) · Zbl 1251.90190 · doi:10.1016/j.cor.2011.02.001 |
| [38] | K. Wang; S. H. Choi, A decomposition-based approach to flexible flow shop scheduling under machine breakdown, Int. Journal of Production Research, 50, 215-234 (2012) · doi:10.1080/00207543.2011.571456 |
| [39] | Y. Wang; X. Li; R. Ruiz; S. Sui, An iterated greedy heuristic for mixed no-wait flowshop problems, IEEE Transactions on Cybernetics, 48, 1553-1566 (2018) · doi:10.1109/TCYB.2017.2707067 |
| [40] | K. C. Ying; S. W. Lin, Minimizing makespan for no-wait flowshop scheduling problems with setup times, Computers and Industrial Engineering, 121, 73-81 (2018) · doi:10.1016/j.cie.2018.05.030 |
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.
