The fixed interval scheduling problem—also known as the personnel task scheduling problem—optimizes the allocation of available resources (workers, machines, or shifts) to execute a given set of jobs or tasks. We introduce a new approach to solve this problem by decomposing it into separate subproblems. We establish the mathematical basis for optimality of such a decomposition and thereafter develop several new techniques (exact and heuristic) to solve the resulting subproblems. An extensive computational analysis of the new techniques proves the efficacy of these approaches when compared to other established techniques in the literature. Specifically, a hybrid integer programming formulation presented in this paper solves several larger problem instances that were not amenable to exact techniques previously. In addition, a constructive heuristic approach (based on quantification metrics for tasks and resources) gives solutions equal to the optimal. We demonstrate that our decomposition approach is applicable for several important variants within the topic of fixed interval scheduling including tactical fixed interval scheduling problem and operational fixed interval scheduling problem.
|Title of host publication||Data and Decision Sciences in Action|
|Subtitle of host publication||Proceedings of the Australian Society for Operations Research Conference 2016|
|Editors||Ruhul Sarker, Hussein A Abbass, Simon Dunstall, Philip Kilby, Richard Davis, Leon Young|
|Place of Publication||Cham Switzerland|
|Number of pages||27|
|Publication status||Published - 2018|
|Name||Lecture Notes in Management and Industrial Engineering|