摘要： 针对两阶段流水车间环境下，工件尺寸不同的批处理机调度问题，提出一种以最小化制造期为目标、满足机器容量约束的凝聚聚类调度算法。结合目标函数的特点，利用基于内部和外部2类空间浪费比的变化量定义距离函数，对工件进行分批处理，并使用Johnson规则排序。实验结果表明，在大规模算例情况下，该算法比已有算法更高效，具有更好的鲁棒性。

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

Abstract: 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.

Key words: flow shop, schedule algorithm, batch processor, clustering, space Waste Ratio(WR), heuristic method

中图分类号: 

• TP301.6