两阶段流水车间批处理机调度的聚类算法  

Clustering Algorithm for Two-stage Flow Shop Batch Processor Schedule

作　　者：郝尚刚[1] 陈华平[1,2] 李小林[1] 

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

出　　处：《计算机工程》2012年第14期272-275,279,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(70821001;71171184)

摘　　要：针对两阶段流水车间环境下,工件尺寸不同的批处理机调度问题,提出一种以最小化制造期为目标、满足机器容量约束的凝聚聚类调度算法。结合目标函数的特点,利用基于内部和外部2类空间浪费比的变化量定义距离函数,对工件进行分批处理,并使用Johnson规则排序。实验结果表明,在大规模算例情况下,该算法比已有算法更高效,具有更好的鲁棒性。This paper proposes a clustering algorithm to minimize the makespan in a two-stage flow shop with batch processor schedule problem and non-identical job sizes. Considering characteristics of the objective function, the distance function between two batches is defined based on two concepts of internal and external space Waste Ratio（WR）. This algorithm is proposed to solve the batching problem by this distance and the sorting problem by Johnson algorithm. Experimental results show that this algorithm is more effective than the existing algorithms, and has better robustness.

关 键 词：流水车间 调度算法 批处理机 聚类 空间浪费比 启发式方法 

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