Endterm SS21

Beispiel 1 (9 Punkte)

A (2 Punkte) Erläutern Sie, ob die folgenden Aussagen stimmen oder nicht?

1. Das Vehicle Routing Problem ist eine spezielle Form des Traveling Salesman Problems
Erläuterung:

2. Wir nutzen Heuristische Verfahren, wenn sich die betrachteten Probleme nicht exakt formulieren lassen
Erläuterung:

3. Verbesserungsverfahren dienen dazu die optimale Lösung für ein bestimmtes Problem zu finden
Erläuterung:

4. Ein ungerichteter Graph ist immer ein symmetrischer Graph

Erläuterung:

B (3 Punkte) Beschreiben Sie die Bestandteile der Subtour Elimination mit eigenen Worten und erklären Sie die generelle
Funktionsweise ggf. mittels eines kleinen Beispiels.

∑ 𝑥𝑖,𝑗 ≤ |𝑆| − 1 ∀𝑆 ⊂ 𝑉, 𝑆 ≠ ∅
𝑖,𝑗∈𝑆

Bestandteil Erklärung
1
2
3
4
5
6

C (2 Punkte) Ihre Eltern möchten Sie am Wochenende in Wien besuchen und planen einen Tag zum Sightseeing. Ihre Eltern
wissen ganz genau was sie besichtigen wollen, kennen jedoch nicht die örtlichen Verkehrsmittel und Reisezeiten. Sie
wohnen an der Rosauer Lände und haben die Reisezeiten zwischen allen Sehenswürdigkeiten ermittelt.
Finden Sie eine Lösung mittels des Nearest Neighbor Verfahrens, um alle Sehenswürdigkeiten ausgehend von ihrer
Wohnung in einer einzigen Rundreise zu besichtigen.
Geben Sie die Rundreise an, tragen Sie die Rundreise im gegebenen Graphen ein indem Sie die Knoten mit den Pfeilen
verbinden und berechnen Sie die benötigte Reisedauer.

Rosauer Lände (R) Donauturm (D) Prater (P) Stephansdom (S) Belvedere (B)
Rosauer Lände (R) 0 35 22 14 28
Donauturm (D) 35 0 23 30 40
Prater (P) 22 23 0 10 24
Stephansdom (S) 14 30 10 0 17
Belvedere (B) 28 42 24 17 0

Route:

Bildliche Darstellung:

Dauer der Rundreise:

D (1 Punkt) Schreiben Sie 4 der 6 möglichen Nachbarschaftslösungen für die obige Lösung aus Aufgabe 3C auf, welche
mittels dem aus der Vorlesung bekannten 2-opt Verfahren (Tausch zweier Kantan) möglich sind.

Start Knoten 1 Knoten 2 Knoten 3 Knoten 4 Ziel

Ausgangslösung

Nachbarschaftslösungen

E (1 Punkt) Finden Sie eine Verbesserung durch einmaligen Tausch zweier Kanten, ausgehend von der Lösung in Aufgabe 3C
(kein Rechenweg nötig und Nachbarschaftslösungen wie in Aufgabe 3C). Schreiben Sie die Route der neunen Lösung,
vervollständigen Sie den Graphen und ergänzen Sie die neue Reisezeit.

Route:

Bildliche Darstellung:

Dauer der Rundreise:

Beispiel 2 (10 Punkte)

A (2 Punkte) Erläutern Sie, ob die folgenden Aussagen stimmen oder nicht?

1. Aus einem Netzplan lässt sich der kritische Pfad eines kostenminimalen Projektplans direkt ablesen
Erläuterung:

2. Crashkosten entsprechen in den meisten Fällen den Beschleunigungskosten.

Erläuterung:

3. Wenn Vorgang B der Nachfolger von C und D und Vorgang A der Nachfolger von B und C ist, dann kann D nach A
fertig gestellt werden
Erläuterung:

4. Durch das Lösen eines LP-Modells lassen sich Projektpläne mit Beschleunigungspotentialen exakt lösen
Erläuterung:

B (1 Punkt) Wir betrachten ein Softwareprojekt an dem normal fünf Mitarbeiter arbeiten. Dazu sind alle Vorgänge, sowie
deren Nachfolger, Dauer und Kosten in der untenstehenden Tabelle gegeben. Wir haben nun die Möglichkeit zu jeder
Aufgabe einen weiteren Mitarbeiter hinzuzuziehen, um den jeweiligen Vorgang zu beschleunigen.
Ein weiterer Mitarbeiter verringert die Dauer um „maximal“ 20% (auf volle Tage runden), wobei die Kosten um exakt 20%
steigen würde. Vorgang Z ließe sich beispielsweise auf 13 Tage reduzieren, was zu 774 GE Crashkosten führen würde.
Berechnen Sie die Crashdauer, Crashkosten sowie die Crashkosten pro Zeiteinheit für alle Vorgänge
 Normal Crash
Vorgang Nachfolger Dauer Kosten Dauer Kosten Kosten / Zeiteinheit
A B 19 765
B C,D 20 820
C Z 14 600
D Z 9 365
E B 13 500
F B 22 900
Z - 16 645

C (2 Punkte) Erstellen Sie einen Netzplan für das in Aufgabe 1B beschriebene Projekt in Normalzeit.
Wann könnte das Projekt OHNE Beschleunigungen frühestens fertiggestellt werden? Wie hoch wären die Gesamtkosten?

Projektende
Gesamtkosten

Netzplan ausfüllen:

D (2 Punkte) Erstellen oder kopieren Sie den Netzplan für das in 1B bzw. 1C beschriebene Projekt.
Passen Sie die Vorgangsdauern so an, dass die Projektlaufzeit minimiert wird, ohne unnötige Kosten zu verursachen.
Wann könnte das Projekt MIT Beschleunigungen frühestens fertiggestellt werden? Wie hoch wären die Gesamtkosten?

Vorgang Beschleunigung Projektende

A Gesamtkosten
B
C
D
E
F
Z

Netzplan ausfüllen:
E (3 Punkte) Wir wollen das hier vereinfachte Problem mit dem Ziel die Projektlaufzeit zu minimieren und einer zusätzlichen
Budgetrestriktion als ausformuliertes LP-Modell aufstellen. Formulieren Sie die Zielfunktion und Nebenbedingungen. Nutzen Sie
dazu hie hier gegebenen Angaben und Bezeichnungen
(Anmerkung: Der Excel Solver wird in dieser Prüfung nicht benötigt!)

Normal Crash Entscheidungen

Vorgang Nachfolger Dauer Kosten Dauer Kosten Kosten/Zeiteinheit Startzeitpunkt Beschleunigung
A C 5 10 4 50 40 Ta Ba
B C,D 6 20 2 60 10 Tb Bb
C D 7 30 5 70 20 Tc Bc
D - 8 40 3 80 8 Td Bd

Fertigstellungszeitpunkt E
Maximales Budget 200

Ausformulieren

Zielfunktion

Erlaubte Einsparungen

Projektstart

Nachfolger

Projektende

Budget

Beispiel 3 (8 Punkte)

A (2 Punkte) Erläutern Sie, ob die folgenden Aussagen stimmen oder nicht?

1. Bei der Maschinenbelegungsplanung ergibt sich die Bearbeitungszeit aus der Durchlaufzeit minus der Wartezeit
Erläuterung:

2. SPT, EDD, LPT, ERD sind Regeln, die die Sortierung der Aufträge bestimmen
Erläuterung:

3. Permutations-Flow-Shop ist eine Vereinfachung des Flow-Shop Problems

Erläuterung:

4. Der Johnson Algorithmus ist ein besonders für das Job-Shop-Problem geeignetes heuristisches Lösungsverfahren
Erläuterung:

B (4 Punkte) Lösen Sie das gegebene Ein-Maschinen-Problem entsprechend der aus der Veranstaltung bekannten
Entscheidungsregeln Earliest Due Date und Longest Processing Time. Als Beispiel wurde die Regel Shortest Processing Time
angewandt.
Ermitteln Sie für Earliest Due Date und LPT die Reihefolge der Aufträge sowie die tatsächlichen Fertigstellungs- und
Durchlaufzeiten. Bestimmen Sie abschließend die Zykluszeit und die durchschnittlichen Durchlaufzeiten.
Anhand einer Regel lassen sich kürzere Zykluszeiten erreichen als durch die anderen Beiden. Woran liegt das?
 Antrag A B C D E F
a_j 1 4 0 6 3 8
t_j 7 3 1 5 4 6
f_j 8 10 4 13 9 15

Beispiel Shortest Processing Time

Reihenfolge C B E D F A
Tat. Fertigstellung 1 7 11 16 22 29 Zykluszeit 29
Durchlaufzeit 1 3 8 10 14 28 Durchschnittliche Durchlaufzeit 10,67

Earliest Due Date

Reihenfolge
Tat. Fertigstellung Zykluszeit
Durchlaufzeit Durchschnittliche Durchlaufzeit

Longest Processing Time

Reihenfolge
Tat. Fertigstellung Zykluszeit
Durchlaufzeit Durchschnittliche Durchlaufzeit

Welche Regel liefert die kürzeste Zykluszeit?

Regel:

Aus welchen Gründen führen die anderen beiden Regeln zu längeren Zykluszeiten?
Erläuterung:

C (2 Punkte) Ihr Praktikant hat Ihnen das gegebene Mehr-Maschinen-Problem den folgenden Maschinenbelegungsplan erstellt.
Sie überprüfen den Plan und stellen fest, dass dieser nicht zulässig ist. Weisen Sie den Praktikanten auf die vier vorhandenen
Fehler hin!
Bearbeitungszeit
Auftrag 1 2 3 4 5 6 7 8 9
A 6 - 5 2 3 1 2 - 2
B 5 2 2 - 4 - 4 3 4

Stationsfolge
Auftrag 1 2 3 4 5 6 7 8 9
µ1 A B A A B A A B B
µ2 B - B - A - B - A

A 5 7 4 1 3 9
B 9 2 8 5 1 7 3
Zeit 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

1. Fehler:

2. Fehler:

3. Fehler:

4. Fehler:
Beispiel 4 (4 Punkte)
A (1 Punkt) Wie könnte der gegebene Netzplan erweitert werden, wenn bestimmte Meilensteine berücksichtigt und eingehalten
werden sollen?
Beispielhafte Meilensteine sind die Planungsphase (PP) und die Bauphase (BP)
Als Tätigkeit wurden beispielhaft Baugenehmigung (BG), Elektroplanung (EP), Elektroinstallation (EI), Heizungsplanung (HP),
Heizungsinstallation (HI), Sanitärplanung (SP), Sanitätsarbeiten (SA) und der Einzug (E) ausgewählt

EP EI

BG HP HI E

SP SA

Erläuterung:

B (1 Punkt) Woran kann man erkennen, dass das Ergebnis des Jackson Algorithmus für ein Mehr-Maschinen Job Shop Problems
bei Zyklusminimierung optimal ist und unter welchen Umständen kann die Optimalität nicht garantiert werden?

Erläuterung:

C (1 Punkt) Nennen Sie Nachteile des Nearest Neighbour Verfahrens und überlegen Sie wie ein vorausschauenderes
Konstruktionsverfahren aussehen könnte.

Erläuterung: