Significantly improved dominance relation for no-wait flowshop scheduling problems with uncertain setup times

Abstract

The problem of minimizing total completion time (TCT) in an uncertain environment is a crucial problem in production engineering. Minimizing the TCT of a two-machine no-wait scheduling problem with uncertain and bounded setup times is known to be very difficult, and is very likely to have no optimal solution. Such problems are known as Non-deterministic Polynomial-time hard. Scheduling literature provides a mathematical dominance relation for the problem. In this article, a substantially more effective mathematical dominance relation is established. In fact, computational methods reveal that the average percentage improvement comparing the established one in this article to the one in the literature is $1407.80 \%$. Furthermore, statistical hypothesis testing is conducted to compare the means of the established dominance relation to that given in the literature, with p-values of (almost) $0$ for every case, meaning that the mean of the established dominance relation is substantially larger than the one given in the literature. Additionally, confidence intervals are constructed for each mean of the randomly generated cases for the proposed dominance relation to confirm the accuracy of the means.

Keywords

• Mathematical dominance relation
• statistical inference
• no-wait flowshop
• total completion time
• uncertain setup times

References

1. [1] A. Allahverdi, Two-machine flowshop scheduling problem to minimize makespan with bounded setup and processing times, IJAM 8, 145-153, 2005.
2. [2] A. Allahverdi, Two-machine flowshop scheduling problem to minimize total completion time with bounded setup and processing times, Int. J. Prod. Econ. 103 (1), 386-400, 2006.
3. [3] A. Allahverdi, Two-machine flowshop scheduling problem to minimize maximum lateness with bounded setup and processing times, Kuwait J. Sci. Eng. 33 (2), 233-251, 2006.
4. [4] A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs, Eur. J. Oper. Res. 246 (2), 345-378, 2015.
5. [5] A. Allahverdi, A survey of scheduling problems with no-wait in process, Eur. J. Oper. Res. 255 (3), 665-686, 2016.
6. [6] A. Allahverdi, T. Aldowaisa and Y. Sotskov, Two-machine flowshop scheduling problem to minimize makespan or total completion time with random and bounded setup times, Int. J. Math. Math. Sci. 39, 2475-2486, 2003.
7. [7] A. Allahverdi and M. Allahverdi, Two-machine no-wait flowshop scheduling problem with uncertain setup times to minimize maximum lateness, Comput. Appl. Math. 37 (5), 6774-6794, 2018.
8. [8] A. Allahverdi and H. Aydilek, Heuristics for two-machine flowshop scheduling problem to minimize maximum lateness with bounded processing times, Comput. Math. with Appl. 60 (5), 1374-1384, 2010.

9. [9] M. Allahverdi and A. Allahverdi, Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times, J. Ind. Manag. Optim. 16 (5), 2439-2457, 2020.
10. [10] A. Aydilek, H. Aydilek and A. Allahverdi, Increasing the profitability and competitivess in a production environment with random and bounded setup times, Int. J. Prod. Res. 51 (1), 106-117, 2013.
11. [11] K.R. Baker and D. Trietsch, Principles of Sequencing and Scheduling, John Wiley and Sons, New jersy, 2009.
12. [12] A.A. Cunningham and S.K. Dutta, Scheduling jobs with exponentially distributed processing times on two machines of a flow shop, Nav. Res. Logist. Q. 20 (1), 69-81, 1973.
13. [13] E.M. Gonzalez-Neira, D. Ferone, S. Hatami and A.A. Juan, A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times, Simulat. Model. Pract. Theor. 79, 23-36, 2017.
14. [14] N.G. Hall and C. Sriskandarajah, A survey of machine scheduling problems with blocking and no-wait in process, Oper. Res. 44 (3), 510-525, 1996.
15. [15] P.J. Kalczynski and J. Kamburowski, A heuristic for minimizing the expected makespan in two-machine flowshops with consistent coefficients of variation, Eur. J. Oper. Res. 169 (3), 742-750, 2006.
16. [16] S.C. Kim and P.M. Bobrowski, Scheduling jobs with uncertain setup times and sequence dependency, Omega 25 (4), 437-447, 1997.
17. [17] G.M. Kopanos, J.M. Lainez and J. Puigjaner, An efficient mixed-integer linear programming scheduling framework for addressing sequence-dependent setup issues in batch plants, Ind. Eng. Chem. Res. 48 (13), 6346-6357, 2009.
18. [18] P.S. Ku and S.C. Niu, On Johnson’s two-machine flow shop with random processing times, Oper. Res. 34 (1), 130-136, 1986.
19. [19] 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, Inf. Sci. 453, 408-425, 2018.
20. [20] M. Pinedo, Stochastic scheduling with release dates and due dates, Oper. Res. 31 (3), 559-572, 1983.
21. [21] D.K. Seo, C.M., Klein and W. Jang, Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models, Comput. Ind. Eng. 48 (2), 153-161, 2005.
22. [22] H.M. Soroush, Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs, Eur. J. Oper. Res. 113 (2), 450-468, 1999.
23. [23] H.M. Soroush, Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem, Eur. J. Oper. Res. 181 (1), 266-287, 2007.
24. [24] K. Wang and S.H. Choi, A decomposition-based approach to flexible flow shop scheduling under machine breakdown, Int. J. Prod. Res. 50 (1), 215-234, 2012.
25. [25] K.C. Ying and S.W. Lin, Minimizing makespan for no-wait flowshop scheduling problems with setup times, Comput. Ind. Eng. 121, 73-81, 2018.