Wie Computer helfen, den optimalen Schichtplan zu finden
Manche Probleme sehen einfacher aus, als sie es wirklich sind. Ein berühmtes Beispiel dafür ist das eines Handlungsreisenden, der verschiedene Städte besuchen will und den kürzesten Weg sucht, der ihn durch alle Städte führt. Die Lösung ist simpel: Wer alle Möglichkeiten durchprobiert, kann ganz einfach den besten Weg auswählen. Doch die Einfachheit ist trügerisch, die Anzahl der möglichen Lösungen steigt sehr rasch mit der Anzahl der Städte. Schon bei 15 Städten gibt es 43 Milliarden mögliche Lösungen, die durchprobiert werden müssen, bei 16 Städten sind es bereits 645 Milliarden. Damit lässt sich auch der leistungsfähigste Computer schnell an seine Grenzen bringen. Das Beispiel des Handlungsreisenden fällt in der Computerwissenschaft in die Kategorie der sogenannten „NP-Hard“-Probleme. Diese stellen ein Problem rechnerischer Komplexität dar, das mindestens so schwer zu lösen ist wie das schwierigste NP-Problem. Ein anderes solches Problem aus dieser Gruppe mit hoher gesellschaftlicher Brisanz ist die Erstellung von Schichtplänen. Auch hier steigt die Anzahl der möglichen Lösungen rasant. Eine Forschungsgruppe um den Computerwissenschafter Nysret Musliu von der Technischen Universität Wien hat nun im Rahmen eines vom Wissenschaftsfonds FWF finanzierten Projekts versucht, besonders effiziente Algorithmen für solche komplexen Rechenaufgaben zu finden.
Unterschiedliche Probleme
Die Thematik besteht eigentlich aus einer ganzen Reihe unterschiedlicher Fragestellungen, wie Musliu erklärt: „Die Dienstplanung von Krankenschwestern ist ein typischer Fall der Schichtzuweisung. Ein völlig anderes Problem ist die Pausenplanung, etwa in Callcentern oder bei Fluglotsen, wo es gesetzlich vorgegebene Pausen gibt.“ Weiters nennt Musliu die Stundenpläne in Schulen als ein komplexes Beispiel von Zeitplanungsproblemen. Allen diesen Problemen ist gemeinsam, dass sie unter die Kategorie „NP-Hard“ fallen, also ähnlich aufwändig zu berechnen sind wie das Problem des Handlungsreisenden. Zudem sind hier Computermethoden bei Weitem noch nicht gängig: „Im Prinzip wird das sehr oft händisch gemacht. Es gibt Leute, die sehr gut darin sind, solche Pläne zu erstellen. Wenn es aber um größere Firmen geht und wirklich die beste Lösung gesucht wird, ist das händisch fast nicht möglich.“ Die Forschung interessiert sich dementsprechend schon länger für solche in der Praxis häufig auftretenden Fragestellungen, die unter dem Begriff Allgemeine Personalplanung zusammengefasst werden, kurz „GES“ nach dem englischen „General Employee Scheduling“. „Viele Fragestellungen aus diesem Bereich wurden in der wissenschaftlichen Literatur natürlich bereits beschrieben. Es gib gute Lösungen für bestimmte Anwendungsbereiche“, berichtet Musliu. Allerdings unterscheiden sich manche dieser Probleme in Details, etwa bei Personalplanungsproblemen in Flughäfen oder Stundenplänen in Schulen, wenn in jedem Land andere Regelungen gelten. Deshalb habe es einen neuen Ansatz gebraucht, um nicht jedes Mal bei Null beginnen zu müssen.
Das allgemeine Problem formulieren
„Das Ziel dieses Projekts war es nicht nur, diese Einzelprobleme zu lösen, sondern weiterzugehen und das GES-Problem zu lösen“, sagt Musliu. Das sei quasi ein Schritt zurück von der Anwendung in die Grundlagenforschung gewesen, so der Forscher: „Wir haben verschiedene Probleme aus der Literatur analysiert und versucht, ein allgemeines Format zu entwickeln, das diese Subprobleme mit einschließt.“ Obwohl es sich um die Ergebnisse eines Grundlagenprojekts handelt, sind die gefundenen Lösungen nah an der Praxis: „Damit sind im Prinzip praktische Probleme sofort lösbar, die Aufgabenstellungen müssen nur in dieses neue Format konvertiert werden.“ Dieser neue Rahmen hilft außerdem, die Fragestellung umzukehren und nicht Angestellte auf ein bestimmtes Schichtmodell zu verteilen, sondern zu fragen, welcher Schichtplan für ein bestimmtes Unternehmen optimal ist.
Sudoku als Modell für Zeitplanung
Um die neuen Zugänge zu testen, haben sich Musliu und seine Gruppe im Rahmen des Projekts noch einigen speziellen Fragestellungen zugewandt. Dabei haben sie unter anderem Methoden für Sudoku entwickelt. „Es gibt bestimmte Ähnlichkeiten mit Sudoku, aber Sudoku ist viel einfacher. Aber wir konnten zeigen, dass bestimmte Methoden, die für Sudoku gut sind, auch beim GES gute Ergebnisse schaffen können“, sagt Musliu. „Wir haben unsere Methode mit den bisherigen Benchmarks in der wissenschaftlichen Literatur verglichen und konnten zeigen, dass wir in bestimmten Bereichen bessere Ergebnisse erzielen können.“ In einem Problem namens „Torpedo-Scheduling“, das aus der Stahlindustrie kommt, wo heißes Metall in sogenannten Torpedos transportiert wird, konnte ein Master-Student des Projekts, Lucas Kletzander, einen internationalen Wettbewerb für den besten Algorithmus gewinnen.
Ausgangspunkt für neue Forschungen
Das Projekt, das 2012 begann, war ursprünglich für drei Jahre angelegt, wurde aber kostenneutral auf fünf Jahre verlängert und letztes Jahr abgeschlossen. Die Ergebnisse waren der Ausgangspunkt für ein „Christian Doppler Labor“ zum Thema Planung und Scheduling, das kürzlich genehmigt wurde, und dessen Leiter Musliu ist. Darin gibt es einen Teilbereich, der sich mit komplexeren Personalplanungsproblemen beschäftigt. Dabei wird nun enger mit Wirtschaftspartnern zusammengearbeitet. „Das FWF-Projekt hat hier sehr geholfen, in diesem Gebiet Fuß zu fassen“, betont Nysret Musliu.
Zur Person Nysret Musliu ist Computerwissenschafter an der Technischen Universität Wien. Er interessiert sich unter anderem für Künstliche Intelligenz, Maschinenlernen und Optimierung sowie für die Entwicklung von Zeitplänen.
Publikationen
