A modularity-based improved small-world genetic algorithm for large-scale intercell scheduling with flexible routes

Intercell scheduling arises due to intercell movements of exceptional parts in cellular manufacturing system. With the shift to large-scale production in manufacturing, existing algorithms struggle to obtain ideal solutions in an acceptable time because search space grows exponentially with size of problems. Large-scale intercell scheduling with flexible routes is addressed and a scheduling optimization model aiming at minimizing makespan and total cost is established. To improve performance of metaheuristic algorithms in solving the large-scale optimization model, potential relationships between complex network feature and scheduling optimization objectives are explored. It is shown that a scheduling scheme with larger modularity would optimize makespan and total cost for its complex network model. A modularity-based improved small-world genetic algorithm (SWGABM) is proposed. A modularity-based initial population generation method which combines individuals with high modularity and random individuals is proposed to improve quality while maintaining diversity. Additionally, a selection mechanism based on modularity is designed in crossover operator, where one offspring individual with larger modularity is retained with a decreasing probability during the iteration process. It guides search direction and improves convergence speed. To evaluate the performance of SWGA-BM, it is first compared with Cplex on eight small-scale problems. The results indicate that SWGA-BM has a significant advantage with respect to computational time and solution quality. Then effectiveness of two improvement terms is verified by comparison on 11 large-scale problems. Finally, comparison on 41 large-scale problems show that SWGA-BM outperforms both NSGA-II and DPSO in terms of solution quality, diversity and convergence. It is verified that complex network feature can be used to improve performance of a metaheuristic algorithm. It provides a new perspective for effectively addressing large-scale challenge by analyzing, extracting and utilizing complex network feature of scheduling problems.