求解总拖期时间最小化流水车间调度问题的多智能体进化算法

摘要

In this research, we propose a multi-agent evolution-ary algorithm for the permutation flow-shop scheduling problem (PFSP) considering the total tardiness minimization criterion. The algorithm includes the tardiness rank based learning scheme to generate high quality solution by using the specific knowledge of the related problem. We also develop and integrate the prob-ability acceptance model into the proposed algorithm to evolve the whole agent lattice network. A complete calibration of the different parameters of the proposed algorithm by means of a design of experiment approach is given. Using the 540 bench-mark problems, a comparative evaluation with other heuristic methods in the literature have been carried out. The results show that the proposed algorithm is effective and competitive.%针对总拖期时间最小化的置换流水车间调度问题(Total tar-diness permutation flow-shop scheduling problem)提出了一种基于多智能体的进化搜索算法。在该算法中，采用基于延迟时间排序的学习搜索策略(Tardiness rank based learning)，快速产生高质量的新个体，并根据概率更新模型进行智能体网格的更新进化。同时通过实验设计的方法探讨了算法参数设置对算法性能的影响。为了验证算法的性能，求解了Vallada 标准测试集中540个测试问题，并将测试结果与一些代表算法进行比较，验证了该算法的有效性。