A new dominance relation no-wait flowshop scheduling problems with interval setup times
List of Authors
  • Muberra Allahverdi

Keyword
  • Mathematical Dominance Relation, No-wait Flowshop, Total Completion Time, Uncertain Setup Times

Abstract
  • Minimizing the total completion time (TCT) is essential in numerous manufacturing settings. Since such a problem is considered NP-hard, it is not likely that an optimal solution exists. Accordingly, many papers in scheduling literature look for a dominance relation as a solution to minimizing TCT. Furthermore, due to a wide range of unpredictability in manufacturing settings, it is essential to consider settings with uncertain and bounded setup times. Nonetheless, most of the scheduling literature do not take this uncertainty into account. In this paper, we propose a dominance relation for the problem of minimizing TCT with uncertain and bounded setup times, which is considerably better than the best one in the literature. The percentage of improvement comparing the proposed dominance relation in this paper with the one in scheduling literature is over 1000 %. Hypothesis testing and confidence intervals are also used to further confirm the effectiveness of the proposed dominance relation.

Reference
  • 1. Al-Anzi, F. S., Allahverdi, A. 2013. An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time. Journal of Manufacturing Systems, 32(4), 825-830.

    2. Aydilek, A., Aydilek, H., Allahverdi, A., 2015. Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan. International Journal of Production Research, 53(9), 2803-2819.

    3. Aydilek, H., Aydilek, A., Allahverdi, M., & Allahverdi, A., 2022. More effective heuristics for a two-machine no-wait flowshop to minimize maximum lateness. International Journal of Industrial Engineering Computations, 13(4), 543-556.

    4. Allahverdi, A, 1997. Scheduling in stochastic flowshops with independent setup, processing and removal times. Computers & Operations Research 24, 955-960.

    5. Allahverdi, A., 2006. Two-machine flowshop scheduling problem to minimize total completion time with bounded setup and processing times. International Journal of Production Economics, 103(1), 386-400.

    6. Allahverdi, A., 2022. A survey of scheduling problems with uncertain interval/bounded processing/setup times. Journal of Project Management 7, 225-264.

    7. Allahverdi, M., 2022. An improved algorithm to minimize the total completion time in a two-machine no-wait flow-shop with uncertain setup times. Journal of Project Management, 7(1), 1-12.

    8. Allahverdi, A., Al-Anzi, F. S. 2006. Scheduling multi-stage parallel-processor services to minimize average response time. Journal of the Operational Research Society, 57(1), 101-110.

    9. Allahverdi, A., Aydilek, H., 2010. Heuristics for the two-machine flowshop scheduling problem to minimise makespan with bounded processing times. International Journal of Production Research 48, 6367-6385.

    10. Allahverdi, A., Aydilek, H. 2014. Total completion time with makespan constraint in no-wait flowshops with setup times. European Journal of Operational Research, 238(3), 724-734.

    11. Allahverdi, A., Aydilek, H., Aydilek, A. 2014. Single machine scheduling problem with interval processing times to minimize mean weighted completion time. Computers & Operations Research, 51, 200-207.

    12. Allahverdi, A. and Allahverdi, M. 2018. Two-machine no-wait flowshop scheduling problem with uncertain setup times to minimize maximum lateness. Computational and Applied Mathematics. 37, 6774-6794.

    13. Allahverdi, M., Allahverdi, A. 2020. Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times. Journal of Industrial and Management Optimization. 16, 2439-2457.

    14. Allahverdi, A. 1997. Scheduling in stochastic flowshops with independent setup, processing and removal times. Computers & Operations Research 24, 955-960, 1997.

    15. Allahverdi, A. 2016. A survey of scheduling problems with no-wait in process. European Journal of Operational Research. 255, 665-686, 2016.

    16. Allahverdi, A., Mittenthal, J. 1998. Dual criteria scheduling on a two-machine flowshop subject to random breakdowns. International Transactions in Operational Research, 5(4), 317-324.

    17. Gonzalez-Neira, E., Ferone, D., Hatami, S. & Juan, A. A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times. Simulation Modelling Practice and Theory. 79, 23-36 (2017).

    18. Hall, N. and Sriskandarajah, C. A survey of machine scheduling problems with blocking and no-wait in process. Operations Research. 44, 510-525 (1996)

    19. Kim, S. Bobrowski Scheduling jobs with uncertain setup times and sequence dependency. Omega, Int. Journal of Management Science. 25, 437-447 (1997).

    20. Ruiz, R., Allahverdi, A. 2007. Some effective heuristics for no-wait flowshops with setup times to minimize total completion time. Annals of Operations Research, 156(1), 143-171.

    21. Ruiz, R., Allahverdi, A. 2009. New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness. International Journal of Production Research, 47(20), 5717-5738.