基于MMAS算法的带到达时间批调度问题研究  

Research on batch scheduling problem with job release time based on max-min ant system

作　　者：许瑞[1] 陈华平[1] 朱俊红[2] 

机构地区：[1]中国科学技术大学管理学院,安徽合肥230027 [2]合肥工业大学管理学院,安徽合肥230009

出　　处：《系统工程学报》2011年第4期474-484,共11页Journal of Systems Engineering

基　　金：创新研究群体科学基金资助项目(70821001);国家自然科学基金资助项目(70821001);博士点基金资助项目(200803580024);中国科学技术大学研究生创新基金资助项目(KD2008073)

摘　　要：研究了工件带到达时间的目标为极小最大完工时间(C_(max))的单机批调度问题,采用最大-最小蚂蚁系统(max-min ant system,MMAS)进行求解。针对问题带到达时间以及分批的特性,提出了两种候选列表(candidate list)构建批序列,有效地缩小了搜索空间的维度;考虑两种候选列表的工件对构造解具有不同的影响,针对不同的候选列表设计了相应的启发式信息.仿真实验部分从求解质量和时间性能两方面比较了本文提出的算法和标准的蚂蚁系统(ant system,AS)算法以及使用不同候选列表的MMAS算法.结果表明,本文的算法在质量和时间两方面均全面优于标准的AS算法,而提出的候选列表使得该算法在大幅度提高时间性能的同时,仍然能够取得近似最优解,从而在求解质量和时间性能两方面取得平衡.This paper studies the batch scheduling problem with job release time whose aim is to minimize the makespan using max-min ant system （MMAS）. Based on the characteristics of job release time and hatching, two kinds of candidate list （CL） were proposed to construct batch sequence, which can reduce the dimension of search spaces effectively. Considered the different influences of two CLs on constructing solution, correspond- ing heuristic information was designed for each CL. In the computational experiment, the algorithm proposed in this paper was compared with the pure ant system （AS） and the MMAS algorithm with different CLs in the respects of solution quality and execution time. The results demonstrate that our algorithm outperforms the pure AS algorithm in the above two respects. And the novel way making use of CL helps the algorithm lighten the computational burden significantly, while obtain near-optimal solutions. It can thus provide a good tradeoff between solution quality and execution time.

关 键 词：批调度 到达时间 最大完工时间 蚁群算法 最大-最小蚂蚁系统 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]