时间窗约束规则应用于起重机的循环时间安排.doc

时间窗约束规则应用于起重机的循环时间安排 Haoxun Chen, Chengbin Chu, Jean-Marie Proth 摘要：本文为在印制电路板电镀设备中用时间窗约束开发最优的起重机的循环调度建立了一个模型和与其相关的算法。此算法是基于分支区间算法，它需要一种特殊的线性编程问题（LPP’s）的解决方案。LPP’s问题与bi值图中循环时间评估问题是等价的。在本文中经计算得出的实验数据证实了用我们提出的新算法获得的结论。 术语索引—bi值图，支路与范围，循环时间，起重机调度，时间窗约束规则。 Ⅰ介绍 许多工业企业用计算机控制起重机来管理原料。编程控制起重机来做一些固定的重复性的连续的移动。每个连续移动的重复过程我们称之为一个循环。处理印制电路板（PCB’s）的自动电镀生产线是其中的一个应用。这个生产线有一组电镀槽组成（见图1）。在每个槽中在PCB’s上进行化学或电镀的处理。操作必须按给定的程序进行。一个槽容器一次最多对一件PCB’s进行处理。因为化学反应的规律，在PCB槽中的时间受上限、下限的限制。这就是说起重机的移动受到时间窗约束规则的影响。起重机不仅从一个电镀槽移到下一个来运送PCB（定位移动），而且在其空闲时要从一个电镀槽移到其它槽处（避让移动）。 起重机在每个循环中运行这种给定顺序的移动过程定义为循环调度。在本文中，我们考察简单循环调度[1]-[3]。在简单循环调度中，系统在一个循环内将一个PCB板被在每个电镀槽之间移动一个循环；因此一个PCB板进入，前面的那个PCB板移出。起重机所用的完成这个循环所需的总时间就是循环时间。起重机调度问题的目的就是最小化循环时间，使循环时间最小化也就等于使吞吐率最大化。 此类起重机调度问题已经被证明是完全NP问题[4]。所有现存的方法[1]-[3]，[5]，[6]都是类支路与范围的方法。然而，支路与范围方法的效率很大程度上依靠范围下限的质量、获得范围下限的计算量和支路的策略。 在本文中，我们为在印制电路板电镀设备中用时间窗约束开发最优的起重机的循环调度建立了一个模型、提出与其相关的算法，此算法是基于支路与范围方法，它需要一种特殊的线性编程问题（LPP’s）的解决方案。 我们用的是两支路范围过程。下面过程A列举了在一个循环中可能的初始化PCB板的分配，已知： 1）装载站一般一个PCB板； 2）在一个循环中的第一次移动是将一个PCB板从装载站搬运到电镀槽1的移动。 我们用数学式表达的和PCB板的过程时间相对应的约束来减少PCB板初始化分配的数目。过程B为每个潜在可行的初始化分配列举了起重机移动的顺序。 在支路范围算法中与下限计算相对应的LPP’s问题在过程A和过程B中被变换为在bi值图中的循环时间评估问题。这种问题应用基于图的迭代算法来解决。 在本文中关于一些基本问题的计算实验数据证实了用我们提出的新算法获得的结论。 在经典的长篇调度著作[7]，[8]中没有时间窗约束规则，与它们相比目前很少有关于起重机调度问题的著作，尽管这一领域的应用非常的重要。我们着重研究的是应用时间窗约束规则的调度问题，它不仅仅是要考虑到起重机能力约束。 下面介绍本文是如何组织的。在第Ⅱ章中我们用公式表示起重机调度问题。在第Ⅲ章中，我们论述如何确定在循环开始时板数目的最大上限。在第Ⅳ章和第Ⅴ章中我们提出了支路范围算法用它来解线性变成问题的。第Ⅵ章给出了计算的结果，第Ⅶ章给出结论。 图一 生产PCB板的自动电镀生产线的布局 图二 在含有N+2个站的系统中的PCB板运动流程 图三 简单的六站系统的循环调度 Ⅱ问题的公式化 考察一个含有N+2个站（电镀槽）…,SN,SN+1,其中S0和SN+1分别是装载站和卸货站，起重机在它们之间调运PCB板（如图二）。为了方便起见，我们称PCB板从Si到Si+1的移动为移动i,i=0,1,…,N。给定起重机完成移动i的时间用表示,,起重机完成从Sj到Sk的移动用表示, 。假设这些事件是连续的。站Si在某一时间最多处理一个PCB板，,每个PCB板在时间ti在站i中必须得到处理,处理事件的下限是ai,上限是bi,等，。ai和bi的值是给定的常量，i=1,2,…,N。这些条件对于一个循环中的移动产生对时间窗约束规则的影响。也就是说，给定一个PCB板在时间t被放入电镀槽Sk,起重机必须准备好在[t+ai,t+bi]时间段内将此PCB板从电镀槽中移走。另外，我们假设S0（装载站）可以容纳一定数目的PCB板。此时， 电镀槽间部允许有PCB板在等待处理，不允许有某一处理流程被别的流程抢占。 如在介绍中提到的，我们只考察了简单循环调度。简单循环调度有一般包含n个循环的调度（n1）i=0,1,…,N，x代表循环时间。假设S0=0(注释：如果S00，我们可以变换时间轴式的S0=0)。根