Solving the car sequencing problem via Branch & Bound

In a mixed-model assembly line, varying models of the same basic product are to be produced in a facultative sequence. This results to a short-term planning problem where a sequence of models is sought which minimizes station overloads. In practice – e.g. the final assembly of cars – special sequencing rules are enforced which restrict the number of models possessing a certain optional feature k to r_k within a subsequence of s_k successive models. This problem is known as car sequencing. So far, employed solution techniques stem mainly from the field of Logic and Constraint Logic Programming. In this work, a special Branch & Bound algorithm is developed, which exploits the problem structure in order to reduce combinatorial complexity.