Deutsch

Aus einer praktischen Problemstellung zur Reihenfolgeplanung von Produtkionsaufträgen in der automobilen Zulieferkette wird ein Optimierungsproblem abgeleitet. Wesentliche Eigenschaften des Optimierungsproblems (Materialverfügbarkeit, Rüstzeiten, Vorrangbeziehungen und Fälligkeiten) werden hinsichtlich der daraus erwachsenden Komplexität analysiert und Eigenschaften zulässiger Lösungen ermittelt. Ein exakter Branch-and-Bound-Ansatz sowie ein Branch-and-Price-and-Cut-Ansatz werden zusätzlich zu ganzzahligen Optimierungsmodellen als Verfahren zur Bestimmung von optimalen Lösungen vorgestellt. Das Hauptaugenmerk bei der Entwicklung des Branch-and-Bound-Ansatzes liegt in der Bestimmung von zulässigen unteren Schranken für das Problem. Im Branch-and-Price-and-Cut-Ansatz wird eine neue Art der Zerlegung von Ein-Maschinen-Scheduling-Problemen in ein Masterproblem und mehrere Unterprobleme vorgestellt, die die vorhandenen Vorrangbeziehungen in Form von Ketten ausnutzt. Die Verfahren werden mittels computergestützter Experimente für Instanzen mit bis zu 15 Produkten und 75 Aufträgen bei verschiedenen Settings für Rüstzeiten und Zeitfenster evaluiert. Es ergibt sich eine deutliche Überlegenheit des Branch-and-Bound-Verfahrens gegebenüber der IP-Standardsoftware sowie dem Branch-and-Cut-and-Price-Ansatz hinsichtlich der Rechenzeit und der resultierenden Optimalitätslücke für nicht optimal gelöste Probleminstanzen.

English

The problem setting at an automotive supplier company motivates the consideration of a special single machine scheduling problem. The structure and complexity given by the problems' properties such as material availability constraints, setup times, precedence relations and deadlines is investigated. Common properties of feasible solutions are identified. A Branch and Bound Approach and a Branch and Price and Cut Approach are proposed in addition to Integer Programming based optimization models. The development of the Branch and Bound approach focuses on lower bounds derived from different properties of the problem. For the Branch and Price and Cut approach a new decomposition scheme for single machine scheduling problems is given based on the presence of precedence relations. The algorithms are evaluated by a computational study on instances with up to 15 products and 75 jobs with different setup times and time windows. The tests indicate the superiority of the Branch and Bound Approach over the IP-based approach as well as the Branch and Price and Cut approach with regard to CPU time and the optimality gap obtained.