Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads

In this paper, a new transfer line balancing problem is considered. The main difference from the simple assembly line balancing problem is that the operations are grouped into blocks (batches). All the operations of the same block are carried out simultaneously by one piece of equipment (multi-spindle head). Nevertheless, the blocks assigned to the same workstation are executed in series. The line cost consists of the sum of block and workstation costs. At the considered line design stage, the set of all available blocks is given. The aim is to find a subset from the given set of available blocks and to find a partition of this subset to workstations such that each operation is executed once and the line cost is minimal while all the precedence, cycle time, and compatibility (operation inclusion and block exclusion) constraints are respected. A new lower bound based on solving a special set partitioning problem is presented and a branch and bound algorithm is developed. The experimental results prove the quality of the lower bound and applicability of the suggested branch and bound algorithm for medium sized industrial cases.