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

A Multi-agent Evolutionary Algorithm for Solving Total Tardiness Permutation Flow-shop Scheduling Problem

作　　者：王大志[1,2] 刘士新[1,2] 郭希旺[1,2] 

机构地区：[1]东北大学信息科学与工程学院系统工程研究所,沈阳110819 [2]流程工业综合自动化教育部重点实验室,沈阳110819

出　　处：《自动化学报》2014年第3期548-555,共8页Acta Automatica Sinica

基　　金：国家自然科学基金(61333006;71171038);中央高校基本科研业务费(N110404024)资助~~

摘　　要：针对总拖期时间最小化的置换流水车间调度问题(Total tardiness permutation flow-shop scheduling problem)提出了一种基于多智能体的进化搜索算法.在该算法中,采用基于延迟时间排序的学习搜索策略(Tardiness rank based learning),快速产生高质量的新个体,并根据概率更新模型进行智能体网格的更新进化.同时通过实验设计的方法探讨了算法参数设置对算法性能的影响.为了验证算法的性能,求解了Vallada标准测试集中540个测试问题,并将测试结果与一些代表算法进行比较,验证了该算法的有效性.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.

关 键 词：流水车间调度 总拖期时间 多智能体 进化算法 

分 类 号：TH186[机械工程—机械制造及自动化]