A modified colonial competitive algorithm for the mixed-model U-line balancing and sequencing problem

Abstract

Implementation of mixed-model U-shaped assembly lines (MMUL) is emerging and thriving in modern manufacturing systems owing to adaptation to changes in market demand and application of just-in-time production principles. In this study, the line balancing and model sequencing (MS) problems in MMUL are considered simultaneously, which results in the NP-hard mixed-model U-line balancing and sequencing (MMUL/BS) problem. A colonial competitive algorithm (CCA) is developed and modified to solve the MMUL/BS problem. The modified CCA (MCCA) improves performance of original CCA by introducing a third type of country, independent country, to the population of countries maintained by CCA. Implementation details of the proposed CCA and MCCA are elaborated using an illustrative example. Performance of the proposed algorithms is tested on a set of test-bed problems and compared with that of existing algorithms such as co-evolutionary algorithm, endosymbiotic evolutionary algorithm, simulated annealing, and genetic algorithm. Computational results and comparisons show that the proposed algorithms can improve the results obtained by existing algorithms developed for MMUL/BS.

Keywords:

• mixed-model U-line balancing and sequencing
• colonial competitive algorithm
• genetic algorithm

Acknowledgements

The authors thank the anonymous referees whose comments helped considerably to improve this paper. This research is supported by the State Key Programme of the National Natural Science Foundation of China (Grant No. 51035001), National Natural Science Foundation of China (Grant No. 50825503), the National High-Tech Research and Development Programme of China 863 Programme (Grant No. 2007AA04Z107) and the National Natural Science Foundation of China (Grant No. 50875101).