Cost-oriented assembly line balancing: Model formulations, solution difficulty, upper and lower bounds

This paper deals with cost-oriented assembly line balancing. First we focus on the special objective function and a formal problem statement. Then we concentrate on general model formulations that can be solved by standard optimisation tools and introduce several improvements to existent models. These models are designed for either general branch-and-bound techniques with LP-relaxation or general implicit enumeration techniques. Further we discuss the solution difficulty of the problem and show that the “maximally-loaded-station-rule” has to be replaced by the “two-stations-rule”. Compared to the time-oriented version, this causes an enormous increase in solution difficulty. We introduce improved and new bounds for the number of stations and for the relevant costs per product unit. These are used in the general model formulations as well as in specially designed optimisation methods. Finally we give a brief overview of these specially designed methods that are discussed in detail in Amen (2000a,b, 2001).