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

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