Abstrakt
Fixed interval scheduling (FIS) problems arise in many areas of economics and industry where jobs with processing intervals known in advance are assigned to available machines with forbidden preemption. A special case of such problems appears in the personnel task scheduling where the decision maker (manager) is looking for a minimal number of workers to cover all prescribed shifts.
This problem can be classified as a tactical fixed interval scheduling. In this paper, we focus on scheduling of jobs with uncertain processing intervals where the finishing times are modelled as random variables with a known probability distribution.
We provide a stochastic integer programming formulation with a joint chance constraint which ensures the reliability of the resulting schedule. We propose an iterative decomposition algorithm for a reformulation where the partial operational FIS problems can be solved as the min-cost network flow problems.
The performance of the algorithm is verified on simulated instances.