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.

Created from the Publication Database of the Vienna University of Technology.