Title: | Parallel Variable Neighbourhood Search for the Car Sequencing Problem | Language: | English | Authors: | Knausz, Markus | Qualification level: | Diploma | Keywords: | Variable Nachbarschaftssuche; parallele Optimierung; CarSP; Metaheuristik Variable Neighbourhood Search; parallel optimization; CarSP; metaheuristic |
Advisor: | Raidl, Günther | Assisting Advisor: | Prandtstetter, Matthias | Issue Date: | 2008 | Number of Pages: | 60 | Qualification level: | Diploma | Abstract: | 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. 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. 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. 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. |
URI: | https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-24045 http://hdl.handle.net/20.500.12708/12404 |
Library ID: | AC05039060 | Organisation: | E186 - Institut für Computergraphik und Algorithmen | Publication Type: | Thesis Hochschulschrift |
Appears in Collections: | Thesis |
Files in this item:
File | Description | Size | Format | |
---|---|---|---|---|
Parallel Variable Neighbourhood Search for the Car Sequencing Problem.pdf | 621.13 kB | Adobe PDF | ![]() View/Open |
Page view(s)
13
checked on Feb 25, 2021
Download(s)
52
checked on Feb 25, 2021

Google ScholarTM
Check
Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.