基于带随机网络的多种群粒子群优化算法求解多资源受限柔性作业车间调度问题

A multi-population particle swarm optimization algorithm with random network for solving multi-resource constrained flexible job shop scheduling problems

多资源受限柔性作业车间调度问题(MRC-FJSP,multi-resource constrained flexible job shop scheduling problem)是一类复杂的组合优化问题。针对以最小化最大完工时间为目标的MRC-FJSP,提出了一种带随机网络的多种群粒子群优化算法(MPSO-RDnet,multi-population particle swarm optimization algorithm with random network)。首先,设计了一种半主动解码和基于启发式规则解码相结合的新型解码方式,对原有解空间进行有效裁剪。其次,提出了基于关键路径的两种邻域结构,提高算法局部搜索能力;引入了基于随机网络的多种群策略,提高算法全局搜索能力;提出了面向算法搜索停滞问题的重新初始化策略,增强算法的鲁棒性。最后,采用MRC-FJSP基准算例SFTSP进行测试,验证了算法的可行性和有效性。

Multi-resource constrained flexible job shop scheduling problem(MRC-FJSP)is a kind of complex combinatorial optimization problem.A multi-population particle swarm optimization algorithm with random network(MPSO-RDnet)was proposed for solving MRC-FJSP with the objective to minimize makespan.First,a new decoding method which combines semi-active decoding and heuristic rule decoding was designed.The original solution space was cut out effectively.Second,two neighborhood structures based on the critical path were designed to improve the local search ability of the population,and a multi-population strategy based on the random network structure graph was added to improve the global search ability of the algorithm.A reinitialization strategy for the algorithm search stagnation was proposed to enhance the robustness of the algorithm.Numerical experiments verified the effectiveness and efficiency of proposed algorithm.