Der Campbell-Dudek-Smith-Algorithmus Legende N m Anzahl Aufträge Anzahl Maschinen n i j Letzter Maschinenindex für Maschine 1 nach Johnson Auftragsindex Maschinenindex t i , j , pi , j r Bearbeitungszeit für Auftrag i an der Maschine j Auftragsreihenfolge nach Johnson optfst optn optr Frühester Maximaler Fertigstellungstermin n des optfst r des optfst x, y Hilfsvariablen Campbell-Dudek-Smith-Algorithmus optfst = ∞ Frühester maximaler Fertigstellungstermin ist zunächst plusunendlich Für n = 1 bis m n pi ,1 = ∑ t i , j ∀i ∈ [1; N ] j =1 pi ,2 = m ∑t i, j ∀i ∈ [1; N ] j = n +1 Alle Maschinen von 1 bis n werden für Johnson zur Maschine 1 zusammengefasst Alle Maschinen von n + 1 bis m werden für Johnson zur Maschine 2 zusammengefasst r = johnson(p) Ermittlung der Auftragsreihenfolge nach Johnson Wenn fst(r,t,N,m) < optfst optfst = fst(r,t,N,m) optn = n optr = r Wenn diese Lösung ein besseres Ergebnis liefert, als der bisher früheste maximale Fertigstellungstermin, so wird dieses Ergebnis als neues Optimum festgehalten. Frühester Fertigstellungstermin fst(r,t,i,j) 0 x= fst (r , t , i − 1, j ) 0 y= fst (r , t , i, j − 1) ,i = 1 , sonst , j =1 , sonst fst = max( x, y ) + t ri , j Campbell-Dudek-Smith-Algorithmus Der Fertigstellungstermin des Vorgängerauftrags an der Maschine j oder 0, falls es sich um den ersten Auftrag handelt Der Fertigstellungstermin der Vorgängermaschine des Auftrags i oder 0, falls es sich um die erste Maschine handelt Die Fertigung von Auftrag i an Maschine j kann beginnen, sobald der Vorgängerauftrag dieser Maschine und dieser Auftrag an der Vorgängermaschine abgearbeitet wurden. Der Fertigstellungstermin ergibt sich als aus dem Maximum dieser beiden Größen plus der Bearbeitungszeit des Auftrags an dieser Maschine selbst. Christian Silberbauer
© Copyright 2024 ExpyDoc
