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

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

从聚类角度研究差异工件批调度这一组合优化问题.论证了差异工件的分批问题实质为一种广义聚类问题,为求解批调度问题提供了一个全新的途径.提出了批的空间浪费比的概念,将最小化批的总加工时间目标变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明.此外,以批的空间浪费比为基础,进一步定义了批间的距离度量,提出了批的约束凝聚聚类算法(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.