Exact and Heuristic Algorithms for Balancing Transfer Lines with Simultaneously Activated Spindle Heads : A Computational Evaluation

http://www.emse.fr/spip/IMG/pdf/RR_2005-500-001.pdfA balancing problem for transfer lines with workstations in series and simultaneously activated spindle heads is considered. The problem is to choose a block of operations for each spindle head from a given set of the blocks and to assign them to workstations while minimizing the line cost and satisfying technological constraints (precedence relation, inclusion constraints related to operations and exclusion constraints with regard to blocks). Exact and heuristic algorithms are developed. Exact algorithms are based on graph and MIP approaches. Three heuristic algorithms are proposed. One of them assigns randomly step by step blocks to a current workstation. The second algorithm uses depth-first search technique. The third algorithm is based on a decomposition of the initial problem into several sub-problems and solving them by an exact algorithm. Experimental results are presented