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

第３８卷　

Ｖｌ０１．３８　第１４期　ＮＯ．１４　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１２年７月　

Ｊｕｌｙ　２０１２　

・开发研究与设计技术・　文章缡号ｔ　１００　－３４２８（２０１２）１４＿＿０２７２—＿０４　文献标识码：Ａ　中圈分类号：ＴＰ３０１・６　

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

郝尚刚　，陈华平　，李小林　

（１．中国科学技术大学管理学院，合肥２３００２６；２．中国科学技术大学计算机科学与技术学院，合肥２３００２７）　

摘要：针对两阶段流水车间环境下，工件尺寸不同的批处理机调度问题，提出一种以最小化制造期为目标、满足机器容量约束的凝聚聚　

类调度算法。结合目标函数的特点，利用基于内部和外部２类空间浪费比的变化量定义距离函数，对工件进行分批处理，并使用Ｊｏｈｎｓｏｎ　

规则排序。实验结果表明，在大规模算例情况下，该算法比已有算法更高效，具有更好的鲁棒性。　关健词：流水车间；调度算法；批处理机；聚类；空间浪费比；启发式方法　

Ｃｌｕｓｔｅｒｉｎｇ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｔｗｏ—－ｓｔａｇｅ　Ｆｌｏｗ　Ｓｈｏｐ　

Ｂａｔｃｈ　Ｐｒｏｃｅｓｓｏｒ　Ｓｃｈｅｄｕｌｅ　

ＨＡＯ　Ｓｈａｎｇ．ｇａｎｇ　，ＣＨＥＮ　Ｈｕａ．ｐｉｎｇ　’＿，ＬＩ　Ｘｉａｏ—ｌｉｎ　

（１．Ｓｃｈｏｏｌ　ｏｆＭａｎａｇｅｍｅｎｔ，ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅ　ａｎｄＴｅｃｈｎｏｌｏｇｙｏｆＣｈｉｎａ，Ｈｅｆｅｉ２３００２６，Ｃｈｉｎａ；　２．Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　ｏｆＣｈｉｎａ，Ｈｅｆｅｉ　２３００２７，Ｃｈｉｎａ）　

｜Ａｂｓｔｒａｃｔ！Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｍｉｎｉｍｉｚｅ　ｔｈｅ　ｍａｋｅｓｐａｎ　ｉｎ　ａ　ｔｗｏ—ｓｔａｇｅ　ｆｌｏｗ　ｓｈｏｐ　ｗｉｔｈ　ｂａｔｃｈ　ｐｒｏｃｅｓｓｏｒ　ｓｃｈｅｄｕｌｅ　ｐｒｏｂｌｅｍ　

ａｎｄ　ｎｏｎ—ｉｄｅｎｔｉｃａｌ　ｊｏｂ　ｓｉｚｅｓ．Ｃｏｎｓｉｄｅｒｉｎｇ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｔｈｅ　ｏｂｊｅｃｔｉｖｅ　ｆｕｎｃｔｉｏｎ，ｔｈｅ　ｄｉｓｔａｎｃｅ　ｆｕｎｃｔｉｏｎ　ｂｅｔｗｅｅｎ　ｔｗｏ　ｂａｔｃｈｅｓ　ｉｓ　ｄｅｆｉｎｅｄ　ｂａｓｅｄ　ｏｎ　ｔｗｏ　ｃｏｎｃｅｐｔｓ　ｏｆ　ｉｎｔｅｒｎａｌ　ａｎｄ　ｅｘｔｅｒｎａｌ　ｓｐａｃｅ　Ｗａｓｔｅ　Ｒａｔｉｏ（ＷＲ）．Ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｂａｔｃｈｉｎｇ　ｐｒｏｂｌｅｍ　ｂｙ　ｔｈｉｓ　ｄｉｓｔａｎｃｅ　ａｎｄ　ｔｈｅ　ｓｏｒｔｉｎｇ　

ｐｒｏｂｌｅｍ　ｂｙ　Ｊｏｈｎｓｏｎ　ａｌｇｏｒｉｔｈｍ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｍｏｒｅ　ｅｆｆｅｃｔｉｖｅ　ｔｈａｎ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ａｌｇｏｒｉｔｈｍｓ，ａｎｄ　ｈａｓ　ｂｅｔｔｅｒ　

ｒｏｂｕｓｔｎｅｓｓ．　［Ｋｅｙ　ｗｏｒｄｓ］ｆｌｏｗ　ｓｈｏｐ；ｓｃｈｅｄｕｌｅ　ａｌｇｏｒｉｔｈｍ；ｂａｔｃｈ　ｐｒｏｃｅｓｓｏｒ；ｃｌｕｓｔｅｒｉｎｇ；ｓｐａｃｅ　Ｗａｓｔｅ　Ｒａｔｉｏ（ＷＲ）；ｈｅｕｒｉｓｔｉｃ　ｍｅｔｈｏｄ　

ＤＯＩ：ＩＯ．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１２．１４．０８１　

１概述　批处理机调度问题是将工件在批处理机上进行分批加工　

的一类调度问题，是生产调度领域一个新的研究方向。该问　题涉及到众多的生产领域，如半导体生产过程中的预烧工　序、印刷电路板应力测试工序、金属加工业的热处理操作等。　

批处理机调度问题被证明为ＮＰ—Ｈａｒｄ问题＿ｌｊ，与经典调度问　

题相比，解空间和问题复杂性大大增加。因此，批处理机调　

度问题具有极强的理论价值和现实意义。　

目前，大多数关于批处理机调度问题的研究主要集中于　单机［２－４ｌ和并行机　问题。然而在现实的生产环境中，还存　

在连续２台批处理机的调度问题¨Ｊ，该问题兼具流水车间调　

度与批处理机调度的特征，比单机和并行机问题更为复杂。　

至今只有少数研究对此类问题进行了求解。文献【７］首次提出　

最小化制造期两阶段流水车间不同尺寸工件批处理机调度问　

题的数学规划模型。　

文献［８】对文献［７］模型进行改进，提出下界算法和基于改　

进模型的启发式算法。文献［９］提出一种基于Ｊｏｈｎｓｏｎ规则的　启发式算法Ｈ．Ｊ，并采用模拟退火（Ｓｉｍｕｌａｔｉｏｎ　Ａｎｎｅａｌｉｎｇ，ＳＡ）　

算法进一步优化。　

文献［１０］提出ＡＲＡ（Ａｃｃｅｐｔ／Ｒｅｊｅｃｔ　Ａｌｇｏｒｉｔｈｍ）、ＦＬＡ（Ｆｉｒｓｔ　Ｌｏｎｇｅｓｔ　Ｔｉｍｅ　Ａｌｇｏｒｉｔｈｍ）等启发式算法，进一步提出２种模拟　

退火算法，并对其进行改进，且提出一种下界算法。然而模　拟退火算法由于其自身的局限性，搜索最优解的效率较低，　在求解大规模问题时效果并不理想，对启发式算法生成的初　

始解具有很强的依赖性。但此前提出的算法并未充分考虑该　

问题的启发式信息，本文针对该问题提出一种满足机器容量　

约束的凝聚聚类调度算法，对两阶段流水车间批处理机调度　

问题进行求解，优化目标为最小化制造期。　

２　两阶段流水车问批处理机调度问题模型　两阶段流水车问批处理机调度问题可以描述如下：在生　

产环境中，ｎ个工件要在２台批处理机上连续加工，工件集　

合记为Ｊ：｛１，２，…，　｝，机器集合记为Ｍ＝｛ｌ，２｝，其中，工件／　

在机器ｍ上的加工时间为Ｐ，　；工件尺寸为Ｓ　；２台机器容　

量均为Ｂ；分批后形成的批次为　（　ｌ，２，…，ｋ）；其在机器ｍ　

上的加工时间为　；尺寸记为Ｓｉ；优化目标为最小化制造期　

ｃｍ　，即最后一批工件在第２台机器上的完工时间。　

该调度问题需要满足的约束条件为：（１）每一个批次的工　

件尺寸之和不能超过机器容量Ｂ，即Ｓｉ≤Ｂ，ｖｉ≤ｋ。（２）批　

的加工过程不允许中断，批６Ｉ在机器ｍ上的ＪＪｎＩ时间为该批　

在机器ｍ上加工时间的最大值，即　≥Ｐ　ｖｊ∈ｂｉ。（３）任　

基金项目：国家自然科学基金资助项目（７０８２１００１，７１１７１１８４）　作者筒介：郝尚刚（１９８６一），男，硕士研究生，主研方向：生产调度，　

人工智能；陈华平，教授、博士生导师；李小林，博士研究生　收稿日期：２０１１－１０—０７　Ｅ—ｍａｉｌ：ｈｓｇ＠ｍａｉｌ．ｕｓｔｃ．ｅｄｕ．

ｃａ　第３８卷第１４期　郝尚刚，陈华平，李小林：两阶段流水车间批处理机调度的聚类算法　２７３　

意机器一次只能加工一个满足容量约束的分批。（４）所有的工　

件加工工序相同，并且２台机器间的中间存储无限。（５）每台　

机床一次只能加工一道工序，同一道工序也不能在多台机床　

上同时加工。　

３基本凝聚聚类算法　

批凝聚聚类算法可以描述为：给定ｎ个数据点的集合　

＝｛Ｘｉ，Ｘ２，…，　｝和衡量２个聚类　和Ｃ，的间距离或相异度　

函数Ｄ（　，Ｃ，），然后按照如下流程进行聚类：　

Ｓｔｅｐｌ构造　个类，Ｃ＝｛ＣＩ，Ｃ２，…，　｝，Ｃｉ＝｛Ｘｉ）。　

Ｓｔｅｐ２计算类与类之问的距离Ｄ（Ｃ，Ｃ，），并合并距离最　

近的２个类为一个新类。　

Ｓｔｅｐ３如果类的个数等于１，则转Ｓｔｅｐ４，否则，计算新　

类与当前各类之间的距离，转Ｓｔｅｐ２。　Ｓｔｅｐ４输出聚类结果，并按照一定准则选择聚类。　

凝聚聚类算法关键在于距离函数和全局评分函数，距离　

函数用来衡量数据点之间的差异程度，而全局评分函数用来　衡量聚类结果的优劣。一般的，对于可以表示成向量的数据　

点的集合进行聚类分析时，距离函数常用欧几里德距离或者　

明氏距离：　

ｆ　ｄ　、１／　ｄ（ｘｇ，　，）＝ｌ∑Ｊ　Ｘｉ厂　，ｘｉ，ｘｊ∈９ｃ　（１）　、　Ｉ　，　全局评分函数一般采用聚类内部平方和与聚类问差异平　

方和，其形式如下：　

ｗｃ（Ｃ）＝∑∑ｄ（ｘｉ，ｒｋ）　：１－∈　

ｂｃ（Ｃ）＝∑ｄ（ｒｊ，ｒｋ）　１，＜　Ｋ　（２）　

（３）　

（４）　

其中，Ｃ＝｛　，Ｃ２，…，　｝表示聚类结果；　为聚类的中心；　

ｗｃ（Ｃ）表示聚类内部平方和；ｂｃ（Ｃ）表示聚类差异平方和。　

４满足机器容量约束的凝聚聚类调度算法　

批处理机调度问题分为分批和排序２个子问题，分批问　

题主要解决将哪些工件归为一批进行加工的问题，排序问题　

主要解决对分好的批如何调度。其中，排序问题往往可以利　

用经典调度的方法进行求解，比如两阶段流水车间批处理机　

调度问题可以利用Ｊｏｈｎｓｏｎ规则…　进行排序，因此，分批问　

题往往是批处理机调度问题的关键。　文献［１２］首次从聚类角度分析单机批处理机调度问题中　

的分批问题，并论证了分批问题是一类广义的聚类问题。由　

于分批问题的目标和一般的聚类问题目标不同，在进行合并　

时，距离函数也有较大差异，文献［１２］提出空间浪费比（Ｗａｓｔｅ　

Ｒａｔｉｏ，ＷＲ）的概念来衡量聚类的质量，将合并时的空间浪费　

比变化量定义为距离函数。　

由于两阶段流水车间批处理机调度问题相比单机问题更　

为复杂，本文对文献［１２】空间浪费比的概念进行扩展，并进　

一步提出更为合理的距离函数，应用凝聚聚类算法对分批问　

题进行求解，应用Ｊｏｈｎｓｏｎ规则…Ｊ对批次进行排序。　

４．１空间浪费比　在单机的批处理机调度问题中，空间浪费比概念定义为　

在批加工过程中，由于批的尺寸未达到机器容量和各个工件　

加工时间不同而造成的浪费与实际占用的时间空间资源之　

比，计算公式如下：　（　一Ｐｊ）　（　一　）　（　生—｛　上　

其中，　表示批　的加工时间；Ｐ，和Ｓ，分别是工件／的加工　

时问和尺寸；Ｂ为机器容量。　

与单机问题相比，两阶段流水车间批处理机调度问题不　

仅需要考虑２台机器在实际加工时由于批的尺寸不足或者加　

工时间差异而造成的浪费，还需要考虑在调度过程中，由于　

等待而造成机器空闲时间浪费，如果一个调度方案使得２类　

浪费尽量小，那么该调度方案越优。基于此，本文提出批的　

内部空间浪费和外部空间浪费示例图如图ｌ所示，假定及其　

容量为１０。　

机器　尺寸　工件　】　３　４　

ｌ　９　９　７　６　

ｆＪｔ　ｌ０　９　４　４　

７　６　４　

（ａ）算例　

口　工件　口　批内部浪费匿　批外部浪费　

（ｂ）可行调度下的２类浪费　

图１批内部空阔浪费和批外部空间浪费示倒图　

定义１批内部空间浪费，由于批内部工件之间的差异造　

成机器资源的浪费，量纲为工件尺寸与加工时间的乘积，对　

于分批　，其计算公式如下：　

ＷＳＩ（￣）＝∑（　ｌ＋Ｔ２一Ｐ　一Ｐ，２　，＋（　１十　２）（　一∑Ｓ，）　（６）　厍　札　定义２批外部空间浪费，由于分批集合在机器１和机　

器２上加工时间的差异造成机器空闲而产生的机器资源浪　费，该浪费记为ＷＳＥ，其计算公式如下：　ｋ　ｋ　ＷＳＥ＝Ｉ∑　１一∑　２　ＪＢ　ｉ＝ｌ　１　由于批与批之问进行比较时，每个批实际占用的资源量　

不一样，而比较空问浪费的量就没有意义，因此提出２类空　间浪费比和整体空间浪费比的概念。　定义３内部空间浪费比，批　内部浪费与该批加工时实　

际占用的机器资源之比，公式如下：　

删（６ｒ）　Ｗ　Ｓｌ（ｂｉ）　

Ｊ∈ｈ　。　。　。　定义４外部空间浪费比，整个批集合加工过程中的外部