Heuristic decomposition approaches for an integrated task scheduling and personnel rostering problem

Pieter Smet, Andreas T Ernst, Greet Vanden Berghe

Research output: Contribution to journalArticleResearchpeer-review

15 Citations (Scopus)

Abstract

Real world combinatorial optimisation problems do not often reduce to neatly delineated theoretical problems. Rather, they combine characteristics of various subproblems which then appear to be strongly intertwined. The present contribution introduces a challenging integration of task and personnel scheduling in which both tasks and shifts must be assigned to a set of multi-skilled employees. Three constructive heuristics, based on column generation and other decomposition schemes, are presented, as well as a very large-scale neighbourhood search algorithm to further decrease the schedule's cost. The performance of these algorithms is evaluated on a large set of diverse instances. Computational results illustrate the effectiveness of the proposed approaches, and provide insight into their behaviour. The initial benchmarks are published so as to encourage further research.

Original languageEnglish
Pages (from-to)60-72
Number of pages13
JournalComputers and Operations Research
Volume76
DOIs
Publication statusPublished - 1 Dec 2016

Keywords

  • Column generation
  • Personnel rostering
  • Task scheduling
  • Timetabling
  • Very large-scale neighbourhood search

Cite this