Inhaltsverzeichnis Seite

1.  Einleitung - 6 -  

2.  Beschreibung des Problems - 8 -  

2.1.  Teilaufgaben - 8 -  

2.2.  Zielbeschreibung - 10 -  

2.3.  Modellhafte Umsetzung - 11 -  

2.4.  Graphische Darstellung - 12 -  

2.5.  Einschränkungen und Besonderheiten des Ansatzes - 16 -  

3.  Mathematische Darstellung - 18 -  

3.1.  Einleitung - 18 -  

3.2.  Annahmen in Anlehnung an die Modellbeschreibung - 18 -  

3.2.1.  Standorte - 18 -  

3.2.2.  Personal - 19 -  

3.2.3.  Unternehmen - 19 -  

3.3.  Modellparameter - 20 -  

3.3.1.  Mengen und Indizes - 20 -  

3.3.2.  Eingabewerte - 21 -  

3.3.3.  Entscheidungsvariablen - 22 -  

3.4.  Mathematischer Ansatz - 23 -  

3.4.1.  Zielfunktion - 23 -  

3.4.2.  Restriktionen und Definitionsbereich - 24 -  

4.  Lineare Programmierung - 28 -  

4.1.  Modellrechnung mittels Lingo - Optimization Software - 28 -  

4.1.1.  Begrenzung des Modells - 28 -  

4.1.2.  Resultate - 30 -  

4.1.3.  Analyse - 32 -  

4.1.4.  Fazit - 33 -  

5.  Anwendung des Simulated Annealing Algorithmus - 35 -  

5.1.  Theoretische Grundlagen - 35 -  

5.2.  Problemabhängige Parameter - 38 -  

5.2.1.  Generierung der Nachbarschaft - 38 -  

5.2.2.  Kostenfunktion - 43 -  

5.3.  Problemunabhängige Parameter - 44 -  

- 2 -

5.3.1. Einfache Kühlfunktionen ............................................................ - 44 -

5.3.2.  Angepasste Kühlfunktionen - 48 -  

5.4.  Resultate und Analyse - 52 -  

6.  Zusammenfassung - 54 -  

7.  Anhang - 56 -  

8.  Literaturverzeichnis - 58 -  

- 3 -

Tabellenverzeichnis Seite

Tabelle 1: Eingabewerte der Wechselanfragen und Upgrade-Optionen.. - 29 -Tabelle 2: Ergebnis Lineare Optimierung………………………………- 30 -Tabelle 3: Parameter lineare Kühlfunktion…………………………….. - 46 -Tabelle 4: Parameter der angepassten Kühlfunktion…………………... - 51 -Tabelle 5: Parameter reduziertes Modell I……………………………. - 52 -

- 4 -

Abbildungsverzeichnis Seite Abbildung 1: Netzwerk - 15 -

Abbildung 2: Strategien der Nachbarschaftssuche - 42 -

Abbildung 3: Ergebnisse lineare Kühlfunktion - 46 -

Abbildung 4: Zusammenhang zwischen Kosten und Kontrollparameter - 49 -Abbildung 5: Zusammenhang zwischen Iterationen pro Einheiten der Differenz zum vorherigen gleichgewichtige Kostenzustand und dem Kontrollparameter - 50 -

Abbildung 6: Ergebnisse mit angepasster Kühlfunktion - 51 -

Abbildung 7: Ergebnisse reduziertes Modell I - 52 -

- 5 -

1. Einleitung

Die vorliegende Arbeit greift mit dem Base Transfer Problem eine aktuelle Problematik der Fluglinie Easyjet Airline Company plc auf. Die Aufgabe besteht in der standortübergreifenden Allokation der Mitarbeiter und stellt neben der Aufstellung der Dienstpläne eine der großen Herausforderungen der Personaleinsatzplanung dar. Unter dem Grundproblem der Personaleinsatzplanung wird die „Zuordnung von Menschen zu bestimmten Arbeitsaufgaben“ ¹ verstanden und oft unter dem Begriff Job Shop Scheduling Problem ² , als ein spezieller Fall des Transportproblems behandelt ³ . Die Optimierung erfolgt dabei unter dem Gesichtspunkt der Leistungsfähigkeit. In der Regel findet eine Zuordnung des Mitarbeiters zu einer Maschine oder vergleichbarem statt. ⁴ Die Zielgrößen der Planung reichen von der Verbesserung der Durchlaufzeiten, der Auslastung, bis hin zur Liefertreue und den Beständen einer ein-, oder mehrstufigen Arbeitsfolge. 5

Bei dem Base Transfer Problem, i.e. Standort-Versetzungsplanung steht der die Deckung des ständig wechselnde Personalbedarfs auf den einzelnen Standorten im Fokus. Bedingt durch eine natürliche Fluktuation, saisonale und marktbedingte Nachfrageschwankungen, sowie durch Beförderungen vom Ersten Offizier zum Kapitän ist die optimale Zuordnung eine ständig neue Herausforderung.

Um auf Veränderungen in der Personalstruktur zu reagieren stehen dem Unternehmen folgende Maßnahmen zur Verfügung:

• Neueinstellungen von Personal

• Die Versetzung eines Mitarbeiters auf einen anderen Standort

• Beförderung eines Ersten Offiziers zum Piloten Ziel der Arbeit ist es, nach einer eingehenden Analyse des Problems das stochastische Nachbarschaftssuchverfahren Simulated Annealing auf das

¹ Ambrosy, R. (1982), Personaleinsatzplanung bei variabler Organisationsstruktur, Vgl.

Bochum, S. 14.

² Vgl. Laarhoven, P.J.M. (1988), Theoretical and computational aspect of simulated

annealing, Amsterdam, S. 66.

³ Ambrosy, R. (1982), Personaleinsatzplanung bei variabler Organisationsstruktur, Vgl.

Bochum, S. 15.

⁴ Vgl. Ambrosy, R. (1982), S. 15.

⁵ Vgl. Glaser, H. et al. (1998), Retrograde Terminierung mit Personalzuordnung,

Saarbrücken, S.8.

- 6 -

Base Transfer Problem anzuwenden. Die Besatzungsmitglieder sind so auf die Standorte zu verteilen, dass die Personalkosten langfristig minimiert werden. Da Neueinstellungen einen wesentlichen Kostenfaktor bei der Personalplanung ausmachen, ist eine stattdessen gezielt ausgeführte Versetzung eine kosteneffiziente Maßnahme, mit der notwendige Einstellungstrainings und ein erhöhter Personalstamm umgangen werden können. Eine möglichst hohe Anzahl an Versetzungsmöglichkeiten stellt somit eine wünschenswerte operative Flexibilität dar. Um dies zu erreichen sollen Versetzungsanfragen möglichst zeitnah stattgegeben werden. Im ersten Teil der Diplomarbeit wird ein Programm modelliert, um anstehende Versetzungen in einer rollierenden Planung über einen Zeitraum von 6 Monaten optimal zu realisieren. Dabei wird auf die Teilaufgaben der Standort-Versetzungsplanung im Rahmen der linearen Optimierung unter Ableitung der algorithmischen Handhabbarkeit eingegangen und eine mathematische Modellierung unter Nennung der zuvor genannten Regeln und Annahmen erarbeitet. Des Weiteren wird das Problem in einem reduzierten Modell anhand konkreter Zahlen mit der globalen Optimierungssoftware Lingo gelöst. Es werden Einsparungsmöglichkeiten bei vorhandener Datenbasis dargestellt und eine Vorstellung über entstehende Mehrkosten, die bei einer suboptimalen Allokation anfallen, abgeleitet und analysiert. Darüber hinaus wird die Lösbarkeit des umfangreichen Modells diskutiert.

Im zweiten Teil der Arbeit wird das stochastische Verbesserungsverfahren Simulated Annealing erarbeitet und auf das, im ersten Teil beschriebene Problem angewendet. Die Generierung der Nachbarschaft wird ebenso erarbeitet, wie eine einfache Kühlfunktion. Außerdem wird eine angepasste Kühlfunktion vorgestellt. Das Ergebnis des heuristischen Verfahrens wird anschließend analysiert.

- 7 -

2. Beschreibung des Problems

2.1. Teilaufgaben

Die Easyjet Airline Company plc unterhält 15 Flugzeugstandorte, von denen mit insgesamt mehr als 130 Flugzeugen täglich über 300 Ziele angeflogen werden. Den jeweiligen Standorten sind auch die dazu gehörenden Bordmitglieder zugeordnet. Die Flugzeugflotte besteht ausschließlich aus dem Flugzeugtyp Airbus 319, zu deren Besatzung im Cockpit der Kapitän und der Erste Offizier gehören. Die Pilotengehälter machen einen Großteil der Personalkosten aus.

Seitens der Fluggesellschaft besteht die Notwendigkeit einer optimalen Verteilung auf die unterschiedlich großen Standorte. Dies ist regelmäßig notwendig, da der Bedarf an entsprechendem Personal auf den einzelnen Standorten schwankt. Außerdem existiert eine natürliche Fluktuation der angestellten Piloten.

Eine Versetzung von der Heimatbasis zu einer anderen Basis (Base Transfer) kommt unter wirtschaftlich normalen Umständen und bei bestehenden Arbeitsverträgen allerdings nur in Frage, wenn der jeweilige Pilot eine Einwilligung bzw. eine Anfrage dazu stellt. So existiert auf jedem Standort eine Warteliste, auf der die Anfragen der Piloten nachgehalten werden und die nach Möglichkeit und nach Bedarf, in der Reihenfolge der eingegangenen Anfragen abgearbeitet werden. Diese Regel der Rangordnung ist obligatorisch.

Hinsichtlich des Personalbedarfs existiert eine Dreijahresplanung, die detaillierte Zahlen des wöchentlichen Mitarbeiterbedarfs der einzelnen Standorte enthält.

Eine minimale Besetzung der einzelnen Standorte ist somit vorgegeben. Um saisonale Bedarfsschwankungen auszugleichen bedient sich die Fluggesellschaft ebenso der Möglichkeit Piloten Teilzeit-Arbeitszeitverträge anzubieten. Eine Versetzung und Beförderung ist dagegen nur in Vollzeit möglich. Die Arbeitszeitplanung findet im Base Transfer Problem keine Berücksichtigung. Bestehende Verträge werden als gegeben angenommen. Erste Teilaufgabe des Problems besteht darin, die für das Unternehmen optimale Verteilung der Mitarbeiter entsprechend den Versetzungsanfragen zu finden. Dies geschieht für Kapitäne und Erste Offiziere getrennt.

- 8 -

Die aus operativer Sicht dringende Notwendigkeit zur Beförderung der Mitarbeiter ist indes Bestandteil der Aufgabe. Nach Absolvierung einer vorgegebenen Anzahl von Flugstunden und im Rahmen einer fünfwöchigen Ausbildung, in der die ausgewählten Ersten Offiziere dem operativen Geschäft nicht zur Verfügung stehen, werden diese zum Kapitän ernannt. Dieser Prozess wird Upgrade genannt und findet nach Bedarf und nach Verfügbarkeit statt.

Piloten, die für ein Upgrade infrage kommen werden nach einem aufwendigen Qualifizierungsverfahren ausgewählt und dessen Namen auf eine Warteliste für den Upgrade gesetzt. Es existiert nur eine Upgrade-Liste für das gesamte Unternehmensnetzwerk.

Nachdem das für einen Upgrade notwendige Training absolviert wurde, kann der neue Kapitän auf jeden Standort eingesetzt werden. Dieser muss vor Trainingbeginn dem Pilot bekannt gegeben werden. Zur Bedarfsdeckung an Kapitänen und Ersten Offizieren steht es dem Unternehmen natürlich frei neue Piloten einzustellen. Dies allerdings belastet aufgrund der kostenintensiven Ausbildung und einem insgesamt erhöhten Personalstamm das Jahresergebnis. Ein Upgrade ist daher einer Neueinstellung vorzuziehen und bei der Durchführung der Versetzungen kostenoptimal zu berücksichtigen. Als Zweite Teilaufgabe gilt es die optimale Auswahl an Beförderungen für eine kostenminimale Personalstruktur zu generieren. Die Berechnung der optimalen Allokation wird wöchentlich in Form einer rollierenden Planung durchgeführt. Das heißt, die Planung wird nur für die erste Periode verbindlich geplant. Bei jeder weitern Neuauflage werden alle anderen Daten aktualisiert. 6

⁶ Vgl. Kistner K.-P. et al. (2001) Produktionsplanung, Heidelberg, S. 214.

- 9 -

2.2. Zielbeschreibung

Ziel der Optimierung ist es, die gesamten Personalkosten des Unternehmens möglichst gering zu halten. Kostentreiber sind dabei:

• Trainingskosten die bei einer Neueinstellung anfallen

• Trainingskosten eines Upgrade-Prozesses

• Gehälter für beschäftigtes Personal

Keinerlei Kosten für das Unternehmen verursacht dagegen die Versetzung eines Mitarbeiters auf einen anderen Standort. Eine hohe Anzahl an Versetzungsanfragen seitens der Mitarbeiter erhöht die Möglichkeit diese entsprechend des Bedarfs an Personal auf den einzelnen Standorten zu realisieren. Um Versetzungsanfragen seitens der Mitarbeiter zu fördern, versucht das Unternehmen eine Anfrage nach Möglichkeit auch möglichst schnell und in möglichst hoher Anzahl zu realisieren. Versetzungen sind jedoch vorrangig über den gesamten Planungshorizont als Instrument zur Kostenminimierung durchzuführen.

Das Problem ist ein gemischt ganzzahliges lineares Minimierungsproblem der genannten Kosten unter Berücksichtigung aller relevanten Restriktionen.

- 10 -

2.3. Modellhafte Umsetzung

Das Personal einer Firma ist auf mehreren Standorten, denen es fest zugeteilt ist, verteilt. Nun soll die Möglichkeit einer Versetzung einiger Mitarbeiter von einem Standort zu einem anderen Standort zur Kostenminimierung genutzt werden. Zum einen muss der Bedarf auf den jeweiligen Standorten stets erfüllt sein. Zum anderen soll dem Wechselwunsch der Mitarbeiter in möglichst großer Zahl, möglichst schnell stattgegeben werden.

Als spezielles Transportproblem in einem gerichteten Netzwerk ⁷ modelliert, werden von einer bestimmten Anzahl von Produktionsstandorten über eine Vielzahl von Zwischenlagern eine ebenso große Anzahl an Vertriebsstandorten beliefert. Der Transport ist mit Kosten verbunden und kapazitiert. Das Entscheidungskriterium, nämlich aus einer Vielzahl möglicher Transporte einen auszuwählen, beruht auf der Ermittlung der kostengünstigsten. Folgende Dimensionen werden eingeführt:

• die Zeit mit der Ausprägung einer bis 26 Wochen (auch als Planperiode bezeichnet)

• der Pilot p mit der Ausprägung Erster Offizier oder Kapitän Der Wechsel eines Piloten , findet von Standort zu Standort in der Zeit statt.

Bei dieser Anschauung ist zu berücksichtigen, dass alle Personen auf allen Standorten von der Zeit t in die Zeit 1 bewegt werden müssen. So wird ein und derselbe Standort, jedoch zu fortschreitenden Planperioden angesteuert. Dies ist der Fall, wenn die Person auf dem Standort i auch in der folgenden Planperiode (Woche) 1 verbleibt. Diese Bewegung wird als Step bezeichnet.

Ist eine Person zum Zeitpunkt auf dem Standort i stationiert und wird zum Zeitpunkt 1 zum Standort versetzt, so wird ein Base Transfer vollzogen.

Auf den wechselnden Bedarf der einzelnen Standorte an Mitarbeitern zu den jeweiligen Zeiten kann insgesamt mit Versetzungen, Neueinstellungen oder durch Beförderungen reagiert werden.

⁷ Vgl. Laarhoven, P.J.M. (1988), Theoretical and computational aspect of simulated

annealing, Amsterdam, S. 67.

- 11 -

Da eine Versetzung von einem Standort zu einem anderen, genauso wie eine Beförderung in der Reihenfolge der gemachten Anfragen bzw. Qualifizierungen durchgeführt werden muss, wird eine weitere Dimension eingeführt:

• Die Rangfolge , mit der Ausprägung 1,2,3…30. Die jeweiligen Anfragen vom Standort zu Standort in der Zeit versetzt

zu werden, werden durchnummeriert mit . Ein Step kommt dagegen ohne das Indizien Paar , aus. Auch die Dimension findet bei dieser Bewegung keine Berücksichtigung.

Für einen Upgrade wurde ein eigener fiktiver Standort eingeführt. Auch wird für den Upgrade eine eigene Variable benutzt. Wird diese Bewegung zu dem Standort Upgrade als Erster Offizier durchgeführt, so wird sie mit dem Indizienpaar , geführt. Wechselt der zum Kapitän Beförderte wieder

bezeichnet. Die Upgrades mit dem Indizienpaar , müssen in der Reihenfolge vollzogen werden, in der die Anwärter dafür ausgewählt wurden. Dazu werden auch die Beförderungsanwartschaften durchnummeriert mit .

2.4. Graphische Darstellung

Das Problem ist in seiner Grundstruktur als Transportproblem mit Zwischenlagern sehr anschaulich in einem Netzwerk darstellbar ⁸ (siehe unten Abbildung 1: Netzwerk). Daraus lässt sich anschließend eine plausible mathematische Darstellung ableiten.

In dem Netzwerk wird je Standort und Planperiode ein Knoten gezeichnet. Die Pfeile geben die möglichen Bewegungen zwischen den Knoten und die Richtung der Bewegung vor. In diesem skizzierten Modell wird über 3 Planperioden optimiert. Die Planperiode 0 gibt den Anfangszustand an. Da das Base Transfer Problem sich ausschließlich mit der Zuordnung der Mitarbeiter zu den einzelnen Standorten je Planperiode beschäftigt, werden nur die Bewegungen zu einem Standort hin, bezeichnenderweise am Anfang

⁸ Vgl. Klose, A, Lidtke, T. (2005), Lagrange-Ansätze zur Lösung des Transportproblems

mit Fixkosten, S.1, in Supply Chain Management und Logistik, Günter, H-O, et al

[Hrsg.] (2005), Heidelberg (S. 507-530).

- 12 -

der Planperiode, und von einem Standort weg, also nach Ende der Planperiode betrachtet. Die Arbeitswoche, über die sich die individuelle Planperiode erstreckt, beginnt für die einzelnen Piloten allerdings unterschiedlich. Jede Versetzung auf einen anderen Standort findet nach Ende und vor Beginn einer individuellen Arbeitswoche statt. So hat eine Versetzung für die übergeordnete Einsatzplanung keinen Einfluss. Da sich die Planzahlen für jeden Standort auf eine festgelegte Woche beziehen wird die Versetzung der Mitarbeiter aus Sicht der Personalplanung zwischen den von der Bedarfsplanung vorgegebenen Planperioden vollzogen. Eine Bewegung zwischen den Knoten findet in Bezug auf die Dimension Zeit vereinbarungsgemäß in der Planperiode statt, in die gewechselt wird. Zur Vereinfachung wird in der Skizze von nur 2 Standorten (blaue Knoten und schwarze Knoten) ausgegangen. Da ein Erster Offizier ohne entsprechende Ausbildung einen Kapitän nicht ersetzten kann und andersherum ein Kapitän nicht ohne weiteres die Rolle eines Ersten Offiziers übernimmt, wurden die Standorte für beide Qualifizierungsgrade von einander getrennt. Im unteren Bereich wurden die für die Ersten Offiziere, im oberen die für die Kapitäne eingezeichnet. Die roten Pfeile kennzeichnen die Versetzungsanfragen als mögliche Bewegung von einem Standort zu einem anderen. Unter Berücksichtigung, dass der Rang auf der entsprechenden Warteliste eingehalten werden muss, wird für jeden Rang ein Pfeil benötigt. Die Minimalkapazität der roten Pfeile für den Standortwechsel ist 0. Die Maximalkapazität der Summe aller Pfeile eines Ranges je Ebene über die gesamte Planungszeit ist gleich 1. Die Kapazität auf diesen Pfeilen ist ganzzahlig. Der gestrichelte Pfeil in blau oder in schwarz markiert die Bewegung von einem Standort in der Zeit t zu demselben Standort in t+1. Es findet keine Versetzung auf einen anderen Standort statt. Diese Bewegung wird -wie bereits erwähnt- als Step bezeichnet. Diese Pfeile haben eine Minimalkapazität gleich der Summe aller auf diesem Standort stationierten Mitarbeiter, abzüglich der Personen, die diesen Standort verlassen. Die Einführung einer Maximalkapazität auf den gestrichelten Pfeilen birgt die Gefahr der Nichtlösbarkeit. Die Summe der auf einen Standort (Knoten) eingehenden Einheiten muss gleich der Summe der herausgehenden Einheiten sein. Die Summe der

- 13 -

eingehenden Einheiten ist mindestens so groß wie der Bedarf auf dem Standort.

Neueinstellungen und Kündigungen wurden als einzelne Pfeile den einzelnen Standorten 1 und 2 zugeordnet. Auf die Verbindung dieser Pfeile über zusätzliche Knoten, sowie die Verbindung der Ausgangs- und Endknoten zu einem Netzwerk ist aus Darstellungsgründen verzichtet worden.

Der braune Standort zwischen den beiden Ebenen markiert den Trainingsort für die Upgrades. Erste Offiziere, die befördert werden, werden zu diesem Standort für die Trainingsmaßnahme versetzt. Die nun zum Kapitän ernannten Piloten werden dann von diesem Standort u den ihnen zugeteilten Standorten zugewiesen. Die möglichen Bewegungen wurden mit einem durchzogenen braunen Pfeil gekennzeichnet. Auch hier gilt die Regel der Rangfolge. Bei einer Rangtiefe von 3 sind 3 Pfeile notwendig, je einen für jeden Rang. Da der Pilot für die Zeit der Ausbildung zum Kapitän auf dem Standort u verweilt wird auch hier für jede Planperiode ein Standort eingezeichnet. Der Pilot muss wieder von einer Planperiode zur nächsten bewegt werden. Es ist ersichtlich, dass dabei 2 Planperioden überbrückt werden, in der der Pilot dem Flugbetrieb nicht zur Verfügung steht. In der stark verkleinerten Darstellung wurde also eine Ausbildungszeit von 2

Planperioden (2 Wochen) angenommen. Die fett markierten Pfeile in der Abbildung stellen ausgeführte Versetzungen dar. Je eine Versetzung findet in jeder Planperiode von Standort 1 zum Standort 2 auf der Ebene der Kapitäne statt. Auch von Standort 2 wurden 3 Versetzungen vollzogen. Hier gibt es eine Versetzung in der Planperiode 1 und 2 in der Planperiode 3.

- 14 -

Abbildung 1: Netzwerk

2.5. Einschränkungen und Besonderheiten des Ansatzes

Bei der Modellierung dieses Problems wurde der Rahmen und die Gegebenheiten der Firma Easyjet Airline Company plc berücksichtigt. Diese Regeln werden über entsprechende Restriktionen implementiert. Diese Restriktionen lassen sich in weiche und harte Restriktionen einteilen. Harte Restriktionen sind sogenannte institutionelle Grenzen, die nicht überschritten werden dürfen. Diese sind:

• Der Bedarf an entsprechendem Personal auf den einzelnen Standorten ist unbedingt einzuhalten.

• Eine Versetzung, die nicht angefragt wurde, darf nicht ausgeführt werden.

• Ein Upgrade darf nur erfolgen, wenn eine zusätzliche Nachfrage nach Kapitänen besteht.

• Ein Upgrade darf nur erfolgen, wenn dazu eine entsprechende Auswahl an Ersten Offizieren getroffen wurde. Es muss also jemand auf der Warteliste für ein Upgrade stehen.

• Eine stattgegebene Versetzungsanfrage darf nur in der Reihenfolge der abgegebenen Anfragen erfolgen. (gleiches gilt für ein Uprade) Diese Regel wird als First in - First out bezeichnet. Weiche Restriktionen hingegen können mit einem Strafpreis umgangen werden. Dazu wird ein Strafparameter implementiert. Weiche Restriktionen weist das Problem bei gegebener Modellierung nicht auf. Auf diese Möglichkeit wird aber bei der Anwendung des Simulated Annealing Algorithmus zurückgegriffen.

Die Restriktion zur Beachtung der Reihenfolge ist in der Literatur auch als Rangfolgen-Problem ⁹ bekannt. Es zeichnet sich insbesondere dadurch aus, dass das Problem durch diese Regeln sehr umfangreich wird. Beachtet man eine Rangtiefe von 30, so multipliziert sich die Anzahl der Variablen um eben diesen Wert. Wenn es möglich ist und zudem Kostenersparnisse mit sich bringt, die Anfrage auf eine Versetzung von einem Standort A zum Standort B in der Zeit zu vollziehen, muss zunächst

⁹ Vgl. Holländer, M., et al. (1977), Function Decreasing in Transposition and their

Application in Ranking Problems, S. 1, in The Annals of Statistics, Institute of

Mathematical Statistics (IMS) [Hrsg.] (1977), Vol. 5, No. 4 (S. 722-733).

- 16 -

geprüft werden, ob die Versetzung gemäß der Anfrage mit dem nächst besseren Rang bereits generiert wurde. Dieser Umstand erhöht die Anzahl der Restriktionen und die Rechenleistung, die zur Lösung aufgewendet werden muss.

Findet ein Upgrade statt, so verlässt derjenige Erste Offizier seinen bisherigen Standort, der gemäß der Rangordnung der nächste Anwärter ist. Dies muss bei einem Standortwechsel in so weit berücksichtigt werden, dass auch weiterhin der Bedarf an Ersten Offizieren auf dem Standort, gegebenenfalls durch eine Neueinstellung gedeckt wird. Durch die Möglichkeit des Upgrades berühren sich die Ebene der Kapitäne und die der Ersten Offiziere miteinander.

Dieses Problem ist, wie es für Transportprobleme charakteristisch ist, NPhard. Eine optimale Lösung kann nicht durch ein Verfahren ermittelt werden, dessen Rechenzeit durch eine ganzrationale Funktion mit der Größe der Eingabewerte begrenzt wird. ¹⁰ Da einige Variablen zwingend ganzzahlig sind, ist das Problem der gemischt ganzzahligen Linearen Optimierung (MILP) zu zuordnen. Diese Probleme weisen exponentiell mit der Anzahl der Eingabedaten wachsende Rechenlaufzeiten auf. 11

¹⁰ Vgl. Sechen, C. (1988), VLSI Placement and Global Routing Using Simulated

Annealing, Boston, S.31.

¹¹ Vgl. Kallrath, J. (2002), Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis,

Wiesbaden, S. 15.

- 17 -

3. Mathematische Darstellung

3.1. Einleitung

Abgeleitet aus dem bereits erarbeiteten Modell erfolgt nun die mathematische Darstellung. Sie ist Voraussetzung für die Lineare Programmierung, aber auch Grundlage für die Programmierung des Simulated Annealing Algorithmus. Kapitel 3.2 fasst noch einmal die Hypothesen zusammen und ordnet diese bereits den mathematischen Begriffen und Indizes zu. Die Annahmen werden nach den betreffenden Bereichen geordnet. Diese sind die Annahmen der Standorte, des Personals und die des Unternehmens. Die Modellparameter werden in Kapitel 3.3. separat aufgelistet und erläutert. In Kapitel 3.4 sind der mathematische Ansatz unter Nennung der Zielfunktion, die Restriktionen, geordnet nach den Bedingungen der Standorte, Upgrades und Transfers, sowie der Definitionsbereich der Variablen wiedergegeben.

3.2. Annahmen in Anlehnung an die Modellbeschreibung

3.2.1. Standorte

1a) Es gibt insgesamt 15 Standorte , , von denen aus operiert •

wird. Diese sind zum einen den Kapitänen und zum anderen den Ersten Offizieren zugeordnet. 1b) Es gibt einen Standort (Leave), der beiden •

Mitarbeiterausprägungen zugeordnet wird, Kapitänen , sowie Ersten Offizieren .

1c) Es gibt einen Standort (Upgrade) für die Ersten Offiziere . •

1d) Es gibt einen Standort (New) für Neueinstellungen, der •

beiden Mitarbeiterausprägungen zugeordnet wird, Kapitänen , sowie Ersten Offizieren .

- 18 -

3.2.2. Personal

•

versetzt zu werden, wird in einer Warteliste nachgehalten und mit einem Rang versehen. Die Versetzungen werden nach dem Prinzip First in - First out abgearbeitet.

• 2b) Die Beförderung eines Ersten Offiziers zum Kapitän bedingt eine Ausbildungszeit von 5 Wochen. Die Person steht in dieser Zeit dem operativen Geschäft nicht zur Verfügung. Wird ein Erster Offizier in der Planperiode auf den Standort versetzt, ist ein Wechsel vom Standort zum Standort der Kapitäne in der Planperiode 5 zu vollziehen. Der Erste Offizier wird nun als Kapitän geführt.

• 2c) Es existiert eine Upgrade-Warteliste für alle Anwärter auf den Posten des Kapitäns.

• 2d) Besteht keine Anfrage auf eine Versetzung, kann eine Person nicht von Standort zum Standort versetzt werden. Diese Person verbleibt also auf dem Standort und es findet lediglich eine Bewegung vom Standort in der Planperiode zum Standort in der Planperiode 1 statt. (Step)

3.2.3. Unternehmen

3b) Der Planungshorizont Τ beträgt 26 Wochen, eine Planperiode • t beträgt eine Woche.

3c) Das Minimum an benötigtem Personal auf den •

jeweiligen Standorten zur jeweiligen Zeit ist vorgegeben.

- 19 -

3.3. Modellparameter

3.3.1. Mengen und Indizes

є Standorte von denen gewechselt wird, wenn dieser Index vor •

dem Index steht, 1,2,3. . , ,, ,, , . . ._ j є B Standorte zu denen gewechselt wird, wenn der Index hinter •

dem Index steht, 1,2,3. . , ,, ,, ,, . . ._ є Piloten mit der Ausprägung Kapitän oder Erster Offizier f. •

є Rangordnung der Transfer- und Upgradelisten, durch die eine •

First In -. First Out Versetzungs- und Beförderungspolitik gewährleistet wird; 1, … , Ρ 30. є Planperiode, mit 1, … , Τ 26 •

є Upgrade-Standort. Auf diesem befindet sich der Erste •

Offizier während seiner Ausbildung zum Kapitän

- 20 -

3.3.2. Eingabewerte

Bedarf am Standort j zur Planperiode t von Piloten p •

Anzahl Piloten p, die zur Planperiode t=0 am Standort i •

benötigt werden (Anfangsbestand) • Personalkosten pro Pilot

Kosten für die Ausbildung bei einer Neueinstellung eines • Ersten Offiziers

Kosten für die Ausbildung bei einer Neueinstellung eines • Kapitäns

Ausbildungszeit eines Ersten Offiziers zum Kapitän •

(Upgrade). Diese beträgt 5 Planperioden (5 Wochen). Kosten für die Ausbildung zum Kapitän im Rahmen eines • Upgrade

Bonus (negativ) für eine ausgeführte Versetzung •

Anfrage vom Standort nach Standort versetzt zu werden, •

abgegeben in der Planperiode , vom Piloten , mit dem Rang auf der Warteliste

Upgrade-Anwartschaft vom Standort eines Ersten Offiziers •

zur Planperiode vom Wartelistenrang

- 21 -

3.3.3. Entscheidungsvariablen

Anzahl der Piloten , die das Unternehmen vom Standort zur •

Planperiode , eines Piloten verlassen. Anzahl Neuanstellungen vom Standort zur Planperiode , • eines Piloten p.

(1) mit : Anzahl von Ersten Offizieren, die vom •

Standort zum Standort versetzt werden, um dort zum Kapitän ausgebildet zu werden (Upgrade), oder aber (2) mit : Anzahl der zu Kapitänen ausgebildeten Piloten, die vom Standort zum Standort versetzt werden. Diese Bewegung findet jeweils in der Planperiode und vom Listenrang statt. Die Ausprägung der Variable ist also lediglich (einstellen eines Ersten Offiziers in den Upgrade-Standort) oder als Parameter dafür, dass der

nun zum Kapitän ausgebildete dem operativen Geschäft wieder zugeteilt wird. Der Wert ist größer gleich Null, ganzzahlig und maximal 1 (binär).

Vereinbarungsgemäß soll gelten, dass 0, ü und 0, ü .

• , zur Planperiode t, eines Piloten p, mit dem Wartelistenrang r stattfinden. Der Wert ist größer gleich Null, ganzzahlig und maximal 1 (binär).

Anzahl der Piloten p, die zur Planperiode p von Standort i •

zum Standort j, mit (i, j nicht gleich u) wechseln, also de facto am selben Standort verbleiben (Step). In den hier

benutzt. Dies ist gegebenenfalls einfacher zu Programmieren. Der Indizes ist jedoch redundant.

- 22 -

3.4. Mathematischer Ansatz

3.4.1. Zielfunktion Die Zielfunktion summiert:

Die getätigten Versetzungen x von einem Standort zu einem •

Standort zu allen Planperioden , über alle Ränge , multipliziert mit der Bonuskonstanten dividiert durch den Wert des Indizes . (Dadurch wird eine späterer Transfer geringer belohnt.) Alle Piloten p von allen Standorten , über alle Planperioden •

multipliziert mit einer Kostenkonstante . Alle getätigten Upgrades u zu allen Zeiten und Rängen r, •

multipliziert mit den Ausbildungskosten zu der Planperiode . Alle Neueinstellungen n zu allen Zeiten , multipliziert mit den •

Kosten für Neueinstellungen , inklusive aller Kosten für die Anwerbung und Ausbildungskosten, etc.

// x wb є є єє єє є

x y k

є єє єє є єє

u nc

єє є є

n nkf є єє

n nkc

єє є єє

- 23 -

3.4.2. Restriktionen und Definitionsbereich

Die Restriktionen der Standorte sind die Restriktionen (1)-(3):

є

^{є єє} (1)

in der Zeit 1 zu transferieren, entweder durch einen Step y , Upgrade

transportierten Piloten müssen auch wieder aus dem Standort heraus transportiert werden (1).

^{єє єє} üü єє, 0, єє (2)

In der Restriktion (2) erhält jeder Standort die benötigten Ausgangswerte zu Planperiode 0, an Piloten . D.h. es wird festgelegt, dass alle Piloten , den Standort verlassen, sei es durch einen Transfer x , einen Step y , oder durch Verlassen des Unternehmens (Leave) l , der Anzahl des Ausgangswertes entspricht.

єє єє

ü є, , 1, . . , Τ , є (3)

Restriktion (3) garantiert, dass der Bedarf an Piloten auf jedem Standort zu jeder Planperiode gedeckt ist, entweder durch die Summe aller Versetzungen x zum Standort ü є, einem Step y , einem Upgrade u oder einer Neueinstellung n .

- 24 -

Die Restriktionen (4)-(8) sind die die Upgrades betreffende:

u u 0

^{є єє єє єє} ü єє (4)

(4) stellt in Verbindung mit Restriktion (1) sicher, dass für alle Ersten Offiziere, die zum Kapitän ausgebildet werden (Upgrade) auch ein Bedarf an Kapitänen besteht und der Upgrade-Standort nach der Ausbildungszeit tu wieder verlassen wird.

u u 0

єє

üü єє, єє, єє\Ρ (5)

Da auch für die Upgrades eine Rangfolge eingehalten werden muss erlaubt Restriktion (5) ein Upgrade eines Ranges r+1 nur, wenn der Upgrade mit dem Rang r bereits getätigt wurde. Dies gilt nur für die Upgrades der Ersten Offiziere.

üü єє, єє, t tu (6)

Bei einer rollierenden Berechnung müssen die ersten Offiziere, denen bereits ein Standort als Kapitän zugeordnet wurde, sich jedoch noch in der Ausbildung auf dem Standort u (Upgrade) befinden, berücksichtigt werden. Mit der Restriktion (6) wird dies beachtet notwendigerweise für die Zeit .

u 1

є

üü єє, єє, єє (7)

Die Restriktion (7) garantiert, dass jeder Upgrade nur maximal ein Mal getätigt wird.

- 25 -

üü єє, єє, єє (8)

Restriktion (8) stellt sicher, dass ein Upgrade nur durchgeführt wird, wenn ein Erster Offizier über eine entsprechende Qualifikation verfügt. Ist ein Erster Offizier für ein Upgrade zur Planperiode qualifiziert, so ist er dies auch für alle nachfolgenden Planperioden. D.h., ist ein Upgrade-Anwärter für einen Upgrade in der Planperiode ausgewählt worden ( 1) so ist er dies für alle . Dies wird bei den Eingabewerten berücksichtigt. Ein Upgrade in der Zeit Τ Τ Τ sind nicht möglich, hier gilt: 0, ü Τ .

- 26 -

Die Restriktionen (9)-(11) sind die der Versetzungsanfragen:

x x 0

єє

üü єє, єє, єє, єє (9)

Restriktion (9) stellt sicher, dass die Reihenfolgeregel bei einer Versetzung auf einen anderen Standort eingehalten wird.

x 1

^є für alle iєB jєB, pєP, rєR (10)

Die Restriktion (10) garantiert, dass jede Versetzung von Standort nach Standort des Piloten vom Rang über alle Planperioden maximal einmal getätigt wird.

üü єє, єє, єє, єє, єє (11)

Restriktion (11) stellt sicher, dass es zu jeder Versetzung auch eine Versetzungsanfrage gestellt wurde.

Eine Anfrage die zur Planperiode gestellt wurde, ist für alle nachfolgenden Planperioden gültig. D.h. Anfragen für eine Versetzung in der Periode ist für alle gleich 1. Dies wird bei den Eingabewerten berücksichtigt.

Definitionsbereich:

, , , , , , 0 0, 1 (binär)

- 27 -

4. Lineare Programmierung

4.1. Modellrechnung mittels Lingo - Optimization Software

4.1.1. Begrenzung des Modells

Für eine Modellrechnung mittels Lingo - Optimization Software wurde das Problem in einem kleineren Modell abgebildet, um die Kapazität der vorliegenden Software-Version von maximal 4500 Variablen und 8000 Restriktionen nicht zu überschreiten.

Es wurde mit nur 6 Standorten, zuzüglich des Standortes für ein Upgrade u, über einen gesamten Planungshorizont von 6 Planperioden (6 Wochen) mit einer Wartelistenrangtiefe von 5 gearbeitet.

Da nur eine begrenzte Anzahl an Binär- und Integer-Variablen zulässig sind, wurde der Definitionsbereich angepasst. Die Variablen , , , sowie und sind ganzzahlig. Die Variable ist stetig und größer

Null.

Das Modell wird im Folgenden Modell I genannt. Der Bonus für einen Wechsel beträgt 1 Einheiten. Die Kosten für eine Neueinstellung für die ersten Offiziere betragen 2 Einheiten und für Kapitäne 6 Einheiten. Ein Upgrade kostet 2 Einheiten. Die Personalkosten pro Planperiode betragen 1 Einheit. Dadurch ist gewährleistet, dass die eine Beförderung in jedem Fall einer Neueinstellung eines Kapitäns vorgezogen wird. Transfers werden immer zunächst so vorgenommen, dass gegebenenfalls Neueinstellung umgangen, oder aufgeschoben werden. Es werden alle möglichen Versetzungen vollzogen.

Die Ausgangswerte wurden aus der realen Personalplanung der Firma Easyjet Airline Company plc entnommen. Es konnten zunächst nur die 6 größten Standorte berücksichtigt werden.

Die Eingabedaten, die die Versetzungsanfragen und Beförderungswarteliste wiedergeben sind in Tabelle 1 dargestellt. In der oberen Spalte ist der früheste Zeitpunkt für eine Versetzung bzw. ein Upgrade mit DOR (Day of Request) angegeben. Alle Versetzungsanfragen aus dem betrachteten Zeitraum stammen von Kapitänen (CP).

Tabelle 1 gibt die Anfragen bis zum 31. März 2009 wieder. Anfragen für die Zeit nach dem 22. Februar 2009 können nicht berücksichtigt werden. Da noch keiner Versetzung stattgegeben wurde, ist der Status für alle Anfragen

- 28 -

noch offen (open). Die Spalte mit der Überschrift Current gibt den derzeitigen Standort an. Die angefragten Standorte finden sich hingegen in der ersten Spalte (Requested). Die Spalten ganz rechts geben die Codierung der Anfragen für die Verarbeitung in den Optimierungsprogrammen an.

Tabelle 1: Eingabewerte der Wechselanfragen und Upgrade-Optionen

- 29 -

Ähnlich verhält es sich mit der Upgrade-Warteliste, die abgesetzt von den Versetzungsanfragen am unteren Ende der Tabelle platziert wurde.

4.1.2. Resultate

Der Zielwert der optimalen Lösung beträgt 5468,77. Insgesamt wurden 4 Upgrades durchgeführt. 26 von 27 Versetzungsanfragen konnten der Berechnung folgend vollzogen werden. Um den Bedarf auf den Standorten zu decken mussten 13 neue Erste Offiziere und 5 neue Kapitäne eingestellt werden. In Tabelle 2 ist das Ergebnis zusammengestellt. Dem errechneten Ergebnis ist die Situation gegenübergestellt worden, die sich ergibt, wenn weder Versetzungsmöglichkeiten noch Beförderungen generiert werden. Die Ergebnisse sind für jeden Standort einzeln zusammengestellt worden. Das berechnete optimale Ergebnis findet sich dabei in den Spalten unter denen der Lösung, die sich ergibt, wenn jegliche Versetzungs- und Upgrade-Möglichkeiten ausgeschlossen sind. Die Standorte (Base) sind entsprechend der Codierung im Programm nummeriert. In der ersten Reihe findet sich die Anzahl der benötigten Mitarbeiter (Target Used), die für beide Positionen im Cockpit gleich sind.

In den Reihen darunter werden die Kapitäne (CP) und Erste Offiziere (FO) getrennt betrachtet. Hier sind die Anzahl der tatsächlich beschäftigten Mitarbeiter als Äquivalent einer Vollzeit-Planstelle (FTE), sowie die Zahl der Kündigungen (Resignations) eingetragen. Das Datum in der Überschrift entspricht dem jeweiligen Anfang der Planperiode. Die Ausgangssituation ist die der Planperiode 0 (05.-11.Januar). Ein Pilot hat in der Regel 3 bis 5 aufeinander folgende Arbeitstage. Darauf folgen 2 bis 5 arbeitsfreie Tage. Werden darüber hinaus Ausfallzeiten wie Urlaub und Krankheit berücksichtigt, bedarf es nahezu einer 4-Fach Besetzung an Mitarbeitern auf jeder Position. In der Planperiode 1, vom 12. - 18. Januar, besteht auf dem Standort 1 (BRS=Bristol) ein Bedarf von durchgehend 44 Mitarbeitern je Position. Es befinden sich dagegen 60 Kapitäne und 57 Erste Offiziere auf dem Standort. Sind die Mitarbeiterzahlen in der 1. Periode noch gleich, so verschieben sich diese in den Reihen der Optimalen Berechnung aufgrund durchgeführter Versetzungen und Upgrades. Die Mitarbeiterzahlen, die sich aufgrund eines Standortwechsels ändern wurden rot hervorgehoben. Tabelle 2: Ergebnis Lineare Optimierung.

- 30 -

- 31 -

Die hellere Färbung markiert eine Versetzung von dem Standort auf dem der Pilot zuvor stationiert war, eine dunklere Färbung den Standort zu dem er versetzt wurde.

Die Anzahl der versetzten Mitarbeiter ist in der Zeile Transferred wiedergegeben. Ein Minus bedeutet, dass diese Anzahl an Mitarbeitern auf dem Standort in der nächsten Periode nicht mehr zur Verfügung steht. Die auf einen Standort versetzten Mitarbeiter stehen dagegen bereits zum Periodenbeginn zur Verfügung. Daher sind diese in der Anzahl der auf dem Standort stationierten Piloten bereits enthalten. Base Transfers und Upgrades vom Standort 2 (LGW=London Gatwick) sind in der ersten Planperiode exemplarisch durch Pfeile nachgezeichnet worden. Fett formatierte Zahlen bezeichnen ein Mitarbeiterzuwachs durch Neueinstellungen entsprechender Piloten. Eine Neueinstellung wird jeweils zum Periodenanfang vollzogen. Die Anzahl der Einstellung ist in der ganz rechten mit New überschriebenen Spalte noch einmal für jeden Standort summiert.

Kündigt der Mitarbeiter, so verlässt er das Unternehmen stets am Periodenende. Dies ist in der Zeile Resignation aufgeführt. Abgänge durch Upgrades sind in der Reihe CMD Upgrades gesondert festgehalten worden und wie den korrelierenden Zugängen in blau herforgerufen. In der rechten Spalte mit der Überschrift Sum sind die Zahlen der jeweiligen Reihe addiert.

4.1.3. Analyse

Der entsprechende Kostenwert einer Personalplanung ohne Versetzungen und Beförderungen beträgt 5.529. Das sind 60,23 Einheiten mehr als bei der optimalen Allokation. Insgesamt mussten 7 Kapitäne und 10 Erste Offiziere neu eingestellt werden. Inklusive der 2 Abgänge wurden 5.467 Wochenplanstellen benötigt. Dem gegenüber stehen 5.444

Wochenplanstellen bei einer optimalen Ausnutzung der Wechsel- und Upgrade-Optionen. Dies bedeutet eine Ersparnis von 23 Wochengehältern. Einsparungen konnten vor allem auf dem Standort 2 erzielt werden. Hier wurde ein Personalüberhang durch den Abgang von 5 Kapitänen infolge von Versetzungen und von 3 Ersten Offizieren aufgrund von Beförderung gleich in der ersten Planperiode abgebaut werden. Weitere Kosten konnten

- 32 -

dadurch eingespart werden, dass anstatt der Neuanstellung eines Kapitäns eine Beförderung durchgeführt wurde. Betrachtet man die Versetzungen bei den Kapitänen isoliert so ergibt sich folgendes Bild. Während ohne Versetzungen 7 Kapitäne hätten neu eingestellt werden müssen, so sind bei der optimierten Verteilung nur 5 Neueinstellung notwendig. So konnten 2 Neueinstellungen auf Standort 3 durch die Versetzung je eines Kapitäns von Standort 2 und Standort 6 eingespart werden. Dadurch wurde jedoch der Überhang an Kapitänen zunächst erhöht, umgekehrt aber auf Standort 6 und 2 verringert. Addiert man die 4 Kapitäne hinzu, die durch ein Upgrade rekrutiert werden konnten, so werden insgesamt 2 Kapitäne mehr im Netzwerk gehalten. Durch die Beförderungen konnten Versetzungen von Standort 4 in der Planperiode 5 generiert werden. Der resultierende Überhang auf Standort 1 und 5 fällt nicht mehr ins Gewicht, da die Planung nach 6 Wochen abbricht. Insgesamt wurde jedoch ein Pilot mehr angestellt. Eine rollierende Planung über einen Zeitraum von 26 Wochen verhindert diese Fehlplanung.

4.1.4. Fazit

Bereits in einem kleinen Modell mit nur 6 Standorten und über ein Planungshorizont von 5 Perioden konnten 23 Wochengehälter eingespart werden. Bei einem 5 stelligen Wochengehalt der Piloten ist gezeigt worden, dass die Optimierung des Base Transfer Problems eine ernst zu nehmende Kosteneinsparungsmaßnahme darstellt. Das Base Transfer Problem kann über ein Planungshorizont von mehreren Wochen bei 15 Standorten und eine großen Anzahl von Versetzungsanfragen und Beförderungsmaßnahmen manuell nicht annähernd optimal gelöst werden. Der Rechenaufwand der Problematik unter Berücksichtigung aller Parameter wirft jedoch die Frage nach der Lösbarkeit innerhalb einer praktikablen Zeit auf. Das Problem wird mit dem Lingo Solver im Branch & Bound Verfahren ¹² mit LP-Relaxation gelöst. Das Unterproblem wird durch das Simplexverfahren berechnet, deren Rechenzeit durch die Anzahl der durchzuführenden Pivotschritte bestimmt wird. Bei 93.922 Restriktionen

¹² laut Lingo Status Bericht Modell I, siehe Angang.

- 33 -

und 23.350 Variablen ist die Anzahl möglicher Basen und einhergehend damit der möglichen Pivotschritte sehr groß. 13

Bei dem kleineren Modell I mit 3.152 Restriktionen und 2.310 Variablen ¹⁴ und einer Prozessorleistung von 3GHz wurden 3: 09 Minuten an Rechenzeit benötigt. Für das Auffinden des globalen Optimums wurden 390 Iterationen benötigt. „Das Simplexverfahren kann zwar in extrem konstruierten Fällen exponentielles Wachstum (…) zeigen, in der Praxis beobachtet man eher ein lineares Verhalten (…).“ ¹⁵ Eine Aussage über die Rechenzeit bei Verwendung des Branch & Bound Verfahrens ist dagegen kaum möglich. Zur Lösung eines Modells mit 510 Restriktionen und 243 Variablen (Modell II - siehe Kapitel 5.2.1) mit dem Lingo - Optimizator dauerte 1 Sekunde Rechenzeit. Es wurden 33 Iterationen benötigt. ¹⁶ Ein linearer Zusammenhang über die Anzahl der Variablen kann damit ausgeschlossen werden.

Eine Reduzierung des Problems durch die Verkürzung des Planungshorizontes kann zu Fehlplanungen führen. Insbesondere da der Flugbetrieb saisonalen Bedarfsschwankungen unterworfen ist.

Kosteneinsparungsmöglichkeiten bleiben dadurch gegebenenfalls ungenutzt. Eine rollierende Planung sollte allerdings mindestens über einen Planungshorizont von 12 Wochen optimieren, Upgrades gegebenenfalls nur in der Zeit 0 erlaubt sein, um eine Fehlplanung wie im gezeigten Beispiel zu vermeiden. Eine Aufstockung des Personalstamms wird bei einem Kostenwert von einer Einheit pro Woche entsprechend gewichtet werden.

Es scheint jedoch langfristig möglich die Rangtiefe zu verkürzen. Es Konnte gezeigt werden, dass bereits bei der Lösung des Modells I über 95% der Versetzungsanfragen genehmigt werden konnten. Der Häufung an nicht genehmigten Versetzungsanfragen wird durch eine Optimierung der Zuordnung schnell entgegengewirkt. Diese Maßnahmen verringert die Größe des Problems.

¹³ Kallrath, J. (2002), S. 65.

¹⁴ laut Lingo Status Bericht Modell I, siehe Angang.

¹⁵ Vgl. Kallrath, J. (2002), S. 36.

¹⁶ laut Lingo Status Bericht Modell II, siehe Anhang.

- 34 -

5. Anwendung des Simulated Annealing Algorithmus

5.1. Theoretische Grundlagen

Auf der Grundlage des Mathematischen Ansatzes aus Kapitel 3.4. soll nun die Lösung des Problems mittels Simulated Annealing erfolgen. Die optimale Lösung des reduzierten Modells I ist durch die lineare Optimierung der vorangegangenen Berechnung aus Kapitel 4.1. hinlänglich bekannt. Sie wird abschließend zur Bewertung des im Folgenden vorgestellten Verfahrens herangezogen.

Simulated Annealing ist ein stochastisches Nachbarschaftssuchverfahren zur Lösung von Optimierungsproblemen kombinatorischer Art. ¹⁷ Es basiert auf einem Verfahren aus der statischen Mechanik und simuliert den Abkühlungsprozess, mit dem, wenn er entsprechend langsam vollzogen wird ¹⁸ , der energetische Grundzustand einer kristallinen Flüssigkeit ermittelt werden kann. Der Kontrollparameter , 0, 1, 2, 3, 4, … , ,, des n-ten Durchlaufs ist der Temperatur des physikalischen Verfahrens nachempfunden und wird im Laufe des Suchprozesses gegen einen minimalen Wert 0 abgesenkt. Unter Anwendung des Verfahrens

ein Nachbarschaftszustand aus der Menge an Nachbarschaftszuständen einer aktuellen Lösung ausgewählt. Dieser wird unter

Berücksichtigung der Metropolis Kriterien ²¹ als neue Lösung mit einer

Und damit auch, wenn er einen höheren Kostenwert fjj

¹⁷ Vgl. van Laarhoven, P.J.M. (1988), S. 7.

¹⁸ So langsam, dass die Flüssigkeit vor einem jeden weiteren Absenken der Temperatur

den Energetischen Gleichgewichtszustand erreicht. Dieser ist charakterisiert durch die

Bolzmannverteilung der Form

die Wahrscheinlichkeit wieder, dass die Flüssigkeit den energetischen Zustand mit der

Energie bei der Temperatur erreicht. Dabei ist die aus der Physik bekannte

Boltzmannkostante (Vgl. Arts, E. et al. (1989), Simulated Annealing and Boltzmann

Machines, Chichester, S. 14).

¹⁹ Vgl. Arts, E. et al. (1989), S. 14.

²⁰ Vgl. Sechen, C. (1988), S.38

²¹ Vgl. Arts, E. et al. (1989), S. 14.

²² Vgl. Arts, E. et al. (1989), S. 35.

- 35 -

einnimmt. ²³ Dadurch kann der Prozess auf der Suche nach dem globalen Minimum aus einem vermeintlichen lokalen Optimum wieder nach oben klettern. 24

Für eine Vielzahl von Anwendungen hat sich der Simulated Annealing Algorithmus bereits als erfolgreiches Näherungsverfahren bewiesen. ²⁵ Wird der Kontrollparameter , , 1, 2, … , nach einer noch zu bestimmenden Regel im Laufe des Suchprozess abgesenkt kann der Prozess als eine einfache homogene oder inhomogene Markov-Kette modelliert werden. ²⁶ Eine Markov Kette ist homogen, wenn die Übergangsmatrix nicht von der Durchlaufnummer abhängt. Sie ist inhomogen, wenn diese Abhängigkeit besteht. ²⁷ Diese Übergangsmatrix der Form.

gibt die Wahrscheinlichkeit an, von einem Zustand zu einem Zustand zu gelangen und weiter von einem Zustand zu einem Zustand , etc. ²⁹ Die Theorie der Markov-Kette besagt folgendes: Gibt es ein , so, dass gilt 0 für alle , , , 1,2,3 … , ,, dann besitzt die Matrix P eine eindeutige Grenzverteilung . Wenn nun gegen unendlich strebt gilt ³⁰ . Die Lösung eines Durchlaufs ist beim Simulated Annealing

Algorithmus also nur abhängig von der Lösung des vorherigen Durchlaufs

1. ³¹ und ³² für alle , .

²³ Vgl. Arts, E. et al. (1989), S. 15.

²⁴ Vgl. Kolonko, M. et al. (1996) Convergence of Simulated Annealing with Feedback

temperature Schedules, Hildesheim, S. 2.

²⁵ Vgl. Arts, E. et al. (1989), S. 89.

²⁶ Vgl. Kolonko, M. (1996), A Semi-Inhomogeneous Markov Model for Simulated

Annealing, Hildesheim, S. 2.

²⁷ vgl. Arts, E. et al. (1989), S. 34.

²⁸ Vgl. van Laarhoven, P.J.M. (1988), S. 21.

²⁹ Vgl. Diaconis, P. (2009), The Marcov Chain Monte Carlo Revolution, S. 182, in

American Mathematical Society [Hrsg.] (2009), Bulletin of the American Mathematical

Society, Volume 24, No.2, USA (S. 179-206).

³⁰ Vgl. Arts, E. et al. (1989), S. 47.

³¹ Vgl. Arts, E. et al. (1989), S. 34.

³² Vgl. Arts, E. et al. (1989), S. 38.

³³ Vgl. Arts, E. et al. (1989), S. 40.

- 36 -

lim

Wird immer weiter abgesenkt, so nähert sich die Lösung einem globalen Optimum. Damit sind zwei Punkte zu klären.

a. Die genaue Ausgestaltung der Erzeugungswahrscheinlichkeit, explizit der Verteilung .

b. Die genaue Ausgestaltung der Kühlfunktion, die das Absenken des Kontrollparameters unter Einhaltung der Bedingungen für die Existenz einer stationären Verteilung bestimmt Die Modellierung einer inhomogenen Markov-Kette ³⁵ soll kurz beschrieben werden. Der Kontrollparameter wird anders als bei einer homogenen Makov-Kette für eine ausreichend große Anzahl an Iterationen auf demselben Niveau festgehalten. So lange, bis sich die Grenzverteilung eingestellt hat. Dann wird der Parameter in einem größerem Schritt

abgesenkt und der Vorgang wiederholt. Dieses Variante hat erhebliche Vorteile gegenüber einer homogenen Kühlfunktion ³⁶ . In Kapitel 5.3.1. wird dies einmal exemplarisch gezeigt.

Von besonderem Interesse ist die Frage, wie lang eine Markov-Kette sein muss, um einer Quasi-Grenzverteilung ³⁷ zu entsprechen. Es sei die Länge der n-ten Markov-Kette, und der dazu gehörige Wert des Kontrollparameters. Wie groß muss also sein, so dass gilt: | | ? ³⁸ ||

Diese Bedingung konnte bisher nur für wenige Anwendungen beantwortet werden. ³⁹ In der Literatur finden sich einige unterschiedliche

Seien A uns A´ A zwei Mengen. Dann ist die Ausprägung ^χ ´ :A ^0,1der Menge 34

A´definiert als ^χ ´ a 1, wenn a a A´, und ^χ ´ a 0 sonst (vgl. Arts, E. et al. (1989), S. 19).

³⁵ Vgl. Arts, E. et al. (1989), S. 43.

³⁶ Vgl. Sechen, C. (1988), oder: van Laarhoven, P.J.M. (1988), S. 41.

³⁷ Vgl. Sechen, C. (1988), oder: van Laarhoven, P.J.M. (1988), S. 40.

³⁸ Vgl. Diaconis, P. (2009), S. 183.

- 37 -

Herangehensweisen der Bestimmung von ⁴⁰ , oder wurden zumindest kommentiert ⁴¹ . Auf einen Zusammenhang zwischen dem Kontrollparameter und der Länge der Markov-Kette wird in Kapitel 5.3.2. eingegangen. Eine einfache Berechnung der Länge wird in Kapitel 5.3.1. vorgestellt.

5.2. Problemabhängige Parameter

5.2.1. Generierung der Nachbarschaft

Der Zustand einer Allokation wird in einem String bestehend aus Nullen und Einsen abgebildet. Die Variablen und sind exogen. Die

errechenbar und somit endogen. Werden die Zustände aller möglichen Variablen und ebenso aller möglichen Variablen durch eine

Stelle in dem String dargestellt, so ist die aktuelle Lösung eindeutig definiert. Der Zustand der exogenen Variablen ist gleich 0 oder 1. Findet eine Bewegung, eine Versetzung, wiedergegeben durch den

dargestellt wird statt, so ist der Wert der entsprechenden Stelle im String 1. Ansonsten ist er 0. Die Generierung der Nachbarschaft findet dadurch statt, dass zufällig der Wert einer Stelle im String geändert wird. Von 0 auf 1, oder von 1 auf 0. Der String besteht bei 15 Standorten, 26 Planperioden 2 unterschiedliche Qualifizierungsgrade der Piloten und einer Wartelistenrangtiefe von Ρ Ρ 30 aus || || Τ || Ρ 351.000 Elementen für die Transfers und noch einmal || Τ tu || Ρ 18.900 Elemente für die Upgrades.

Nicht alle Variationen des Strings sind jedoch zulässig, da eine Rangordnung eingehalten werden muss und jeder angefragte Wechsel nur maximal ein Mal in der gesamten Periode vollzogen wird. In der Literatur wird auf die Möglichkeit hingewiesen auch nicht erlaubte Zustände zunächst zuzulassen ⁴² . Durch den Einsatz von Strafparameter werden nicht

³⁹ Vgl. Diaconis, P. (2009), S. 183.

⁴⁰ Vgl. Dige, P. et al. (1993), Timetable by Simulated Annealing, S. 162, in Applied

Simulated Annealing, Vidal, R. [Hrsg.] (1993), Heidelberg (S.151-174), oder: Arts, E.

et al. (1989), S. 65.

⁴¹ Vgl. Sechen, C. (1988), S. 43, oder: van Laarhoven, P.J.M. (1988), S. 32.

⁴² Vgl. Arts, E. et al. (1989), S. 153.

- 38 -

erlaubte Zustände in der Lösung verhindert. Aufgrund der Strafkosten ergibt sich ein hoher positiver Kostenunterschied [ 0]. Mit absenken

und einhergehender abnehmender des Kontrollparameters

Akzeptanzwahrscheinlichkeit wird ein nicht erlaubter Zustand mit einer immer geringeren Wahrscheinlichkeit aufgesucht. Der Algorithmus bewegt sich aus diesen kostenintensiven Zuständen heraus. Eine große durchschnittliche Kostendifferenz verlängert allerdings die Laufzeit des Algorithmus (siehe Kapitel 5.3.1.). Es werden viele Zustände bewertet, die gar nicht zulässig sind. Es ist daher gegebenenfalls von Vorteil, die genannten Restriktionen bereits bei der Nachbarschaftswahl zu berücksichtigen. Dass auch dann die Übergangswahrscheinlichkeiten

strebt, soll an einem kleinen Beispiel gezeigt werden. Es sei ein String mit 4 Elementen gegeben, die alle den Wert 0 oder 1 annehmen können. Damit sind unter der Berücksichtigung der Rangordnung || 5 Zustände möglich: 1: 0000, 2: 1000, 3: 1100, 4: 1110, 5: 1111.

Unter Berücksichtigung der Rangordnung existieren folgende Nachbarschaftsmengen : 1 1000, 2 0000, 1100, 3 1000, 1110, 4 1100,1111, 5 1110.

Die Kostenwerte für die Zustände seien wie folgt: 1 0; 2 1, 3 3, 4 4, 5 5.

- 39 -

Der Wert des Kontrollparameters wird mit 1 angenommen. Damit gilt für die Akzeptanzwahrscheinlichkeit entsprechend der Zustandsvariationen:

. 1, 1. 0,368, 1

1: für

Bereits für 16 strebt die Eintrittswahrscheinlichkeit für das Erreichen bis auf eine Abweichung von 1/1000 gegen die eines Zustandes 0,471; 0,346; 0,127; 0,047; 0,009. Grenzverteilung Die

Wahrscheinlichkeit den Zustand zu erreichen ist immer gleich, ganz gleich welcher Ausgangszustand gewählt wurde. Es kann gezeigt werden, dass dies für alle gilt. Es gilt für alle , 2.

Werden nicht erlaubte Zustände bei der Suche ausgeschlossen ergibt sich folgendes Bild:

Existiert eine Anfrage auf eine Versetzung vom Standort A zum Standort B und hat diese Anfrage den Rang , so kann es keine weitere Anfrage mit gleichem Rang geben, um von Standort A zu einem anderen Standort zu , so gilt: wechseln. Besteht also eine Anfrage 1, ü 0, üü

und da die Anfrage frühestens zum angefragten Zeitpunkt durchgeführt werden kann ist

Diese Tatsache wird bereits in der Aufstellung der Eingabedaten für die Anfragen berücksichtigt.

In Verbindung mit Restriktion (11) gilt dann: 0, ü \, , und

- 40 -

Mit 0 gilt im Einklang mit der Rangfolge Restriktion (9) 0, ü , 1,2,3, … , . Ist 1, dann ist laut Restriktion (10) : 0, ü

und laut Restriktion (9) ist genau ein 1.

Die Anzahl an möglichen Zustandsvariationen im Bereich der Transfers reduziert sich damit auf eine je Standort und Planperiode . Analog gilt für die Upgrades: gibt es eine Upgrade-Anfrage , so ist 1, ü 0, üü

Auch diese Regel wird bereits bei der Aufstellung der Eingabewerte der Beförderungsoptionen berücksichtigt. In Verbindung mit Restriktion

(8) folgt: 0, üü

Ist 1, dann ist laut Restriktion (7) :

und laut Restriktion (5) genau ein

1.

Ist 0, dann ist laut Restriktion (5) :

Die Anzahl an Variationsmöglichkeiten des Ausgangszustandes im Bereich der Upgrades eines Ersten Offiziers reduziert sich auf eine je Planperiode .

Für die Verteilung des nun zum Kapitän ausgebildeten Piloten ergibt sich ein ähnliches Bild. Für diese Bewegung gibt es allerdings keine Einschränkung bei der Auswahl eines bestimmten Standortes. Bei Berücksichtigung dieser Restriktionen wird die Anzahl der möglichen Nachbarschaftszustände eines Ausgangszustandes reduziert auf maximal ||| ||| Τ ||| Τ 1116.

In der Abbildung 2 werden 3 Nachbarschaftsgenerierungsstrategien miteinander verglichen. Bei der Strategie 2_6 werden keinerlei Einschränkungen bei der Nachbarschaftssuche gemacht und alle nicht

- 41 -

erlaubten Zustände zunächst zugelassen. Diese Strategie arbeitet also mit vielen Strafparametern. In der Strategie 2_5_2 wurden alle wie oben genannten nicht erlaubten Zustände von vorne herein ausgeschlossen. Die Darstellung eines kompletten Upgrades bedarf indes zwei Permutationen. Zum einen um einen Ersten Offizier zum Upgrade zu schicken, zum anderen um ihn dann als Kapitän wieder einer Basis zu zuordnen. Um zu garantieren, dass alle Ersten Offiziere, die ein Update Training absolviert haben gemäß Restriktion (4) auch einem Standort als Kapitän zugeordnet bekommen und keiner auf dem Upgrade-Standort (s. Abbildung 1) verbleibt, wird daher ein Strafparameter notwendig. In der Strategie 2_5_3 wird zunächst ein kompletter Upgrade durch zufällige Wahl der Indizes , , , ausgewählt. Die Variable , , 0 wird durch die Indizes i, t und bestimmt und die zusammenhängende Variable , , 1 durch die Indizes , , beschrieben. Die

Variationsmöglichkeiten eines vorgegebenen Zustandes reduzieren sich im Bereich der Upgrades um auf ||.

Für die Testläufe wurde ein kleines Modell aus ||| 3 Standorten, 3 Planperioden, einer Wartelistenrangtiefe von Ρ Ρ 3 , sowie einer

Trainingszeit für das Upgrade von 2 angenommen. Dieses Modell wird weiter als Modell II bezeichnet. Alle drei Strategien wurden 250-mal durchgeführt. In der folgenden Grafik werden die Ergebnisse, der Größe nach geordneten, gegenüber gestellt. Für diesen Strategie-Vergleich wurde das inhomogene Marcov Modell benutzt. Die notwendigen Parameter des Simulated Annealing Algorithmus wurden gemäß der im Kapitel 5.3.1 vorgestellten Formeln errechnet und angewendet.

Abbildung 2: Strategievergleich der Nachbarschaftsgenerierung

Die Strategie 2_5_3 liefert die besten Ergebnisse. Sie hat auch einen weiteren entschiedenen Vorteil. Die Anzahl an Iterationen ist hier am geringsten.

Daher wird die Strategie 2_5_3 im Folgenden benutzt und weiterentwickelt.

5.2.2. Kostenfunktion

Da keinerlei Strafparameter zur Vermeidung von unerlaubten Zuständen gebraucht wurden, ändert sich die Kostenfunktion gegenüber der im mathematischen Ansatz formulierten nicht. Die Ermittlung der Variablen und ergibt sich aus den Restriktionen (2) und (3). Es existiert

folgender Zusammenhang:

für 0 (Erste Offiziere)

für 1 (Kapitäne)

wenn n 0 gilt:

n a und n 0

und

Damit wird in einer fortlaufender Schleife für =1, 2, …, T der Gesamtpersonalstamm berechnet und bewertet. Die Neueinstellungen der Kapitäne und die der Ersten Offiziere werden mit den zugehörigen Kosten

- 43 -

multipliziert. Für einen Standortwechsel wird ein Bonus berechnet und jede Bewegung eines Piloten über die einzelnen Planperioden mit den Personalkosten pro Periode 1 berechnet.

5.3. Problemunabhängige Parameter 5.3.1. Einfache Kühlfunktionen

Die Kühlfunktion berechnet den Verlauf des Kontrollparameters . Dazu gehört

• eine Funktion zur Reduzierung des Wertes des Kontrollparamaters c

• ein Endwert des Kontrollparameters, der zum Abbruch des Algorithmus führt. 43

Sowie eine endliche Anzahl von Übergängen bei jedem Wert des Kontrollparameters . 44

Der Anfangswert des Kontrollparameters ist so zu wählen, dass alle

Χ mittels der durchschnittlichen Kostenzunahme Δf folgender Ausgangswert c :

⁴⁵ .

Die durchschnittliche Kostenzunahme von 25.000 zufälligen Iterationen beträgt Δf 2,3388 . Bei einer Anfangsakzeptanz von 0,925 ist der Ausgangswert des Kontrollparameters c somit c 30. Eine einfache inhomogene exponentielle Kühlfunktion lautet z.B.: , 1,2, … , , 1.

Normalerweise wird ein zwischen 0,8 und 0,99 gewählt. ⁴⁶ Tests ergaben, dass die Güte der Lösungswerte mit abnehmendem erheblich abnimmt. Daher wird bei allen homogenen Makov-Kühlfunktionen aufgrund der

⁴³ Vgl. van Laarhoven, P.J.M. (1988), S. 30.

⁴⁴ Eine endliche Länge einer jeden homogenen Markov Kette (Vgl. Arts, E. et al. (1989),

S. 57).

⁴⁵ Vgl. van Laarhoven, P.J.M. (1988), S. 32.

⁴⁶ Vgl. Arts, E. et al. (1989), S. 59.

- 44 -

hohen Kostenrelevanz für das Unternehmen 0,99 gewählt. Auch wenn dies bedeutet, dass der Algorithmus wesentlich mehr Permutationen durchläuft als bei einem kleinerem .

Der Wert , an dem der Logarithmus abbricht, sollte so klein sein, dass die Wahrscheinlichkeit einen schlechteren Zustand anzunehmen nahezu 0 ist.

Bei der Ermittlung eines geeigneten Endwertes wird auf die oben

Endakzeptanz Χ 0,005 ergibt sich dann der Wert für c 0,4414.

Die Temperatur wird also in

Algorithmus abbricht.

Die Länge der n-ten Markov-Kette ist gleich der Größe der Anzahl der Nachbarschaftslösungen, so ergibt sich folgendes: werden alle Nachbarschafszustände akzeptiert, dann liegt der Anteil der

aufeinander folgenden Morkov-Ketten ist dieser Anteil gleich 1. Das hieße, dass alle Nachbarschaftszustände untersucht worden wären. ⁴⁷ Damit ist gewährleistet, dass die eindeutige Grenzverteilung erreicht wird. Die Anzahl der Iterationen ist .

Die Parameterwerte für c und C wurden nun variiert. Daraus ergeben

sich unterschiedliche Kühlfunktionen.

Die Abbildung 3 stellt die Ergebnisse der Berechnungen dar. Die Lösungswerte für jeweils 250 Versuche sind der Größe nach geordnet miteinander verglichen worden. Der optimale Wert liegt bei 453,17 und wurde in allen Versuchen mehrmals erreicht. Für alle Kühlfunktion wurden die entsprechenden Parameter in einer Tabelle angegeben.

⁴⁷ Vgl. Arts, E. et al. (1989), S. 65

- 45 -

Abbildung 3: Ergebnisse lineare Kühlfunktion

Tabelle 3: Parameter lineare Kühlfunktion

- 46 -

Parallel wurde der Algorithmus mit einer homogenen Kühlfunktion gelöst. Anstatt den Kontrollparameter für eine Anzahl von Iterationen auf dem gleichen Niveau festzuhalten und dann in einem größeren Schritt zu reduzieren, wird die Temperatur, respektive der Kontrollparameter, sehr

Da sich der homogene Algorithmus nur sehr langsam dem Abbruchkriterium nähert, ist der Wert für schwierig zu bestimmen. Der Algorithmus wurde auf 500.000 Iterationen begrenzt. Bei einer

log 2,207.

Die ersten 4 Versionen wurde zum besseren Vergleich mit einer angepassten Kühlfunktion (s. Kapitel 5.3.2.) auf über 15. 000 Iterationen festgelegt. Dazu wurde die Länge der Markov-Kette von 21 auf 42 verdoppelt. Der Algorithmus mit den Werten 30 und 0,4414 (Kurve 2) wie im vornherein bestimmt liefert 1 mal die optimale Verteilung mit einem Kostenwert 453,17. Der Mittelwert der Ergebnisse aller 250 Durchläufe beläuft sich auf 455,87. Dieser Wert kann durch Absenken des Wertes und korrelierend damit des Wertes verbessert werden. Die Version mit 0,2539 (Kurve 3) liefert 4 Mal den Optimalkostenwert 453,17. Der Algorithmus der Kurve 4 ebenfalls 4 mal. Der Mittelwert aller Ergebnisse für die Kosten konnte auf 455,37 gesenkt werden. Die Ergebnisse der Version 3 und 4 sind bei einem Konfidenzintervall von 0,05 signifikant besser als die der Version 2. Die Erhöhung des Wertes auf 60 und entsprechend des Wertes _ 0,9080 ergab keine Verbesserung.

Mithin konnte gezeigt werden, dass das Optimum von 453,17 im Laufe der Suche öfter gefunden wurde, jedoch nicht immer auch als Endergebnis ausgeworfen wurde.

Die homogene Kühlfunktion (Kurve 5) ist nicht geeignet. Zwar werden 500.000 Iterationen durchgeführt, der Ausgangswert ist jedoch so klein, das der Algorithmus regelmäßig in einem lokalen Optimum stecken bleibt.

- 47 -

5.3.2. Angepasste Kühlfunktionen

In der Literatur finden sich zahlreiche Vorschläge für eine angepasste Kühlfunktion ⁴⁸ . Oft wird der Vorteil eines angepassten Algorithmus damit bewiesen, dass weit weniger Iterationen benötigt werden bis optimale Lösung gefunden wurde, als mit der einer einfachen Kühlfunktion. Diese Vorgehensweise ist jedoch nur möglich wenn der optimale Lösungswert im vornherein bekannt ist und der Algorithmus nach dem Erreichen dieses Wertes abbricht. Der Lösungswert ist von vorneherein bekannt, wenn lediglich ein Satisfizierungsziel ⁴⁹ verfolgt wird. Also eine Lösung zu festgelegten Parameterwerten gesucht wird ⁵⁰ , oder Standardprobleme mit bereits bekannten optimalen Lösungswerten mit einer angepassten Kühlfunktion berechnet werden ⁵¹ . Beides liegt nicht vor. Im Kapitel 5.3.1 konnte gezeigt werden, dass der Algorithmus bei dem vorliegenden Problem insbesondere bei Durchlaufen von sehr kleinen Werten des Kontrollparameters bei gleich hoher Anzahl an Iterationen gute Werte liefert (siehe Kurve 3 und 4). Eine Aussage in Diege et. al (1996) wird daher auf der Suche nach einer verbesserten Kühlfunktion näher untersucht. „Moreover, if it takes a certain number of iterations to reach equilibrium after a temperature decrease, and if this number depends on the energy decrease then for a given temperature decrease more iterations are needed in the range 0,2 1,0 than anywhere else.” 52

Der gleichgewichtige Kostenzustand bei Erreichen einer Grenzverteilung wurde bei einer Reihe fester Kontrollparameter als Mittelwert über die letzten 500.000 von insgesamt 1.000.000 durchgeführten Iterationen ermittelt. Dieser Kostenzustand wurde in der Abbildung 4

dem Wert des Kontrollparameters gegenübergestellt.

⁴⁸ Vgl. Dige, P. et al. (1993), S. 165, und Kolonko, M. et al (1996).

⁴⁹ Vgl. Zelewski, S. et al. (2008), Produktionsplanungs- und Steuerungssysteme,

München, S. 288.

⁵⁰ Vgl. Dige, P. et al. (1993), S. 156.

⁵¹ Vgl. Kolonko, M. et al. (1996), S. 11.

⁵² Vgl. Dige, P. et al. (1993), S. 166.

- 48 -

Abbildung 4: Zusammenhang zwischen Kosten und Kontrollparameter

asymptotisch gegen einen Wert von 470. Der gleichgewichtige Kostenzustand sinkt leicht in Form einer Hyperbel, aber nahezu linear

bei abnehmenden Temperaturwerten (abnehmenden Werten des Kontrollparameters 1 ). Ab einem Wertebereich für den

Kontrollparameter 1 treten große Schwankungen auf. In Abbildung 5 wurde die Anzahl der Iterationen pro Differenz zum vorherigen Energie-Gleichgewichtszustand, hier dem gleichgewichtigen Kostenzustand , dem Wert des Kontrollparameters gegenübergestellt. Der Graph verläuft für Werte 10 linear steigend. Die Anzahl an Iterationen pro abgesenkten gleichgewichtigen Kostenzustand schwankt bei den untersuchten Kontrollparameterwerten 10. Diese Schwankungen werden in dem Bereich 2 erheblich größer. Die Anzahl der Iterationen sinkt teilweise unter den Wert von 10. Nach von Dige et. al (1993) ⁵³ und den im vorherigen Kapitel gemachten Beobachtungen wird die Anzahl der Iterationen , die durchlaufen werden, bevor der Kontrollparameter ein weiteres Mal abgesenkt wird nun

⁵³ Vgl. Dige, P. et al. (1993), S. 166

- 49 -

Abbildung 5: Zusammenhang zwischen Iterationen pro Einheiten der Differenz zum vorherigen gleichgewichtige Kostenzustand und dem

Kontrollparameter

Obwohl weniger Iterationen durchgeführt werden, übertreffen die Ergebnisse die der linearen Kühlfunktion. Der optimale Zustand mit einem Kostenwert von 453,17 wurde 3 mal als Ergebnis ermittelt. Der Mittelwert ist mit 455,20 niedriger. Bei einem Konfidenzintervall von 5% sind die Resultate der angepassten Kühlfunktion signifikant besser als die mit einer linearen Kühlfunktion. Der maximale Kostenwert liegt bei 458,83 Einheiten und weicht um 1,2% vom optimalen Wert ab. Alternativ

abgebildet. Eine signifikante Verbesserung konnte dabei nicht

erreicht werden. Es ist aber anzunehmen, dass eine verbesserte Lösung durch eine Erhöhung der Iterationen erreicht werden kann. Dabei sollte die Länge der Marcov-Kette in der Form einer Hyperbel in Abhängigkeit

weiter abgesenkt werden.

- 50 -

Die Ergebnisse sind in der Abbildung 6 dargestellt. Die Parameterwerte werden daneben in Tabelle 4 aufgeführt.

Abbildung 6: Ergebnisse mit angepasster Kühlfunktion

Tabelle 4: Parameter der angepassten Kühlfunktion

5.4. Resultate und Analyse

Das Resultat auf Basis der Inputwerte des Modells I (s. Kapitel 4.) ist nachfolgend dargestellt. Die optimale Verteilung wurde nicht erreicht. Im Vergleich zu Modell II liegt der Mittelwert bei 435,59 und die

Abbildung 7: Ergebnisse reduziertes Modell I

Tabelle 5: Parameter reduziertes Modell I

Der maximale Kostenwert weicht um 0,2% vom Optimalen Wert ab. Das Ergebnis ist im Mittel um 49 Kosteneinheiten besser als eine Situation ohne Versetzungen und Beförderungen. Selbst der schlechteste ermittelte Lösungswert ist um 32 Einheiten besser. Im Mittel wurden 5400,1 Steps, 21,5 Versetzungen und 5,3 Beförderungen durchgeführt, sowie 13,0 Erste Offiziere und 5,3 Kapitäne eingestellt. Ein Hinweis auf die reale Kosteneinsparung ergibt sich aus der Anzahl der berechneten Wochenplanstellen. Dieser Wert liegt im Mittel bei 5444,8 Planstellen, gegenüber 5467 Planstellen ohne Optimierungsoptionen. Schlechtesten falls wurden durch das Verbesserungsverfahren 5449 Planstellen vorgehalten. Durch den Einsatz des Simulated Annealing Algorithmus wurde ein deutliches Einsparungspotential realisiert.

Die Durchschnittliche Rechenzeit beträgt 20,84 Minuten. Das ist etwa 373 mal so viel wie bei der Berechnung des kleineren Modells (Modell II) in den vorangegangenen Kapiteln. Der Simulated Annealing Algorithmus benötigt damit etwa 22,20 Millisekunden pro Iteration. Dieses Verhältnis lag bei den vorangegangenen Modell-Berechnungen bei 0,21 Millisekunden pro Iteration. Die Rechenzeit pro Iteration ist also um das 105-fache gestiegen. Die Rechenzeit kann durch folgende Problemunabhängige Maßnahmen noch reduziert werden:

• Die Kosten einer neuen Iteration werden dadurch ermittelt, dass zu den Kosten der letzten Iteration nur der Unterschiedsbetrag der von der neuen Iteration verursachten Kosten addiert wird.

• Die Werte des Kontrollparameters, der Akzeptanzwahrscheinlichkeit und der Anzahl der Iterationen bevor der Kontrollparameter ein weiteres Mal abgesenkt wird, werden aus einer Tabelle abgelesen. ⁵⁴ Zu berücksichtigen ist jedoch, dass bei jeder Iteration die Anzahl der Neueinstellungen und Steps für jede Planperiode neu berechnet werden müssen. Das ergibt bei einer Optimierung über 5 Planperioden und 6 Standorten bereits 120 Rechnungen pro Iteration. Dieser Wert steigt exponentiell bei Erhöhung der Eingabedaten. Problemabhängige Maßnahmen zur Reduzierung des Rechenaufwandes sind:

⁵⁴ Vgl. Dige, P. et al. (1993), S. 172.

- 53 -

• Anpassung der Indexe , an die tatsächliche Länge der Transfer-Wartelisten auf den einzelnen Standorten.

• Einführen eines Indexes für die Upgrade-Warteliste der Anwärter auf eine Beförderung.

Der Simulated Annealing Algorithmus ist indes einfach zu programmieren und daher kostengünstig zu implementieren.

6. Zusammenfassung

Die vorliegende Arbeit des Base Transfer Problems greift die Problematik der Fluglinie Easyjet Airline Company plc auf. Erste Teilaufgabe des Problems ist es, die für das Unternehmen optimale Mitarbeiterallokation zu finden. Daneben ist eine Beförderung (Upgrade) kostenoptimal durchzuführen. Das Ziel der Optimierung besteht darin, die gesamten Personalkosten des Unternehmens möglichst gering zu halten. Als allgemeines Transportproblem formuliert wird von einer bestimmten Anzahl von Produktionsstandorten über eine Vielzahl von Zwischenlagern eine ebenso große Anzahl an Vertriebsstandorten beliefert. Das Problem ist in seiner Struktur als Transportproblem in einem Netzwerk darstellbar. Daraus wird eine plausible mathematische Darstellung abgeleitet. Harte Restriktionen geben die institutionellen Grenzen wieder, weiche Restriktionen dagegen können durch einen Strafpreis umgangen werden und bedingen daher der Verwendung eines Strafparameters. Durch die Rangordnungsregel bei der Auswahl der Versetzungen und Beförderungen wird das Problem sehr groß.

Die mathematische Darstellung ist Grundlage der linearen Programmierung und des Programmieren des Simulated Annealing Algorithmus. Für eine Modellrechnung der linearen Programmierung in Lingo wurde das Problem stark gekürzt.

Nach Berechnung der optimalen Verteilung konnten 26 der 27 Versetzungsanfragen stattgegeben werden. Eine Ersparnis von 19 Wochengehältern werden durch die optimale Berechnung der Versetzungs-und Upgrade -Optionen gegenüber der Null-Optionen Lösung eingespart werden.

- 54 -

Der Simulated Annealing Algorithmus ist ein stochastisches Nachbarschaftssuchverfahren zur Lösung von Optimierungsproblemen kombinatorischer Art.

Die Strategie, in der alle Restriktionen bereits bei der Auswahl der Nachbarschaftszustände berücksichtigt werden liefert die besten Ergebnisse. Durch Absenken der Werte für lassen sich die Ergebnisse noch

verbessern. Die angepasste Kühlfunktion berücksichtigt diese Beobachtung, in dem die Anzahl der Iterationen, die durchgeführt werden, bevor der Kontrollparameter ein weiteres Mal abgesenkt wird in Form einer Hyperbel angepasst wird. Das Ergebnis übertrifft das einer linearen Kühlfunktion.

Durch den Einsatz des Simulated Annealing Algorithmus wurde ein deutliches Einsparungspotential realisiert. Im Mittel wurden 26,2 Planstellenweniger benötigt, als ohne Optimierungsoptionen. Ein linearer Zusammenhang zwischen Anzahl der Variablen und der Rechenzeit konnte bei der Anwendung auf das Base Transfer Problem nicht nachgewiesen werden.

Der Annealing Algorithmus ist durch seine einfache Handhabbarkeit einfach zu implementieren. Durch den Umfang des Base Transfer Problems ist jedoch die Anwendbarkeit des Algorithmus in Frage gestellt.

- 55 -

7. Anhang

Lingo Solver Status Modell I:

Lingo 11.0 Solver Status Modell II:

8. Literaturverzeichnis

Ambrosy, R. (1982), Personaleinsatzplanung bei variabler Organisationsstruktur, Bochum.

Arts, E. et al. (1989), Simulated Annealing and Boltzmann Machines, Chichester.

Diaconis, P. (2009), The Marcov Chain Monte Carlo Revolution in Bulletin of the American Mathematical Society, American Mathematical Society [Hrsg.] (2009), Volume 24, No.2, USA, S. 179-206.

Dige, P. et al. (1993), Timetable by Simulated Annealing, S. 162, in Applied Simulated Annealing, Vidal, R. [Hrsg.] (1993), Heidelberg S.151-174. Glaser, H. et al. (1998), Retrograde Terminierung mit Personalzuordnung, Saarbrücken.

Holländer, M., et al. (1977), Function Decreasing in Transposition and their Application in Ranking Problems in The Annals of Statistics, Institute of Mathematical Statistics (IMS) [Hrsg.] (1977), Vol. 5, No. 4, Beachwood, S. 722-733.

Kallrath, J. (2002), Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis, Wiesbaden.

Kistner K.-P. et al. (2001) Produktionsplanung, Heidelberg Klose, A, Lidtke, T. (2005), Lagrange-Ansätze zur Lösung des Transportproblems mit Fixkosten in Supply Chain Management und Logistik, Günter, H-O, et al [Hrsg.] (2005), Heidelberg, S. 507-530. Kolonko, M. (1996), A Semi-Inhomogeneous Markov Model for Simulated Annealing, Hildesheim.

Kolonko, M. et al. (1996) Convergence of Simulated Annealing with Feedback temperature Schedules, Hildesheim. Laarhoven, P.J.M. (1988), Theoretical and Computational Aspect of Simulated Annealing, Amsterdam.

Sechen, C. (1988), VLSI Placement and Global Routing Using Simulated Annealing, Boston.

Zelewski, S. et al. (2008), Produktionsplanungs- und Steuerungssysteme, München.

- 58 -