Significantly improved dominance relation for no-wait flowshop scheduling problems with uncertain setup times
Significantly improved dominance relation for no-wait flowshop scheduling problems with uncertain setup times
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.
___
- [1] A. Allahverdi, Two-machine flowshop scheduling problem to minimize makespan with
bounded setup and processing times, IJAM 8, 145-153, 2005.
- [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] 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] A. Allahverdi, The third comprehensive survey on scheduling problems with setup
times/costs, Eur. J. Oper. Res. 246 (2), 345-378, 2015.
- [5] A. Allahverdi, A survey of scheduling problems with no-wait in process, Eur. J. Oper.
Res. 255 (3), 665-686, 2016.
- [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] 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] 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] 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] 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] K.R. Baker and D. Trietsch, Principles of Sequencing and Scheduling, John Wiley
and Sons, New jersy, 2009.
- [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] 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] 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] 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] S.C. Kim and P.M. Bobrowski, Scheduling jobs with uncertain setup times and sequence
dependency, Omega 25 (4), 437-447, 1997.
- [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] 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] 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] M. Pinedo, Stochastic scheduling with release dates and due dates, Oper. Res. 31 (3),
559-572, 1983.
- [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] 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] 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] 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] 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.