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

第 14 卷第 12 期 2011 年 12 月 管理科学学报 Vol. 14 No. 12 Dec.2011 JOURNAL OF MANAGEMENT SCIENCES IN CHINA 聚类视角下的差异工件平行机批调度问题① 杜冰，陈华平，杨勃，李小林 (中国科学技术大学管理学院，合肥 23∞26) 摘要:从聚类角度研究差异工件批调度这一组合优化问题.论证了差异工件的分批问题实质 为一种广义聚类问题，为求解批调度问题提供了一个全新的途径.提出了批的空间浪费比的概 念，将最小化批的总加工时间目栋变换为最小化批的加权空间浪费比，从而可以更容易地寻找 启发式信息指导分批过程，两者的等价性也在文中给出了证明.此外，以批的空间浪费比为基 础，进一步定义了批间的距离度量，提出了批的约束凝聚聚类算法 (constrained agglomerative clustering of batches , CACB). 实验结果表明，与现有的 BF四川 best-fit longest processing time) 启发式规则和 GA (genetic algorithm) 等算法相比，CACB 在大规模算例的情况下更为有效. 关键词:调度;批处理机;聚类;组合优化 中圄分类号: TP301 文献标识码:A 文章编号: 1∞7 -9807 (2011) 12 -∞27 -11 。引 批调度问题是工业工程等领域中新的研究热 点.不同于经典调度问题，批调度模型中 1 台机器 可以同时处理多个工件.如半导体工业中的芯片 预烧工序，金属加工业的热处理工序，港口货物装 卸等等.因此，批调度问题的研究有着极为重要的 现实意义. 差异工件批调度问题是批调度中较复杂的一 类.在模型中每个工件具有不同的尺寸，批中工件 的总尺寸不能超过机器的容量限制. Uzsoy[I) 首先 提出这个问题，证明了问题是强 NP 难的，给出了 几个启发式算法，其中 FFL肝性能较好. Dupont 等[2) 提出另外两个启发式算法 BF四F 和 SKP，及 一个分支定界法[3) 一些学者采用元启发算法求 解该问题，如 Melouk 等问]的模拟退火算法， Damodaran [5) 和 Kashan[6] 的遗传算法，玉栓狮 等[7) 的蚁群算法，和程八一等问的粒子群算法. 还有一些研究考虑不同目标函数，或对模型 ① 收稿日期: 2∞9-06-26; 修订日朔: 2010 -1Yl -19. 进行扩展. Sung [9] , Ghazvini [ 10] 和 Chang[lI]研究了 目标为总完工时间的批调度问题. Lee 和 Uz- S町[叫研究了工件动态到达的问题，但该文中，工 件被假设为单位尺寸以简化模型. Sh吨uang 等[臼] 研究了具有不同到达时间的差异工件批调度问 题，提出近似比为 2 的算法. Chou 等问]则采用海 合遗传算法求解该问题. 但目前，对该问题的研究主要集中在单机环 境下，而在实际生产当中，对批的加工往往是由多 台机器[15- 17]同时进行.因此，对复杂生产环境下 批调度问题的研究显得尤为必要.本文旨在解决 平行机环境下的批调度问题. 1 问题模型 本文研究的问题可具体描述如下. 1 )工件集合 J 中有 n 个待加工的工件，记为 J = 11 ， 2 ，… ， nl. 其中，工件j 的加工时间记为Pj 尺寸为 Sj. 基金项目:创新研究群体科学基金资助项目 (70821∞1);博士点基金资助项目 (2∞80358∞24). 作者简介:杜冰(1981一) .舅，安徽合肥人，博上生. Email: toto@ mail.酬. edu. cn - 28 一 管理科学学报 2011 年 12 月 2) 机器集合 M 中有 m 台平行机，记为 M= 11 ，2 ，…，时，其容量均为 C. 设 B 为所有批的集 合 ， BI(l E M) 为安排在第 l 台机器上加工的批集 合.Jb(bEB) 表示批 b 中的工件集合 ， Jb 不为空 集，且 Jb 中工件尺寸之和不超过 C，假定没有尺寸 大于 C 的工件存在. 3) 批的加工过程不允许中断，批 b 可以在任 意一台机器上加工，其加工时间 l 等于批中工件 加工时间的最大值. 4) 第 l 台机器的完工时间记为 T1(l = 1 ,2 , … ,m) ， 目标为最小化 C皿，其中 Cmax 等于 T1 的最 大值. 根据调度问题的 3 参数表示法，上述问题可 表示为 Pm I batch ， 马~ cl c.... ，其数学模型如下 Min Cm=mri R|(1) s t =1 , VjeJ(2) L, Ybl = 1 , V b ε B (3) leM L， S卢jb