Genetic algorithm for assembly line balancing

Research on single-model assembly line balancing has produced several good algorithms for solving large problems. The majority of these algorithms generate just one solution to the problem, whereas the real line design faces the need to investigate alternative solutions, where preferences for work allocation to stations are considered, or constraints other than technological precedence are taken into account. The MUST algorithm suggested by Dar-El and Rubinovitch is one of the few algorithms that provides such diversity of solutions. Heuristics enable MUST to solve relatively large line-balancing problems. However, when the initial problem has relatively few constraints, the time and memory requirements needed by MUST may become excessive. This paper describes the development and testing of a Genetic Algorithm for the generation of multiple solutions to the assembly line balancing (ALB) problem. The results are compared with MUST results for different classes of problems. Good results are achieved by combining the genetic approach with a simple local optimization procedure. This procedure performs much faster than MUST for problems with large number of stations and high flexibility ratio. Different crossover and mutation procedures are tested and evaluated, in order to recommend these which are most effective for solving ALB problems.