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

• 作者: 李小林 杜冰 杨勃 陈华平
• 来源期刊: 管理科学学报
• 学科: 工学
• 关键词: 调度 批处理机 聚类 组合优化
• 年，卷（期）: 2011,（12）
• 所属期刊栏目: 论文
• 页码范围: 27-37
• 分类号: TP301
• 字数: 8011字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈华平	中国科学技术大学管理学院	72	1503	19.0	36.0
2	李小林	中国科学技术大学管理学院	11	101	7.0	10.0
3	杜冰	中国科学技术大学管理学院	11	109	6.0	10.0
4	杨勃	中国科学技术大学管理学院	4	33	2.0	4.0