Martin-Luther-Universität Halle-Wittenberg

Weiteres

Login für Redakteure

Job Shop Scheduling unter Berücksichtigung von Fertigstellungsterminen

Maschinengestütze Fertigung

Maschinengestütze Fertigung

Übersicht

Gegenstand und Ziele

 Gegenstand des Forschungsprojekts ist das allgemeine Job Shop Scheduling Problem unter Berücksichtigung vorgegebener Fertigstellungstermine. Da die Nichteinhaltung von Fertigstellungsterminen z. B. Vertragsstrafen für ein Unternehmen zur Folge haben kann, erhalten Terminziele, etwa die Minimierung der durchschnittlichen Verspätung von Aufträgen oder die Minimierung der Anzahl verspäteter Aufträge große wirtschaftliche Bedeutung. Ziel des Projekts ist die Entwicklung und der Vergleich von leistungsfähigen problemspezifischen Heuristiken und von Nachbarschaftssuchverfahren, die mittels Metaheuristiken gesteuert werden.

Kurzdarstellung

In einer Vielzahl von Branchen (z.B. Druckindustrie) existieren Dienstleister, die Fertigungsaufträge von anderen Unternehmen übernehmen. Hierbei verursacht die Nichteinhaltung von Fertigstellungsterminen Vertragsstrafen und andere negative Konsequenzen für die Unternehmen, sodass Terminziele in der Produktionsfeinplanung, wie z. B. die Minimierung der durchschnittlichen Verspätung aller Aufträge oder die Minimierung der Anzahl verspäteter Aufträge, erhebliche Bedeutung gewonnen haben. Gegenstand der Feinplanung in der Werkstattfertigung sind einzelne Aufträge, die in einer vorab festgelegten Anzahl und Reihenfolge genau spezifizierter Arbeitsschritte auszuführen sind. Dabei ist die Durchführung jedes Arbeitsschrittes in der Regel an maschinelle Ressourcen gebunden. Da die Reihenfolge der zu durchlaufenden Maschinen für die Aufträge unterschiedlich sein kann, stellt sich die Frage, wie ein zulässiger und zugleich wirtschaftlicher Ablaufplan erzeugt werden kann.

Bisherige Forschungsarbeiten konzentrieren sich auf eine Planung, bei der die benötigte Gesamtbearbeitungszeit zur Durchführung aller Aufträge minimiert werden soll. Gegenstand dieses Projekts ist hingegen die Entwicklung und der Vergleich von leistungsfähigen Verfahren wie z. B. lokalen Suchverfahren und Metaheuristiken zur Bestimmung von Ablaufplänen unter Terminzielen. Methodisch wird hierbei auf das Modell Disjunktiver Graphen zurückgegriffen, welches zu diesem Zweck an die Erfordernisse von Terminzielen angepasst wird. Auf dieser Grundlage werden neue und effiziente Nachbarschaften für heuristische Planungsverfahren entwickelt.

Basisliteratur:

  • Michael L. Pinedo: Scheduling - Theory, Algorithms and Systems, 3. Auflage, Springer-Verlag, New York, 2008
  • Simon French: Sequencing and Scheduling - an Introduction to the Mathematics of the Job Shop, Ellis Horwood Ltd., 1981
  • Günther Zäpfel, Roland Braune: Moderne Heuristiken der Produktionsplanung, Verlag Franz Vahlen, München, 2005

Spezialliteratur:

  • Stephan Kreipl: A large step random walk for minimizing total weighted tardiness in a job shop, Journal of Scheduling 2000, Issue 3, p. 125-138
  • Svetlana Kravchenko: Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem, Discrete Applied Mathematics 98 (2000), p. 209-217
  • Yazid Mati, Stéphane Dauzère-Pérès, Chams Lahlou: A general approach for optimizing regular criteria in the job-shop scheduling problem. European Journal of Operational Research 212 (1), p. 33-42

Projektzeitraum

2009 - 2014

Kontakt

Das Projekt wird bearbeitet von Dipl.-Wirt.-Math. Jens Kuhpfahl ()

Projektbezogene Publikationen

  • Kuhpfahl, J.; Bierwirth, C.: A Study on Local Search  Neighborhoods for the Job Shop Scheduling Problem with Total Weighted  Tardiness Objective, eingereicht zur Publikation
  • Kuhpfahl, J., Bierwirth, C.: A GRASP approach for the Job Shop Scheduling Problem with minimizing the Total Weighted Tardiness, In: Proceedings of 6th  Multidisciplinary International Scheduling Conference: Theory and  Applications (MISTA 2013), 613-616
  • Zhang, R., Kuhpfahl, J.: Corrigendum to "A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted objective" [Computers and Operations Research 38(2011) 854-867], Computers & Operations Research40 (2013), 2816, Link   
  • Kuhpfahl, J., Bierwirth, C.: A New Neighbourhood Operator for the Job Shop Scheduling Problem with Total Weighted  Tardiness Objective, In: Applied Mathematical Optimization and Modelling - APMOD  2012 Extended Abstracts, 204-209
  • Kuhpfahl, J., Bierwirth, C.: Computational Comparison of Neighbourhoods for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective, In: Proceedings of 5th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2011), 536-538, Link    

Vortragsübersicht

  • Vortrag mit Titel: A GRASP approach for the job shop scheduling problem with the objective of minimizing the total weighted tardiness, OR 2013 - The  International Conference on Operations Research, Rotterdam (Niederlande), 05.09.2013
  • Vortrag mit Titel: A GRASP approach for the Job Shop Scheduling Problem with minimizing the Total Weighted Tardiness, 6th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2013), Gent (Belgien), 29.08.2013
  • Vortrag mit Titel: A new Method for the Evaluation of a Neighbor Solution in  Local Search Procedures for Solving the JSPTWT, EURO XXVI - European  Conference on Operational Research 2013, Rom, 01.07.2013
  • Vortrag mit Titel: Job Shop Scheduling unter Berücksichtigung von Fertigstellungsterminen, Vortrag im Forschungskolloquium, Halle, 17.05.2013
  • Vortrag mit Titel: A GRASP Approach for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective, EURO XXV  2012, European Conference  on Operational Research, Vilnius (Litauen),  09.07.2012
  • Vortrag mit Titel: Job Shop Scheduling unter Berücksichtigung von Fertigstellungsterminen, 14. Doktorandenworkshop Nordost, Wittenberg, 11.05.2012
  • Vortrag mit Titel: A New Neighbourhood Operator for the Job Shop Scheduling Problem with  Total Weighted Tardiness Objective. International Conference of Applied Mathematical Optimization and Modelling (APMOD 2012), Paderborn, 28.03.2012
  • Vortrag mit Titel: A Computational Study of Local Search Neighbourhoods for the Job Shop Scheduling Problem with a Tardiness Objective. International Conference on Operations Research (OR 2011), Zürich (CH), 31.08.2011
  • Vortrag mit Titel: Computational Comparison of Neighbourhoods for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective. 5th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2011), Phoenix (USA), 10.08.2011
  • Vortrag mit Titel: Job Shop Scheduling unter Berücksichtigung von  Fertigstellungsterminen. 12. Doktorandenworkshop Nordost, Cottbus, 22.04.2010

Algorithmen und Daten

Zum Seitenanfang