41542 KE 1 Reihenfolgeplanung Akers Friedman 2.5.4 Die Elimination nichtoptimaler Lösungen in Job-Shop-Problemen die Bestimmung von Bounds wie in 2.5.3 versagt bei Job-Shop-Problemen Methode von AKERS und FRIEDMAN S. 57 ff Beschränkung auf J = 2 Aufträge In diesem Skript wird das Beispiel der Kurseinheit S.57 ff ausgeführt, gleichzeitig werden vereinfachte Lösungswege für Klausuraufgaben mit 2 Aufträgen und 3 Maschinen gegeben. Maschinenfolgen : fx1 = ( A1 , A2 , A3 , A4 ) fx2 = ( A4 , A2 , A1 , A3 ) Vorschrift, daß Auftrag X1 vor Auftrag X2 auf Maschine A1 bearbeitet werde,d.h. rA1 = (X1, X2) Vorschrift, daß Auftrag X2 vor Auftrag X1 auf Maschine A1 bearbeitet werde,d.h. rA1 = (X2, X1) , bezogen auf Maschine A2 , bezogen auf Maschine A3 , bezogen auf Maschine A4 Die Anzahl der möglichen Programme bei 3 Maschinen ( J ! ) M 23 = 8 = 24 16 mögliche Kombinationen von Auftragsfolgen für A1 bis A4 Programmnummer 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1. Anzahl der zulässigen Belegungsprogramme : M N 1 M ik k2 mit ik : Häufigkeit, wie oft jeweils k Maschinen ( k = 2 ,..., M ) unabhängig von dazwischenliegenden anderen Maschinen in den beiden Maschinenfolgen der Aufträge in derselben Reihenfolge hintereinander auftreten. Hier : M = 4, k = 2, 3, 4, i2 = 2 ( für A1und A3 bzw. A2 und A3 ), i3 = 0, i4 = 0 N=1+4+2+0+0=7 Anzahl zulässiger Programme bei 3 Maschinen N = 1 + 3 + 1 + 0 = 5 Rolf Baumanns Seite 1 41542 KE 1 Reihenfolgeplanung Akers Friedman 2. Theorem - Zulässigkeit eines Belegungsprogramms : Eine notwendige und hinreichende Bedingung für die technologische Zulässigkeit eines Programms mit 2 Aufträgen ist, daß für jedes Maschinenpaar Am und Am´ mit Am vor Am´ bezüglich Auftrag X1 und Am hinter Am´ bezüglich Auftrag X2 der Ausdruck m m´ nicht in dem Programm auftritt. Dies bedeutet eine Prüfung nur bei nicht gleicher Reihenfolge von zwei Maschinen X1 Am , Am´ X2 Am´, Am dann ist m m´ nicht zulässig wurde ab jetzt im Skript durch ersetzt, da sonst missverständlich durch doppelte Bedeutung von X1 : (A1,A2,...) X2 : (..,A2,A1,..) nicht zulässig X1 : (A1,...,A4) X2 : (A4,..,A1,..) nicht zulässig X1 : (..,A2,...,A4) X2 : (A4,A2,.....) nicht zulässig X1 : (..,A3,A4) X2 : (A4,..,A3) nicht zulässig unzulässig sind folglich , , , Frage ob Kombinationen nicht zulässig sind systematisch vergleichen – A1-A2 ; A1-A3; A2-A3 (Gantt Diagr.zur Verdeutlichung Theorem) X1:(A1,...,A3,..) X2: (...,A1,A3) Test - X1 vor X2 auf A1 - X2 vor X1 auf A1 - X1 vor X2 auf A3 - X2 vor X1 auf A3 3. Mögliche Optimalität eines Belegungsprogramms : Eine notwendige und hinreichende Bedingung dafür, dass ein zulässiges Programm für zwei Aufträge zur Menge der (möglicherweise) optimalen Programme gehört, besteht darin, dass dieses Programm keine freien Maschinen enthält. (S.60 ff). Doppelter Spezialfall Im Gegensatz zur KE zunächst der doppelte Spezialfall (S. 61 f) Eine Maschine Am ist die erste Maschine für Auftrag X1 bzw. die letzte Maschine für Auftrag X2 dann ist m nicht optimal und kann gestrichen werden. Eine Maschine Am ist die erste Maschine für Auftrag X2 bzw. letzte Maschine für Auftrag X1 dann ist m nicht optimal und kann gestrichen werden hier doppelter Spezialfall m entspricht Vorschrift, daß Auftrag X1 vor Auftrag X2 auf Maschine A4 bearbeitet werde fx1 = ( A1 , A2 , A3 , A4 ) Rolf Baumanns fx2 = ( A4 , A2 , A1 , A3 ) Seite 2 nicht optimal 41542 KE 1 Reihenfolgeplanung Akers Friedman Regeln zur Optimalität Regel 1 (S. 60 unten) (1) bei Maschinenfolgen f x1 (..., Am´ , Am ,..., Am´´ ,...) und f x2 (..., Am´ ,..., Am , Am´´ ,...) darf der Ausdruck m´ m m´´ nicht im Programm auftreten auf die Lücken achten! Spezialfall Am ist die erste Maschine für Auftrag X1 bzw. die letzte Maschine für Auftrag X2 im Ausdruck m´ m m´´ kann das m´ bzw.das m´´ gestrichen werden. Bei einer Klausuraufgabe mit 3 Maschinen können nur die Spezialfälle auftreten, nicht die Allgemeinen Daraus folgt bei einer Folge Am Am’’ Am ist die erste Maschine für Auftrag X1 hier darf m m´´ nicht im Programm auftauchen bzw. bei einer Folge Am’ Am Am ist die letzte Maschine für Auftrag X2 hier darf m´ m nicht im Programm auftauchen Am = A1 Am´´ = A3 A1 A3 f x1 (..., Am´ , Am ,..., Am´´ ,...) f x2 (..., Am´ ,..., Am , Am´´ ,...) fx1 = ( A1 , A2 , A3 , A4 ) m´ m m´´ fx2 = ( A4 , A2 , A1 , A3 ) Am Am´´ A1 A3 Am´ = A2 Am = A3 A2 A3 f x1 (..., Am´ , Am ,..., Am´´ ,...) f x2 (..., Am´ ,..., Am , Am´´ ,...) A2 Rolf Baumanns fx1 = ( A1 , A2 , A3 , A4 ) m´ m m´´ A3 Seite 3 fx2 = ( A4 , A2 , A1 , A3 ) Am´ Am 41542 KE 1 Reihenfolgeplanung Akers Friedman Regel 2 S.61 oben (2) bei Maschinenfolgen f x1 (..., Am´ ,..., Am , Am´´ ,...) und f x2 (..., Am ´, Am ,..., Am´´ ,...) darf der Ausdruck m´ m m´´ nicht im Programm auftreten auf die Lücken achten! Spezialfall Am ist die erste Maschine für Auftrag X2 bzw. die letzte Maschine für Auftrag X1 im Ausdruck m´ m m´´ kann das m´ bzw.das m´´ gestrichen werden. Daraus folgt bei einer Folge Am Am’’ Am ist die erste Maschine für Auftrag X2 hier darf m m´´ nicht im Programm auftauchen bzw. bei einer Folge Am’ Am Am ist die letzte Maschine für Auftrag X1 hier darf m´ m nicht im Programm auftauchen daher und nicht optimal f x1 (..., Am´ , Am , Am´´ ,...) und f x2 (..., Am ´,..., Am , Am´´ ,...) f x1 (..., Am´ ,..., Am , Am´´ ,...) und f x2 (..., Am ´, Am , Am´´ ,...) Es bleiben nur die 4 Programme 1, 2, 6 und 8 als möglicherweise optimale zulässige Programme übrig. Es sind Gantt Diagramm zu zeichnen um optimale Lösung zu finden Rolf Baumanns Seite 4 41542 KE 1 Reihenfolgeplanung Akers Friedman Zusammenfassung für Klausur mit 3 Maschinen Die Anzahl der möglichen Programme bei 3 Maschinen ( J ! ) M 23 = 8 Anzahl zulässiger Programme bei 3 Maschinen N = 1 + 3 + 1 + 0 = 5 Theorem Zulässigkeit Dies bedeutet eine Prüfung nur bei nicht gleicher Reihenfolge von zwei Maschinen X1 Am , Am´ X2 Am´, Am dann ist m m´ nicht zulässig Doppelter Spezialfall Eine Maschine Am ist die erste Maschine für Auftrag X1 bzw. die letzte Maschine für Auftrag X2 dann ist m nicht optimal und kann gestrichen werden. Eine Maschine Am ist die erste Maschine für Auftrag X2 bzw. letzte Maschine für Auftrag X1 dann ist m nicht optimal und kann gestrichen werden Spezialfälle 1. bei einer Folge Am Am’’ Am ist die erste Maschine für Auftrag X1 hier darf m m´´ nicht im Programm auftauchen bzw. bei einer Folge Am’ Am Am ist die letzte Maschine für Auftrag X2 hier darf m´ m nicht im Programm auftauchen 2. bei einer Folge Am Am’’ Am ist die erste Maschine für Auftrag X2 hier darf m m´´ nicht im Programm auftauchen bzw. bei einer Folge Am’ Am Am ist die letzte Maschine für Auftrag X1 hier darf m´ m nicht im Programm auftauchen Rolf Baumanns Seite 5
© Copyright 2024 ExpyDoc
