On the combinatorial structure of the permutation flow shop problem |
| |
Authors: | F. Werner |
| |
Affiliation: | (1) Sektion Mathematik, TU Otto von Guericke Magdeburg, PSF 124, O-3010 Magdeburg, FRG |
| |
Abstract: | In this paper we investigate the combinatorial structure of then/m/P/Cmax permutation flow shop problem. To each solution (a permutation ofn elements) we introduce a network which represents the job and machine orders. Based on the introduced generalized distance between a permutation and a path of a network we derive combinatorial properties with respect to special neighbourhoods which are important for developing iterative heuristics for the considered problem.For several neighbourhood structures we calculate the mean cardinality of reduced neighbourhoods where each neighbour satisfies a necessary condition for an objective improvement.
Zusammenfassung In der vorliegenden Arbeit wird die kombinatorische Struktur desn/m/P/Cmax Permutationsflußproblems untersucht. Zu jeder zulässigen Lösung, beschreibbar durch eine Permutation vonn Elementen, wird ein Netzplan eingeführt, der die Bearbeitungsreihenfolge der Operationen charakterisiert. Aufbauend auf einem eingeführten verallgemeinerten Abstand zwischen einer Permutation und einem Weg in einem Netzplan werden danach einige kombinatorische Eigenschaften bezüglich spezieller Nachbarschaftsstrukturen abgeleitet, die im Hinblick auf die Entwicklung von iterativen Heuristiken für das betrachtete Problem von Bedeutung sind. So werden u. a. für ausgewählte Nachbarschaftsstrukturen mittlere Mächtigkeiten reduzierter Nachbarschaften, bei denen jeder Nachbar eine notwendige Bedingung für eine Zielfunktionswertverbesserung erfüllt, hergeleitet. |
| |
Keywords: | Combinatorial optimization scheduling permutation flow shop problem networks structural investigations |
本文献已被 SpringerLink 等数据库收录! |
|