应用离散事件系统控制理论求解生产调度的新方法

伍乃骐, 乔 岩

(澳门科技大学系统工程研究所,澳门)

1 引言

调度问题是一个经典的研究问题,也是各个领域广泛面对的问题.它的一个重要分枝是生产调度.一般认为,生产调度的理论和方法已基本成熟,有大量的研究,早在1974年Baker就出版了相关的专著[1].由于一般的调度问题属于NP-hard问题,为了有效求解,对于大规模的生产调度问题,人们一般选择启发式算法、搜索算法和元启发式算法求解[2-7].随着生产过程越来越复杂,调度问题的规模越来越大,以及客户定制导致产品的多样化和小批量(甚至单件定制),实时动态调度成为迫切需求.在动态调度的要求下,元启发式算法也难满足实时性需求,而启发式算法难于保证解的性能.因此,目前生产调度问题仍是热门的研究领域,人们希望根据不同问题的特点,寻求有效的方法.人工智能也引入调度领域的研究[8-9].此外,有些系统存在潜在的冲突或死锁,为了求得无死锁、无冲突的调度,研究人员结合Petri网模型和启发式算法求解[10-11].这些算法也涉及到计算复杂性问题.

有一大类的生产过程具有严格的工艺约束.例如,自动化的生物化学物质快速筛选系统(high throughput screening systems,HTSS)中某些工序必须在一个严格的时间窗口内完成[12];印刷电路和半导体芯片制造中,很多工序要求加工完成后工件必须在规定的时间内从加工装置中移出[13];在某些石油化工过程中,物料罐相当于离散制造中的一台加工设备,经常在物料注入罐中后需要等待规定的时间才能使用[14].由于这些约束的存在,启发式算法和元启发式算法难于保证约束得到满足,人们不得不寻求数学规划的求解方法[15-19],这就面临计算复杂性问题.当问题规模巨大时,几乎无法实际应用.同样,当不确定性存在,需要实现动态调度时,基于数学规划的方法也难于应用.这是调度问题研究中面临的严峻挑战之一.

注意到,调度问题面对的系统包含了离散事件过程.在离散事件过程控制中,过程的状态可分为合法状态和非法状态.离散事件过程控制的重要问题之一是设计一种控制策略使得合法状态保留,而所有的非法状态不会出现.对以上调度问题,可以应用离散事件系统控制理论将所有违反约束的状态定义为非法状态,而其他状态定义为合法状态.然后,利用该理论研究解的存在性,并推导出解的存在性条件.基于所获得的条件,可以在可行空间内求解,从而获得有效的求解方法.

本文旨在介绍这一生产调度新方法,并以半导体芯片制造中的一类典型系统作为例子,较为详细地说明这种方法的求解过程.它把本来非常复杂的离散优化问题转换为简单的连续优化问题.结果,不仅可以对给定的问题有效求解,还可以对系统的干扰实现有效的优化响应.

2 问题描述

半导体芯片是由很多层电路构成的集成电路,每一层电路的形成都要经历沉积、涂胶、曝光、显影、光刻、蚀刻、清洗等工艺过程,其中绝大部分工艺过程是由称之为组合设备(cluster tools)的装备完成.因此,它的调度和控制问题是晶圆制造的关键之一.

如图1所示,一台组合设备主要由若干加工模块(process module,PM),两个称之为loadlocks(LLs)的装卸装置,以及一台机械手.在图中两个LL分别用AL和CL表示.机械手可以是单臂和双臂的,相应的组合设备称之为单臂和双臂组合设备.在晶圆加工过程中,一般以25枚晶圆为一批,它们装在一个箱子里.装有25枚晶圆的箱子通过车间的物料传送装置载入其中的一个LL,抽真空后即可进行加工.晶圆的加工路径是根据工艺要求预先设定的.在加工中,机械手从一个LL中取出一枚晶圆,按照预先设定的顺序送到各PM进行加工,加工完毕的晶圆送回原来的LL.当一个LL中的晶圆在加工时,另一个LL可以进行晶圆箱的装卸操作,因此整个系统可以连续不断地运行.

图1 组合设备示意图Fig.1 The illustration of cluster tools

一些工艺过程需要反复进入某些PM进行加工,这种加工工艺称之为具有重入的加工工艺.原子沉积是一种重要的电路层生成工艺,属于典型的重入工艺[19].本文以一种双臂组合设备重入工艺调度问题讨论所提出的算法,其加工流程可以表示为(PM1,(PM2,PM3)2).它的含义是,一枚晶圆首先由PM1加工第1道工序,然后依次由PM2和PM3完成第2和第3道工序,此后晶圆需要再进入PM2和PM3进行第4和第5道工序的加工,最后回到相应的LL.

晶圆在PM的加工是一个物理化学过程,工序加工完成后,如果晶圆在PM驻留时间过长,PM中的环境会损害加工好的晶圆.这就要求加工完的晶圆须在规定的时间内取出.令ai表示晶圆在PMi中所需要的加工时间,δi表示加工完成后可在其中的停留时间,τi表示晶圆在PMi中的驻留时间(包括加工时间和停留时间).那么,这一工艺约束可以表示为

正是约束(1)给系统的调度带来严峻的挑战,这一约束称之为驻留时间约束.

为了保证加工质量的稳定性和一致性,希望求得一个单晶圆周期性调度.如果每完成一枚晶圆后系统完全回到原来的状态,这样的调度称之为单晶圆调度.

本文以双臂组合设备在加工流程(PM1,(PM2,PM3)2)下的调度问题进行讨论.双臂组合设备在交换策略下运行.机械手在PMi的交换策略可以描述如下:在一只手臂握着从PMi−1卸下的已加工晶圆而另一只手空闲的状态下,机械手移动到PMi,取出其中的已加工晶圆,然后将从PMi−1中取出的晶圆载入PMi中.这就完成了一次在PMi的交换操作.

在没有重入和忽略驻留时间约束,以及尽早执行策略(earliest starting strategy,ESS)的条件下,已被证明交换策略是生产率最大化意义上的最优运行方式[20].在有重入和忽略驻留时间约束的条件下,人们曾经认为,应用交换策略会形成一个最优的单晶圆周期调度[21].实际上,文献[22]证明这样的系统不可能形成一个单晶圆调度,而是一个3-晶圆调度,即每完成3枚晶圆才重复原来的过程.同时还证明,在某些参数下系统永远不会进入稳态,而是一直处于一种动态过程中.接下来,本文讨论如何应用基于控制理论的方法解决所面临的这一系列问题.

3 系统建模

离散事件系统控制建立在一个系统模型之上.作为一种有效的离散事件过程建模工具,研究人员用面向进程的Petri网(process-oriented Petri nets,POPN)对组合设备建模,从而推导出整数规划模型对系统的调度问题求解[15-19].与其他研究人员的建模方法不同,本文用面向资源的Petri网(resource-oriented Petri nets,ROPN)建模.它是一种有限容量的Petri网,表示为:PN=(P,T,I,O,M,K),其中:P={p1,p2,··· ,pm}是有限库所集合;T={t1,t2,··· ,tn}是有限变迁集合,且有P ∪T ̸=∅和P ∩T=∅;I:P×T →N={0,1,2,···}是输入函数;O:P×T →N为输出函数;M:P →N为系统标识,描述系统中令牌在库所中的分布状态,M0代表初始标识;K:P →{1,2,3,···}是容量函数,K(p)表示库所p可以容纳的最大令牌数.

用•t={p:p ∈P和I(p,t)>0}表示变迁t的前集,即t的输入库所集;它的后集则表示为t•={p:p∈P和O(p,t)>0}.类似地,p的前集表示为•p={t∈T:O(p,t)>0}以及其后集表示为p•={t ∈T:I(p,t)>0}.然后,可以定义有限容量Petri网的变迁使能和引发规则如下.

定义1 有限容量PN中一个变迁t ∈T称之为被使能,如果∀p ∈P有

一个被使能的变迁可以引发,在标识M下引发变迁t导致一个新的系统标识

定义1表示,只有在t的前集所有库所有足够的令牌,而后集的所有库所有足够的空间,t才可以引发.因此,条件(2)表明进程使能,而条件(3)表明资源使能.

基于上面的知识,可以讨论系统的建模,系统的模型如图2所示.系统的调度本质上是资源分配,用ROPN可以很好描述资源分配.在所讨论的系统中,主要的资源是3个PM,2个LL,以及一台双臂机械手.所要完成的加工流程是(PM1,(PM2,PM3)2).由此可知,系统有3个加工步骤,且PMi服务于步骤i.将2个LL视为装卸站,用库所pL表示.由于任何时候2个LL中均有晶圆需要加工,因此有K(pL)=∞.用库所r表示机械手,且K(r)=2代表它有2只手臂.

图2 系统的Petri网模型Fig.2 The Petri net model for the system

令N3={1,2,3},用模块化方式对步骤i ∈N3建模.其中用pi表示PMi,且有K(pi)=1.用库所qi1和qi3分别表示机械手对PMi的交换操作前后的等待,且有K(qi1)=K(qi3)=1.用q22表示机械手在交换操作过程中的等待,此时每一只手臂均握着一枚晶圆,所以K(qi2)=2.用ti0表示交换操作中从PMi下载已加工晶圆,它的引发需要库所pi,qi1和r中有令牌,因此,如图所示•ti0={pi,qi1,r};同时,引发后两只手臂各握着一枚晶圆,并执行交换操作中的等待,因此t•i0={qi2}.用ti1表示交换操作中将从PMi−1卸下的已加工晶圆载入PMi,它的引发需要库所qi2中有令牌,因此,•ti1={qi2};同时,释放一只手臂,然后机械手在qi3中等待,因此t•i1={pi,qi3,r}.至此,完成了步骤i ∈N3的模块化建模.

在模块化建模基础上,变迁t12连接库所q13和q21,t23连接库所q23和q31,t32连接库所q33和q21,tL1连接库所pL和q11,以及t3L连接库所q33和pL.注意到,q33中的令牌可使能t32也可使能t3L,这是一个冲突问题,需要予以解决.为此,引入颜色,使得模型成为着色Petri网.

定义2 在以上PN模型中,定义变迁ti具有唯一颜色C(ti)=ci.

基于定义2,定义q33中令牌的颜色以解决以上冲突问题.令Wd为一个令牌,代表第d枚从LL送到系统中加工的晶圆.那么,q33中令牌的色定义如下.

定义3 如果q33中的一个令牌Wd下一步要到步骤j ∈{2,L}加工,那么定义该令牌的颜色为C(q33,Wd)=c3j.

令Wd(q)为q33中的一个令牌,它代表停留在库所q33并完成了第q道工序的第d枚送到系统加工的晶圆.那么,基于图2 的模型,如果1 ≤q<5,则有C(q33,Wd(q))=C(t32)=c32;以及C(q33,Wd(5))=C(t3L)=c3L.当Wd的颜色为cij,此时Wd使能tij.结果,如果1 ≤q<5,q33中令牌Wd(q)使能t32,而Wd(5)使能t3L.因此,系统的生产流程得到精确描述.

通过上面的建模过程确定了模型结构,但还需要描述系统的状态(即标识),变迁使能和引发规则,以及时间特性.首先,需要确定初始标识M0.理论上,初始标识应描述系统启动时的状态,即空闲状态,此时所有PM均空闲.但是,考虑到本文的目标是求一个最优的稳态周期调度.在稳态下,所有的PM均处于加工状态.为了解决这一问题,可以认为,初始时系统正在处理一种虚拟晶圆W0,结果可以设置初始标识M0为M0(pi)=K(pi)和M0(qij)=0,i ∈N3,j ∈N3.当系统模型按照规则演化时,虚拟晶圆会一枚一枚移出,而实际的晶圆会一枚一枚载入,当所有虚拟晶圆移出后,系统进入真正的稳态.

在这一初始标识下,为了保证机械手交换操作的正确执行,设定ti0,i ∈N3的使能必须满足下列条件:

以上得到的模型存在着潜在死锁.观测图2所示的PN模型,假设系统达到标识M使得M(q13)=M(r)=1.在此标识下,按照变迁使能和引发规则,tL1已使能,可以引发.它的引发将一个令牌移入q11,同时从r取走一个令牌.此时,容易验证系统处于死的状态,因为没有变迁可以引发,也就是说它是一个死锁标识.可以通过施加一个控制规则避免这一事件的发生.这由加入一个控制库所cp实现,使得cp是tL1的输入库所,即•tL1⊃{cp}.然后令u为库所cp的一个函数使得u(cp)∈{1,0}.如果u(cp)=1,那么cp的输出变迁控制使能,否则其输出变迁在控制上禁止引发.为此,下面的引理成立.

引理1 如果下列条件满足,以上获得的PN无死锁

观测图2所示的模型可知,模型中所有库所与变迁代表的事件均需花费时间来完成,因此它们均需要赋予时间.用µ表示引发t12,t23和t32所需的时间,即机械手在两个PM之间移动或PM与LL之间移动所需时间;用α和β表示引发ti0和ti1分别需要的时间,即机械手从PM卸载晶圆和装载晶圆至PM分别所需时间.因此,引发tL1和t3L所需时间分别为α+µ和β+µ.如果在库所pi,i ∈N3的交换操作中没有等待,引发ti0和ti1的时间构成了交换操作的时间,用λ表示.机械手在qij中的等待时间是本方法求解调度的决策变量,令ωi1,ωi2和ωi3分别表示机械手在qi1,qi2和qi3的等待时间(即交换操作前、交换操作中和交换操作后的等待时间).如果交换操作中等待时间不为零,交换操作所需的时间为λ+ωi2.考虑到qi3后接着是ti(i+1),然后是q(i+1)1,因此机械手在qi3和q(i+1)1中的等待可以合并.为此,总令ωi3=0.表1总结了模型中各库所和变迁的含义,以及所需要的时间.

表1 模型中库所和变迁的含义和分别所需时间Table 1 The meaning of places and transitions in the model and the time associated with them

至此,已完成了系统的建模.尽管,通过建模保证系统是无死锁的,但不能保证系统不会出现非法状态.考虑约束(1),它意味着对每一个库所pi都与此关联,一旦违反该约束,系统进入一个非法状态.而约束(1)满足与否,取决于ti0和ti1开始引发的时刻.注意到,ti0和ti1引发与否是一个离散事件,传统的方法通过数学规划建模和求解[15-19],无法逾越组合爆炸的问题.基于所建立的模型给出可行调度的定义如下.

定义4 基于为具有重入和晶圆驻留时间约束双臂组合设备所建立的PN模型,一个周期调度称之为可行的,如果在该调度下任何可达标识都是合法的,即在任何标识M下如果ti0被使能,有τi −ai≤δi,i ∈N3,成立.

基于所建立的模型和分析,本文应用离散事件控制理论,将一个调度视为一个控制策略,研究系统的可调度性,从而获得有效的调度方法.

4 可行调度存在性分析和调度算法

这里所讨论的调度问题需要满足严格的工艺约束,因此在给定的参数下存不存在可行解是一个首要问题.正如文献[22]中所指出,如果按照标准的交换策略,问题不存在单晶圆调度,甚至不能达到稳态.因此,首要问题是单晶圆稳态解的存在性.

4.1 单晶圆稳态解的存在性

令M={Γ1,Γ2,Γ3,Γ4}表示图2所示PN的标识,其中Γi={Wd(q)},i ∈N3,表示pi中的令牌.令牌Wd(q)表示第d枚送进系统中的第q道工序正在加工中,而Γ4={Wd(q)}表示机械手握着第d枚送进系统的晶圆,接下来要加工第q道工序.例如,如果第1、第2、第3枚晶圆正分别在PM3,PM2,PM1中加工,而机械手握着将要加工第1道工序的第4枚晶圆,此时的标识为M={W3(1),W2(2),W1(3),W4(1)}.因为第1道工序必须由PM1加工,因此机械手位于PM1并准备执行交换操作.实际上,如果按照标准的交换策略,这就是系统刚进入稳态时的标识,可认为是初始状态.

已证明,通过控制系统的初始标识可以求得单晶圆稳态调度[23].例如,如果初始标识为M1={W4(1),W2(4),W3(3),W5(1)},那么图2所示的PN的演化轨迹为

注意到M1和M6是等同的,因此完成了一个周期,并且加工完一枚晶圆.这一过程可以反复进行,因此是一个单晶圆稳态过程.

接下来分析一个周期的特点.在上面的演化过程中,从M1到M2需要执行变迁引发序列(机械手操作)σ1=〈在p1交换→引发t12〉;从M2到M3需执行σ2=〈在p2交换→引发t23〉;从M3到M4需执行σ3=〈在p3交换→引发t32〉;从M4到M5需执行σ4=〈在p2交换→引发t23〉;从M5到M6需执行σ5=〈在p3交换→引发t3L →引发tL1〉.序列σ3和σ4一起形成了重入过程的循环,称之为局部循环;而序列σ1,σ2,σ5一起形成了对全部3个步骤的循环,称之为全局循环.也就是说,从M1到M6包含了一个局部循环和一个全局循环.这意味着反复地从局部循环到全局循环,再从全局循环到局部循环的切换,每经历一个局部循环和一个全局循环之后,一个周期完成.

4.2 时间特性分析

从上面的周期性分析可知,系统的演化由机械手的操作决定,因此机械手的等待起着关键作用.实际上,后面将看到,一个调度完全由调节机械手的等待时间决定.因此需要合适地描述机械手等待时间.

4.3 可行解存在条件和调度算法

基于以上的分析,现在可以讨论可行解的存在性和调度算法.从式(9)以及式(11)-(14),可以得出如下结果:

令π1,π2i和π3i,i ∈{1,2}分别表示PM1,PM2和PM3完成一枚晶圆所需的时间.然后,基于式(9)以及式(11)-(14),可以得到下列这些表达式:

注意到,φ1和η1是已知常数.因此,按照上面的表达式,要决定π1,π21,π22,π31和π32就是要调节φ2,η2,φ3和η3,也就是要调节机械手在库所qij的等待时间.从图2所示的PN模型及其演化规则可知,当机械手的等待时间确定之后,所有机械手的操作任务均已确定.这就意味着,系统的调度可以通过调节机械手的等待时间,也只需通过确定机械手的等待时间实现.问题的关键在于如何调节机械手等待时间使得对所有的PM约束(1)满足,同时系统的生产率最高.

从前面的表达式还可知,通过调节机械手的等待时间可以在某种程度上改变晶圆在PM的驻留时间而保证晶圆可以加工完毕.下面讨论通过调节机械手等待时间使得系统总保持在合法状态空间内的条件及相应的调度算法.以下的结果来自文献[24],由于篇幅所限,这里只给出结论不提供证明,有兴趣的读者可以参考文献[24].

定理1 如果通过调节机械手的等待时间求得ψ使 得:1)π1=π21+π22=π31+π32=ψ;2)a1≤τ1≤a1+δ1,a2≤τ2i≤a2+δ2和a3≤τ3i≤a3+δ3,i ∈{1,2}.那么,对这里讨论的组合设备调度问题可以求得一个单晶圆稳态调度使得系统不会出现非法状态.

在定理1的条件下,调节机械手等待时间使得每一个PM完成一枚晶圆的时间相等,因此,需要将ψ2表达的等待时间合理地进行分配.要使非法状态不会出现,π1,π2i和π3i,i ∈{1,2},应该在一个允许的区间内,这一区间的下界ΠiL和上界ΠiU可表达为

注意到每一枚晶圆都要访问PM2和PM3两次,令Πmax=max{Π1L,2Π2L,2Π3L},基于定理1,算法1可以求得相应的可行调度.

调度算法1 如果[Π1L,Π1U]∩[2Π2L,2Π2U]∩[2Π3L,2Π3U]̸=∅以及η1≤Πmax/2成立,那么一个可行调度可以通过以下步骤决定机械手的等待时间获得

1)ω12=ωg22=ωl22=ωg32=ωl32=0;

可以证明,由算法1获得的解,有π21=π22=π31=π32,以及π1=π21+π22=π31+π32=Πmax=ψ,也就是说定理1的条件1)满足.此时,系统的节拍是Πmax.下面的定理保证由算法1获得的解满足定理1中的条件2).

定理2 假设1)[Π1L,Π1U]∩[2Π2L,2Π2U]∩

[2Π3L,2Π3U]̸=∅;2)η1≤Πmax/2;3)机械手等待时间由算法1确定.那么,所获得的调度对所有的PM均满足约束(1).

如果某些条件满足,下面给出的调度算法2也可求得可行的调度,从而保证非法状态不会出现.

定理3 假设1)Πmax/2<η1≤ΠiU,i∈{2,3};2)η1≤Π1U/2;3)机械手等待时间由算法2确定.那么,所获得的调度对所有的PM均满足约束(1).

定理3要求η1≤ΠiU,i ∈{2,3}以及η1≤Π1U/2.这就提出一个问题,如果η1>ΠiU,i ∈{2,3}或者η1>Π1U/2,是否可行解存在.下面的定理证明,如果η1>ΠiU,i ∈{2,3},系统不存在可行调度.

定理4 假设∃i,i ∈{2,3}使得ΠiU<η1,那么系统没有可行的单晶圆稳态调度.

但是,在某些条件下,当Π1U/2<η1成立时,系统仍可以求得单晶圆稳态调度.下面的定理给出了其条件.

定理5 假设1)Πmax/2<η1≤ΠiU,i ∈{2,3};2)Π1U/2<η1;3)η1+max{Π2L,Π3L,φ1}≤Π1U;4)机械手等待时间由算法2确定.那么,所获得的调度对所有的PM均满足约束(1).

以上的讨论要求[Π1L,Π1U]∩[2Π2L,2Π2U]∩[2Π3L,2Π3U]̸=∅,但是[Π1L,Π1U]∩[2Π2L,2Π2U]∩[2Π3L,2Π3U]=∅情况可能发生.在此情况下,令

定理8 对于这里讨论的组合设备的调度问题,一个由算法1至算法3求得的单晶圆稳态调度在生产率的意义上是最优的.

至此,基于本文的应用对象,介绍了基于控制理论的调度新方法的建模、解的存在性分析和求解算法的全过程.在文献[24]中,提供了应用的例子以显示如何应用所提出的方法,有兴趣的读者可以参考文献[24].需要指出的是,就上面讨论的应用问题来说,分析了所有可能可行解存在的情况.也就是说,上面的可行调度存在性分析揽括了整个可行解空间,因此所获得的解是最优的.

5 讨论

众所周知,与本文前面讨论的对象一样,生产过程本质上包含了离散事件过程,相应的调度问题是离散优化问题,涉及到组合爆炸的难题.因此,没有一般性的有效求精确最优解方法.特别是在有严格工艺约束的条件下,启发式算法和元启发式算法难于应用,系统的调度问题是严峻的挑战.为此,人们不得不应用数学规划建模和求解,但由于计算复杂性,难于在实际中应用.实际上,在半导体制造组合设备的调度中,除了本文的研究团队外,其他研究人员基本上应用数学规划方法进行研究,通过POPN建模,然后建立整数规划模型求解[15-19].由于整数规划求解指数增长的计算复杂性,其研究成果很难在实际中应用.

需要指出的是,当生产过程存在着严格工艺约束的时候,一定会存在着没有可行解的情况.因此,如果应用数学规划的方法,不仅求解困难,当求不出可行解时,还难于找出无解的原因.另外,一个离散调度问题,尽管用一般性方法求解面临着组合优化的难题,但并不意味着没有有效的方法可以求解.在某些情况下,根据问题的特征,有可能简单求解.

就半导体制造中组合设备的调度问题而言,应用基于离散事件系统控制理论的新方法,本文成功地将一个离散优化问题转换为决定机械手等待时间的问题,它是一个典型的连续优化问题.并且利用了其特点,使得最优解可以非常简单地求得.应用所提出的方法,解决了一系列半导体制造中组合设备的调度问题[25-36].

生产系统中的扰动是不可避免的,一个有效的调度系统需要对扰动快速和正确的响应.对此,基于数学规划的方法很难做到.应用本文提出的基于离散事件系统控制理论的新方法,半导体制造中组合设备的扰动可以有效地处理,并能保证其可行性[37-39].

组合设备是半导体芯片制造的关键装备,从前面的讨论可知,其加工过程是通过调度装备内部的机械手的动作实现的.这种调度不是芯片制造厂家完成的,而是装备制造商将算法写入到装备的控制器.因此,其调度算法是芯片制造装备研发的关键之一.由于,基于离散事件系统控制理论调度算法的优越性,本文研究团队正在与半导体芯片制造装备开发商合作进行相关装备的研发.

相对于半导体芯片制造组合设备的调度问题,石油化工生产过程的规模极其巨大、约束更多、需要优化的目标很多,因此其生产调度问题更为复杂、更为困难.基于离散事件系统控制理论的调度新方法成功地应用于炼油生产过程的调度问题,使得对于规模巨大的实际应用问题能够有效地求解[41-51].

本文所提出的方法的应用范围是一个需要进一步探索的问题.比如说什么类型工艺约束下的调度问题可以应用,用什么模型建模可以达到此目的.这需要根据实际应用问题进行分析,也是今后需要探索的方向.另一个问题是,可行性分析可能会损失某些可行解,导致可行解空间的压缩,从而降低解的最优性.对这一问题,一方面,可以通过对系统的深入分析,提高可行性分析的质量,从而提高解的质量.另一方面,在问题非常复杂并无法精确求得最优可行解的情况下,求得一个满意的次优可行解也是十分重要的.实际上,启发式算法、进化计算等方法都是为了解决计算复杂性而求次优解的方法.在启发式算法、进化计算等方法不能应用的情况下,本文的方法是一个很好的补充.

6 结论

尽管调度问题是一个经典的研究问题,并且人们认为相关的理论已经基本成熟.但是,一方面由于当今面对的系统越来越复杂,新的调度问题层出不穷,现有的理论和方法面临着挑战.另一方面,由于信息化的需要和工业4.0的提出,需要实现对系统的自动化管理和控制,对调度的有效性提出了更高的要求.

具有严格工艺约束的生产调度问题是目前面临的许多复杂调度问题中的重要一类.对这类问题已有的精确求解方法难于解决计算复杂性问题,不能满足实际的应用需求.而启发式算法和元启发式算法又不能保证调度的可行性,在很多情况下元启发式算法也不满足实时性要求.面对这一挑战,本团队在离散事件系统控制理论的框架下研究了半导体芯片制造组合设备、石化炼油过程、生化物质高速筛选系统的调度问题,提出了有效的求解方法.本文是这些方法的总结和提炼,并通过半导体芯片制造组合设备的调度问题进行介绍.接下来的工作是致力于将这一方法推广到更多的应用领域.同时,也将与相关的企业合作,努力将所获得的成果实现转化.