Scheduling Jobs with Stochastic Processing Time on Parallel Identical Machines

Richard Stec, Antonín Novák, Premysl Sucha, Zdenek HanzálekIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of scheduling jobs with uncertain processing times on identical machines to maximize the probability of completing all jobs before a common deadline. The authors introduce a novel Branch-and-Price algorithm that significantly outperforms existing methods, particularly for larger numbers of machines and jobs, by efficiently exploring the solution space and avoiding common symmetries.

What Problem Does This Paper Address?

In many real-world scenarios, the exact time it takes to complete a task (job) is not precisely known beforehand. Instead, it's often best described by a probability distribution. This paper focuses on a specific scheduling problem: assigning jobs to multiple identical machines when each job's processing time follows a normal distribution. The goal is to find an assignment that maximizes the probability that all jobs finish by a predetermined common due date. This is a "β-robust" scheduling problem, aiming to achieve a high probability of meeting a specific objective threshold. Existing methods, like Branch-and-Bound, struggle to scale efficiently as the number of machines increases due to symmetries and the complexity of exploring the vast solution space.

Methods

The core of this paper is a Branch-and-Price algorithm. This is an exact method that combines Branch-and-Bound (a tree search for optimal solutions) with Column Generation (a technique to efficiently handle problems with an exponential number of potential solutions).

Here's a breakdown of their approach:

  • Master Problem: This is a linear program that represents the overall scheduling problem. It uses variables to indicate which "configurations" (assignments of jobs to machines) are selected. To handle the exponential number of configurations, they are not all explicitly listed but are generated as needed.
  • Pricing Problem: This is the crucial component for generating new, potentially better configurations. It's formulated as a mixed-integer program and is derived from the dual of the Master Problem. The authors prove that this Pricing Problem is at least weakly NP-hard, meaning it's computationally challenging. They also propose an efficient way to solve it using a linearized model.
  • Branching Scheme: When the Master Problem's solution isn't "integer" (meaning some jobs aren't definitively assigned), the algorithm branches. Instead of branching on machine assignments (which can create symmetries), they branch on job pairs, enforcing either that two jobs must be on the same machine or must be on different machines. This scheme is designed to avoid symmetries.
  • Initial Heuristic (LJAF): To speed up the Branch-and-Price process, they start with a good initial solution. Their "Large Job Allocated First" (LJAF) heuristic sorts jobs by the product of their mean and variance (breaking ties with larger means) and assigns them greedily to the machine that currently offers the highest probability of meeting the deadline. They show this heuristic performs better than previous ones.

Datasets

The authors generated their own instances for evaluation, following the methodology proposed by [Ranjbar et al., 2012]. They created instances with:

  • 2, 4, and 6 parallel machines.
  • 14, 16, 18, and 20 jobs.
  • Two different values for a parameter 'c' (0.25 and 0.75) that influences the range of variances.

In total, they created 240 instances (10 for each combination of parameters).

Key Insights and Ideas

  • Branch-and-Price for Robust Scheduling: Applying Branch-and-Price to this specific β-robust scheduling problem is a novel and effective approach. It allows for an exact solution while managing the combinatorial explosion.
  • Symmetry Breaking is Key: The authors highlight that avoiding symmetries, especially those arising from identical machines, is critical for efficient exact algorithms. Their branching strategy directly on job relationships, rather than machine assignments, is a clever way to achieve this.
  • Pricing Problem Complexity: Proving the Pricing Problem is NP-hard is important because it justifies the need for sophisticated solvers and heuristics. Their reduction from the KNAPSACK problem provides a formal basis for this.
  • LJAF Heuristic Superiority: The proposed LJAF heuristic provides better initial solutions than prior methods, which can significantly reduce the overall computation time for the Branch-and-Price algorithm. This is likely due to its similarity to the LPT rule, known for its effectiveness in deterministic scheduling.
  • Scalability Matters: The experimental results strongly suggest that their Branch-and-Price approach scales much better than existing Branch-and-Bound methods, especially as the number of machines and jobs grows.

Key Results

The paper demonstrates that their Branch-and-Price algorithm significantly outperforms the state-of-the-art Branch-and-Bound algorithm by Ranjbar et al. (2012) in terms of runtime and the number of nodes explored.

  • For 4 and 6 machines: Their algorithm is dominant, especially for instances with 18 and 20 jobs, where the existing method had very high timeout rates. They drastically reduced running times in these cases.
  • For 2 machines: The Branch-and-Price algorithm was slower than the reference method. The authors attribute this to the Pricing Problem generating a much larger number of configurations, indicating this might be a bottleneck for this specific scenario.
  • Heuristic Performance: Their LJAF heuristic consistently produced better initial bounds compared to the heuristic from Ranjbar et al. (2012), as visualized in Figure 2.

Limitations and Future Work

  • Two-Machine Bottleneck: The authors acknowledge that their algorithm is slower for instances with only two machines. They suggest that a heuristic approach to the Pricing Problem might be necessary to improve performance in these cases.
  • Generalizing Distributions: The current work focuses on normally distributed processing times. Future work could explore other probability distributions, especially those closed under convolution (like Poisson or Gamma) or using approximations for distributions like lognormal.
  • Sampling Methods: For general cases where distributions are not well-behaved, the authors suggest adapting sampling methods from stochastic knapsack problems to modify the Pricing Problem's structure.
  • Non-linear Model Performance: While they developed a non-linear mixed-integer model for comparison, it was too slow for general use, highlighting the advantage of their Branch-and-Price approach.

Summary updated

BibTeX
@inproceedings{stec2019scheduling,
  author = {Richard Stec and Antonín Novák and Premysl Sucha and Zdenek Hanzálek},
  title = {{Scheduling Jobs with Stochastic Processing Time on Parallel Identical Machines}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/781},
}
Figure