Measures of robustness and stability to scheduling problems with uncertainty: A review of the state of the art




Robustness, Stability, Scheduling Problem, Uncertainty, Reactive, Proactive


In this work we summarize the different and more used approaches and policies found in the literatura to measure the robustness and stability of solutions for scheduling problems. These policies are based in the analysis of proactive scheduling problems with an approach of planning scenes. Moreover, we present and review the more recent studies developed to measure the robustness and the stability of solutions for uncertainty scheduling problems and we suggest future lines of research.


Al Fawzan, M. and Haouari M. A bi-objective model for robust resource-constrained project scheduling. International Jounal of Production Economics, 9, 175-187, 2005

Artigues C., Billaut, J.C. and Esswein, C. Maximization of solution flexibility for robust shop scheduling. European Journal of Operational Research, 165, 314-328, 2005

Barber, F. and Salido, M.A. , Robusteness, stability, recoverability and realiability in constraint satisfaction problems. Knowledge and Information Systems, 44(3), 719-734, 2015.

Chtourou, H. and Haouari, M. , A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling. Computers & Industrial Engineering, United Kingdom, 55, 183-194, 2008

Climent, L. Wallace, R., Salido, M. and Barber, F. , Finding robust solutions for constraint satisfaction problem with discrete and ordered domains by coverings. Artificial Intelligence Review, 1-26, 2015.

Daniels, R.L. and Carillo, J. E. _-robust scheduling for single machine systems with uncertain processing times. IIE Transactions, 29, 977-985, 1997.

Daniels, R. and Kouvelis, P. Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 41(2), 363-376, 1995.

Glumac, S. and Kovacic, Z. Relative consistency and robust stability measures for sequential co-simulation. Proceedings of the 13th International Modelica Conference, Regensburg, Germany, 2019.

Guo, B. and Nonaka, Y. Rescheduling and optimization of schedules considering machine failures. International Journal of Production Economics, 60(61), 503-513, 1999.

Goren, S. and Sabuncuoglu, I. Robustness and stability measures for scheduling: single-machine environment. IIE Transactions, 40(1), 66-83, 2008.

Goren, S. and Sabuncuoglu, I Optimization of schedule robustness and stability under random machine breakdowns and processing time variability. IIE Transactions, 42(3), 203-220, 2009.

Herroelen, W. and Leus, R. Project scheduling under uncertainty, survey and research potentials. European Journal of Operational Research, N165(2), 289-306, 2005

Herrman, H. N, Scheinder, C., Moreira, A. Andrade, Jr. J. and Havlin, S. Onion-like network topology enhances robustness against malicious attacks. Journal of Statistical Mechanics: Theory and Experiment, 2011(1), 1-7, 2011.

Jensen, M. T. and Hansen, T. K. Robust solutions to job shop problems. Proceedings of the Congress of Evolutionary Computation, 1138-1144, 1999.

Jensen, M. T. Improving robustness and flexibility of tardiness and total flow time job shops using robustness measures. Applied Soft Computing, 1, 35-32, 2001.

Jensen, M.T. Generating robust and flexible job shop schedules using genetic algorithms. IEEE Transactions on Evolutionary Computation, 7(3), 275-288, 2003.

Kasperski, A. Minimizing maximal regret in the single machine sequencing problem with maximim lateness criterion. Operations Research Letters, 33, 431-436, 2005.

Kitano, H. Toward a theory of biologial robustness. Mol Syst. Biol, 3(1), 137, 2007.

Kutanoglu, E. and Sabuncouglu, I. Experimental investigation of iterative simulation-based scheduling in a dynamic and stochastic job shop. Journal of Manufacturing Systems, 20(4), 264-279, 2001.

Kolisch, R., Schwindt, C. and Sprecher, A. Benchmark instances for project scheduling problems In J.Weglarz (Ed.). Handbook on recent advances in project scheduling. Dordrecht: Kluwer, 1998.

Lawler, E. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math, 2, 75-90, 1978.

Li, W. and Glazebrook, K.D. On stochastic machine scheduling with general distributional assumptions. European Journal of Operational Research, 105, 525-536, 1998.

Leung, J. Y. T. and Pinedo, M. A note on scheduling parallel machines subject to breakdown and repair. Naval Research Logistics, 51(1), 60-71, 2004.

Liao, F. and van Wee, B. Accesibility measures for robustness of the transport system. Transportation, 44, 1213-1233, 2017.

Leon, V. J. ,Wu, S.D. and Storer, R. , Robustness measures and robust scheduling for job shops. IIE Transactions, 26(5), 32-43, 1994

Mehta, S. V. and Uzsoy, R. Predictable scheduling of a job shop subject to breakdowns. IEEE Transactions on Robotics and Automation, 14(3), 365-378, 1998.

Mehta, S.V. and Uzsoy, R. Predictable scheduling of a single machine subject to breakdowns. Int. J. Computer Integrated Manufacturing, 12(1), 15-38, 1999.

O’Donovan, R., Uzsoy, R. and Mckay K. N. Predictable scheduling of a single machine with breakdowns and sensitive jobs. Int. J. Prod. Res., 37(18), 4217-4233, 1999.

Rossi, F., van Beek, P. and Walsh, T. A general computational method for robustness analysis with applications to synthetic gene networks. Bioinformatics, 25(12), 168-179, 2006.

Sabuncuoglu, I. and Goren, S. Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research. International Journal of Computer Integrated Manufacturing, 22(2), 138-157, 2009.

Sabuncuoglu, I. and Goren, G. Generating Robust and Stable Schedules in a Single Machine Environment. Industrial Engineering Research Conference, 2004.

Sevaux, M. and Sorensen, K. A genetic algorithm for robust schedules in a one-machine environment with ready times and due dates. OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2, 129-147, 2004.

Sotskov, Y., Sotskova, N.Y. and Werner, F. Stability of an optimal schedule in a job shop. Omega: The International Journal of Management Science, 25(4), 397-414, 1997

Taillard, E. Benchmark for basic scheduling problems. Eur. J. Oper Res, 64(2), 278-285, 1993

Van der Vonder, S., Demeulemeester, E. and Herroelen, W. Proactive heuristic procedures for robust project shceduling: An experimental Analysis. European Journal of Operational Research, 189(3), 723-733, 1998.

Verfaillie, G., and Jussien, N. Constraint solving in uncertain and dynamic environment: a survey. Constraints 10(3), 253-281, 2005.

Wallace, R., Grimes, D. and Freuder, E. Solving dynamic constraint satisfaction problems by identifying stable features.

Proceedings of International Joint Conferences on Artificial Intelligence (1JCAI-09), 621-627, 2009.

Wiggins, S. Introduction to applied nonnlinear dynamical systems and chaos, Springer, New Yor, U.S.A., 1990.

Wu, S. D., Storer, R. N. and Chang, P. A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness. Operations Research, 47(1), 113-124, 1999.

Wu, D.D., Storer, R. N. and Chang, P. One-machine rescheduling heuristics with efficiency and stability as criteria. Computers Ops Res., 20(1), 1-14, 1993.

Yang, J. and Yu, G. On the robust single machine scheduling problem. Journal of Combinatorial Optimization, 6, 17-33, 2002.



How to Cite

Asmat U., R., Vergara M., E., & Gutiérrez S., F. (2019). Measures of robustness and stability to scheduling problems with uncertainty: A review of the state of the art. Selecciones Matemáticas, 6(02), 297-310.