On the car sequencing problem: analysis and solution methods

This work deals with the car sequencing (CS) problem, a combinatorial optimization problem for sequencing mixed-model assembly lines. The aim is to find a production sequence for different variants of a common base product, such that work overload of the respective line operators is avoided or minimized. The variants are distinguished by certain options (e.g., sun roof yes/no) and, therefore, require different processing times at the stations of the line. CS introduces a so-called sequencing rule H:N for each option, which restricts the occurrence of this option to at most H in any N consecutive variants. It seeks for a sequence that leads to no or a minimum number of sequencing rule violations. In this work, CS’ suitability for workload-oriented sequencing is analyzed. Therefore, its solution quality is compared in experiments to the related mixed-model sequencing problem. A new sequencing rule generation approach as well as a new lower bound for the problem are presented. Different exact and heuristic solution methods for CS are developed and their efficiency is shown in experiments. Furthermore, CS is adjusted and applied to a resequencing problem with pull-off tables.

Die vorliegende Arbeit beschäftigt sich mit dem Car Sequencing (CS) Problem, einem kombinatorischen Optimierungsproblem zur Reihenfolgeplanung bei Variantenfließfertigung. Ziel ist es für verschiedene Varianten eines Basisproduktes eine Produktionsreihenfolge zu finden, sodass Überlastungen der Fließbandarbeiter vermieden bzw. minimiert werden. Die Varianten unterscheiden sich hinsichtlich der Ausprägung bestimmter Optionen (z.B. Schiebedach ja/nein) und benötigen dementsprechend eine unterschiedliche Montagezeit an den einzelnen Stationen des Fließbandes. CS führt für jede Option eine sogenannte Reihenfolgeregel H:N ein, die das Auftreten der Option in N aufeinanderfolgenden Varianten auf maximal H beschränkt. Es wird eine Reihenfolge gesucht, die zu keiner bzw. minimaler Anzahl an Regelverletzungen führt. In dieser Arbeit wird untersucht inwieweit sich CS tatsächlich für die überlastungsorientierte Reihenfolgeplanung eignet. Hierzu wird in Experimenten seine Lösungsqualität mit dem verwandten Mixed-Model Sequencing Problem verglichen. Die Arbeit präsentiert einen neuen Ansatz zur Erstellung von Sequenzregeln für CS, sowie eine neue Methode zur Berechnung einer unteren Schranke für das Problem. Verschiedene exakte und heuristische Lösungsverfahren für CS werden entwickelt und deren Effizienz in Experimenten nachgewiesen. Darüberhinaus wird CS auf ein Resequencing Problem mit Pull-Off Tables anpasst and angewendet.