[Back]

M. Knausz:
"Parallel variable neighborhood search for the car sequencing problem";
Supervisor: G. Raidl, M. Prandtstetter; Institut für Computergraphik und Algorithmen, 2008; final examination: 2008-10.

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 e ciency
of neighborhoods, i.e. the relation of computation time and the solution improvement,
should be used for identifying e cient neighborhood orderings on the
y. 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 identi ed which implies that such a parallel
self-adaptive approach is valuable and necessary for obtaining good solution qualities.