This study explores a stochastic single-machine scheduling problem with precedence constraints, where job durations are subject to randomness due to unforeseen events. Initially, each job’s duration is assumed to equal its expected value, and we consider only symmetric probability distributions about this expectation. The scheduling process consists of two main steps: first, generating an initial schedule without time lags, and second, applying a right-shift control policy to manage disruptions. Stability is measured as the mean expected deviation in job start times, and the objective is to minimize this measure. A job is considered safer than another if the positive deviation in the duration of the other job stochastically dominates that of the safer job. We provide a theoretical rationale for why the “safe jobs first” heuristic leads to effective scheduling solutions and support this insight with computational experiments across various probability distributions. The results demonstrate the strong performance of heuristics based on this rule in improving schedule stability.
Keywords: scheduling theory, stochastic scheduling, single machine problem, stability
Received May 12, 2025
Revised June 5, 2025
Accepted June 9, 2025
Published online June 19, 2025
Sergei Igorevich Gladyshev, doctoral student, Moscow Institute of Physics and Technology, Moscow, 141701 Russia, e-mail: gladyshev.si@phystech.edu
Elena Gennadievna Musatova, Cand. Sci. (Phys.-Math.), V.A.Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow, 117997 Russia, e-mail: nekolyap@mail.ru
REFERENCES
1. Sabuncuoglu I., Goren S. Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research. Inter. J. Comp. Int. Manuf., 2009, vol. 22, no. 2, pp. 138–157. https://doi.org/10.1080/09511920802209033
2. Leon V.J., Wu D.S., Storer R.H. Robustness measures and robust scheduling for job shops. IIE transact., 1994, vol. 26, no. 5, pp. 32–43. https://doi.org/10.1080/07408179408966626
3. Khakifirooz M., Fathi M., Dolgui A., Pardalos P.M. Scheduling in industrial environment toward future: insights from Jean-Marie Proth. Inter. J. Prod. Res., 2024, vol. 62, no. 1–2, pp. 291–317. https://doi.org/10.1080/00207543.2023.2245919
4. Lee M., Moon K., Lee K., Hong J., Pinedo M. A critical review of planning and scheduling in steel-making and continuous casting in the steel industry. J. Operat. Res. Soc., 2024, vol. 75, no. 8, pp. 1421-1455. https://doi.org/10.1080/01605682.2023.2265416
5. Ghobakhloo M. Industry 4.0, digitization, and opportunities for sustainability. J. Cleaner Prod., 2020, vol. 252, art. no. 119869. https://doi.org/10.1016/j.jclepro.2019.119869
6. Lasi H., Fettke P., Kemper H.-G., Feld T., Hoffmann M. Industry 4.0. Bus. Inf. Syst. Eng., 2014, vol. 6, pp. 239–242. https://doi.org/10.1007/s12599-014-0334-4
7. Martinelli R., Mariano F.C.M.Q., Martins C.B. Single machine scheduling in make to order environments: a systematic review. Comp. Ind. Eng., 2022, vol. 169, art. no. 108190. https://doi.org/10.1016/j.cie.2022.108190
8. Lawler E.L., Lenstra J.K., Kan A.H.G.R, Shmoys D.B. Sequencing and scheduling: algorithms and complexity. In book: Handbooks in operations research and management science, 1993, vol. 4, pp. 445–522. https://doi.org/10.1016/S0927-0507(05)80189-6
9. Du J., Leung J.Y.T. Minimizing total tardiness on one machine is NP-hard. Math. Operat. Res., 1990, vol. 15, no. 3, pp. 483–495. https://doi.org/10.1287/moor.15.3.483
10. Lawler E.L. Optimal sequencing of a single machine subject to precedence constraints. Manag. Sci., 1973, vol. 19, no. 5, pp. 544–546. https://doi.org/10.1287/mnsc.19.5.544
11. Lawler E.L. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discr. Math., 1978, vol. 2, pp. 75–90.
https://doi.org/10.1016/S0167-5060(08)70323-6
12. Chekuri C., Motwani R. Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discr. Appl. Math., 1999, vol. 98, no. 1–2, pp. 29–38.
https://doi.org/10.1016/S0166-218X(98)00143-7
13. Moore J.M. An $n$ job, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci., 1968, vol. 15, no. 1, pp. 102–109. https://doi.org/10.1287/mnsc.15.1.102
14. Brucker P. Classification of scheduling problems. In book: Scheduling algorithms, Berlin, Heidelberg, Springer, 2007, p. 1–10. https://doi.org/10.1007/978-3-540-69516-5_1
15. Ertem M., Ozcelik F., Saraç T. Single machine scheduling problem with stochastic sequence-dependent setup times. Inter. J. Prod. Res., 2019, vol. 57, no. 10, pp. 3273–3289. https://doi.org/10.1080/00207543.2019.1581383
16. Jia C. Stochastic single machine scheduling with an exponentially distributed due date. Operat. Res. Letters, 2001, vol. 28, no. 5, pp. 199–203. https://doi.org/10.1016/S0167-6377(01)00065-7
17. Soroush H.M., Fredendall L.D. The stochastic single machine scheduling problem with earliness and tardiness costs. Eur. J. Operat. Res., 1994, vol. 77, no. 2, pp. 287–302.
https://doi.org/10.1016/0377-2217(94)90373-5
18. Al-Turki U., Andijani A., Arifulsalam S. A new dispatching rule for the stochastic single-machine scheduling problem. Simulation, 2004, vol. 80, no. 3, pp. 165–170. https://doi.org/10.1177/0037549704045047
19. Ronconi D.P., Powell W.B. Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming. J. Sched., 2010, vol. 13, no. 6, pp. 597–607. https://doi.org/10.1007/s10951-009-0160-6
20. Mehta S.V. Predictable scheduling of a single machine subject to breakdowns. Inter. J. Comp. Integr., Manufact., 1999, vol. 12, no. 1, pp. 15–38. https://doi.org/10.1080/095119299130443
21. Lu C.-C., Lin S.-W., Ying K.-C. Robust scheduling on a single machine to minimize total flow time. Comput. Operat. Res., 2012, vol. 39, no. 7, pp. 1682–1691. https://doi.org/10.1016/j.cor.2011.10.003
22. Gutjahr W.J., Hellmayr A., Pflug G.C. Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound. Eur. J. Operat. Res., 1999, vol. 117, no. 2, pp. 396-413.
https://doi.org/10.1016/S0377-2217(98)00279-3
23. Motwani R., Raghavan P. Randomized algorithms. ACM SIGACT News, 1995, vol. 26, no. 3, pp. 48–50. https://doi.org/10.1145/211542.606546
24. CPOptimizer: IBM ILOG CP Optimizer User’s Manual. IBM [e-resource]. 2022. https://www.ibm.com/docs/ru/icos/22.1.1?topic=optimizer-cp-users-manual
25. Kolisch R., Sprecher A., Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems. Manag. Sci., 1995, vol. 41, no. 10, pp. 1693–1703. https://doi.org/10.1287/mnsc.41.10.1693
Cite this article as: S.I. Gladyshev, E.G. Musatova. Heuristic “Safe Jobs First” for stochastic single machine scheduling problem. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 3, pp. 91–104
