摘要：从聚类角度研究差异工件批调度这一组合优化问题.论证了差异工件的分批问题实质为一种广义聚类问题,为求解批调度问题提供了一个全新的途径.提出了批的空间浪费比的概念,将最小化批的总加工时间目标变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明.此外,以批的空间浪费比为基础,进一步定义了批间的距离度量,提出了批的约束凝聚聚类算法（constrained agglomerative clustering of batches,CACB）.实验结果表明,与现有的BFLPT（best-fit longest processing time）启发式规则和GA（genetic algorithm）等算法相比,CACB在大规模算例的情况下更为有效.

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

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