A review of scheduling problems with bounded processing/setup times
List of Authors
  • Ali Allahverdi

Keyword
  • Scheduling, review, uncertain processing times, uncertain setup times

Abstract
  • The scheduling literature reveals that majority of the studied scheduling problems are for the deterministic case where all parameters of jobs are known in advance and are fixed. However, in some real-world environments, the assumption of fixed parameters of jobs is not valid since job parameters are uncertain. An uncertain parameter can be modelled as a random variable within some interval with some lower and upper bounds, called bounded. The objective of this paper is to review the investigated scheduling problems with bounded processing or setup times. The scheduling literature is reviewed, the addressed problems are analysed, and classified based on shop environments (single machine, parallel machine, flowshop, job shop), performance measures, the approach taken in the papers to solve the considered problem, and interval/bounded processing times or setup times. Some future research opportunities with interval/bounded processing/setup times are presented.

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. Allahverdi, A, 1997. Scheduling in stochastic flowshops with independent setup, processing and removal times. Computers & Operations Research 24, 955-960.

    4. 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.

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

    6. 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.

    7. 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.

    8. 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.

    9. 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.

    10. 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.

    11. Diaz, H., Palacios, J.J., Diaz, I., Vela, C.R., Gonzalez-Rodriguez, I., 2022. Robust schedules for tardiness optimization in job shop with interval uncertainty. LOGIC JOURNAL OF THE IGPL, In Press.

    12. 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, 143-171.

    13. 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.

    14. Ying, K.C., Lin, S.W., 2018. Minimizing makespan for the distributed hybrid flowshop scheduling problem with multiprocessor tasks. Expert Systems with Applications 92, 132-141.

    15. Zhu, Z., Zhou, X., 2020. Flexible job-shop scheduling problem with job precedence constraints and interval grey processing time. Computers & Industrial Engineering 149, Article 106781.

    16. Xie, N., Chen, N., 2018. Flexible job shop scheduling problem with interval grey processing time. Applied Soft Computing 70, 513-524.