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 flow shop scheduling with unexpected arrivals of new jobs anduncertain processing times," Journal of Manufacturing Systems, 33 (1), pp. 84-92 (2014). 
[4]     Zhiqiang Lu, Weiwei Cui, and Xiaole Han, "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 buffers," 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]     Gören, 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 flow-time scheduling with a single breakdown," 26  (7), pp. 679 (1989). 
[12]     Ganji, F., Moslehi, G., "Minimizing maximum earliness in single-machine scheduling with flexible maintenance time," Scientia Iranica, 24 (4), pp. 2082-2094 (2017). 
[13]      Wu, S-D., Storer, R-H.  and  Pei-Chann, C., "One-machine rescheduling heuristics with efficiency and stability as criteria," Computers & Operations Research, 20 (1), pp. 1-14 (1993). 
[14]     Jafari, A. and Lotfi, 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., "Bi-objective scheduling for re-entrant hybrid flow shop with learning effect 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-of-processing time based models: Strongly NP-hard," Applied Mathematical Modelling, 50, pp. 314–332 (2017). 
[17]     N. Hamta, N., Fatemi Ghomi, S-M-T., Tavakkoli-Moghaddam, et al., "A hybrid meta-heuristic for balancing and scheduling assembly lines with sequence-independent 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 flow 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 fixed non-availability interval: Differential 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 schedulingA survey," Annals of Discrete Mathematics, vol. 5, p. 287–326, 1979. 
[22]     Pinedo, M-L., Scheduling: theory, algorithms, and systems, Fifth Edn., Springer, USA (2016).
[23]     Bo┼╝ejko, 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).