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

Scheduling a single batching machine with non-identical job release times and sizes using ant colony clustering

作　　者：杜冰[1] 陈华平[1] 邵浩[1] 许瑞[1] 李小林[1] 

机构地区：[1]中国科学技术大学管理学院,合肥230026

出　　处：《系统工程理论与实践》2010年第9期1701-1709,共9页Systems Engineering-Theory & Practice

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

摘　　要：研究具有不同到达时间的差异工件在单机环境下的批调度问题.通过引入工件单元的概念并对分批约束进行松弛,提出了该问题的一个新的下界,证明了该下界的有效性.将蚁群算法和聚类算法相结合,提出了一种基于多阶段聚类的蚁群聚类算法ACC(Ant colony clustering).算法首先利用K-均值聚类将工件分簇,在簇内部通过蚁群算法搜索分批,最后提出一个全局优化算法对局部分批结果进行合成和优化.克服了蚁群算法随着工件规模增大求解时间过长的问题,适合于求解大规模算例.实验结果表明:与现有的启发式规则LPTBFF(Longest processing time & batchfirst fit)和HGA(Hybrid Genetic algorithm)算法相比,该算法求解效果更好.This paper studies the problem of scheduling a batch processing machine with non-identical job release times and job sizes. By introducing the concept of job unit and relaxing batching constraint, we proposed a new lower bound of the problem and prove its validity. An Ant Colony Clustering Algorithm based on multi-stage clustering was also presented. The algorithm adopts K-mean algorithm to divide jobs into k clusters and uses ACO to search batching plan in these clusters subsequently. A global process was then proposed to synthesize and optimize local batching plans. The algorithm can improve the efficiency of traditional ACO and is suitable for the cases with large job number. The experimental results show that ACC achieves better effectiveness than the existing approaches such as LPTBFF （Longest Processing Time ＆ Batch First Fit） and HGA （Hybrid Genetic Algorithm）.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]