(PDF)
Michael Bergen.
Constraint-based assembly line sequencing.
MSc thesis,
University of Alberta, Department of Computing Science,
2000.
A wide variety of combinatorial optimization problems have been studied in recent years. Of particular interest are a class of optimization problems arising from the manufacturing of vehicles on assembly lines. These problems consist of sequencing the vehicles that are going to be produced such that their production is done in an efficient cost effective manner. In this thesis we introduce a real-world vehicle sequencing problem that was provided by TigrSoft, who solved the problem for one of their clients using a greedy search approach. We began by modeling this problem as a constraint satisfaction problem and from there we devised three different solution techniques for solving it. These solution techniques include a simple hill-climbing algorithm, a backtracking algorithm with parameterized soft constraints, and a branch and bound algorithm that is capable of finding optimal solutions. We were able to improve results, compared to TigrSoft's algorithm, using any of these three solution techniques. For our best method, a branch and bound technique with a decomposition into smaller sub-problems, we obtained improvements ranging between 3% and 13% for six real-world problem instances.