Applying genetic algorithms to the U-shaped assembly line balancing problem

The traditional assembly line balancing problem considers the manufacturing process of a product where production is specified in terms of a sequence of tasks that need to be assigned to workstations. Each task takes a known number of time units to complete. Also, precedence constraints exist among tasks: each task can be assigned to a station only after all its predecessors have been assigned to stations. The U-shaped assembly line balancing problem is a relatively new problem derived from the traditional assembly line balancing problem. In the U-shaped assembly line balancing problem tasks can be assigned to stations either after all its predecessors or all of its successors have been assigned to stations. This paper presents a genetic algorithm (GA) solution to the Type I U-shaped assembly line balancing problem. Our research provides a global framework which can be used to deal with the two possible variations of this problem, minimizing total idle time, and balance of the workload among stations, or a combination of both. We developed six different assignment algorithms as a means for interpreting a chromosome and assigning tasks to workstations. The results show the GA to be an excellent technique for this problem. In the 61 standard test cases from the literature, our GA obtained the same results as previous researchers in 49 cases, superior results in II cases, and in only one case did worse. Moreover, the GA proved to be computationally efficient.