A genetic algorithm for the balancing and sequencing problem in the mixed-model U-line

The mixed-model assembly line has been widely studied by many researchers in the operations management field. The two fundamental optimization problems (i.e. the balancing problem and the sequencing problem) have often been investigated in a separate manner. Although the two problems are actually interrelated, very few researchers have solved both of them simultaneously. In this paper, we study the integrated balancing and sequencing problem in a mixed-model U-line (MMUL/BS) with the objective of minimizing ADW (Absolute Deviation of Workstation). A constrained optimization model has been developed for describing the problem. Due to the NP-hardness of MMUL/BS we present a genetic algorithm combined with greedy rules. Based on the traditional genetic algorithm, we have proposed improvement strategies for the encoding, decoding, crossover and mutation operators. The algorithm achieves a successful balance between efficiency and solution quality by combining the genetic algorithm with the heuristic rules. Finally, this algorithm is applied to a previously studied problem instance and a better solution is obtained.