1.2 相关研究综述
结合本书的研究背景和意义，本节将主要针对以下几个方面的研究进行综述。可重入生产系统的建模、多产品可重入生产系统的投料控制策略、可重入生产系统的推拉调度控制策略等。
1.2.1 可重入生产系统的基本研究模型
半导体制造系统一直被认为是当今最复杂的制造系统之一。鉴于半导体生产线的复杂特性，需要借助抽象化的模型语言建立仿真模型，才能对这样一个复杂的生产系统进行研究。目前，国内外对可重入生产线研究的模型做了大量的研究工作，概况来说主要包括以下几种：Petri网（petri networks）模型、排队网（queuing networks）模型、流体（fluid networks）模型、连续模型（continuous model）、仿真模型等。以下分别简述。
1． Petri网模型
Petri网模型能对生产系统进行系统建模、仿真和性能分析，是研究离散事件动态系统的一个重要工具。Petri网模型的优势在于有比较完善的理论体系，同时可明确反映缓冲区、设备冲突和并发现象。然而，由于多重入生产系统为复杂的大规模制造系统，其庞大的规模使得Petri网模型的空间极度膨胀，带来了局限性。因此，应根据特定的应用环境，对Petri网模型进行拓展。由此衍生出了带多值标记的Petri网——Petri网（high level petri nets）应运而生，如谓词变迁Petri网、着色Petri网、赋时Petri网、面向对象Petri网等，可以更好地对生产系统进行建模。
Zhou等（1998）[17]利用Petri网方法来对半导体制造系统进行建模、分析、模拟、调度和控制，同时，引入了时间Petri网对制造系统进行仿真、性能评估和调度控制的目的。Lin等（1999）[18]利用广义随机着色时间Petri网（GSCTPN）对晶圆制造系统进行建模。Kim和Deserochers（1997）[19]利用时间Petri网建立和分析了面向客户的半导体制造系统，从客户订单到配送阶段。同时，通过分析模型的行为特征来获得生产周期，在制品状态和负载能力。Odrey等（2001）[20]利用广义随机Petri网对多重入流建立了一个典型半导体生产系统模型，并在此基础上进行了一些探讨。Wang（2002）[21]将连续模型和离散模型的转换相结合降低了模型的维数，从而建立了面向对象的混合Petri网模型。Lin等（2003）[22]利用Petri网建立了具有积极反馈回路的系统的一个不稳定充分条件，同时，利用缓冲区有界性的方法（buffer-boundness approach）研究多重入生产线的稳定性。Liu等（2003）[23]利用着色时间Petri网（CTOPN）对半导体制造系统进行研究，提出了多目标实时调度的方案，并通过仿真不同的调度规则证明了该模型的有效性。Zhai等（2006）[24]利用面向代理的有色赋时Petri网方法对半导体生产线进行建模，并且建立了一个分布的离散事件仿真平台来评估半导体生产系统的性能。Chiang等（2006）[25]利用排队着色Petri网（QCPN）对半导体生产线进行性能的评估和调度，同时提出了一个如何实现模型的优先规则机制。
2．排队网模型
排队网模型能够直观地描述晶圆生产线中的离散加工过程，并且能够得到解析的性能评价表达式，还可以用来评价调度策略的稳定性。然而，在大批量多品种混合生产的模式下，随着系统规模的增大和复杂度的增加，很难对模型求得解析解，也无法解决实际生产问题[26]。这是因为在分析可重入生产系统时，排队网络模型有以下几个缺陷。
（1）通过引入不同的客户类来处理多重入加工步时，随着系统中加工机器数量的增加，模型的复杂度将会不断增大。
（2）排队网络模型只能解决系统稳态下的优化控制问题，即所有的模拟结果只有在t→∞时才有效。
（3）排队网络模型必须忽视工厂中所有的临时故障，临时故障是不能通过排队网络模型来建模的。
Wein（1990）[27]利用多级排队网络模型，研究了两个工作站台的投料速率控制及调度优先级问题以解决工厂的调度问题。Kumar等（1994）[28]针对半导体制造系统利用排队网络方法做了大量的研究工作，但采用的排队网络方法很难得到解析解。Kumar and Kumar（2000）[29]利用排队网络模型用于半导体生产系统的设计和分析。Jeng等（2000）[30]利用马尔可夫时间Petri网（markovian timed Petri nets）对半导体生产系统进行建模，考虑了加工过程的优先级、加工路径的优先级、资源的重入和非抢占优先操作。Thomas和Shanthikumar（2002）[31]拓展了单阶段马尔科夫（markov）决策模型，解决了如何调度维修和计划具有多产品多阶段的半导体生产制造系统。针对Markov模型现有的研究结果都只是理论性的，尚无法解决实际半导体生产线的一些现实的问题[20]，[32]。
3．流体模型
流体模型很好地降低了生产系统的维数，有良好的鲁棒性，适用于随机环境。流体模型[2]，[33]来自交通流理论，是由Newell（1965，1973）[34]，[35]提出的。流体模型近似求解排队问题，将队列的长度视为一个连续的变量，并且它的变化率是由式（1-1）给出的。
其中：λ（t），μ（t）分别为物料的进入速率和系统的加工速率；q（t）为队列中在制品的数量。将系统中的每个加工机器都看作一个独立的队列，每个队列长度的特征都可以用式（1-1）表示。当系统中有多个这样的队列时，将前一个队列物料离开的速率作为下一个队列物料进入的速率，并将多个这样的排队模型连接起来，就形成了流体网络模型。由此，流体网络模型可以通过求解常微分方程（组）快速地得到计算结果，而且计算时间不受系统规模的影响。但是，流体模型也有其自身的缺点[7]。
（1）流体模型不能模拟系统的随机性。式（1-1）的λ（t），μ（t）均为平均值，是一个完全确定的系统，不能反映随机性。
（2）假定系统有恒定的产出率，流体模型是非常严格的。当系统达到稳定状态时，系统队列中将不会有任何工件在等待。并且当系统为非稳定状态时，队列将会出现维数爆炸。同样，一个队列的波动将不会传送到任何队列的上游或是下游，除非该队列的长度为0。
（3）当流体网络模型中的工件是一个连续的变量时，将每个加工机器视为一个独立的离散队列。因此，对于一个典型的芯片需要经历上百道工序，将生产加工步视为一个连续的变量是合理的。
鉴于流体模型自身的特点，使得它只能在系统稳定性方面取得了一些成果，却不能对系统的性能进行分析。对于无参Jackon网，Dai和Reiman（1994）[36]给出了一个结合近似分解法和交通流理论的耦合计算方法，来分析广义Jackson网络，并且通过模拟实验表明耦合的计算方法相比其他近似算法具有更好的研究结果。Chen和Yao （1996）[37]指出，在给定任何一个满足交通条件的情况下，从另外一个角度解决了多重入生产系统的稳定性问题。Dai和Weiss （1996，2000）[33]，[38]研究了具有确定路径的两站多级排队网络的流体模型，说明流体网络模型是不稳定的，并且特别指出当流体模型稳定的时候，排队网络模型也是稳定的。Gottlich等（2005）[39]对供应链流体网络模型进行了描述，推导出了常微分方程下的守恒定律，同时利用前向跟踪法证明了模型解的存在性。Ciro D'Apice（2006）[40]对供应链的流体网络模型做了论述，提出了一种离散—连续混合模型，同时讨论了保证流量守恒的点是模型可能的解。Armbruster和Ringhofer（2005）[8]，[41]针对多重入供应链，通过引入一个随机的相速度对标准模型进行拓展，得到对应动力学和流体模型的温度和扩散的概念。
4．连续模型
为了能从整体上对半导体生产线的性能进行分析，为此引入连续建模的方法。Armburster等（2006）[11]利用χ语言［由Van Beek等（2006）[42]创立］建立了包含有一个序列的缓冲队列和具有一定的生产周期和产能处理器的供应链，推导出了供应链中一个关于工件密度和流量的双曲型守恒定律，即连续模型。连续模型不能从细节上反映生产系统的特征，但是有其独有的优势。
（1）连续模型随着生产系统中物料的数量、加工机器的数量、加工步骤的数量越多和工件的重入程度越高，即系统复杂度的增加，所得到的模拟结果越精确。
（2）连续模型的计算时间不受系统规模的影响，并且有成熟的方法来求解该模型，可以非常快速地得到数值结果。
（3）连续模型可以很好地反映系统的瞬态行为。
Anderson（1981）[43]针对作业车间调度，给出了一个新的连续模型，并且能够有效地得到优化控制问题的解。Armburster等（2004）[12]利用交通流和空气动力学模型，通过一个连续的密度变量和一个连续的完成度变量，建立了大规模可重入生产系统的连续模型。这一模型为非线性非局部的双曲型守恒定律的变体，可以非常快速地得到精确的模拟结果[11]。Lee等（2002）[44]针对供应链模拟，提出了将离散事件仿真及连续建模方法相结合的组合方法对生产系统进行研究。Van den Berg等（2008）[45]针对生产流，提出了一种新的模型，即偏微分方程（PDE）模型。通过将三种不同的偏微分方程模型进行对比，以验证所提出模型的有效性。另外，利用该PDE模型来设计一个模型预测控制器（MPC控制器），并且通过证明MPC控制器优于经典的推式策略。Zou等（2006）[46]针对像半导体这样复杂的制造系统，提出了利用计算机辅助建模的方法，结合长时间尺度和短时间尺度来求解粗粒度偏微分方程。Sun和Dong（2008）[47]利用连接矩阵，基于供应链网络物料流守恒定律，建立偏微分方程的连续模型，采用DG（discontinuous galerkin）方法来求解供应链网络的生产流，同时指出所提出的建模方法是可以应用于大规模多重入生产线的情况。Jodlbauer和Stocher（2006）[48]研究了在连续型生产系统中Little's Law的形式。
通过以上的分析可以得知，建立不同的生产模型分别反映了生产系统的不同侧面，不同的模型均在某一些方面表现出一定的优越性。然而，为了对大规模复杂制造系统的整体性能进行评估，同时对生产系统提出合理的动态实时调度策略，应采用连续的建模方法。
1.2.2 可重入生产系统投料策略的研究现状
可重入生产系统的投料控制一般分为两类。一类是静态策略，即根据事先设定的速率进行物料投放，而不考虑制造系统当前的生产状况。如固定时间间隔投料策略（CONRIN）、随机投料或按随机分布泊松流投料策略等。该控制方法简单易实施，但为开环系统，不能做到及时反馈到投料控制端。另一类是动态策略，主要是使用启发式方法，根据生产线状况实时决定具体的投料时间、投料量及投料品种的控制方式，并且考虑的指标往往是交货时间和在制品水平。如固定在制品水平投料策略（CONWIP）、避免瓶颈设备饥饿投料策略（SA）、调节工作负载量投料策略（WR）等。动态投料策略的优点之一是能够最小化生产过程中随机事件的影响，根据现场状况的变化及时调整投料量、投料时间及投料品种。目前此种方式仍然是研究的热点。
在投料规则中，Wein（1988）[49]通过对几种不同的投料策略进行比较分析，在某种程度上投料策略比调度策略更重要。Spearman等（1990）[50]提出了定量在制品（constant WIP，CONWIP）方法，给出了CONWIP相比推式系统和拉式系统的实践优势，同时指出了支持该系统的理论依据并且通过仿真对系统的性能进行研究。Stidham （1985）[51]从控制和优化的角度出发，综述了通过静态（开环）和动态（闭环）模型来控制排队系统的投入量。在Brownian模型的基础之上，Glassey和Lozinski（1988）[52]，[53]引入了一个避免饥饿（starvation avoidance，SA）的投料策略，通过图表来说明这个概念，并且在半导体晶圆制造的加工车间取得了良好的控制效果。在实际的半导体制造系统中，瓶颈设备并不都是静止不动的，而是随产品的种类及数量的不同出现多个瓶颈设备甚至出现瓶颈漂移的现象。Leachman等（1988）[54]对SA策略进行了扩展，以适应瓶颈设备位置变化及有多个瓶颈设备的情形。尽管该方法提供了较好的思想，但在实际生产中却很难得到应用。Wein（1992）[55]针对多站点多级排队网络，利用Brownian运动控制问题，导出了启发式投料策略。由于Wein提出的投料策略是复杂的而且调度规则也是动态的，Duenyas（1994）[56]基于CONWIP与静态调度策略相结合的方法，对投料策略的性能进行测试，并且指出利用简单的投料规则也是有效的。Rodriguez（1997）[57]针对Mini-Fab模型设计了一种闭环系统的投料策略控制器，研究了稳定的CAF状态反馈策略。李莉等（2006）[14]提出了半导体生产线投料策略的系统动力学模型，并以生产线简化模型为例，给出了投料方法的计算流程并进行了仿真模拟。同时指出，系统动力学的投料策略有改进系统性能的潜力。Marca La等（2010）[58]通过连续建模的方法作为非线性优化问题的约束，研究了两种典型的控制问题：需求跟踪问题和库存积压问题。
综上所述，各种投料策略均有一定的合理适用范围，投料策略须考虑订单的选择、订单的生产周期、交货时间的紧急度、加工工艺路径的长短等，因此在实际应用中需要根据生产线的实际情况决定采取何种投料策略。
1.2.3 可重入生产系统调度策略的研究现状
半导体市场竞争激烈，企业要不断地提高产能降低制造周期，以使企业更快速地响应市场需求。对实际生产线而言，有效的投料控制策略能够改善生产状况，提高企业绩效。然而，由于生产过程中存在大量不确定性因素，单纯依靠投料策略往往无法有效控制芯片厂的整个制造过程，需要相应的生产调度来进一步控制。根据使用方法的不同，主要有基于以下几种模型建立的调度方法。
1．基于Brownian模型
Harrison和Wein（1990）[59]利用Brownian模型研究了一个具有两个单台服务站的多级闭环排队网络，主要是对工作站进行调度以最大化平均产出量，得到了一种使负载平衡的调度规则（workload balancing policy，WBP）。Chevalier和Wein（1993）[60]将它推广到多台服务器多级闭环排队网络，但Brownian模型计算量大，且得不到唯一封闭形式的解。Wein（1992）[61]研究了多机台多类闭环排队网络，针对多维Brownian模型，利用线性规划来减少负荷形式的控制问题，计算复杂度远高于两机台情况。赵丽娜等（1999，2000）[62]，[63]针对闭环可重入生产系统，设计了并行顺流定级法（parallel priority ordered downstream，PPOD），利用线性规划方法对性能边界的计算结果及仿真结果证明了该方法良好的适应性。
2．基于Markov模型
Kumar等（1993）[64]基于Markov排队论建立半导体生产线的排队模型，描述了几种不同的调度策略并给出了一些有关系统稳定性的模拟结果。Li等（1996）[65]将半导体生产线近似为Markov模型，提出了一种最低库存量变化的调度（MIVS），以降低半导体晶圆厂的生产周期的均值和方差。同时，将该调度策略与其地调度策略相比，表明具有更大的调度优越性。郑应平与王利存（2001，2002）[66]，[67]利用Markov决策模型，提出了可应用于可重入生产系统调度的递阶增强型学习算法，并且通过仿真表明该调度策略明显优于两种启发式调度策略。
3．基于Petri网模型
Cavalier等（1997）[68]介绍了一种用着色标记Petri网的方法对柔性半导体制造系统进行调度，同时改善了生产系统的性能。Jeng等（2000）[30]针对具有加工优先级、路径优先级、资源重入及可操作的半导体制造系统，利用马尔科夫时间Petri网方法来建立模型。Park等（2001）[69]利用有色Petri网来开发一个分布的晶圆控制器的事件驱动。由于路径的灵活性和辅助资源的共享，这个方法结合了制造系统的详细操作特性，包括配料、安装、返工、维护、机器故障和复杂资源的动态配置问题，同时通过小规模试验验证了该方法的有效性。乔非等（2004）[70]建立了有色Petri网的分层调度模型，并且进一步研究了该调度模型的实现方法。
4．基于流体网络模型
Chen和Yao（1992）[71]研究了具有随机中断的流体网络模型，同时研究了该模型的质量和相关性。在强大数定理（FSLLN）下，这个模型是排队网络系统的渐进行为。Connors（1994）[72]基于确定的流体网络模型，给出了一种新的半导体调度控制方法。该方法的主要优点是提出了一个基于整体的状态而不是基于局部信息的动态调度策略。同时，给出了一些有关流体模型的理论结果。Sharifnia（1995）[73]通过实际（离散）生产控制问题的连续流松弛法（continuous-flow relaxation），来操作生产系统使其尽可能接近理想化的策略。卫军胡（2001）[74]基于流体网络模型，结合离散事件仿真的方法，决策规则方法等提出多个模型交互的层次化结构模型和调度方法。
1.2.4 可重入生产系统推拉策略的研究现状
半导体制造系统是最先进的工业生产过程之一。由于它的生产周期（几个星期）和多重入流给生产计划和控制带来了更大的挑战[75]-[77]。大多数时候，需求的波动变化相比工厂的生产周期是在一个更短的时间尺度上，使得采用初始调度策略来响应需求波动变得越来越难。特别是，对于一个恒定的平均需求量，以均值需求量开始。由于生产的随机性和需求波动的变化，使得日产出量和需求量之间存在很大的差异。在实际生产中，为了减少它们之间的差值，给定一段时间内的生产目标，同时硅片在后期的加工过程中可以通过调度策略来加快或是减慢生产。由于半导体生产系统中的一个加工机器具有多个加工步，因此可以通过调度策略来重新设置所有加工步的优先级。
Sterman（2002）[78]指出在长的需求期和较大的需求波动的情况下，需要通过调整初始投料速率来弥补期望在制品水平的变化。Fowler等（2002）[79]针对工件负荷控制应用到半导体工厂的现状进行了综述。Bergamaschi等（1997）[80]将订单发放看作流控制，做了完整的文献综述。同时，Panwakar和Iskander（1977）[81]和Blackstone等（1982）[82]均对分派策略做了深入的研究。常用的调度策略有：先入先出（FIFO）、最早交货期（EDD）、加权最短加工时间（WSPT）、最小空闲时间（LS）和最小调整成本（LSC）。Aytug等（1994）[83]实现了动态调度策略研究。Atherton和Dayhoff（1986）[84]研究了纯推式和拉式调度策略。目前几乎没有文献提到在生产能力满足的情况下，晶圆厂收到意外订单时，产品出现激增或是短时间硅片的增加所带来的影响。McKiddie（1995）[85]，Kato（1996）[86]和Dummler（2000）[87]对需求激增问题进行了初步的研究。Lu等（1994）[88]没有考虑产出量问题，而是考虑了生产周期的均值和方差的性能与不同调度策略之间的函数关系。
离散事件模拟可以得到非常准确的模拟结果，在实际生产系统中也得到了广泛的应用。然而，离散事件模拟不论是运行还是维修都非常耗时。利用连续的流体动力学方程的供应链模型近几年成为研究的热点[8]，[89]，[91]。对于大规模的生产系统，以半导体生产线为例，Dieter等认为[11]，利用对应确定的连续模型可以进行离散事件模拟预测。对离散事件模拟来说，由于连续模型具有更丰富的解析结构，因此它可以有效地用于优化控制策略中[61]，[92]，[94]。然而，到目前为止，只有针对平均需求的长期预测的最优控制问题得到了研究。然而，对半导体工厂来说，存在另外一个更短的时间尺度，在这个时间尺度上的控制可以采用常用的调度策略[90]。最近，这个过程已经通过一系列的双曲型偏微分方程进行建模。在这里，研究了该模型的解析性质，并且引入了一种基于调度策略的控制模型。