Solution techniques for specific bin packing problems with applications to assembly line optimization [Elektronische Ressource] / von Wolfgang Stille

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2008
• Nombre de lectures: 33
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Solution Techniques
for specific
Bin Packing Problems
with Applications to
Assembly Line Optimization
Zur Erlangung des Grades eines Doktors der Naturwissenschaften (Dr. rer. nat.) vom Fach–
bereich Informatik genehmigte Dissertation von Dipl.-Math. Wolfgang Stille aus Göppingen
Juni 2008 — Darmstadt — D 17
Fachbereich Informatik
Fachgebiet AlgorithmikSolution Techniques
for specific
Bin Packing Problems
with Applications to
Assembly Line Optimization
vom Fachbereich Informatik genehmigte Dissertation von Dipl.-Math. Wolfgang Stille aus Göp-
pingen
1. Gutachten: Prof. Dr. Karsten Weihe
2. Gutachten: Prof. Dr. Matthias Müller-Hannemann
Tag der Einreichung: 19. Mai 2008
Tag der Prüfung: 30. Juni 2008
Darmstadt — D 176
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 = 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 pre-
sented 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 effi-
ciently 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 algo-
rithms, 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
1Abstracthold 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 isNP-complete.
In the scope of an industrial cooperation project with Philips Assembléon in Eindhoven, we devel-
oped 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 optimiza-
tion software.
2 Abstract6
Zusammenfassung
Die vorliegende Arbeit beschäftigt sich mit Techniken zur Lösung von speziellen BIN PACKING Proble-
men 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 An-
wendung widmen wir uns im letzten Kapitel der Optimierung von Fertigungslinien für die Leiterplat-
tenbestü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 Ob-
jekten 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 = NP 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 Prob-
lems 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ösungsver-
fahren entwickelt. Das Verfahren berechnet in polynomialer Zeit Lösungen, die maximal einen Behäl-
ter 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 ef-
fizient 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 Con-
straints 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
au