罗钧元 任秀蕊 徐占鑫 吕博凯 常馨月 李林瑛

摘要：考虑有滞留时间约束的集束型晶圆制造装备调度问题，其调度要同时考虑晶圆加工排序和机械手搬运作业排序，给出了基于图论的分支定界算法，并采用最长路径方法确定调度目标。仿真实验结果验证了算法的有效性。

关键词：集束型装备；分支定界算法；晶圆制造

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2018）09-0242-02

Abstract：This paper addresses the cluster tools scheduling problem with residency time constraints for wafer fabrication. The scheduling object is to determine both wafer input sequence and transfer robot task sequence. A branch and bound algorithm based graph theory is proposed， and the longest path method is to determine the scheduling object. Experimental example shows that the proposed method is effective.

Key words：Cluster Tools； Branch and bound algorithm； Wafer fabrication

1 引言

集束型裝备由若干单晶圆加工模块和一个计算机控制的物料搬运机械手组成。晶圆在加工模块上的停留时间可以在给定的时间上下界范围之内柔性变化，称为滞留时间约束。该类调度问题与经典的流水车间调度的区别在于：不仅要合理安排晶圆加工的排序问题，还要有效地规划机械手搬运作业的排序问题，因此更加复杂[1，2]。本项目采用JAVA语言编程实现基于图论的分支定界算法，该算法设计上采用枚举树表示晶圆分布和机械手搬运作业排序，利用深度搜索和广度搜索遍历枚举树，并采用有向图的最长路径算法确定调度目标。

2 问题描述

为了研究集束型装备的调度问题，本文从基于图论的分支定界算法研究，采用遍历枚举树确定晶圆分布情况、机械手搬运作业顺序等，并采用最长路径确定调度目标。具体的技术路线如下：首先构建包括加工模块能力约束和机械手搬运能力约束的数学规划模型，并采用基于Java的IBM CPLEX软件求解，并作为分支定界算法的比较基准。其次，研究的分支定界算法主要通过求解一系列的线性规划问题来获得研究问题的最优调度周期时间。为了有效求解上述线性规划问题，将求解T的问题转化成有向图中求解最长路径的问题[3]；最后分支定界算法主要由三个分支定界树A、B以及C组成，其中树A、B用来枚举可能的初始晶圆分布情况和晶圆加工顺序，而树C负责枚举树A或B中未被删除的叶节点对应的机械手搬运作业顺序。

3 算法实现

3.1 分支定界算法

分枝定界算法由Land等[4]在20世纪60年代提出，是最为流行的规划方法之一，其应有非常广泛。它的基本思想是先求出整数规划问题A所对应的线性规划问题B的最优解，如果该解不符合A的整数条件，那么B的最优目标函数必是A最优目标函数的上界，而A的任意可行解的目标函数值是其最优值的下界。然后将B的可行域分成子区域（称为分枝），逐步减少上界和增大下界，最终求得最优解。在调度问题的研究上，分枝定界算法一直是最重要的算法之一，如文献[5～8]分别提出了不同的分枝定界算法，它们的不同主要表现为分支规则、定界机制和上界三个方面的差异。

本文研究的分支定界算法由三个嵌套的分支定界树组成，分别称为分支定界树A、树 B和树C。若从A树生成的初始工件分布可得知所有工件的加工顺序，则直接激活分支定界树C；反之，则激活分支定界B树并且接着 A树的枚举工作继续枚举剩余工件的加工顺序。当B树枚举完剩余工件的加工顺序后，再激活分支定界树C。A树和B树实质上都是在枚举工件的加工顺序，设计它们的目的是首先删除不可能的初始工件分布和确保所有工件的加工顺序已知。其次是在A 树或B树枚举完所有工件的加工顺序之后，再由分支定界树C负责隐枚举保存下来的可能的初始工件分布和可能的所有工件的加工顺序所对应的机械手搬运作业顺序，这样做可以缩小搜索空间和节省搜索时间。

3.2 基于有向图的最长路径算法求解

分支定界算法主要通过求解一系列的线性规划问题来获得研究问题的最优生产周期。分枝定界算法中任意节点[o]对应的线性规划问题描述如下：

上述模型的目标函数为最小化生产周期T，约束条件集（式（1））为节点o对应的n个约束，这些约束包括加工时间约束、加工模块能力约束和机械手能力约束。约束条件集（式（1））刻画了集束型装备机械手在生产周期内搬运作业之间的约束关系，决策变量[Si]和[Sj]分别表示搬运作业i和搬运作业j的开始时间，[hk]为生产周期T的整数系数，[ak]和[bk]为实数常量。约束条件集（式（2））为生产周期T的可行范围约束，约束条件集（式（3））为决策变量的非负约束。由于约束条件集（式（1））具有特殊差分约束结构，可以通过图论方法转化为赋权有向图。由此，上述线性规划问题被转化为有向赋权图中最长路径问题。由于图中弧的权值是T的线性函数f（T），若图中有正回路，即回路上所有弧的权值总和Σf（T）>0，则该问题无解；反之，则该问题有解。周期时间T则为在可行区间[e，f]中使图中不存在正回路的最小值。将求解的调度问题转化成有向图中求解最长路径的问题，即将式（1）转换为图1中的节点、边以及权值。

3.3 算法流程图

以下为分支定界算法求解调度问题的算法流程图。

4 仿真实验

根据如上所述的加工方式，以加工三种不同类型晶圆算例对分支定界算法进行验证。该算例共包括8个加工模块，其中1～8号加工模块i负责晶圆加工，0号和9号模块分别为输入装载室和输出装载室。晶圆加工时间约束、机械手搬运时间见表1～表2。机械手空驶时间Cij=5|i-j|，其中i和j为工位号。

分支定界算法运行大约6.00098秒后，求出此问题的最优生产周期T=923.00秒，周期开始时刻的工件初始分布为{1，0，3，0，0，0，0，2，0}，从中可以看出晶圆的最优加工顺序为晶圆1→晶圆2→晶圆3。

5 结论

本文提出的算法有效地解决了在具有晶圆滞留时间约束的集束型装备的调度过程中，由于滞留约束限制而产生的冲突和死锁的问题，为此类集束型装备的调度问题提供了一个可行的方法。实验结果验证分支定界算法方法可以有效地解决集束型装备调度问题。

参考文献：

[1] 李林瑛， 盧睿， 李绍华，等. 有滞留时间约束的集束型装备在线调度方法[J]. 系统仿真学报， 2017， 29（2）：337-345.

[2] 王跃岗， 车阿大. 基于混合量子进化算法的自动化制造单元调度[J]. 计算机集成制造系统， 2013， 19（9）：2193-2201.

[3] Yan P C， Chu C B， Yang N D， et al. A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows[J]. International Journal of Production Research， 2010， 48（21）：6461-6480.

[4] Land A， Doig A. An automatic method of solving discrete programming problems[J]. Econometrika， 1960， 28（3）：497-520.

[5] Garey M R， Johnson D S， Sethi R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research， 1973， 1（2）：117-129.

[6] Cho Y， Sahni S. Preemptive scheduling of independent jobs with release and due times on open， flow and job shops[J]. Operations Research， 1981， 29：511-522.

[7] Potts C N， var Wassenhove L N. a branch and bound algorithm for the total weighted tardiness problem[J]. Operations Research， 1983， 33：363-377.

[8] Sarin S C， Ahn S， Bishop A B. An improved branching scheme for the branch and bound procedure of scheduling n jobs on m machines to minimize total weighted flowtime[J]. International Journal Production Research， 1988， 26：1183-1191.