apl. Prof. Dr. Frank Werner

Otto-von-Guericke Universität Magdeburg

Institut für Mathematische Optimierung


Forschungsteam     
 
Kontakt Publikationen Aktivitäten & Interessen Lehre Betreuung Laufbahn & Projekte Private Links
 
  
 

Sommer 2009:

Scheduling (Reihenfolgeoptimierung, Maschinenbelegung)



Information:

Eine Vorlesung `Scheduling' ist das nächste Mal im Sommersemester 2010 für den Masterstudiengang in verkürzter Form (2 V / 1 Ü) im Lehrangebot.



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)



Klausuren früherer Jahrgänge

Klausur Februar 2008 (pdf)

Klausur Juli 2006 (pdf)

Klausur Juli 2005 (pdf)

Klausur Juli 2004 (pdf)

Klausur Juli 2003 (pdf)

Klausur Juli 2002 (pdf)

Klausur Juli 2001 (pdf)

Klausur Juli 2000 (pdf)

Klausur Juli 1999 (pdf)

Klausur Juli 1998 (pdf)



<frank.werner@mathematik.uni-magdeburg.de>

  
English version Last updated: 1 Dec 2009