具有不同到达时间的差异工件批调度问题的蚁群聚类算法

摘要：

研究具有不同到达时间的差异工件在单机环境下的批调度问题.通过引入工件单元的概念并对分批约束进行松弛,提出了该问题的一个新的下界,证明了该下界的有效性.将蚁群算法和聚类算法相结合,提出了一种基于多阶段聚类的蚁群聚类算法ACC(Ant colony clustering).算法首先利用К-均值聚类将工件分簇,在簇内部通过蚁群算法搜索分批,最后提出一个全局优化算法对局部分批结果进行合成和优化.克服了蚁群算法随着工件规模增大求解时间过长的问题,适合于求解大规模算例.实验结果表明:与现有的启发式规则LPTBFF(Longest processing time&batch first fit)和HGA(Hybrid Genetic algorithm)算法相比,该算法求解效果更好.

关键词：调度、批处理机、聚类、蚁群算法、组合优化

所属期刊栏目：30

分类号：TP301(计算技术、计算机技术)

资助基金：创新研究群体科学基金70821001;国家自然科学基金70671096;国家杰出青年基金B类70629002;博士点基金项目200803580024

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

页数：共9页

页码：1701-1709