上述模型的目标函数为最小化生产周期,约束条件集式(3-1)为节点ε对应的刀个约束, FBMH1608HM331-T这些约束包括加工时间约束、加工模块能力约束和机械手能力约束。约束条件集刻画了集束型装备机械手在生产周期内搬运作业之间的约束关系,决策变量凸和岛分别表示搬运作业∫和搬运作业丿的开始时间,q lc为生产周期r的整数系数,泸和3k为实数常量。约束条件集式为生产周期r的可行范围约束,约束条件集式(3-3)为决策变量的非负约束。由于约束条件集式(3-1)具有特殊差分约束结构,可以通过图论方法转化为赋权有向图。由此,上述线性规划问题被转化为有向赋权图中最长路径问题。由于砥权有向图中弧的权值是Γ的线性函数r(D,若赋权有向图中有正回路,即回路上所有弧的权值总和Ⅴ(D)0,则该问题无解;反之,则该问题有解。周期时间Γ则是在可行区间k,r]中,使赋权有向图中不存在正回路的最小值。

   基于上述思想,Rostami等⒓l]提出基于图论的多项式算法求解差分线性规划问题,并设计三种剪枝技术用来减少解空间的大小,从而提高分支定界算法的整体效率。在其调度中,将机械手其中的一个臂作为临时缓冲区使用,通过迭代算法使约束得到满足。先不考虑晶圆驻留时间约束,并求得其生产周期Γ。然后进行搜索分析是否存在一个调度方案使得其生产周期为T,如果存在则求得一个可行解。若不存在,将Γ加1,再进行搜索,直到求得可行解为止。随后本章参考文献[22]推广这一算法,来研究同时考虑晶圆滞留时间约束和双臂机械手滞留时间约束的集束型装备调度问题,也用来研究具有中间缓冲区的双臂集束型装备调度问题。该算法不仅适合双臂机械手,而且也能够解决复杂的二臂机械手调度问题,但理论上其复杂度是随工序数指数增长的。当集束型装各的工序数比较少时,该算法还是有效的。Carlicr等⒓剑把集束型设备调度问题分成两个调度子问题来解决,然后提出精确的分支定界法来求得最优解。Jung㈣等提出基于Pc“i网的分支定界法,其节点的评估采用双简化算法代替求解线性规划模型,其算法具有通用性。但该算法没有考虑问题的结构特征,其计算效率一般。