Abstract
Classical job shop scheduling assumes fixed task durations, which rarely reflects real-world uncertainty. This paper investigates the Probabilistic Job Shop Scheduling Problem (PJSP), where task durations are random variables. We propose "proactive" algorithms that utilize deterministic models as filters to identify high-quality schedules efficiently. By incorporating a risk-awareness parameter $q$ to pad task durations, we show that deterministic approximations can highly correlate with true probabilistic performance. Our results demonstrate that these methods significantly outperform standard approaches, particularly in large-scale scheduling scenarios.
Introduction
In industrial scheduling, the assumption of deterministic task durations often leads to fragile schedules that fail during execution. The Probabilistic Job Shop Scheduling Problem (PJSP) addresses this by modeling durations as random variables. The objective is to minimize the probabilistic makespan—the time $D$ such that there is a high confidence (e.g., 95%) that all jobs will complete by $D$. However, calculating this makespan exactly requires computationally intensive Monte Carlo simulations, making traditional search methods impractical for large problems.
Methodology
We propose two primary strategies to navigate the search space without exhaustive simulation at every step:
1. Iterative Descending Bound Search (B&B-DQ-L)
This novel constraint-based search transforms the probabilistic problem into a series of deterministic ones. Task durations are set to $d_i = \mu_i + q\sigma_i$, where $\mu_i$ is the mean, $\sigma_i$ is the standard deviation, and $q$ is a risk-awareness factor. The algorithm starts with a conservative (high $q$) schedule and iteratively performs Branch-and-Bound (B&B) searches. As better probabilistic makespans are found, $q$ is decreased, and the current best value serves as an upper bound for subsequent iterations.
2. Deterministic Filtering Algorithms
These algorithms use fast deterministic solvers to generate a pool of candidate schedules based on a fixed $q$. Only the most promising candidates are then validated via Monte Carlo simulation.
- Timed Better Solution (TBS): Finds a good deterministic starting point within a time limit, then simulates any improvements.
- Iterative Best Solution (I-BS): Systematically simulates all solutions within a specific percentage of the optimal deterministic makespan.
Experimental Results
The algorithms were tested on synthetic JSP instances ranging from $4\times4$ to $20\times20$ with varying uncertainty levels.
Performance Comparison
As shown in the performance table below, the B&B-DQ-L approach consistently outperformed standard Branch-and-Bound with simulation (B&B-N). For the largest $20\times20$ instances, Tabu-based filtering emerged as the most effective strategy, highlighting the necessity of local search in high-dimensional spaces.
The Power of Correlation
A key finding of this research is the high correlation between padded deterministic models and true probabilistic performance. By setting $q > 0$, the scheduler accounts for variance, making a "good" deterministic schedule much more likely to be robust in practice.
As illustrated in the correlation analysis, coefficients reached as high as 0.97 when using optimized $q$ values, compared to significantly lower values when ignoring variance ($q=0$). This validates the use of deterministic models as effective filters for probabilistic scheduling.
Conclusion
Proactive scheduling, which incorporates uncertainty during the planning phase, yields superior results compared to reactive or mean-duration-based approaches. While iterative filtering is practically incomplete for massive search spaces, it provides a powerful heuristic for real-world applications. Future work will focus on automated parameter tuning and exploring performance under non-normal duration distributions.
Summary updated