Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems

D Niraj Ramesh, M Krishnamoorthy, Andreas T Ernst

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review


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.
Original languageEnglish
Title of host publicationData and Decision Sciences in Action
Subtitle of host publicationProceedings of the Australian Society for Operations Research Conference 2016
EditorsRuhul Sarker, Hussein A Abbass, Simon Dunstall, Philip Kilby, Richard Davis, Leon Young
Place of PublicationCham Switzerland
Number of pages27
ISBN (Electronic)9783319559148
ISBN (Print)9783319559131
Publication statusPublished - 2018

Publication series

NameLecture Notes in Management and Industrial Engineering
ISSN (Print)2198-0772
ISSN (Electronic)2198-0780

Cite this