Predictive heuristics for generating robust and stable schedules in single-machine systems under disruption

Document Type : Article


1 Department of Industrial Engineering, College of Engineering, Shahed University, Tehran, Iran.

2 Department of Industrial Engineering, College of Engineering, Shahed University, Persian Gulf Expressway, Tehran, Iran.

3 Department of Industrial Engineering, K.N. Toosi University of Technology, Tehran, Iran.


The present paper examines the problems of stable and robust scheduling under disruptions with uncertain processing times. In order to handle such problems, in addition to exact solution approaches, a general predictive two-stage heuristic algorithm is proposed. In the first stage of the algorithm, the optimal robust schedule is generated by only considering the uncertain job processing times and forgoing the breakdown disruptions. In the second stage, adequate additional times are embedded in job processing times to enhance stability. Extensive computational experiments are carried out to test the performances of the proposed methods. The achieved results show the superiority of the proposed general predictive heuristic approach over the common methods in the literature.


Main Subjects

1. Liu, L., Gu, H., and Xi, Y. Robust and stable scheduling of a single machine with random machine breakdowns", Int J Adv Manuf Technol, 31, pp. 645{ 654 (2007). 2. Goren, S. and Sabuncuoglu, I. Optimization of schedule robustness and stability under random machine breakdowns and processing time variability", IIE Transactions, 42(3), pp. 203{220 (2009). 3. Rahmani, D. and Heydari, M. Robust and stable ow shop scheduling with unexpected arrivals of new jobs and uncertain processing times", Journal of Manufacturing Systems, 33(1), pp. 84{92 (2014). 4. Lu, Z., Cui, W., and Han, X. Integrated production and preventive maintenance scheduling for a single machine with failure uncertainty", Computers & Industrial Engineering, 80, pp. 236{244 (2015). 5. Briskorn, D., Leung, J., and Pinedo, M.-L. Robust scheduling on a single machine using time bu_ers", IIE Transactions, 43(6), pp. 383{398 (2011). 6. O'Donovan, R., Uzsoy, R., and McKay, K.-N. Predictable scheduling of a single machine with breakdowns and sensitive jobs", International Journal of Production Research, 37(18), pp. 4217{4233 (1999). 7. Mehta, S.-V. and Uzsoy, R.-M. Predictable scheduling of a job shop subject to breakdown", IEEE Transactions on Robotics and Automation, 14(3), pp. 365{378 (1998). 8. Mehta, S.-V. Predictable scheduling of a single machine subject to breakdowns", International Journal of Computer Integrated Manufacturing, 12(1), pp. 15{38 (1999). 9. Yang, J. and Yu, G. On the robust single machine scheduling problem", Journal of Combinatorial Optimization, 6(1), pp. 17{33 (2002). 10. Goren, S. Robustness and stability measure for scheduling policies in a single machine environment", MS Dissertation, Bilkent University, Turkey (2002). 11. Adiri, I., Bruno, J., Frostig, E., et al. Single machine ow-time scheduling with a single breakdown", 26(7), p. 679 (1989). 12. Ganji, F. and Moslehi, G. Minimizing maximum earliness in single-machine scheduling with exible maintenance time", Scientia Iranica, 24(4), pp. 2082{ 2094 (2017). 13. Wu, S.-D., Storer, R.-H., and Pei-Chann, C. Onemachine rescheduling heuristics with e_ciency and stability as criteria", Computers & Operations Research, 20(1), pp. 1{14 (1993). 14. Jafari, A. and Lot_, M. Single machine scheduling to minimize the maximum tardiness under piecewise linear deteriorating jobs", Scientia Iranica, 25(1), pp. 370{385 (2018). 15. Mousavi, S.-M., Mahdavi, I., Rezaeian, J., et al. Biobjective scheduling for re-entrant hybrid ow shop with learning e_ect and setup times", Scientia Iranica, 25(4), pp. 2233{2253 (2017). 16. Rudek, R. The single machine total weighted completion time scheduling problem with the sum-ofprocessing time based models: Strongly NP-hard", Applied Mathematical Modelling, 50, pp. 314{332 (2017). 17. Hamta, N., Fatemi Ghomi, N., Tavakkoli-Moghaddam, S.-M.-T., et al. A hybrid meta-heuristic for balancing and scheduling assembly lines with sequenceindependent setup times by considering deterioration tasks and learning e", Scientia Iranica, 21(3), pp. 963{ 979 (2014). 18. Rahmani, D. A new proactive-reactive approach to hedge against uncertain processing times and unexpected machine failures in the two-machine ow shop scheduling problems", Scientia Iranica, 24(3), pp. 1571{1584 (2017). 19. Grigoriu, L. and Friesen, D.K. Scheduling on uniform processors with at most one downtime on each machine", Discrete Optimization, 17, pp. 14{24 (2015). 20. Kacem, I. and Paschos, V.-T. Weighted completion time minimization on a single-machine with a _xed non-availability interval: Di_erential approximability", Discrete Optimization, 10(1), pp. 61{68 (2013). 21. Graham, R.-L., Lawler, E.-L., Lenstra, J.-K., et al. Optimization and approximation in deterministic sequencing and scheduling A survey", Annals of Discrete Mathematics, 5, pp. 287{326 (1979). 22. Pinedo, M.-L., Scheduling: Theory, Algorithms, and Systems, Fifth Edn., Springer, USA (2016). 23. Bo_zejko, W., Rajba, P., and Wodecki, M. Stable scheduling of single machine with probabilistic parameters", Bulletin of the Polish Academy of Sciences Technical Sciences, 65(2), pp. 219{231 (2017). 24. Elsayed, E.-A., Reliability Engineering, Prentice Hall, USA (1996).