A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements

• We consider U-shaped assembly lines with equipment assignment decisions and fixed number of workstations.
• We aim to assign the tasks and equipments to the workstations so as to minimize the total equipment cost.
• We present a mathematical model and a branch and bound procedure.
• Our computational study has revealed the satisfactory behavior of our branch and bound procedure.

In this study we consider a U-shaped assembly line balancing problem where each task uses a specified set of equipments and each type of equipment has a specified cost. Our problem is to assign the tasks together with their equipments to the workstations so as to minimize the total equipment cost. We formulate the problem as a mixed integer linear programming model that is capable of solving small sized instances. We propose a branch and bound algorithm that uses efficient precedence relations and lower bounds. We find that the algorithm is able to solve moderate sized problem instances in reasonable times.