TY  - CHAP
A1  - Henning, André
T1  - Short Listing für multikriterielle Job-Shop Scheduling Probleme
N2  - In ersten Teil des Vortrages wird eine Heuristik zur Approximation der Pareto Menge multikriterielle verallgemeinerter Job-Shop Scheduling-Probleme vorgestellt. Der Algorithmus basiert auf einer genetischen lokale Suche Heuristik. Die Mittelwertbildung der Startzeiten der Vorgänge wurde hierbei als Rekombinationsoperator verwendet. Als lokale Suche wurde ein Threshold Accepting Algorithmus implementiert. Der Algorithmus wurde auf einer großen Menge von Benchmark-Instanzen und den Zielfunktionen Makespan, Tardiness, Lateness und Summe der Fertigstellungszeiten getestet. Die Ergebnisse zu den verschiedenen Zielfunktionen werden vorgestellt. Die vom Algorithmus erzeugte Approximation der Pareto Menge kann eine große Anzahl von Lösungen enthalten. Aus dieser Menge muss der Entscheidungsträger eine Lösung auswählen. Da die Datenmenge schon bei moderaten Problemdimensionen sehr umfangreich wird, stellt dies ein Problem für den Entscheider dar. Deshalb muss die große Menge der Lösungen auf eine überschaubare Anzahl reduziert werden. Bei dieser Reduktion der Lösungen muss die Diversität der verbleibenden Lösungen beachtet werden. Diese Reduzierung wird als Short Listing bezeichnet und im zweiten Teil des Vortrages vorgestellt. Im ersten Schritt des Short Listings werden die Lösungen mittels Abstandsmaßen im Lösungsraum geclustert. Die dazu verwendeten Abstandsmaße werden auf den Permutationen der Vorgänge auf den Ressourcen definiert. Es wurden fünf Abstandsmaße und zwei Clusterverfahren, ein hierarchisches und ein nicht-hierarchisches, untersucht. Im zweiten Schritt wird aus jedem Cluster jeweils eine Lösung ausgewählt und dem Entscheidungsträger vorgelegt. Dabei wurden zwei Methoden untersucht. Im ersten Fall wurde die bezüglich einer Ranking-Funktion beste Lösung und im zweiten Fall die Medianlösung bezüglich des Abstandsmaßes ausgewählt. Die Abstandsmaße, Clusteralgorithmen und Auswahlmethoden wurden auf einer großen Menge von Benchmark-Instanzen verglichen. Die Ergebnisse werden im Vortrag vorgestellt.
KW  - Reihenfolgeproblem
Y1  - 2003
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:gbv:wim2-20111215-2988
ER  - 
TY  - CHAP
A1  - Sotskov, Yuri N.
T1  - Stability of an optimal schedule for a flow-shop problem with two jobs
N2  - The problem F|n=2|F is to minimize the given objective function F(C1,m, C2,m) of completion times Ci,m of two jobs i Î J={1, 2} processed on m machines M={1, 2, …, m}. Both jobs have the same technological route through m machines. Processing time ti,k of job iÎ J on machine kÎ M is known. Operation preemptions are not allowed. Let R2m be space of non-negative 2m-dimensional real vectors t=(t1,1,…, t1,m, t2,1,…, t2,m) with Chebyshev’s distance d(t, t*). To solve problem F|n=2|F, we can use the geometric algorithm, which includes the following steps: 1) construct digraph (V, A) for problem F|n=2|F and find so-called border vertices in (V, A); 2) construct the set of trajectories corresponding to the shortest paths Rt in digraph (V, A) from the origin vertex to each of the border vertices; 3) find an optimal path in the set Rt that represents a schedule with minimal value of the objective function F. Let path tu Î Rt be optimal for the problem F|n=2|F with operation processing times defined by vector t. If for any small positive real number e > 0 there exists vector t*Î R2m such that d(t, t*) = e and path tu is not optimal for the problem F|n=2|F with operation processing times defined by vector t*, then optimality of path tu is not stable. The main result of the paper is the proof of necessary and sufficient conditions for optimality stability of path tu. If objective function F is continuous non-decreasing (e.g., makespan, total completion time, maximal lateness or total tardiness), then to test whether optimality of the path tu Î Rt is stable takes O(m log m) time.
KW  - Ablaufplanung
KW  - Reihenfolgeproblem
Y1  - 2003
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:gbv:wim2-20111215-3690
ER  -