Premium
Exact and heuristic algorithms for balancing transfer lines when a set of available spindle heads is given
Author(s) -
Dolgui Alexandre,
Guschinsky Nikolai,
Levin Genrikh
Publication year - 2008
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2008.00635.x
Subject(s) - computer science , heuristic , set (abstract data type) , workstation , integer programming , algorithm , programming language , operating system , artificial intelligence
A balancing problem for paced tandem transfer lines with several spindle heads at each station is considered. A spindle head executes a block of operations. The set of all available spindle heads as well as the operations executed by each spindle head, the spindle head times and costs are known. There are operations with several spindle head candidates. The problem at the line design stage consists in the choice of spindle heads from the given set and their assignment to workstations. The goal is to minimize the line cost while satisfying the precedence, inclusion and exclusion constraints. An exact algorithm based on a mixed integer programming approach is developed. Two types of new heuristic algorithms are also suggested. One of them step‐by‐step assigns randomly spindle heads to a current workstation. The second uses depth‐first search techniques. Experimental results are reported.