聚类视角下的差异工件平行机批调度问题  

Scheduling parallel batching machines with non-identical job sizes from a clustering perspective

作　　者：杜冰[1] 陈华平[1] 杨勃[1] 李小林[1] 

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

出　　处：《管理科学学报》2011年第12期27-37,共11页Journal of Management Sciences in China

基　　金：创新研究群体科学基金资助项目(70821001);博士点基金资助项目(200803580024)

摘　　要：从聚类角度研究差异工件批调度这一组合优化问题.论证了差异工件的分批问题实质为一种广义聚类问题,为求解批调度问题提供了一个全新的途径.提出了批的空间浪费比的概念,将最小化批的总加工时间目标变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明.此外,以批的空间浪费比为基础,进一步定义了批间的距离度量,提出了批的约束凝聚聚类算法(constrained agglomerative clustering of batches,CACB).实验结果表明,与现有的BFLPT(best-fit longest processing time)启发式规则和GA(genetic algorithm)等算法相比,CACB在大规模算例的情况下更为有效.The problem of scheduling parallel batch processing machines is considered from a clustering perspective in this paper. We first demonstrate that the batching problem with non-identical job sizes can be regarded as a generalized clustering problem, providing a novel insight into scheduling with hatching. The concept of WR （ waste ratio of batch space） is then presented and the objective function of minimizing makespan is transformed into minimizing weighted WR so as to define the distance measure between batches in a more understandable way. The equivalence of the two objective functions is also proved. In addition, a clustering algorithm CACB （ constrained agglomerative clustering of batches） is proposed based on the definition of WR to generate batches. The experimental results show that CACB outperforms the existing approaches BFLPT （best-Fit longest processing time） and GA （genetic algorithm） in large-scale problems.

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

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