基于差分进化算法的FMS中机器与AGV同时调度方法

An improved differential evolution algorithm for simultaneousscheduling of machines and AGVs in an FMS

针对柔性制造系统中机器与AGV(automated guided vehicle)同时调度问题,提出一种混合变邻域搜索的改进离散差分进化算法。以最大完工时间最小为优化目标,考虑机器与AGV双资源约束,建立相应的数学模型。为了同时调度机器与AGV,采用基于工序、机器、AGV的3层编码结构。通过改进差分进化(differential evolution,DE)算法的变异、交叉算子产生新个体以提高算法的全局搜索能力,并引入模拟退火算法中解的接受准则选择下一代。同时,为了增强算法的局部搜索能力,对算法每次迭代的最优个体进行变邻域搜索。通过算例计算和对比,证明了提出的改进DE算法的有效性、稳定性和优越性。

An improved discrete differential evolution algorithm with variable neighborhood search was proposed for solving simultaneous scheduling of machines and AGVs in flexible manufacturing systems.With the optimization goal of making the maximum completion time minimum,considering the dual resource constraints of machines and AGVs,the corresponding mathematical model was established.The three-layer coding structure of operation,machine and AGV was employed to schedule machines and AGVs simultaneously.In order to improve the global search capability,the differential evolution algorithm generated new individuals by improved mutation and crossover operators,and introduced the acceptance criterion of solution in simulated annealing algorithm to select next generation.Furthermore,a variable neighborhood search was performed on the optimal individual in each iteration of the algorithm in order to enhance the local search capability.Finally,the effectiveness,stability and superiority of the improved differential evolution algorithm were proved by calculation and comparison of examples.