U-shaped Assembly Line Balancing Problem and GA-Based Solving Approaches

In accordance with the character of U-shaped assembly line balancing problem (UALBP), this paper presents a real number encoding operation called “priority-based real number encoding operation”. According to let the chromosomes generate more uniform and quick, this paper also presents a crossover operation called “gene value exchange crossover operation”. Finally this paper presents a decoding operation called “priority-based decoding operation” to support genetic algorithm and display the U-shaped assembly line layout and relative data. “Priority-based decoding operation” is an operation which assign tasks to workstation depend on a forward task permutation and a backward task permutation. Those two task permutations all generate by gene values in the same chromosome. To justify our genetic algorithm model, we use UALBP benchmarks to verify model and analysis the results. The results show that using our genetic algorithm model can find the global optimal solution in some benchmarks. Compare with different objective functions in mathematical models, we find the result that using maximize line efficiency to be the objective function isn’t good enough to solve UALBP. Using minimize variation of workload or minimize sum of workstation idle time square to be the objective function can find better solutions than maximize line efficiency. This paper presents the genetic algorithm solving model can efficiently solve UALBP, and it also can help the engineer to do decisions.