Sommer 2009:

Scheduling (Reihenfolgeoptimierung, Maschinenbelegung)

Information:

Termine: Do 9.00 - 11.00 in G22A-110 and Fr 13.00 - 15.00 in G22A-119

Die Vorlesung richtet sich insbesondere an Studierende der Wirtschaftswissenschaften (z.B. BWL, BWLIM in den Vertiefungsrichtungen Operations Research oder Produktionswirtschaft), der Wirtschaftsinformatik (WIF), des Wirtschaftsingenieurwesens Logistik (WLO) und anderer ingenieurwissenschaftlicher Studiengänge.

Inhalt

Die Vorlesung befasst sich mit den Grundlagen zur Lösung von Reihenfolgeproblemen (Maschinenbelegung). Eine Menge von Aktivitäten (Jobs) ist auf einer Menge von Ressourcen (Maschinen) so auszuführen, dass ein optimaler Plan im Sinne eines vorgegebenen Optimierungskriteriums konstruiert wird. Schwerpunkt sind die Klassifikation und Komplexität von Scheduling-Problemen sowie exakte und approximative Algorithmen zur Lösung von ein- und mehrstufigen Scheduling-Problemen.

Gliederung

1) Einführung

2) Zur Komplexität von Scheduling-Algorithmen

3) Einige Basisalgorithmen zur exakten und näherungsweisen Lösung von Scheduling-Problemen

4) Einmaschinenprobleme

5) Probleme mit parallelen Maschinen

6) Flow Shop und Permutation Flow Shop Probleme

7) Job Shop Probleme

8) Open Shop Probleme

9) Einige Problemerweiterungen

Literatur

1) Brucker, P.: Scheduling Algorithms, Springer Verlag, 1995 (1998, 2001).

2) Blazewicz, J.; Ecker, K.; Schmidt, G.; Pesch, E.; Weglarz, J.: Scheduling Computer and Manufacturing Processes, Springer Verlag, 1996.

3) Domschke, W.; Scholl, A.; Voss, S.: Produktionsplanung, Ablauforganisatorische Aspekte, Springer Verlag, 1993 (1997).

4) Pinedo, M.: Planning and Scheduling in Manufacturing and Services, Springer, 2004.

5) Pinedo, M.: Scheduling: Theory, Algorithms, and Systems, Prentice Hall, 1995 (2002).

6) Pinedo, M.; Chao, X.: Operations Scheduling with Applications in Manufacturing and Services, Irwin, McGraw Hill, 1999.

7) Parker, G.R.: Deterministic Scheduling Theory, Chapman & Hall, 1995.

8) Tanaev, V.S.; Gordon, V.A.; Strusevich, V.A.: Theory of Scheduling. Single-Stage Systems, Kluwer Academic Publishers, 1994.

9) Tanaev, V.S.; Sotskov, Y.N.; Shafransky, Y.M.: Theory of Scheduling. Multi-Stage Systems. Kluwer Academic Publishers, 1994.

Vorlesungsmaterialien (Folien)

I) Einführung

Scheduling-Probleme in Fertigung und Service (pdf)

Klassifikationsschema für Scheduling-Probleme (pdf)

II) Zur Komplexität von Scheduling-Problemen

Zeitkomplexitätsfunktionen (pdf)

Die Klassen P und NP (pdf)

NP-complete und NP-hard Probleme (pdf)

Entscheidungsprobleme in P und NP-complete (pdf)

III) Einige Basisalgorithmen zur exakten und näherungsweisen Lösung von Scheduling-Problemen

Branch and Bound Algorithmus (pdf)

Dynamische Optimierung (pdf)

Algorithmus Iterative Verbesserung (pdf)

Algorithmus Simulated Annealing (pdf)

Algorithmus Tabu Suche (pdf)

Genetischer Algorithmus GEN-ALG (pdf)

Bezeichnungen und Definitionen zu Approximationsverfahren (pdf)

Übungsserien zur Vorlesung

Übungsserie 1 (pdf)

Übungsserie 2 (pdf)

Übungsserie 3 (pdf)

Übungsserie 4 (pdf)

Übungsserie 5 (pdf)

Einige Klausuren früherer Jahrgänge (2 Std.)

Klausur Juli 2006 (pdf)

Klausur Juli 2005 (pdf)

Klausur Juli 2004 (pdf)

Klausur Juli 2003 (pdf)