An enumerative heuristic and reduction methods for the assembly line balancing problem

A new heuristic algorithm and new reduction techniques for the type 1 assembly line balancing problem are presented. The new heuristic is based on the well-known Hoffmann heuristic and builds solutions from both sides of the precedence network to choose the best. The reduction techniques aim at augmenting precedences, conjoining tasks and increasing operation times. The heuristic is tested on its own and also in combination with the reduction techniques. The tests, which are carried out on a well-known benchmark set of problem instances, testify to the efficacy of the combined algorithm, in terms of both solution quality and optimality verification, as well as to its computational efficiency.