Scheduling Jobs with Stochastic Processing Time on Parallel Identical Machines

Scheduling Jobs with Stochastic Processing Time on Parallel Identical Machines

Richard Stec, Antonin Novak, Premysl Sucha, Zdenek Hanzalek

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 5628-5634. https://doi.org/10.24963/ijcai.2019/781

Many real-world scheduling problems are characterized by uncertain parameters. In this paper, we study a classical parallel machine scheduling problem where the processing time of jobs is given by a normal distribution. The objective is to maximize the probability that jobs are completed before a given common due date. This study focuses on the computational aspect of this problem, and it proposes a Branch-and-Price approach for solving it. The advantage of our method is that it scales very well with the increasing number of machines and is easy to implement. Furthermore, we propose an efficient lower bound heuristics. The experimental results show that our method outperforms the existing approaches.
Keywords:
Planning and Scheduling: Scheduling
Heuristic Search and Game Playing: Combinatorial Search and Optimisation