Simple assembly line balancing - heuristic approaches

In this paper heuristics for Type 1 and Type 2 of the Simple Assembly Line Balancing Problem (SALBP) are described. Type 1 of SALBP (SALBP-1) consists of assigning tasks to work stations such that the number of stations is minimized for a given production rate whereas Type 2 (SALBP-2) is to maximize the production rate, or equivalently, to minimize the sum of idle times for a given number of stations. In both problem types, precedence constraints between the tasks have to be considered. We describe bidirectional and dynamic extensions to heuristic priority rules widely used for SALBP-1. For the solution of SALBP-2 we present search methods which involve the repetitive application of procedures for SALBP-1. Furthermore, improvement procedures for SALBP-2 are developed and combined with tabu search, a recent strategy to overcome local optimality. Several optional elements of tabu search are discussed. Finally, the application of a nontraditional tabu search approach to solve SALBP-1 is investigated. Computational experiments validate the effectiveness of our new approaches.