Optimally solving theAlternative Subgraphs AssemblyLine Balancing Problem

Assembly line balancing problems (ALBP) consist of distributing the total workload for manufacturingany unit of the products to be assembled among the work stations along a manufacturing line as used inthe automotive or the electronics industries. Usually, it is assumed that the production process is fixed,i.e., has been determined in a preceding planning step. However, this sequential planning approach isoften suboptimal because the efficiency of the production process can not be evaluated definitely withoutknowing the distribution of work. Instead, both decisions should be taken simultaneously. This hasled to the Alternative Subgraphs ALBP.We give an alternative representation of the problem, formulate an improved mixed-integer programand propose a solution approach based on SALOME, an effective branch&bound procedure for thewell-known Simple ALBP. Computational experiments indicate that the proposed procedure is successfulin finding optimal solutions for small- and medium-sized problem instances and rather good heuristicsolutions for large-scaled instances....