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

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

单位：中国科学技术大学管理学院 合肥230026