Heuristic “Safe Jobs First” for stochastic single machine scheduling problem.

S. I. Gladyshev^a, E. G. Musatova<sup>b

a</sup> Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region
^b V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow

Abstract: 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.

UDC: 519.854.2, 519.856.2

MSC: 90B36

Received: 12.05.2025
Revised: 05.06.2025
Accepted: 09.06.2025

DOI: 10.21538/0134-4889-2025-31-3-fon-04

Bibliographic databases:

•