JavaScript-Applikation zum »Färbungsproblem«

Was tun?

1. Zu acht Fugzeugumläufen wird jeweils die Zeit zwischen Abflug und Rückkehr eines Fliegers angegeben. Der fühest mögliche Starttermin ist 7:00 Uhr, der späteste 20:00 Uhr. Im Beispiel ist für den Flug X106-1 der Start in Dortmund für 8:00 Uhr geplant, Rückkehr in Dortmund 11:59 Uhr. Die übrigen Angaben in der Tabelle sind entsprechend zu lesen. Die Vorauswahl kann von Ihnen durch Anklicken verändert werden. Die Kanten im unten stehenden Graphen werden damit gelöscht und durch Anklicken des Buttons »Build Graph« neu generiert.
   Mit »Clear Table« werden alle Positionen in der Tabelle wie auch die Kanten gelöscht.
   »Reset« lädt das ursprünglich vorgegebene Szenario.
2. Insgesamt müssen die in nachfolgender Tabelle zusammengestellten acht Flüge mit Personal besetzt werden. Als Vereinfachung kann eine Crew das Cockpit ohne Pausen direkt wechseln. Ziel ist es, die Anzahl der insgesamt benötigten Crews zu minimieren.
3. Das Zeitraster sieht vor, dass ab 7:00 Uhr Flüge starten können. Die Crews werden durch verschiedene »Farben« identifiziert. Das Anklicken einer Farbe, Gedrückthalten der linken Maustaste und Ziehen dieser Farbe in einen der Knoten 1 bis 8 färbt den betreffenden Knoten entsprechend ein.
4. Für eine gegebene Zuordnung kann dann jeweils festgestellt werden, ob Restriktionen, die durch die Kanten visualisiert sind, verletzt werden. Tragen zwei mit einer Kante inzidente Knoten dieselbe Farbe, wird die entsprechende Kante rot.
5. Ist der Graph zulässig eingefärbt, wird mit »Schedule« der zugehörige Flugplan erzeugt, in den die Crews gemäß der gewählten Farben den Flügen zugeordnet sind.
6. Mit Erzeugen des Flugplans wird gleichzeitig durch Bestimmung der größten Clique eine untere Schranke für die chromatische Zahl ermittelt und unter den Schaltflächen angezeigt.