EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2863. Instance space analysis of the shift minimization personnel task scheduling problem

Invited abstract in session WC-26: Topics in scheduling (Contributed), stream Combinatorial Optimization.

Wednesday, 12:30-14:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. Reshma Chandrasekharan
Decision Sciences Area, Indian Institute of Management- Bangalore, India
2. Kimmo Nurmi
Research and Development, Satakunta University of Applied Sciences
3. Nico Kyngäs
Satakunta University of Applied Sciences
4. Jari Kyngäs
SAMK

Abstract

The shift minimization personnel task scheduling problem concerns the optimal assignment of a multi-skilled workforce to skill-specific tasks and the objective is to minimize the number of shifts utilized. Due to its widespread applications in personnel scheduling, various efficient algorithms have been proposed for this problem which solves most of the benchmark instances to optimality. However, some of these instances remain extremely hard to solve. Various statistical experiments have been conducted to analyze what makes some of these instances hard and as a result, a new set of benchmark instances have been generated which offer a significant challenge to the state-of-the-art algorithms.

In addition, this shift minimization problem translates as the list coloring problem on interval graphs, a classic coloring problem on graphs. Through this study, we also investigate what are those graph properties that significantly affect the difficulty in coloring interval graphs. We observe that various scheduling problems in the literature can be polynomially reduced to the list coloring on interval graphs and therefore, our observations and insights can shed light on what makes certain interval scheduling problems and specifically the subsets of their benchmark instances hard.

Keywords

Status: accepted

Back to the list of papers