Automatische und assistierende Personaleinsatzplanung basierend auf CSP

Das vorliegende Problem der Personaleinsatzplanung ist ein Zuordnungsproblem und gehört der Klasse NP-schwer an. Im Allgemeinen sind solche Probleme nicht in praktisch angemessener Zeit lösbar. Mit problemspezifischen Suchalgorithmen können diese Probleme dennoch auf aktueller Rechentechnik gelöst werden.

Diese Masterarbeit hat das Ziel, das Problem der Personaleinsatzplanung des Unternehmen Coffee Corner zu lösen. Hierbei geht es um die Zuordnung von Mitarbeitern M zu Arbeitsstationen A zu bestimmten Zeiteinheiten Z, wobei M, A und Z Mengen darstellen. Es müssen demnach |A| · |Z| Variablen belegt werden, welche jeweils |M| Werte annehmen können. Der aufgespannte Suchraum umfasst |M||A|·|Z| Zuordnungsmöglichkeiten und somit 10 hoch 875 potenzielle Lösungen. Doch nicht jede Zuordnungsmöglichkeit ist eine gültige Lösung. Ob eine Zuordnungsmöglichkeit eine gültige Lösung ist, wird durch die Einhaltung von Nebenbedingungen entschieden. Ein Ausprobieren aller Möglichkeiten mit Prüfung auf Einhaltung der Nebenbedingungen ist bei steigender Anzahl von Arbeitsstationen, Mitarbeitern und Zeiteinheiten zeitlich zu aufwändig.

Ziel der Arbeit ist eine Untersuchung der Constraint-Propagierung zur Lösung von Personaleinsatzproblemen und die prototypische Umsetzung. Die Evaluation umfasst die Definition geeigneter Kriterien zur Wertung von Plänen, Auswahl von Constraintoptimierungs-Bibliotheken, Heuristiken zur Reduktion des Suchraumes sowie die Integration von Planung und Neuplanung anhand eines realen Anwendungsfalles in der Stadt Brandenburg.

Kolloqium: 30.08.2013

Betreuer: Dipl.-Inform. Ingo Boersch, Prof. Dr.-Ing. Michael Syrjakow

Download: A1-Poster