Title: An Iterated Local Search Algorithm for a Real-Life Break
Scheduling Problem

Andreas Beer*, Johannes Gartner**, Nysret Musliu***, Werner
Schafhauser*** and Wolfgang Slany*

* Technische Universitaet Graz, Austria
** Ximes Corp., Vienna, Austria
*** Technische Universitaet Wien, Austria

Abstract:

Scheduling breaks within shift plans represents an interesting task
emerging in many working areas. Solutions for these problems should
satisfy constraints resulting from labour rules as well as the
organizational requirements within a particular working field.
Usually, due to a high number of breaks and various, conflicting
constraints break scheduling problems are highly-complex and difficult
to solve. We address a real-world break scheduling problem originating
from industry and propose an iterated local search algorithm for
solving it. We use simulated annealing and a min-conflicts-based
heuristics as local search procedures and in addition we propose
several perturbation mechanisms for the regarded break scheduling
problem. Finally, we evaluate the iterated local search algorithm on
real-world benchmark instances and draw a comparison between iterated
local search and existing algorithms for the addressed break
scheduling problem.