Balancing modular transfer lines with serial–parallel activation of spindle heads at stations

The paper deals with an as yet unexplored combinatorial optimization problem concerning balancing complex transfer lines in the machining/process environment. In contrast to similar problems for assembly lines, in transfer line balancing, tasks are grouped into blocks. All tasks of each block are executed simultaneously (in parallel) by one piece of equipment (spindle head). For the transfer lines considered in this paper, spindle heads at each station are activated in serial–parallel order. The set of all available spindle heads is known beforehand. Precedence, cycle time, compatibility, and parallelism constraints for the blocks and tasks are given. The line investment cost is estimated by the sum of block and station costs. The problem is to assign all tasks (using the available blocks) such that all constraints are respected and line investment cost is at a minimum. This paper focuses on solving the problem via a branch-and-bound algorithm. An approach for obtaining an efficient lower bound is offered, based on a reduction of the initial problem to a set partitioning problem. Computational experiments reveal that the proposed approach is efficient mathematically and can be used to solve practical transfer line design problems of a medium size.