An effective predictive heuristic Model in single-machine systems under uncertainty

Document Type : Research Paper


Department of Industrial Engineering, Shahed University, Tehran, Iran



This paper takes a predictive scheduling approach to deal with machine disruption and uncertain job processing times in single-machine systems. A two-dimensional scale is proposed based on robustness and stability. The expected total realized tardiness of jobs and the expected sum of absolute deviation between the planned and realized job completion times are respectively considered as robustness and stability measures. Considering the total tardiness as a robustness measure includes due dates, the customer satisfaction enhancement level is achievable. We propose a novel heuristic to deal with such an NP-hard problem. Computational results show the proposed method's superiority in satisfying customers and staff and increasing systems accountability, especially in large-size problems over the common methods in the literature.


Abtahi, Z., Sahraeian, R., & Rahmani, D. (2020). A New Approach Generating Robust and Stable Schedules in m-Machine Flow Shop Scheduling Problems: A Case Study. International Journal of Engineering33(2), 293-303.‏
Aissaoui, N. O., Khlif, H. H., & Zeghal, F. M. (2020). Integrated proactive surgery scheduling in private healthcare facilities. Computers & Industrial Engineering148, 106686.‏
Liao, W., & Fu, Y. (2019). Min–max regret criterion-based robust model for the permutation flow-shop scheduling problem. Engineering Optimization.‏
Al-Hinai, N., & ElMekkawy, T. Y. (2011). Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm. International Journal of Production Economics132(2), 279-291.‏
Bo┼╝ejko, W., Rajba, P., & Wodecki, M. (2017). Stable scheduling of single machine with probabilistic parameters. Bulletin of the Polish Academy of Sciences. Technical Sciences65(2), 219-231.‏
Briskorn, D., Leung, J., & Pinedo, M. (2011). Robust scheduling on a single machine using time buffers. IIE Transactions43(6), 383-398.‏
Fazayeli, M., Aleagha, M. R., Bashirzadeh, R., & Shafaei, R. (2016). A hybrid meta-heuristic algorithm for flowshop robust scheduling under machine breakdown uncertainty. International Journal of Computer Integrated Manufacturing29(7), 709-719.‏
Gören, S. (2002). Robustness and stability measures for scheduling policies in a single machine environment (Doctoral dissertation, Bilkent University).‏
Goren, S., & Sabuncuoglu, I. (2009). Optimization of schedule robustness and stability under random machine breakdowns and processing time variability. IIE Transactions42(3), 203-220.
Liu, L., Gu, H. Y., & Xi, Y. G. (2007). Robust and stable scheduling of a single machine with random machine breakdowns. The International Journal of Advanced Manufacturing Technology31(7-8), 645-654.‏
Mehta, S. V., & Uzsoy, R. M. (1998). Predictable scheduling of a job shop subject to breakdowns. IEEE Transactions on Robotics and Automation14(3), 365-378.‏
Maghzi, P., Roohnavazfar, M., Mohammadi, M., & Naderi, B. (2019). A Mathematical Model for Operating Room Scheduling Considering Limitations on Human Resources Access and Patient Prioritization. Journal of Quality Engineering and Production Optimization4(2), 67-82.‏
Mousavi, S. M., Mohagheghi, V., & Vahdani, B. (2015). A new uncertain modeling of production project time and cost based on Atanassov fuzzy sets. Journal of Quality Engineering and Production Optimization1(2), 57-70.‏
Niu, S., Song, S., Ding, J. Y., Zhang, Y., & Chiong, R. (2019). Distributionally robust single machine scheduling with the total tardiness criterion. Computers & Operations Research101, 13-28.‏
Nouiri, M., Bekrar, A., Jemai, A., Trentesaux, D., Ammari, A. C., & Niar, S. (2017). Two stage particle swarm optimization to solve the flexible job shop predictive scheduling problem considering possible machine breakdowns. Computers & Industrial Engineering112, 595-606.‏
O'Donovan, R., Uzsoy, R., & McKay, K. N. (1999). Predictable scheduling of a single machine with breakdowns and sensitive jobs. International Journal of Production Research37(18), 4217-4233.‏
Paprocka, I. (2019). The model of maintenance planning and production scheduling for maximising robustness. International Journal of Production Research57(14), 4480-4501.‏
Pinedo. M. (2016). Scheduling: theory, algorithms, and systems (Fourth Edition ed.). Springer Science+Business Media, LLC, 233 Spring Street, New York, NY.
Rahmani, D. (2017). A new proactive-reactive approach to hedge against uncertain processing times and unexpected machine failures in the two-machine flow shop scheduling problems. Scientia Iranica24(3), 1571-1584.‏
Rastgar, I., & Sahraeian, R. (2017). New Formulation and Solution in PCB Assembly Systems with Parallel Batch processors. Journal of Quality Engineering and Production Optimization2(1), 27-46.‏
O'Donovan, R., Uzsoy, R., & McKay, K. N. (1999). Predictable scheduling of a single machine with breakdowns and sensitive jobs. International Journal of Production Research37(18), 4217-4233.‏
Yang, J., & Yu, G. (2002). On the robust single machine scheduling problem. Journal of Combinatorial Optimization6(1), 17-33.
Zhiqiang Lu, Z., Cui, W., & Han, X. (2015). Integrated production and preventive maintenance scheduling for a single machine with failure uncertainty. Computers & Industrial Engineering80, 236-244.