Charles Explorer logo
🇬🇧

A Stochastic-Integer Programming Approach to Tactical Fixed Interval Scheduling Problems

Publication at Faculty of Mathematics and Physics |
2017

Abstract

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.