Scheduling Under Stochastic Task Durations

46 concepts39 papers1 proposal

Traditional scheduling algorithms rely heavily on the deterministic duration assumption: the belief that the time required to complete a task is a fixed, known constant. In the real world, however, execution times are inherently unpredictable. Human operators speed up or slow down (Teck et al.), physical hardware performance fluctuates with environmental factors like temperature (Hou et al.), and medical or logistics setups introduce random delays (Rambaldi Migliore et al.).

When a scheduling model optimizes purely for average or expected durations, it lacks risk-awareness (Beck et al.). Because tasks are often bound by complex interdependencies, a single delay can propagate downstream, causing a cascading failure of the entire schedule (Garvey et al., Xu). To build systems that survive real-world execution, researchers have shifted toward frameworks that treat task durations as stochastic variables.

Proactive Planning and Temporal Slack

To protect schedules from unexpected disruptions, algorithms must move from reactive replanning—which is computationally expensive and disruptive—to proactive uncertainty modeling during the offline planning phase (Beck et al.).

The core intuition behind proactive scheduling is the strategic insertion of temporal slack (buffers) and alternative execution paths. However, adding too much buffer makes a schedule bloated and inefficient. To balance efficiency and robustness, researchers use hybrid approaches that analyze deterministic plans to find their weak points. For instance, Hiatt et al. developed a framework called PADS (Probabilistic Analysis of Deterministic Schedules) that uses probabilistic feedback to selectively inject redundancy or swap tasks only where failure risks are highest.

Another way to prevent overly conservative schedules is through budgeted uncertainty models. As highlighted by Bampis et al., instead of planning for a worst-case scenario where every task is delayed simultaneously, these models assume that only a bounded subset of tasks will deviate from their expected parameters at any given time. This protects the system against realistic volatility without sacrificing daily operational efficiency.

Chance Constraints and Online Adaptation

When systems require formal guarantees that a deadline will be met, operations research turns to chance-constrained scheduling. Instead of ensuring a schedule works for every mathematically possible delay, a chance constraint provides a formal probabilistic guarantee of success within a user-defined risk threshold (e.g., a 95% probability of on-time completion). Wang demonstrated that by using an iterative, conflict-directed risk allocation approach, autonomous systems can generate these risk-aware policies an order of magnitude faster than traditional methods.

Deterministic: [ Task A (5m) ] -> [ Task B (5m) ] -> Hard Deadline (10m)  --> 50% Success Rate
Stochastic:    [ Task A (5m) + Buffer ] -> [ Task B (5m) ] -> Deadline   --> 95% Chance-Constrained

However, proactive planning assumes that we have access to prior probability distributions. In highly dynamic or non-clairvoyant environments, these distributions are completely unknown, forcing a shift toward stochastic online scheduling (Vredeveld et al., Thai et al.).

In an online setting, the actual duration of a task is only revealed once it finishes executing. This introduces a fundamental exploration-exploitation dilemma: should an agent choose a task with a known history or experiment with an unknown task that might be faster? Ito et al. addressed this by extending multi-armed bandit frameworks to account for unknown processing times, utilizing a "phased-update" Upper Confidence Bound (UCB) algorithm to effectively weigh a task's reward against the stochastic time-resource it consumes. Similarly, Cayci et al. designed continuous-time online allocation algorithms to maintain group fairness when task completion times fluctuate unpredictably.

Overcoming the Computational Bottleneck

The primary barrier to adopting stochastic scheduling is its extreme computational complexity. Evaluating a schedule's performance across thousands of random scenarios using traditional Monte Carlo sampling is far too slow for real-time applications (Povéda et al.).

To bypass this bottleneck, modern approaches integrate deep learning and advanced heuristics to approximate risk profiles instantly:

  • Graph Neural Networks (GNNs): Frameworks like SIREN and SERENE, developed by Povéda et al., use GNNs to exploit the structural graph properties of resource constraints and task dependencies. By combining neural predictions with fast repair heuristics, they generate robust schedules up to 10,000 times faster than traditional solvers.
  • Neural Combinatorial Optimization: For complex industrial environments like flexible job shops, Smit et al. utilize deep learning models to natively incorporate machine lags and processing variance directly into the scheduling policy.
  • Scenario-Based Sampling: Real-world noise rarely follows clean, symmetric Gaussian distributions; delays are often skewed, multi-modal, or fat-tailed. To handle this, Messing et al. proposed a scenario-based scheduling framework that pairs smart sampling with rigorous statistical testing, providing formal deadline guarantees for heterogeneous robot teams without relying on simplified noise assumptions.

By replacing rigid scalar constants with probabilistic frameworks and accelerated learning models, modern scheduling paradigms ensure that systems remain both highly efficient on paper and resilient during real-world execution.

Key Foundational Work

Task Interdependencies in Design-to-time Real-time Scheduling (1993) — contributed 1 concept elements to this direction.
Scheduling Alternative Activities (1999) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_task_duration_f3985bb1,
  title = {stochastic task duration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-task-duration/rdr_f3985bb10d314bf5aa5c0d28c5c1f57e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_stochastic_task_duration_f3985bb1_v1,
  title = {stochastic task duration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-task-duration/rdr_f3985bb10d314bf5aa5c0d28c5c1f57e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake