Problemstellung

Gegeben sind in diesem Problem die Flugzeugumläufe, d. h. die Folge von Flügen, die von jedem einzelnen Flugzeug geflogen werden; diese werden in den Optimierungsschritten Fleet-Assignment und Tail-Assignment bestimmt.

Abbildung 1.3 zeigt ein Beispiel für ein einfaches Crew-Scheduling-Problem. In dem dargestellten Ausschnitt bedient das Flugzeug AC1 die Flüge Berlin (TXL) $\rightarrow$ Frankfurt (FRA), Frankfurt $\rightarrow$ Köln (CGN) und Köln $\rightarrow$ München (MUC) und das Flugzeug AC2 die Flüge München $\rightarrow$ Frankfurt, Frankfurt $\rightarrow$ München und München $\rightarrow$ Palma (PMI). Eine Crew mit Heimatflughafen TXL begleitet den Flug TXL $\rightarrow$ FRA des Flugzeugs AC1, wechselt dort auf das Flugzeug AC2 und begleitet dieses auf den Flügen FRA $\rightarrow$ MUC, MUC $\rightarrow$ PMI und kommt am Ende des Dienstes wieder am Heimatflughafen an. Entsprechendes gilt für eine Crew mit Heimatflughafen MUC, die die restlichen Flüge begleitet.

  

Abbildung 1.3: Ein einfaches Crew-Scheduling Beispiel mit zwei Flugzeugen

Bei der Zuweisung der Crews zu den angebotenen Flügen müssen neben den offensichtlichen Nebenbedingungen (wie z. B. die Verfügbarkeit der Crews an den einzelnen Heimatflughäfen und Zulassungen für Flüge und Flugzeugtypen) auch sehr viel subtilere beachtet werden. Dazu zählen tarifrechtliche und sicherheitsrelevante Bestimmungen, die Beachtung von Reserven und die Berücksichtigung von Mitarbeiterwünschen. Insbesondere gilt es, die Beschränkung hinsichtlich der Flug-, Arbeits- und Ruhezeiten einzuhalten, die auf europäischer Ebene in den JAR-OPS^1.1 festgehalten sind. Darin werden die Dienstschichten in Folgen von Arbeitszeiten, die durch Pausezeiten verbunden werden, zerlegt. Zu den in JAR-OPS formulierten Regelungen zählen unter anderem

• die Beschränkung der Gesamtdauer einer Dienstschicht, der Gesamtdauer der Arbeitszeitblöcke und der darin enthaltenen Flugzeit,
• die Beschränkung jedes einzelnen Arbeitszeitblocks in Abhängigkeit von dem Zeitpunkt des ersten Starts und der Anzahl der enthaltenen Landungen, und
• Anforderungen an die Ruhezeiten: diese müssen jeweils eine gewisse Mindestlänge haben, deren Dauer von dem vorhergehenden Arbeitszeitblock abhängt.