[Back]

M. Widl:
"Memetic algorithms for break scheduling";
Supervisor: N. Musliu; Institut für Informationssysteme, 2010; final examination: 2010-04-30.

Break scheduling problems arise in working areas where breaks are indispensable due to the nature of the tasks to be performed, e.g.
in air traffic control, supervision or assembly lines. We regard such a problem, denoted BSP, originating in the area of supervision personnel.
The objective is to assign breaks to an existing shiftplan such that various constraints reflecting legal demands or ergonomic criteria are satisfied and staffing requirement violations are minimised. We prove NP-completeness of this problem when all possible break patterns are given explicitly in the input. To solve BSP, we propose variations of a memetic algorithm. A memetic algorithm combines genetic operators such as selection, crossover and mutation with local improvement techniques. We suggest two different memetic representations of BSP and three different memetic algorithms built upon these representations. The algorithms differ in their genetic operators and memetic representation, but include the same local search heuristic. We propose three different neighbourhoods the local search can be based upon. Additionally, we evaluate the impact of a tabu list within one of the algorithms, and within another the impact of a penalty system that tries to detect local optima.
Our approaches are influenced by various parameters, for which we experimentally evaluate different settings. The impact of each parameter is assessed with statistical methods. We compare the three algorithms, each with the best parameter setting according to the evaluation, to state of the art results on a set of publicly available instances. 20 instances were drawn from real life scenarios and 10 randomly generated.
One of our algorithms returns improved results on 28 out of the 30 benchmark instances. To the best of our knowledge, our improved results for the real life instances constitute new upper bounds.

Probleme der Pauseneinteilung entstehen in Arbeitsbereichen, in welchen regelmäßige Pausen unabdingbar sind. Dazu zählen Flugsicherung, Überwachungsaufgaben oder Fließbandarbeit. Wir betrachten ein solches Problem, abgekürzt BSP für die englische Bezeichnung "Break Scheduling Problem", aus dem Überwachungsbereich. Das Ziel ist es, Pausen in einen gegebenen Schichtplan unter Berücksichtigung verschiedener rechtlicher und ergonomischer Kriterien so einzuteilen, dass Abweichungen vom gegebenen Personalbedarf minimiert werden.
Wir zeigen, dass BSP NP-vollständig ist, wenn eine fixe Menge an Pausenmustern Teil des Inputs ist.
Zur Optimierung des BSP entwickeln wir verschiede memetische Algorithmen. Ein memetischer Algorithmus kombiniert genetische Operatoren wie Selektion, Kreuzung und Mutation mit lokalen Verbesserungstechniken. Wir präsentieren zwei verschiedene memetische Darstellungen des BSP sowie, darauf aufbauend, drei verschiedene neuartige memetische Algorithmen. Die Algorithmen unterscheiden sich durch ihre genetischen Operatoren und die memetische Darstellung, verwen- den aber dieselbe lokale Suche als Verbesserungstechnik. Für die lokale Suche präsentieren wir drei verschiedene Nachbarschaften, die unterschiedlich kombiniert werden können. Wir evaluieren für einen der Algorithmen den Einfluss einer in den Suchprozess integrierten Tabu Liste, sowie für einen anderen Algorithmus den Einfluss der Vergabe von Strafpunkten zur Vermeidung lokaler Optima.
Der Verlauf dieser metaheuristischen Ansätze wird von mehreren Parametern bee- influsst, für welche wir verschiedene Werte experimentell evaluieren.
Die Bedeutung jedes Parameters wird mithilfe statistischer Methoden beurteilt.
Wir vergleichen unsere Algorithmen, jeweils unter der besten ermittelten Parame- terbelegung, mit Resultaten aus der Literatur auf öffentlich verfügbaren Instanzen. 20 Instanzen stammen aus Szenarien der Praxis und 10 sind zufällig generiert. Unser bester Algorithmus findet bessere Lösungen fuer 28 von 30 Instanzen. Nach unserem Wissen stellen unsere verbesserten Resultate für die Instanzen aus der Praxis neue obere Schranken dar.

Memetic Algorithms, Hybrid Genetic Algorithms, Break Scheduling, Scheduling