@inproceedings{Henning2003,
  author    = {Henning, Andr{\´e}},
  title     = {Short Listing f{\"u}r multikriterielle Job-Shop Scheduling Probleme},
  doi       = {10.25643/bauhaus-universitaet.298},
  url       = {http://nbn-resolving.de/urn:nbn:de:gbv:wim2-20111215-2988},
  year      = {2003},
  abstract  = {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{\"a}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{\"o}sungen enthalten. Aus dieser Menge muss der Entscheidungstr{\"a}ger eine L{\"o}sung ausw{\"a}hlen. Da die Datenmenge schon bei moderaten Problemdimensionen sehr umfangreich wird, stellt dies ein Problem f{\"u}r den Entscheider dar. Deshalb muss die große Menge der L{\"o}sungen auf eine {\"u}berschaubare Anzahl reduziert werden. Bei dieser Reduktion der L{\"o}sungen muss die Diversit{\"a}t der verbleibenden L{\"o}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{\"o}sungen mittels Abstandsmaßen im L{\"o}sungsraum geclustert. Die dazu verwendeten Abstandsmaße werden auf den Permutationen der Vorg{\"a}nge auf den Ressourcen definiert. Es wurden f{\"u}nf Abstandsmaße und zwei Clusterverfahren, ein hierarchisches und ein nicht-hierarchisches, untersucht. Im zweiten Schritt wird aus jedem Cluster jeweils eine L{\"o}sung ausgew{\"a}hlt und dem Entscheidungstr{\"a}ger vorgelegt. Dabei wurden zwei Methoden untersucht. Im ersten Fall wurde die bez{\"u}glich einer Ranking-Funktion beste L{\"o}sung und im zweiten Fall die Medianl{\"o}sung bez{\"u}glich des Abstandsmaßes ausgew{\"a}hlt. Die Abstandsmaße, Clusteralgorithmen und Auswahlmethoden wurden auf einer großen Menge von Benchmark-Instanzen verglichen. Die Ergebnisse werden im Vortrag vorgestellt.},
  subject      = {Reihenfolgeproblem},
  language  = {de}
}
@inproceedings{Sotskov2003,
  author    = {Sotskov, Yuri N.},
  title     = {Stability of an optimal schedule for a flow-shop problem with two jobs},
  doi       = {10.25643/bauhaus-universitaet.369},
  url       = {http://nbn-resolving.de/urn:nbn:de:gbv:wim2-20111215-3690},
  year      = {2003},
  abstract  = {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 {\^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{\^I} J on machine k{\^I} 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 {\^I} 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*{\^I} 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 {\^I} Rt is stable takes O(m log m) time.},
  subject      = {Ablaufplanung},
  language  = {en}
}