基于滚动变时间窗的重组批处理机调度研究

1.上海交通大学机械与动力工程学院，上海 200240

2.安徽工程大学机械与汽车工程学院，安徽芜湖 241000

贾文友1，2，江志斌1，李友1

基于滚动变时间窗的重组批处理机调度研究

1.上海交通大学机械与动力工程学院，上海 200240

2.安徽工程大学机械与汽车工程学院，安徽芜湖 241000

贾文友1，2，江志斌1，李友1

1 引言

半导体芯片制造的整个过程可以分为晶圆制造、侦测、装配与封装、最终测试4个主要阶段。其中，半导体晶圆制造因其具有多重入、多产品混线生产和设备造价昂贵等特性，被誉为最为复杂的制造系统。根据加工操作方式的不同，可以将半导体晶圆制造中的加工设备划分为：单加工型设备、批处理型设备等[1]。所谓批处理是指在不超过批处理型设备的最大加工能力时，一次可以加工多个未完成工件。每次实际加工多个未完成工件集称为批（Batch）。半导体晶圆制造系统中的瓶颈机一般为批处理型设备，它制约着半导体制造系统的绩效，合理调度对改善半导体生产线的性能具有重要意义[2]。文献[3-4]研究了半导体晶圆制造系统中批处理型设备优化调度算法。

关于批处理机的调度问题，Potts等进行了综述研究[5-6]。文献[7]研究工件不允许等待下含两个相邻批处理机的flow-shop调度问题。文献[8]研究柔性作业车间的批量生产调度方法。文献[9]研究工件存在等待时间限制下第一个设备组为批处理机，第二个设备组为离散型设备的混合flow-shop调度问题，且要求所有工件在调度开始可用。文献[10]针对半导体晶圆生产线中批处理设备的重组批调度问题提出基于规则的拉式凑管调度算法。然而很多文献针对重组批处理机的调度提出的动态调度算法和全局优化算法等，存在未能充分考虑平衡算法的运行时间和目标函数值等问题。

关于工件动态到达下大规模实时调度问题，分解策略是一种有效措施[11]。滚动时域策略是一种基于时间序列分解策略，是用沿调度时间滚动进行的一系列小规模或有限时段的局部调度代替大规模或无限时段的一次全局调度，是一个随调度时刻向前推进的迭代过程。在滚动时域策略下，大规模实时调度问题沿着调度时间轴分解成许多时间窗下的子问题进行调度优化。在每个调度子问题中，为了获得精确的优化调度解，可采用混合的整数线性规划方法进行研究[12-13]。

本文研究对象是具有重入特性的半导体晶圆生产线中重组批处理机的调度问题，以拖延时间和最小为目标，考虑等待时间限制和工件动态到达。文献[14]已证明以拖延时间和最小为目标调度问题是NP难题。本文首先对具有重入特性的重组批处理机的代表性问题进行描述，并定义全文术语；然后延伸基于时间序列分解策略，提出基于滚动变时间窗的三层混合调度算法，将大规模的具有重入特性的半导体晶圆生产线中的重组批处理机的调度问题分解成变时间窗对应的子问题，每个子问题通过混合三层调度算法实施优化调度；最后通过实例与分析验证本文算法能够在较短CPU时间内获得满意的目标函数值。

2 问题描述和术语定义

2.1 问题描述

为了使研究问题更具有代表性，建立如图1所示的具有重入特性的重组批处理机的加工工艺流程简图，具体描述如下：

加工工艺流程简图主要包括两个设备组，设备组1和设备组2，且这两个设备组均是批处理机，设备组2的最大批处理能力大于设备组1；设备组的产品组批包括两种类型：产品相容和不相容：设备组1具有产品不相容性组批、重入特性；设备组2具有产品相容性组批，但由设备组1提供的批不拆分，具有最大批处理能力限制，需要对进入缓冲器中产品批进行重组批、排序。基于滚动变时间窗的三层混合优化调度算法确定缓冲器工件如何进入设备组2。主要假设如下：

（1）设备组2由于加工时间长，故此工位是生产瓶颈，假设设备组2不会出现饥饿。

（2）抢占不允许，即任意设备一旦开始加工，加工过程就不允许中断。

（3）缓冲器里产品批到达是动态的。

（4）设备组2的缓冲器里产品批存在等待时间限制，即为了避免由于工件表面接触空气时间过长而对产品的质量造成影响，产品批在设备组1中加工完成后必须在规定的时间内进入设备组2中加工。

（5）三层混合调度算法中第一层完成缓冲器里产品批实时状态信息和设备组2实时状态信息的记录、保存和传送；第二层完成进入缓冲器中产品重组批、排序；第三层完成重组优先批的装载分配及其分配完毕后缓冲器里产品批实时状态信息和设备组2的实时状态信息更新、保存。

（6）不计工件从设备1组到缓冲器，从缓冲器到设备组2和在缓冲器重组批的过程时间。

图1 具有重入特性的批处理加工工艺流程简图

2.2 术语定义

为了使术语具有通用性，对后面需要的术语进行如下定义：

J为当设备组2出现设备空闲可用时，缓冲器里来自设备组1的不同批的数量集；N为当设备组2出现设备空闲可用时，重组批的数量集；S为设备组2的最大加工能力；M为一个足够大的正整数；t为设备组2出现设备空闲可用时当前时间；qj为批j在设备组1和设备组2之间等待限制时间；P为设备组2的加工时间；sj为批j包含的工件数量；rj为批j到达缓冲器的时间；dj为批j的交货时间；ZSj为批j总加工工序数量集；DSj为批j在设备组2上所属的加工工序数；Pk，j为批j在第k个加工工序中加工时间；PRj为批j在设备组2后纯剩余的加工时间；drn为重组批n的交货时间；Crn为重组批n的完工时间；PRrn为重组批n在设备组2后纯剩余加工时间；∑T总拖延时间和。注：j=1，2，…，J；n=1，2，…，N；k=1，2，…，ZSj。

3 重组批处理机优化调度算法

为了优化半导体晶圆制造系统中重组批处理机的调度，基于滚动变时间窗的三层混合调度算法被提出，首先研究算法总体框架的构建，然后研究用于重组批及排序的松弛混合整数线性规划模型建模。

3.1 算法总体框架构建

以拖延时间和最小为目标，且具有等待时间限制和工件动态到达的重组批处理机的NP难调度问题，在分解规则下，将总的调度时间窗分解为许多时间窗，每个时间窗的长度等于相邻两个触发事件之间的时间间隔，其值是变化的，即变时间窗；在滚动时域策略下，每个时间窗之间不断更新优化调度结果。在每个变步长的时间窗下的子问题通过三层混合调度算法实行优化调度：产生触发并传递调度参数信息；重组批及其排序；装载重组优先批且更新调度参数实时信息。第一、三层延伸半导体晶圆制造系统实时调度仿真平台实施[15]，如图2所示；第二层在CPLEX和开发程序联合平台求解，在“基于松弛的混合整数线性规划模型构建”部分研究。基于滚动变时间窗的三层混合调度算法总体框架流程图如图3所示，具体包括如下步骤。

步骤1在滚动时域策略下，实时调度仿真平台产生调度参数信息传递触发事件：一台重组批处理设备空闲可用，第一层被开始执行，初始化时间窗。

步骤2实时调度仿真平台传递缓冲器里的不同产品族的工件数量、到达时间等实时信息的数据库，作为第二层执行的源数据，该空闲可用重组批处理设备为“等待”状态。

步骤3计算重组批的数量集(N)，判断：如果N＞1，程序往下执行，否则跳过第二层，直接转到步骤7。

步骤4接受第一层任务输出的源数据，第二层开始被执行，即执行通过CPLEX和开发程序联合平台运行基于松弛的混合整数线性规划模型的重组批及其排序优化求解过程。

步骤5输出在总拖延时间和最小的目标函数下优化的重组批的一维排序数组，作为第三层的源数据传递给实时调度仿真平台。

图2 半导体晶圆制造系统实时调度仿真平台主要界面

图3 算法流程图

步骤6接受第二层反馈的源数据，第三层开始被执行。

步骤7实时调度仿真平台将重组优先批装载到处于“等待”状态空闲可用重组批处理设备，更新并保存设备组2前的缓冲器里的实时信息，更新并保存设备组2状态信息。

步骤8程序终止判断：如果没有完成全部调度计划，继续往下执行，否则终止基于滚动变时间窗的三层混合调度算法。

步骤9实时调度仿真平台实时记录并保存重组批处理设备组（即设备组2）前的缓冲器里的不同产品族的工件数量、到达时间等实时状态信息；实时记录并保存重组批处理设备组实时状态信息，等待下一个调度参数信息传递触发事件产生。

3.2 基于松弛的混合整数线性规划模型构建

每个时间窗内的子问题，由于规模被减小，精确算法可以适用。在整数规划模型求解重组批及其排序优化调度问题中，重组批状态的0-1变量和重组批的排序位置序号是决策变量；满足设备加工时间，同一设备不能同时加工两个重组批，同一重组批只能占有一个排序位置序号等是约束条件；总拖延时间和最小为目标函数，具体整数规划模型如下。

目标函数：等式（1）是每个时间窗内的总拖延时间和最小的目标函数。约束条件式（2）用于计算重组批n的完工时间。约束条件式（3）和（4）用于确保每个重组批只占有一个排序位置号，且每个排序位置号只有一个重组批。约束条件式（5）引入重组批状态的0-1变量。约束条件式（6）确保缓冲器中每个批都被进行重组批，且只被进行1次重组批。约束条件式（7）用于计算批j在设备组2后纯剩余的加工时间，其中μk是调整系数。约束条件式（8）用于确定调整系数。约束条件式（9）用于计算当设备组2出现设备空闲可用时，重组批的数量集N。约束条件式（10）用于确保任一重组批包含工件数量小于至多等于设备组2的最大加工能力S。约束条件式（11）用于计算重组批n在设备组2后纯剩余的加工时间，其值等于重组批中所包含产品族中在设备组2后纯剩余的加工时间的最小值。约束条件式（12）用于计算重组批n的交货时间，其等于重组批中所包含产品族中交货期的最小值。约束条件式（13）用于确保被调度批j在缓冲器里的等待时间不超过设备组1和设备组2之间等待限制时间qj。

在CPLEX和开发程序联合平台中，线性的约束适合CPLEX求解。约束条件式（11）～（13）中表达关系式是非线性的，需要进行线性化。

综上，等式（1）、约束条件式（2）～（10）和（14）～（16）构建基于松弛的混合整数线性规划模型，适合CPLEX和开发程序联合平台优化求解。

4 实例与分析

为了评价基于滚动变时间窗的三层混合调度算法的有效性，一个简化的小型半导体晶圆制造系统被构建和调试运行。如图4所示，设有8个不同的设备组域，其中DIK对应于图1中的设备组1，LPC对应于设备组2，DIK和LPC之间具有等待时间限制和工件动态到达的特性。

图4 具有重入特性的半导体晶圆制造小型批处理机系统

图5 小型批处理系统的展开图及其对应的加工时间

表1 某时间窗下缓冲器里半导体晶圆的主要实时调度参数

图5是图4的工序展开图，表示8个不同的设备组域含有12个加工工序。不同设备组域的上标表示重入的次数，例如DIK2表示第二次在DIK进行加工。设有4种不同类型的半导体晶圆产品被同时加工，即I=4；不同类型的半导体晶圆产品在DIK和LPC之间等待时间限制相同，且qj=11 360；4种不同类型的半导体晶圆产品有相同的加工路线，即ZSj=12；由于LPC是最后一道工序，所以DSj=12和PRj=0。

如图5所示，每道加工工序的上面标注给定的加工时间，4种不同半导体晶圆产品第二次在DIK加工时间不相同，即PTi，DIK2(i=1，2，3，4)的值分别是180，263，410，300。假设设备组2的最大加工能力是12，即S=12。

实时调度仿真平台、CPLEX和开发程序联合平台都在借用Visual Basic.NET 2008编程，CPLEX为12.2版，运行硬件配置为Intel Core 2 Duo 2.0 GHz具有2 GB DDR-2 RAM。

每当在LPC中有1台空闲可用设备时，第一层中实时调度仿真平台输出LPC缓冲器里的工件数量、到达时间等实时信息的数据库。表1是实时调度仿真平台输出的主要实时调度参数，定义为案例1，其中缓冲器里来自设备组1的不同批的数量集是8，即J=8。

在第二层中，根据表1数据，CPLEX和开发程序联合平台基于松弛的混合整数线性规划模型进行重组批及其排序，主要的执行结果是：CPU运行时间是0.02 s，目标函数值是53，重组批的数量集N=4，重组批的优化排序后位置序号的一维数组(Position(1)，Position(2)，Position(3)，Position(4))=(4，3，2，1)，重组批的0-1变量xjn如表2所示，可知实时调度仿真平台重组优先批是第4个位置重组批，包括原来第3个批和第6个批。

在第三层中，实时调度仿真平台装载重组优先批，然后更新并保存重组批处理设备组前的缓冲器里的不同半导体晶圆的工件数量、到达时间等实时信息，更新并保存重组批处理设备组实时状态信息，案例1的当前时间窗终止，并判断总调度是否终止。

表2 重组批的0-1变量xjn的值

为了进一步评价基于滚动变时间窗的三层混合调度算法有效性，使用常用的智能算法即遗传算法作为参考算法对比。遗传算法模型的主要参数中设置种群数量：80；交叉概率：0.8；变异概率：0.1和遗传代数：120。

在滚动变时间窗的三层混合调度算法和遗传算法对比时，设计两个代表案例对比4个考核指标。

4个重要指标是：CPU运行时间，CPU运行时间改进率，目标函数值和目标函数值偏差率。

验证3个代表案例：案例1、案例2和案例3。其中案例1，在前面已经详细叙述。关于案例2，缓冲器里来自设备组1的不同批的数量集是16即J=16。通过第一层中实时调度仿真平台，LPC设备组的缓冲器里的不同半导体晶圆的工件数量、到达时间等实时信息主要包括：sj=[3，3，4，4，5，5，6，6，6，6，7，7，8，8，9，9]，rj= [100，100，150，150，200，200，300，300，180，263，180，263,410,410,300,300]和dj=[3 611，3 611，3 611，3 611，3 627,3 627,3 627,3 627,3 636,3 636,3 636,3 636,3 245，3 245，3 245，3 245]。关于案例3，令J=18。

滚动变时间窗的三层混合调度算法和遗传算法的实验结果对比分析如表3所示。在案例1～3中，滚动变时间窗的三层混合调度算法的目标函数值优于遗传算法的目标函数值的偏差率分别为+3.64%、+4.19%和+4.30%，同时CPU运行时间改进率分别为+99.81%、+53.71%和-9.66%。可见，滚动变时间窗的三层混合调度算法在两个案例中执行效果较好，在目标函数较优的情况下能保持CPU运行时间较短，但是随着调度规模增加，优势变弱。

表3 基于松弛的混合整数线性规划模型方法和遗传算法重要指标对比表

5 结束语

本文以拖延时间和最小为目标，对具有等待时间限制和工件动态到达的重组批处理调度NP难题进行研究，提出了基于滚动变时间窗的三层混合调度算法，实验结果表明本文所设计的调度算法能保持满意的目标函数值和较短的CPU运行时间。基于滚动变时间窗的三层混合调度算法优越性体现在该算法是一种混合整数线性规划求解（CPLEX求解）和启发式算法（即实时调度仿真平台运行）混合调度（Math-heuristic）算法。为了进一步提高该算法的鲁棒性，需要根据半导体晶圆制造厂的实际情况进一步实验和改进调度算法。

[1]江志斌.半导体芯片制造系统建模与优化调度控制[M].上海：上海交通大学出版社，2011.

[2]Mönch L，Fowler J W，Dauzère-pérès S，et al.A survey of problems，solution techniques，and future challenges in scheduling semiconductor manufacturing operations[J].Journal of Scheduling，2011，14（6）：583-599.

[3]Jia Wenyou，Jiang Zhibin，Li You.Closed loop controlbased real-time dispatching heuristic on parallel batch machines with incompatible job families and dynamic arrivals[J].International Journal of Production Research，2013，51（15）：4570-4584.

[4]Jia Wenyou，Jiang Zhibin，Li You.A job-family-oriented algorithm for re-entrant batch processing machine scheduling[C]//2013 IEEE International Conference on Automation Science and Engineering（CASE），2013：1022-1027.

[5]Potts C N，Kovalyov M Y.Scheduling with batching：a review[J].European Journal of Operational Research，2000，120（2）：228-249.

[6]Mathirajan M，Sivakumar A.A literature review，classification and simple meta-analysis on scheduling of batch processors in semiconductor[J].The International Journal of Advanced Manufacturing Technology，2006，29（9）：990-1001.

[7]Lin B M T，Cheng T.Batch scheduling in the no-wait two-machine flowshop to minimize the makespan[J].Computers&Operations Research，2001，28（7）：613-624.

[8]曾强，沈玲，潘启东，等.批量生产柔性作业车间多目标精细化调度方法[J].计算机工程与应用，2014，50（2）：263-270.

[9]Su L H.A hybrid two-stage flowshop with limited waiting time constraints[J].Computers&Industrial Engineering，2003，44（3）：409-424.

[10]李程，江志斌，李友，等.基于规则的批处理设备调度方法在半导体晶圆制造系统中应用[J].上海交通大学学报，2013，47（2）：230-235.

[11]孙凯，邢立宁，陈英武.基于分解优化策略的多敏捷卫星联合对地观测调度[J].计算机集成制造系统，2013，19（1）：127-136.

[12]Klemmt A，Weigert G，Werner S.Optimisation approaches for batch scheduling in semiconductor manufacturing[J]. European Journal of Industrial Engineering，2011，5（3）：338-359.

[13]Xiao J，Zheng L.A MILP-based batch scheduling for twostage hybrid flowshop with sequence-dependent setups in semiconductor assembly and test manufacturing[C]// 2010IEEEConferenceon AutomationScienceand Engineering（CASE），2010：87-92.

[14]Du J，Leung J Y T.Minimizing total tardiness on one machine is NP-hard[J].Mathematics of Operations Research，1990，15（3）：483-495.

[15]Li Y，Jiang Z B，Jia W Y.A pull VPLs based release policy and dispatching rule for semiconductor wafer fabrication[C]//2012 IEEE International Conference on Automation Science and Engineering（CASE），2012：396-400.

[16]Montagne E.Sequencing with time delay costs[J].Industrial Engineering Research Bulletin，1969，5：20-31.

JIA Wenyou1，2,JIANG Zhibin1,LI You1

1.School of Mechanical Engineering,Shanghai Jiaotong University,Shanghai 200240,China
2.School of Mechanical and Automotive Engineering,Anhui Polytechnic University,Wuhu,Anhui 241000,China

To address the scheduling problem of reforming batch processing machine for minimizing total tardiness with limited waiting time constraints and dynamic arrivals,a rolling variable time windows-based three-phase combined algorithm is proposed.With decomposition rule and rolling horizon control strategy,the scheduling horizon is decomposed into many variable time windows.Each sub-problem corresponds to a time window.At each sub-problem,the scheduling algorithm includes three phases：to send information of scheduling parameters;to reform and sequence batches;and to load super-hot reforming batch and update the state of manufacturing system.The experiments are implemented on realtime scheduling simulation platform and CPLEX.The results show that the proposed algorithm can obtain better solutions in less computation time.

reforming batch processing machine;rolling variable time window;three-phase combined algorithm

针对具有等待时间限制和工件动态到达的重组批处理机调度问题，以拖延时间和最小为目标，提出基于滚动变时间窗的三层混合调度算法。该调度算法是应用滚动时域策略，将重组批处理机调度问题分解为许多变时间窗的子问题；每个子问题调度分三层执行：即产生触发并传递参数、重组批及排序、派工并更新参数。通过实时调度仿真平台和CPLEX平台进行实例验证，结果表明基于滚动变时间窗的三层混合调度算法能够在较短计算时间内获得满意优化解。

重组批处理机；滚动变时间窗；三层混合调度算法

A

TP391.9

10.3778/j.issn.1002-8331.1311-0411

JIA Wenyou,JIANG Zhibin,LI You.Rolling variable time windows for reforming batch processing scheduling problem.Computer Engineering and Applications,2014,50（18）：19-24.

国家科技02重大专项（No.2011ZX02501—005）。

贾文友（1973—），男，博士研究生，讲师，主要研究领域为复杂制造系统建模、调度等；江志斌（1958—），男，博士，教授，长江学者，主要研究领域为生产调度与控制、生产与服务系统、动态系统理论及在制造系统中的应用、医疗卫生系统工程；李友（1987—），男，博士研究生，主要研究领域为半导体晶圆制造系统建模、调度和仿真。E-mail：jiawy@sjtu.edu.cn

2013-11-28

2014-03-26

1002-8331（2014）18-0019-06

CNKI网络优先出版：2014-04-09，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0411.html