带驻留约束的多机械手制造单元的调度算法

中图分类号：TP391；TH 18 doi：10.3969/j.issn.1000.565X.2013.03.018制造单元是-种广泛应用于半导体、航空航天、光纤等制造行业的生产组织方式.随着制造单元的广泛应用，如何提高其生产效率受到了学术界和业界的关注.Sethi等 首次运用解析法确定了2至3台机器的制造单元中机械手动作的最优调度周期；Crama等 从分析调度周期出发，利用解析法求解了递增移动时间的制造单元 的最优调度周期；Dawande等 研究了机械手移动时间为常数的制造单元，并构造出任意数目机器的最优调度周期 ；Gei-smar等 在上述文献基础上，又考虑了并行机的调度问题，给出了相应的调度周期；针对多品种调度，Didem等 运用两阶段启发式算法解决了多品种、两台机器的制造单元的调度问题。

相对于单机械手的制造单元调度问题，多机械手制造单元的调度需考虑多个机械手之间的协作，其研究复杂性大大增加.目前，对于多机械手制造单元调度算法的研究还在起步阶段.文献 [7-8]在文献[5]的基础上，构建了三机械手 、欧几里得移动时间的制造单元调度模型，并建立了最优调度周期；文献[9.10]分析了多个双臂机械手的最优调度方案并给出相应的调度周期低界.上述文献仅仅考虑了单-品种的工件在无驻留约束条件下的调度问题。

对于多品种无驻留的制造单元的调度问题，Che等 提出了求解任意可行 r级周期时间的机械手最小数目、最优动作顺序的调度算法；在此基础上，Che等l 又将算法推广.在考虑驻留约束的调度问题中，Rostami等 运用搜索与规则相结合的方法，对单个带有驻留约束的制造单元进行了调度；Yoon等。

运用先搜索可行解空间，然后选择最优解的思路 ，解决了集束型设备的实时调度问题；刘明祥等 针对多品种工件的带有驻留约束的集束型设备群的调度问题，提出了基于时间约束集的启发式算法。

收稿 日期 ：2012.07-05基金项 目：国家 自然科学基金资助项 目(71071115，61273035)；国家863”计划项目(2009AA043000)作者简介：王翥(1989.)，女，博士生，主要从事制造系统调度与预防性维护建模研究.E-mail：wz7159569wh###163.com十通信作者：周炳海(1965-)，男，教授，博士生导师，主要从事制造系 物流系统调度、建模、仿真与预防性维护研究E-mail：bhzhou###tongji.edu.cn华 南 理 工 大 学 学 报 (自 然 科 学 版) 第41卷手对同-台机器的两次装载时间间隔不得少于该工件在该工作站上的加工时间.式(4)、(6)表示共享工作站上工件卸载开始并经过-段时间的缓冲后，前-工作站上的工件才能卸载并装载在共享工作站上.式(5)表示工件在共享工作站上装载后，为防止机械手冲突，负责该工作站的机械手卸载工件的最早时间.根据假设⑤和⑥，为保证工件的品质，其在工作站上的加工时间必须满足式(7)和(8).式(9)表示工件在工作站上被卸载的时间为其 自完成加工的时刻起，经过驻留直至离开工作站的时刻.根据假设⑦，式(10)表示机械手搬运动作无等待现象。

式(11)表示工件装载完毕的时刻即为工件加工开始时刻.式(12)表示工件在工作站上 自无中断地对工件进行加工直至加工完成.式(13)、(14)表示共享工作站上，相邻机械手对共享工作站的动作时问问隔不得少于时间缓冲.式(15)表示在非共享工作站上，-个工件加工完成后，经卸载、搬运、装载在下- 工作站上，然后机械手才能卸载下-片工件，并搬运、装载在这个非共享工作站上。

2 基于瓶颈的推拉式启发式调度算法在工作站总数为 m，工件总数为 Ⅳ的情况下，通过计算，笔者提出了时间复杂度为 0(m )的算法.算法的核心思想为基于瓶颈的推拉式调度策略。

以瓶颈工作站为界，首先运用拉式的逐级回溯调度瓶颈以前的各级工作站，在满足驻留约束的范围内通过左