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

摘要：

研究了工件带到达时间的目标为极小最大完工时间(Cmax)的单机批调度问题,采用最大-最小蚂蚁系统(max-min ant system,MMAS)进行求解.针对问题带到达时间以及分批的特性,提出了两种候选列表(candidate list)构建批序列,有效地缩小了搜索空间的维度；考虑两种候选列表的工件对构造解具有不同的影响,针对不同的候选列表设计了相应的启发式信息.仿真实验部分从求解质量和时间性能两方面比较了本文提出的算法和标准的蚂蚁系统(ant system,AS)算法以及使用不同候选列表的MMAS算法.结果表明,本文的算法在质量和时间两方面均全面优于标准的AS算法,而提出的候选列表使得该算法在大幅度提高时间性能的同时,仍然能够取得近似最优解,从而在求解质量和时间性能两方面取得平衡.

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

所属期刊栏目：26

分类号：TP273(自动化技术及设备)

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

在线出版日期：2012-01-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：474-484