Solution Techniques for specific Bin Packing Problems with Applications to Assembly Line Optimization

Stille, Wolfgang (2008):Solution Techniques for specific Bin Packing Problems with Applications to Assembly Line Optimization.Darmstadt, Technische Universität, [Ph.D. Thesis]

 Preview
Dissertation - Text
Dissertation_Wolfgang_Stille.pdf
Available under CC-BY-NC-ND 2.5 de - Creative Commons, Attribution Non-commerical, No-derivatives.

Item Type: Ph.D. Thesis
Title: Solution Techniques for specific Bin Packing Problems with Applications to Assembly Line Optimization
Language: English
Abstract:

The present thesis is about efficient solution techniques for specific Bin Packing Problems and their derivatives. Bin Packing Problems arise in numerous applications from industry and economics. They occur for example in the distribution of resources, in operation scheduling of complex processes, in project planning, and logistics, only to mention a few. As one concrete application, we present the optimization of assembly lines for printed circuit board manufacturing in detail. This work arose from a long term cooperation with Philips Assembléon in Eindhoven. The Bin Packing decision problem asks the question whether – given a set of objects of distinct sizes, and a set of bins with specific capacity – there is a distribution of items to bins such that no item is left unpacked nor the capacity of any bin is exceeded. The corresponding optimization problem searches for the minimum number of bins to pack all objects. In general, Bin Packing is NP-hard. As long as P is not NP, this amounts to the fact that there is no algorithm that is able to decide whether a feasible distribution for a given instance exists in time that depends polynomially on the size of the input. However, there are several special cases that may be solved efficiently, either approximately or even optimally. In practice, there are for example problems that comprise only few distinct item sizes, but items of each size are occurring in high multiplicities. The thesis gives theoretical insights for exactly this case. We develop an efficient combinatorial algorithm which solves the problem in polynomial time to a solution that is using at most one more bin than an optimal solution. Moreover, we introduce various rounding techniques for rounding arbitrary input data. The presented techniques are general enough to be applied to various optimization problems, either for the computation of approximate solutions, or for the purpose to efficiently generate upper and lower bounds in order to narrow the solution space. This can be achieved for example by applying an efficiently solvable special case as described above. In order to control the impact of the relaxation, we put special emphasis on the bounding of the rounding error: for any of the presented rounding algorithms, we prove an error estimation. Furthermore, we present a comprehensive qualitative analysis on typical data profiles as well data from real world applications. As an application, we use rounding as a relaxation technique in order to jointly evaluate a global constraint with an arbitrary number of elementary constraints. This problem arises from Constraint Programming which has steadily increased in popularity during the last years for modeling and solving optimization problems. We develop a framework to efficiently evaluate Bin Packing Constraints jointly with a class of fairly general constraints which we call Concave Constraints. These imply a wide variety of elementary constraints as logic operations such as implications and disjunctions, as well as all linear constraints. Moreover, arbitrary concave functions such as quadratic constraints, and constraints modeling a process of growth or decay can be modeled within this framework. We give various examples for the modeling of fundamental optimization problems within this framework. Finally, we develop algorithms that detect infeasibility of a given constraint system. The last chapter is devoted to a concrete application: the optimization of assembly lines for printed circuit board manufacturing. Due to high–mix low–volume batches the production process must be more flexible than ever, and unprofitable setup times should be avoided as far as possible. For this reason, partly–combined processing is introduced: an assembly line consists of multiple trolleys that hold the component types. One or more of these trolleys might be exchanged on the fly during the batch which amounts to a partial change in the machine setup. Changing the setup several times during the batch process implies a partition of the boards in the batch into several groups. There are two problems arising from this approach: (1) how to find an ideal grouping of boards, and (2) how to assign component types to placement modules in order to exploit the high parallelism of the assembly line. In particular, it must be decided which component types to assign statically, and which ones on the exchangeable trolleys. This problem can be understood as a generalized Bin Packing problem with additional side constraints. We show that the problem is NP-complete. In the scope of an industrial cooperation project with Philips Assembléon in Eindhoven, we developed specific algorithms in order to efficiently compute groupings of boards and machine setups for the partly–combined case. We have made several computational experiments with original data sets from customers and compared our technique to another approach from the literature. The results show that our approach is vastly superior with respect to the solution quality. Moreover, it contains some additional benefits: the computed setups are feasible in any case, and infeasibility is detected at an early stage of the framework. Additionally, this results in a much shorter runtime of the optimization software.

Alternative Abstract:
Alternative AbstractLanguage
Die vorliegende Arbeit beschäftigt sich mit Techniken zur Lösung von speziellen Bin Packing Problemen und deren Verwandten. Bin Packing Probleme treten in zahlreichen Anwendungen in Industrie und Wirtschaft auf, beispielsweise bei der Verteilung von Ressourcen, der Ablaufplanung komplexer Vorgänge, im Projektmanagement und in der Logistik, nur um einige zu nennen. Als konkrete Anwendung widmen wir uns im letzten Kapitel der Optimierung von Fertigungslinien für die Leiterplattenbestückung. Diese entstand aus einer langjährigen Industriekooperation mit Philips Assembléon in Eindhoven. Das Bin Packing Entscheidungsproblem stellt die Frage, ob zu einer gegebenen Menge von Objekten verschiedener Größe und einer Menge von Containern mit bestimmtem Fassungsvermögen eine Verteilung der Objekte auf die Container existiert, so daß weder ein Objekt unverpackt bleibt, noch die Kapazität eines Containers überschritten wird. Das korrespondierende Optimierungsproblem sucht nach der minimalen Anzahl an Containern, so daß alle Objekte verpackt werden können. Dieses Problem ist im allgemeinen Fall NP-vollständig. Solange P ungleich NP ist, bedeutet dies, daß es kein Verfahren gibt, welches die Entscheidung, ob für eine gegebene Instanz eine zulässige Verteilung existiert oder nicht, innerhalb einer Zeit treffen kann, die polynomial von der Eingabegröße des Problems abhängt. Für einige Fälle, in denen die Eingabedaten spezielle Strukturen aufweisen, kann das Problem jedoch effizient, d.h. in Polynomialzeit exakt gelöst bzw. approximiert werden. In der Praxis treten beispielsweise oftmals Probleme auf, die sehr viele Objekte beinhalten, die jedoch nur sehr wenige unterschiedliche Größen aufweisen. Für genau diesen Fall werden in dieser Arbeit die notwendigen theoretischen Grundlagen erarbeitet und ein effizientes kombinatorisches Lösungsverfahren entwickelt. Das Verfahren berechnet in polynomialer Zeit Lösungen, die maximal einen Behälter mehr benötigen als die Optimallösung. Darüberhinaus werden Verfahren zur Rundung beliebiger Eingabedaten vorgestellt. Im allgemeinen sind solche Verfahren für Optimierungsprobleme unterschiedlichster Art anwendbar: sei es um effizient obere und untere Schranken zu berechnen oder um Näherungslösungen zu generieren, zum Beispiel indem ein effizient lösbarer Spezialfall angewandt werden kann. Da eine Rundung der Eingabedaten einer Relaxierung des Originalproblems entspricht, legen wir besonderes Gewicht auf die Beschränkung des Rundungsfehlers. Wir beweisen für jedes der vorgestellten Verfahren eine Fehlerabschätzung und präsentieren umfangreiche Rechenergebnisse auf typischen Datenprofilen. Als eine Anwendung der Rundung stellen wir ein Verfahren zur Auswertung von Bin Packing Constraints zusammen mit konkaven Bedingungen vor. Diese Anwendung kommt aus dem Constraint Programming welches sich in den letzten Jahren immer größerer Beliebtheit bei der Lösung von Optimierungs- und Entscheidungsproblemen erfreut. Konkave Bedingungen beinhalten sowohl eine Vielzahl elementarer Constraints wie logische Verknüpfungen, Implikationen und Ausschlüsse, als auch lineare Nebenbedingungen. Darüberhinaus sind beliebige konkave Funktionen verwendbar, wie sie beispielsweise in Wachstums- und Zerfallsprozessen vorkommen. Wir präsentieren umfangreiche Beispiele, wie grundlegende Optimierungsprobleme innerhalb dieses Paradigmas modelliert werden können. Desweiteren entwickeln wir Algorithmen, die die Unzulässigkeit eines gegebenen Constraintsystems feststellen. Das letzte Kapitel beschäftigt sich mit der Optimierung von Produktionslinien zur Platinenbestückung. Die Fertigung muß den immer kürzer werdenden Entwicklungszyklen und der enormen Bandbreite an verschiedenen Artikeln nachkommen und eine flexible Produktion ermöglichen. Damit verbunden sollen unprofitable Rüstzeiten nach Möglichkeit vermieden werden. Daher wird versucht, mit einer Komponentenbelegung möglichst viele verschiedene Platinen zu produzieren, während kleinere Variationen im Setup der Maschine während des Produktionsprozesses mithilfe spezieller austauschbarer Rollwagen, welche die Komponenten beherbergen, vorgenommen werden können. Diese Verfahrensweise impliziert eine Aufteilung der Menge von Platinentypen in verschiedene Gruppen. Zwischen den einzelnen Gruppen findet eine Variation eines Teils des Setups statt, während der Großteil des Setups jedoch über den kompletten Produktionsprozeß hinweg bestehen bleibt. Die Schwierigkeit bei dieser Vorgehensweise besteht zum einen darin, eine möglichst ideale Gruppierung von Modulen zu finden, zum anderen darin, die Bauteile so auf die parallelen Bestückungsautomaten zuzuweisen, daß diese möglichst gut ausgelastet sind. Dieses Problem kann als Verallgemeinerung des Bin Packing Problems mit zusätzlichen Nebenbedingungen verstanden werden. Wir zeigen, daß dieses Problem NP-vollständig ist. Im Rahmen einer Kooperation mit Philips Assembléon in Eindhoven wurden spezielle Algorithmen zur Gruppierung von Modulen und zur effizienten Berechnung von Maschinensetups für den oben genannten Fall entwickelt. Die entstandenen Verfahren wurden an realen Daten aus Kundenaufträgen getestet und mit anderen aus der Literatur bekannten Verfahren verglichen. Dabei stellte sich heraus, daß die Anwendung der entwickelten Algorithmen neben gewisser anderer Vorteile zu einem wesentlich höheren Produktionsdurchsatz führt. Darüberhinaus konnte die Laufzeit der Optimierungssoftware um ein Vielfaches verkürzt werden.German
Uncontrolled Keywords: Algorithms, Assembly Line Optimization, Bin Packing, Constraint Programming, Cutting Stock
Alternative keywords:
Alternative keywordsLanguage
Algorithms, Assembly Line Optimization, Bin Packing, Constraint Programming, Cutting StockEnglish
Classification DDC: 600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften
000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:23