<div class="csl-bib-body">
<div class="csl-entry">Knausz, M. (2008). <i>Parallel Variable Neighbourhood Search for the Car Sequencing Problem</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-24045</div>
</div>
Variable Nachbarschaftssuche (VNS) ist eine relative neue Metaheuristik zum Lösen von schwierigen kombinatorischen Optimierungsproblemen. Ein solches Optimierungsproblem ist das Car Sequencing Problem (CarSP), wo eine Anordnung von Autos am Fließband mit minimalen Produktionskosten gefunden werden muss. Obwohl VNS eine erfolgreiche Metaheuristik ist, dauert es für praxisnahe Instanzen von CarSP eine lange Zeit bis eine brauchbare Lösung gefunden wird. Zwei Ansätze sollen ausführlicher untersucht werden: Erstens sollte die Effizienz von Nachbarschaften, d.h. das Verhältnis von Berechnungszeit und Lösungsverbesserung, während der Programmausführung verwendet werden, um effiziente Nachbarschaftsreihenfolgen zu bestimmen. Zweitens sollte das hohes Parallelisierungspotential ausgenutzt werden. Im Rahmen dieser Diplomarbeit werden beide Ansätze kombiniert. Die Tests zeigten, dass eine beträchtliche Reduktion der Berechnungszeit möglich ist.<br />Weiters haben die Tests gezeigt, dass keine "perfekte" Nachbarschaftsreihenfolge identifiziert werden kann was bedeutet, dass ein paralleler selbst-adaptiver Ansatz nützlich und wichtig ist, um gute Lösungsqualitäten zu erhalten.<br />
de
dc.description.abstract
Variable Neighborhood Search (VNS) is a relatively new metaheuristic for solving hard combinatorial optimisation problems. One such optimisation problem is the Car Sequencing Problem (CarSP), where a sequence of cars along the assembly line with minimum production costs has to be found.<br />Although VNS is a successful metaheuristic, it takes a long time until a suitable solution is found for real-world instances of CarSP. Two approaches should be investigated in more detail: Firstly, the efficiency of neighborhoods, i.e. the relation of computation time and the solution improvement, should be used for identifying efficient neighborhood orderings on the fly. Secondly, the high potential of parallelisation techniques should be exploited. Within this thesis both approaches are combined. Computational tests showed that a substantial reduction of the computation time is possible. Further, the tests revealed that no "perfect" neighborhood ordering can be identified which implies that such a parallel self-adaptive approach is valuable and necessary for obtaining good solution qualities.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Variable Nachbarschaftssuche
de
dc.subject
parallele Optimierung
de
dc.subject
CarSP
de
dc.subject
Metaheuristik
de
dc.subject
Variable Neighbourhood Search
en
dc.subject
parallel optimization
en
dc.subject
CarSP
en
dc.subject
metaheuristic
en
dc.title
Parallel Variable Neighbourhood Search for the Car Sequencing Problem
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Markus Knausz
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Prandtstetter, Matthias
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen