A Discrete Particle Swarm Optimization Algorithm for Assembly Line Balancing Problem of Type 1

A discrete particle swarm optimization (DPSO) algorithm is presented for the assembly line balancing problem of type 1, ALBP-I. A new permutation encoding method is developed to make the particle correspond to a feasible operation sequence (FOS) which satisfies the precedence constrains of assembly tasks. A position based crossover operator for permutation encoding is unitized to update the particle. Based on the encoding method and particle updating mechanism, the DPSO is employed to find the optimum efficiently in the search space comprising the optimal assignments associated with all FOSs. The DPSO algorithm is tested on a set of problems taken from the literature and compared with other approaches. The computational results show the effectiveness and efficiency of the proposed algorithm.