Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations

Session date: 30 June 2025

Session host: Konstantin Sidorov

Summary:

We looked at a variety of papers on scheduling in this seminar series; however, the common assumption underpinning them is that the problem data is deterministic, for example, that the task durations do not fluctuate during the plan execution. In this session, I want to review a paper that lifts this assumption and design a branch-and-bound algorithm that uses Monte Carlo estimates in place of “deterministic” pruning.

Relevant papers

  1. Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations
    J. C. Beck, and N. Wilson
    Journal of Artificial Intelligence Research, Mar 2007