基于Petri网与多代理的半导体调度系统建模及仿真

何睿超，徐骏善，汪惠芬

(南京理工大学机械工程学院,江苏 南京 210094)

近年来，半导体战略地位逐步提升，其带来的经济效益有力推动了国民经济。半导体制造过程属于可重入生产[1]，其工艺复杂，单元生产和流水线生产的调度策略无法完全适用于其生产线，因此半导体生产调度问题成为国内外学者的研究热点。

刘小华等[2]利用数学规划法建立可重入生产系统调度模型，采用混合智能搜索算法对其进行求解，但该方法仅适用于规模较小、性质简单的问题。相比数学规划法，Petri网强大的建模与数学分析能力使其成为各种复杂生产系统建模的优先选择。左婷[3]、程培林[4]采用Petri网建立调度模型，并使用遗传算法进行求解，但该调度模型仅用于求初始解，未能最大化Petri网的作用。文献[5]、[6]采用启发式搜索方法对建立的Petri网可达树进行调度结果搜索，虽然有效利用了Petri网的动态特性，但建立可达树的方式难以运用在层次、着色等Petri网。Zhang等[7]将芯片制造车间的设备映射为调度代理，据此建立了瓶颈设备之间多代理协调交互的Petri网模型，并在EM-plant上进行仿真求解，与实例对比后证明所提方式改善了系统产量，但由于EM-plant非Petri网仿真软件，建立的Petri网模型需要经过二次转化才可在EM-plant上构建。此外，文献[8]～[10]分别将多代理系统(MAS)应用于车间调度、物流配送、卫星任务规划问题中，证明了多代理系统是解决复杂问题的有效方式。

本文在上述文献研究的基础上，引入多代理系统求解半导体调度问题。在分析半导体调度问题的约束条件与目标函数的基础上，设计了基于多代理的调度机制，结合Petri网建立针对半导体的调度系统，最后运用Petri网仿真软件CPN Tools对该调度问题进行求解。

1 调度系统组织结构及调度机制设计

1.1 “图案成型”生产过程简介

芯片制造是半导体制造中的关键步骤，工艺通常包括“薄膜淀积”“图案成型”和“半导体掺杂”。其中“图案成型”是半导体制造的基础。“图案成型”多重入工艺可以归纳为图1所示的9步，所使用设备包括表面处理设备、喷胶机、加热板、光刻机、显影机、检查设备、等离子刻蚀设备、湿法工作台。以某半导体制造商的“图案成型”生产线为例，该生产线由图2所示4个加工区域及11个设备组组成，区域内包含若干设备组，设备组内的任一设备都能完成同样的操作。

图1 “图案成型”工艺流程

图2 “图案成型”生产系统示意图

1.2 调度问题数学模型

半导体“图案成型”生产系统包含多个加工区域，每个加工区域内有若干包含不同数量设备的设备组，用于完成产品加工过程中的某道工序。产品在系统中完成一次表面加工的完整过程称为一个加工阶段，一个加工阶段是若干个工序的有序集合，整个生产过程是加工阶段的不断循环过程。

将该系统调度问题描述为：生产线由M个加工区域内的N个设备组组成，Aream代表第m个加工区域，Gmg代表第m个加工区域内第g个设备组，其最早可用时间用TGmg表示，Emgk代表该设备组内第k台设备，其最早可用时间用tg(mg,k)表示。

集合P={P1,P2,…,Pp}，代表待加工的批次集合,其中Pi为批次号为i的在制品，i=1,2,…,p；集合LS={LS1,LS2,…,LSls}，代表若干加工阶段，其中LSa为第a个加工阶段，a=1,2,…，ls;每个加工阶段完成工序序列S={S1,S2,…,Ss},其中Sb为加工阶段LSa中第b个工序,b=1,2,…,s。设定在制品Pi的交货期为Di，加工优先级为Oi，第a个加工阶段中的第b个工序表示为(Pi,LSa,Sb)，该工序开始时刻为t(i,a,b)，加工工时为T(i,a,b)，(i,a,b)表示Pi的第a个加工阶段中的第b个工序，同理用t(i,1,0)表示Pi到达时间。记布尔值B(i,a,b,g)={0,1}，表示该工序是否在设备组Gg中完成。调度问题中存在的约束如下。

1)在制品Pi前后工序的先后顺序的时间约束：t(i,a,b)+T(i,a,b)≤t(i,a,b+1)，若是两道工序分属不同加工区域，则必须在公式左侧加上搬运时间。

3)工序(Pi,LSa,Sb)在设备组Gmg中开始加工时刻的约束：t(i,a,b)≥max{TGmg,(t(i,a,b-1)+T(i,a,b-1))}。

6)在制品完工时间应尽量小于交货期：t(i,ls,s)+T(i,ls,s)≤Di。

本文在综合考虑批次加工优先级、交货期及滞留时间(等待时间)对单个批次优先参与调度的促进作用的基础上，采用以下3项指标作为确定缓冲区中批次作业顺序的调度决策目标。

1)批次加工优先级LP(i,a,b)。

LP(i,a,b)=Oi·a

(1)

式中：Oi为批次初始优先级。

2)关键比例CR(i,a,b)。

(2)

式中：T为当前时间；Trt为Pi剩余工序加工总工时。

3)批次已松弛时间比例RTR(i,a,b)。

(3)

式中：Tct为已加工工序总工时。

调度决策目标函数为：

(4)

f(i,a,b)=ω1LP(i,a,b)-ω2CR(i,a,b)+

ω3RTR(i,a,b)

(5)

式中:ω1,ω2,ω3为权重系数，规定ω1+ω2+ω3=1。

本文在各类参考文献及这上述3项指标对调度影响的重要性的基础上，取ω1=0.3,ω2=0.5,ω3=0.2。

1.3 多代理系统的组织结构设计

为解决半导体“图案成型”调度问题，设计了图3所示的多代理系统。系统由任务接收Agent、工艺Agent、调度Agent组、设备资源Agent、任务执行Agent组成，其中调度Agent组由中心调度Agent、区域调度Agent和组调度Agent组成。

图3 多代理系统组织结构图

1)任务接收Agent：负责接收新生产任务，并与工艺Agent协同获取任务工艺路线，而后向中心调度Agent传递生产任务。

2)工艺Agent：存储所有产品的工艺路线。

3)调度Agent组：负责对系统中的生产任务进行调度排程。

①中心调度Agent：负责对系统全局任务进行调控。接收来自任务接收Agent的新生产任务和来自区域调度Agent的已完成任务，将所有工序均已完成的任务放入结束结点，未完成的任务调度后下发至对应区域调度Agent。

②区域调度Agent：负责区域内调度子任务，共有4个。接收中心调度Agent的待加工任务，及设备组调度Agent的已完成任务，将已完成任务中下道工序不属于本区域的任务上交给中心调度Agent，仍属于本区域的任务与待加工任务调度后下发给对应设备组调度Agent。

③设备组调度Agent：负责组内调度子任务，共有11个。接收区域调度Agent的待加工任务与任务执行Agent的已完成任务，将组内成功完成的任务上交给区域调度Agent，需重加工的任务与待加工任务一并根据设备组的设备状况及任务加工工时进行调度后下发给任务执行Agent。

4)任务执行Agent：负责实际任务的完成。从设备组调度Agent处接收任务，指派给设备组最早可用的一台设备完成，并更新任务最早可开始时间、设备组最早可用时间，将已更新的任务传回设备组调度Agent。

5)设备资源Agent：用于记录系统中设备的类型、数量、使用状况等等，为其他Agent提供相关信息。

各代理之间的信息交互如图4所示。

图4 代理间信息交互图

1.4 基于招标-投标策略的调度机制设计

采用合同网中招标-投标策略的多代理信息交互与协商技术解决多代理任务分配问题，将各个调度Agent映射为招标方，设备资源Agent映射为投标方，通过代理间相互协作和任务竞争，解决调度问题。

1)招标策略：调度Agent选取到达时间在一定区间范围内的任务，组成可招标任务集合T={T1,T2,…,Tt},Tt为第t个招标任务。然后根据式(5)对任务权值进行计算，依据式(4)选取集合中招标任务。

2)投标策略：设备资源Agent中的各设备判断自身类型与任务工序是否匹配，以及招标任务开始时间与设备最早可用时间是否冲突，二者之中任意一个条件不满足，则拒绝投标。

3)评标策略：根据任务完成的最早时间进行评标。

各个Agent根据上述策略，相互协作，分别完成各自承担的子任务。设计本系统的调度步骤如下：

Step1， 任务接收Agent接收到新任务后，与工艺Agent协同，制定任务招标书，并将招标书传递给中心调度Agent。

Step2，中心调度Agent按式(5)第一项因式计算新招标书权值，与Agent中待调度的招标书一道按权值顺序投至所属区域调度Agent。区域调度Agent对区域内所有待调度招标书进行权值排序，分拣后投至对应设备组调度Agent。

Step3，设备组调度Agent通过各Agent协同，更新组内所有待调度招标书权值(式(5))，根据式(4)决出首先招标的任务，传递给任务执行Agent，并向设备资源Agent发布招标。

Step4，对当前空闲且符合工序要求的设备进行投标，任务执行Agent根据任务最早完成时间决出中标设备。若有多台符合条件的设备，则从中随机挑选一台设备。

Step5，执行完毕后，由任务执行Agent和设备资源Agent分别根据执行结束的时间更新招标书中任务的下一道工序最早可开始时间和设备最早可用时间，并将已执行的招标书返回设备组调度Agent。

Step6，设备组调度Agent判断招标书执行结果，若需重新加工，则将招标书放入组内待调度集合中，否则上交给区域调度Agent。区域调度Agent判断招标书下道工序是否在本Agent管辖范围内加工，若判断结果为是，则将招标书放入区域内待调度集合中，否则上交给中心调度Agent。

Step7，重复执行Step2～Step6，直到所有调度Agent中的待调度集合都为空。

2 基于HTCPN的调度系统建模

半导体制造系统属于大型复杂生产系统，使用基本Petri网建模往往出现结点过多、空间爆炸的现象，难以描述出系统全貌，而层次、着色Petri网是缩减模型结点、对大型复杂系统进行建模的有效工具。本文以层次赋时着色Petri网(HTCPN)为建模方法，利用仿真软件CPN Tools建立调度系统。

2.1 调度系统建模

使用至顶向下的层次网开发模式，首先构造调度系统的系统层，而后构造相应子页。系统层简图如图5所示，共有7个替代变迁，分别代表设备组设定模块(EquipmentAgentsSets)、工时设定模块(ProceedTimeListSets)、任务接收模块(ReceiveTask)、中心调度模块(CenterControlDispatch)、区域调度模块(Area Dispatch Agent)、组调度模块(Group Dispatch Agent)和任务执行模块(Excution Agent)。前2个模块用于设定设备资源Agent的设备型号、数量、加工工时，后5个模块分别对应任务接收Agent、中心调度Agent、区域调度Agent、设备组调度Agent和任务执行Agent。

图5 半导体调度系统模型系统层

模型内主要颜色集的设定如下：将加工任务定义为赋时颜色集Task，Task为五元组(Product, ProduceList, KW, StartTime, Result)。其中Product记录任务所代表的批次的详细信息，是由批次号、产品型号、优先级、交货期、到达时间构成的五元组赋时颜色集；ProduceList记录任务工艺路线，是由加工阶段、工序构成的二元组颜色集的列表；KW记录任务权值；StartTime记录任务当前工序最早可开始时间；Result记录任务当前工序执行结果。TaskList为代表加工任务集合的有序列表。将设备定义为由四元组(EGroup,ENum,EnableTime,Estate)构成的颜色集Equ。其中EGroup记录设备所属设备组信息，由设备组类型、组内设备总数组成；ENum记录设备编号；EnableTime为设备最早可用时间；Estate记录设备当前状态。将设备组EquGroup定义为二元组(Equs,GETime)。其中Equs为组内的设备列表；GETime为设备组最早可用时间。为方便管理，定义EGAL为制造系统内所有EquGroup的列表。设定工时为三元组(PType,LotStage,EquType)构成的颜色集，其中PType为产品类型，LotStage表示当前加工阶段，EquType为设备定型。定义PTL为产品所有工序所需工时的列表。

本文以中心调度Agent、设备组调度Agent及任务执行Agent页面为例进行介绍。中心调度Agent子页面如图6所示，库所UnscheduledQueue和CompletedTask为输入库所，分别代表新任务与已完成任务，两者非空时，将分别激发其下用于权值排序的变迁。变迁CenterControlDispatch用于依次判断待调度队列中任务是否已完成，未完成任务将传向对应加工区域，变迁handle1～handle4代表区域间任务的搬运，时间戳@+handtime为简化的搬运时间延时。变迁OrderbyKw1～OrderbyKw4负责根据任务权值大小对集合内任务进行排序。输出库所Area1Queue～Area4Queue代表下发给各加工区域的待加工任务集合，End代表结束结点。

图6 中心调度Agent子页面

设备组调度Agent子页面如图7所示，变迁TaskFeedback和JudgeRes用于从执行Agent反馈回的完成列表中取出任务并判断任务加工结果，变迁GDA3用于判断任务下道工序所属加工区域是否与本道工序相同，同样具备排序功能。该Agent需要与设备资源Agent进行协同，完成任务权值的计算。图中使用11个替代变迁GroupAgent1～GroupAgent11描绘组调度的细节，这些替代变迁指向的子页面如图8所示，变迁UpdateKweight完成待调度任务集合中所有任务权值的计算，变迁SearchFirst-Task和Research分别用于决出集合权值最高的任务和系统状态更新后再次计算任务权值。

图7 设备组调度Agent子页面

图8 组调度Agent内部图

在任务执行Agent页面(如图9所示)，变迁ExecutionAgent负责更新执行后的任务状态与设备资源状态，时间戳@+(#currentt t)代表任务当前工序工时时延，@+(EType(t,egal)-intTime())时延为设备组新的最早可用时间与过去最早可用时间的差值。

图9 任务执行Agent页面图

2.2 实例验证

为验证本文构建的调度系统的有效性与可行性，以某半导体制造商“图案成型”生产系统(图2)实际生产数据作为模型参数，在CPN Tools仿真平台上进行验证。用于测试的产品型号为A、B、C3种，加工区域中各个设备组的设备数及各工序工时见表1。实际生产中的调度策略为以先到先服务(FIFS)为主的人工调度方式，因而以提出的基于招标-投标调度机制的调度系统(以下简称调度系统)与实际生产中的FIFS策略(以下简称FIFS)两种方式在仿真平台上运行出的调度结果作对比。系统长期运行方面，以实际生产中固定在制品水平作为投料策略，3种产品投料比例为1∶1∶1，分别比较系统生产速度、设备利用率、订单延误率3个指标；短期少量批次调度方面，分别比较最大完工时间、平均加工时间、平均等待时间3个指标，为实际生产的调度决策提供有力参考。

表1 产品型号及对应各工序加工工时信息表

1)系统长期运行角度。

为确保仿真结果的有效性和普适性，将系统独立运行10次，每次运行10 000个时间单位，取平均值进行分析和评价。系统单位时间产量与设备利用率如图10、图11所示。

图10 系统单位时间产量及增长率曲线

图11 设备利用率

由图可知，调度系统单位时间产量几乎均高于FIFS，随着时间的变化，其总产量相对FIFS的增长率在2.26%～4.46%之间波动。各设备组利用率相对FIFS的涨幅为1.1%～7.8%，经统计，两者的平均延误率分别为3.85%与5.19%。由此证明,提出的调度系统对于生产系统的长期调度安排上，可以提高系统的生产率和设备利用率，延误率也更低，优于FIFS策略。

2)短期少量批次调度角度。

用于考察短期调度影响的5个调度批次随机产生，具体信息及详细调度结果见表2。

表2 短期调度批次详细信息及调度结果

由表可以看出，调度系统中的平均工时与平均总等待时间分别比FIFS少1.29%与10.34%。虽然FIFS首批完成的时间比调度系统更早，但由于优先加工某个不适宜的批次导致的等待使得之后的批次加工时间被拉长。结果表明，短期少量批次的调度中，调度系统能取得更短的总加工时间和更少的等待时间。

3 结束语

本文围绕半导体“图案成型”生产系统的复杂调度问题，提出了一种基于层次赋时着色Petri网与多代理的调度系统。分析了调度问题的约束条件及调度决策多目标函数，将解决调度问题的多代理系统组织结构设计为包括任务接收Agent、工艺Agent、调度Agent、资源Agent及任务执行Agent的混合结构，并基于代理之间的招标-投标协同交互方式设计了调度机制，给出多代理系统的调度步骤，最后以HTCPN建模方法，在仿真软件CPN Tools上建立该调度系统模型。经过实例验证，本文构建的调度系统是可行和有效的，该方法为半导体制造的调度优化提供了一种新思路。