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
