(PDF) Michael E. Bergen, Peter van Beek, and Tom Carchrae. Constraint-based vehicle assembly line sequencing. Proceedings of the 14th Canadian Conference on Artificial Intelligence, Ottawa, Ontario, 88-99, June, 2001.


In this paper, we consider the optimal sequencing of vehicles along multiple assembly lines. We present a constraint-based model of the problem with hard and soft constraints. An advantage of a constraint-based approach is that the model is declarative and there is a separation between the model and an algorithm for solving the model. As a result, once the model had been defined, we could experiment with different algorithms for solving the model, with few or no changes to the model itself. We present three approximation algorithms for solving the model---a local search algorithm, a backtracking algorithm with a constraint relaxation and restart scheme, and a branch and bound algorithm---and we compare the quality of the solutions and the computational performance of these methods on six real-world problem instances. For our best method, a branch and bound algorithm with a decomposition into smaller sub-problems, we obtained improvements ranging between 2% and 16% over an existing system based on greedy search.

Return to Publications