A relative position-coded differential evolution for loop-based station sequencing problem

Abstract

Loop layout is very common in flexible manufacturing systems. The quality of the layout scheme directly affects productivity of flexible manufacturing systems. The loop-based station sequencing problem (LSSP) that determines the arrangement of the facilities around a closed loop belongs to the category of the combinatorial optimisation problem, which is known to be NP-Hard. Therefore, the heuristic and meta-heuristic methods are generally adopted to solve the LSSP. In order to improve the existing methods, this paper takes into consideration the permutation property of the LSSP, and proposes an integer-coded differential evolution (DE) algorithm, named as relative position-coded DE. Compared with existing real-coded DEs, the proposed algorithm possesses the following favourable characteristics: (1) it does not need mapping from floating point vectors to integer sequence; (2) the coding space of the new algorithm corresponds with the solution space of LSSP; (3) it avoids the illegal chromosomes in the solving process. Experimental results showed that the proposed relative position-coded DE outperforms the existing DEs, GA, PSO, and SA, especially in the case of large-scale LSSP.

Keywords:

• flexible manufacturing systems
• loop layout problem
• differential evolution
• non-redundant coding

View correction statement:

A relative position-coded differential evolution for loop-based station sequencing problem

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant No. 60674078, 50575031) and National High-tech R&D Program (863 Program) of China (Grant No. 2006AA04Z109).