基于Petri网的批处理调度研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于Petri网的批处理调度研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：批处理过程存在于复杂的动态环境中，来自主客观的干扰及问题固有的易变性，会导致各种过程参数的变化，因此，需要研究对意外事件作出快速反应的动态调度方法，以捕捉生产环境的实时变化。该文针对批处理过程中最常出现的操作处理时间波动，提出了基于petri网仿真技术的批处理过程动态调度方法。仿真结果表明，该方法能有效地改善调度性能，为批处理过程动态调度的研究提供了新思路。

关键词：批处理；Petri网；调度

中图分类号：TP391文献标识码：A文章编号：1009-3044(2008)36-3031-03

Research for Scheduling of Batch Processes Based on Petri Nets

LIU Jun

(Computer Department, Hunan Institute of Technology, Hengyang 421002, China)

Abstract: Batch processes usually exist in a dynamic and complex environment. The objective or subjective disturbance, So, it is required to consider dynamic scheduling with quick responsivity to unexpected events so as to catch the real time changes in production environment. For the deviations of processing times more often occurring in batch processes, a dynamic rescheduling method is put forward in this paper by integrating with rule-based schedule and Petri net simulation. It indicates a new direction for the research in dynamic scheduling of batch processes. Some simulation examples are demonstrated for this method.

Key words: batch processes; Petri nets; scheduling

1 引言

批处理过程由于其固有的灵活性，特别适合于生产小批量、多品种且产出价值较高产品。批处理过程操作可分为三层：层的生产计划，中间层的产品调度与下层设备级的过程控制。其中调度层根据来自生产系统的信息，协调设备、原料及资料的可用性。一般有两种研究方法：一种是静态调度（或预调度，Priorischedule），将计划层来的定单一起分配到可用设备上去;另一种是动态调度（或反应式调度，Reactiveschedule），将定单按时间顺序分批安排，并考虑实际过程参数的变化。所谓动态调度，是当生产过程参数或调度数据变化时，根据过程的实时状况，重新产生一个调度或对原有调度进行在线局部修改的方法，以使生产约束得到满足，生产代价最小。其定义包含了重调度与在线调整两个方面。动态调度的任务是指根据来自设备级的反馈信息和实际的系统状态数据，决定下一步执行哪个操作，它的目标是在整个过程遇到扰动和故障时，根据系统监控到的实时情况修改原定的生产顺序和调度系统的所有资源，使批处理系统持续地、优化地运行。

Petri网用于批处理过程的调度与优化是当今的研究热点，可大多属于离线的调度。它们都是事前调度，缺乏对过程动态因素的考虑。有些方法考虑了处理时间的波动，但倾向于求解可行调度，并未涉及优化问题。批处理过程全局协调层要求调度能实时计算并考虑实际过程中可能出现的变化。本文利用赋时Petri网模型和规则调度思想，基于Petri网仿真技术进行动态调度研究。首先，提出了基于Petri网仿真技术的动态重调度框架；然后，讨论了面向过程动态资源分配状况，自适应选择启发式调度规则的方法。仿真结果表明，该方法不仅能明确表示批处理过程中资源的复杂交互关系，而且能给出最优的过程控制序列，还可以根据过程监控设备检测到的处理时间变化，及时修改延迟时间矢量，重新快速地产生一个新的调度，改善调度性能。

2 基于Petri网仿真的动态调度框架

2.1 动态调度原理

用于计算调度的批操作时间，是往常处理时间的经验值估计。实际的反应时间可能随着设备状态(如原料质量、浓度、反应温度)的变化而波动；另外，反应时间的测量往往是不可行的，有时即使可以测量，也会因为延迟太大，使测量数据无法用于实时分析。因此，很难取得混合物的当前信息，也就无从估计反应的持续时间了。可见，追求离线计算的最优操作顺序是不现实的，因为过程扰动随时都可能发生。本文提出了基于Petri网仿真技术的动态重调度框架，如图1所示。

它由TPPN仿真器、过程监控设备、调度规则库及执行器等组成。执行器负责将TPPN 仿真器产生的调度指令，转化为过程的控制代码，启动批处理设备的运行。过程监控设备采用文献[2]的连续过程仿真器，估计连续活动的延迟，即依据物理过程的连续模型和混合物的当前状态，推断反应操作的实际持续时间，以估计处理时间的偏移(deviation)，并将结果反馈至TPPN 仿真器。具体过程为：根据过程的名义延迟时间矢量DT，应用Petri网模型与启发式调度规则相结合的规则调度方法，事前计算一个静态调度S0，指导过程的运行。过程启动后，对每一个已调度的操作，监控设备记录其名义处理时间(PPTi)和操作开始时间(PSTi)，估计反应的实际完成时间(CTi)，并计算偏差D =(CTi－PSTi)－PPTi。假设D0 为允许处理时间漂移的偏差范围，那么当D≤D0 时，过程继续按原始调度执行；当D＞D0 时，仿真器及时修改延迟时间矢量DT，触发“重调度”。在新的时间和状态起点上，按照当前的系统动态特征，结合启发式调度规则，重新计算调度(控制代码)，以指导尚未调度操作的执行。由于频繁的重调度，将导致紧迫的设备调整和物料传输，使劳动力和生产费用增加，并影响生产的连续性。因此，这里规定D0 为误差的累积，当且仅当D＞D0 时，启动“重调度”，以减少重调度的次数，保证操作的连续性。

2.2 赋时Petri网模型

赋时库所petri网(Timed Place Petri Nets 或TPPN),可用如下6元组表示：TPPN= (P,T,I,O,M0,DT),其中(P,T,I,O,M0)是基网,P是由简单库所、动作库所和控制库所组成的有限库所集，简单库所表示资源（反应器、原料或中间产品），动作库所表示过程操作，控制库所表示外部控制；T是由可控和不可控变迁组成的有限变迁集。可控变迁的触发可通过外部控制禁止，反之称为不可控变迁；DT:P－>R+为托肯在相应库所中的逗留时间，DT={dτ0 , dτ1 , dτ2 , …, dτm }。

在petri网表示的事件驱动系统中，每一库所、变迁分别由一个条件、事件唯一标识。在第k步,网的标记由n维行矢量M(k)=[mp0(k),mp1(k), …,mpn(k)]给出,初始标记M0=M(0)，petri网标记从k步至k+1步的演化可由如下状态转移方程来描述：

M(k+1)=M(k)+Hu(k)（1）

其中H为n×m邻接矩阵,u(k)为m维控制列矢量,即第k步触发矢量。在 u(k)中,与第k步触发的变迁相对应位置处，u(k)的元素为1，其余元素为0。

由于实际系统的逻辑规范和时间约束，当一个变迁使能时，它也许并不立即触发。在实时批处理过程优化中，系统的行为不仅取决于事件发生的逻辑结果，而且取决于事件发生的时间。这里采用TPPN建模，所有变迁的触发都是瞬时的。状态矢量x (τk) ＝( x0 (τk) ，x1(τk ) ， x2(τk) ，…， xm(τk))中，元素xi(τk) 表示在状态演变的第k 步，托肯到达库所pi中的时间。如果pi中没有token，则xi(τk)=-1；如果pi中有token，则xi(τk) 表示该token 到达库所pi 的绝对时间。对于给定的初始标记M0,初始状态矢量为:

■（2）

延时矢量DT包含每一库所的延迟时间dτi在使能矢量v(τ)=(v0(τ), v1(τ), … vj(τ), …, vm(τ))中，vj(τ)表示变迁tj 可触发的最早时间(tj 的使能时间)，等于其所有输入库所中token 可用时间的最大值，v(τ)的元素可如下计算：

i+xi(τk)}（3）

式(3)说明当一个托肯到达pi后，它至少应在pi中逗留dτi个时间单位,才可用于其使能输出变迁的触发。

本文采用赋时库所Petri网(Timed Place Petri Nets 或TPPN)来建模，如果将每一操作用一个变迁对(t, t')和一个库所p来建模，变迁t/t'分别表示操作的开始/终止，库所p表示操作本身，且p∈OP(t)∧p∈IP(t')，那么在设备R中完成的子处理可用如图2所示的子网来描述，其中p'/p''表示原料/产品，资源库所r 表示处理设备R，IP(t)/OP(t)表示t 的输入/输出库所集合。

2.3 仿真算法

2.3.1 仿真用于动态调度

动态实时调度要求现场反应速度快、调度命令可执行性好。在离散事件控制中，仿真技术用于评价和选择调度方案、分析系统的动态性能，还可以预测拟采取的生产步骤的可行性，发现生产过程的非正常状态。仿真调度方法具有较强的模型描述能力，克服了复杂问题求解析解的困难；在仿真方法中引入人工智能，可使本来计算复杂性很高的问题也能求得可行解；专家系统决策的规则，增强了系统处理意外事件的能力和结果分析能力。因此，开发基于规则的决策调度系统，是综合专家系统和仿真技术，共同解决实时批处理调度问题的一条有希望的途径。基于Petri网仿真的批处理动态调度方法，利用启发式调度方法速度快、对问题规模不敏感的优点，并在仿真中交叉使用多种调度规则，以选出较好的规则，作为解决冲突的依据。所以，它能自适应地跟踪过程参数的变化，适合于解决动态调度问题。

2.3.2 调度规则

本文选取了6 种调度规则，采用分层决策的方法，动态地分配资源，减小设备空闲时间，即：1) EDD：交货期最早的作业，其操作优先；1) FCFS：先到先服务；2) SPT：处理时间最短的操作优先；3) MWKR：剩余总加工时间最大的作业，其操作优先；4) LWKR：剩余总加工时间最小的作业，其操作优先；5) MONPNR：剩余操作数最大的作业，其操作优先；6) RANDOM：随机选择一操作。

经过大量的仿真试验可得出：对使能的冲突变迁，如果有交货期约束，则按规则1)选择优先执行的操作；否则，如果其所属作业的剩余操作数不同，则按规则5)选择优先触发的变迁；要不然按规则3)或4)选择优先变迁。如果其所属操作的剩余操作数及剩余总加工时间均相同，则按规则6)任意选择优先变迁。另外，对于复杂的调度问题，如果无法估计调度规则及其组合对调度性能的影响，则仿真可以作为决策的依据，通过多个仿真结果的比较，确定有利于调度目标的控制和决策规则。

2.3.3 优化算法

在基于Petri网的离散事件仿真过程中，随着仿真时间的推进，按“先使能先触发”的变迁规则，控制变迁的触发，利用Petri网的矩阵方程分析方法和式(4)计算新的状态，形成优化算法：即根据网的当前状态和该状态发生的时间，确定下一步可能发生的最优变迁集，使Makespan为最小。当系统状态转移到终态时，相应批量产品库所中token的到达时间即为该产品的Makespan，并行产品流中最大的Makespan即为批处理系统的循环时间。仿真过程中采用强触发规则，使能的变迁立即触发，如果遇到多个同时使能的冲突变迁，则根据系统运行中的动态资源分配情况，利用上述启发式调度规则，对冲突变迁进行排序，随后仿真继续运行，直至到达终态。算法流程如图3所示。但是，这里涉及到调度系统与被控过程的交互，即当每步控制命令启动后，在执行器驱动的操作执行过程中，监控设备检测子任务延迟的实际偏差D，当D 累积至一定程度(如D＞D0)时，触发“重调度”。

3 仿真实例

考虑如图4所示的多目的批处理过程，由4个批设备和3个不同的产品流程组成。系统循环地执行预先定义的各个任务，即：原料A 分别在设备R1、R2、R3、R4上处理20、13、8、6 min，生成产品A；原料B分别在设备R1、R3、R4 上处理13、24、7min，生成产品B；原料C 分别在设备R4、R2、R1 上处理20、10、7min，生成产品C。

按照TPPN建模方法，可得过程的Petri网模型图(略)。生产过程开始时，系统的初始标识为M(0)=(1,0,0,0,0,0,0,0,0,1,0,0, 0,0,0,0,1,0,0,0,0,0,0,1,1,1,1)，终止标识为M(K)=(0,0,0,0, 0,0,0,0,1, 0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1)，延迟矢量DT=(0,20,0,13,0,8,0, 6,0,0,13,0,24,0,7,0,0,20,0,10,0,7,0,0,0,0,0)，初始状态矢量x(τ0)=(0,-1,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,0,0,0,0)。当系统到达终止状态M(K)时，状态矢量演变为x(τK) 。在x(τK)中，与批量A、B、C 产品库所相应的分量xi (τK )的值，即为产品的完工时间Makespan。设τ0 =0，按给定的DT，采用“先使能先触发”的状态转移规则，指导过程Petri网的运行，当遇到冲突变迁时，通过交叉使用多种调度规则进行仿真，并从中选出较好的规则，作为解决冲突的依据。这里按照LWKR规则，选出优先触发的变迁，预先产生一个调度S0。S0 给出了各个批处理设备的生产顺序R1：ABC；R2：CA；R3：AB；R4：CAB。

假设生产启动后，检测到批量A在反应器R1上的处理时间由20 min 变为21 min，令延迟偏差D =0.5，则仿真器触发“重调度”，根据过程监控设备检测到的实际处理时间，结合系统的即时动态，重新计算一个调度S，以减小因处理时间的波动而引起的设备等待时间，提高设备利用率，改善调度性能。S给出的批设备的生产顺序为R1：ABC；R2：AC；R3：BA；R4：CBA。仿真结果表明，当发生过程参数(反应时间)摄动后，如果采用S0 调度策略，将使设备间的等待时间明显增加；如果根据过程监控设备检测到的现场工况，动态调整资源分配，即按照S给出的生产顺序控制尚未调度操作的执行，将缩短设备之间的等待时间，减小批处理循环时间。可以看出，S相对于S0，不仅需要较少的迭代次数，而且可使批处理循环时间减小12%。下表给出了S0、S调度结果的比较。

4 结论

本文提出了基于Petri网仿真技术的批处理过程动态调度框架，过程监控设备和过程的Petri网仿真器。过程监控设备用于检测操作的实际延迟时间；Petri网仿真器根据给定的延迟时间矢量，通过仿真Petri网的运行来计算调度。仿真结果说明了该动态调度方法的有效性和可行性。

参考文献：

[1] Wu Zhiming.An FMS Dynamic Model Based on High-Level Petri Nets[N].China Computerworld,2005-04.

[2] 李慧芳.基于赋时Petri网的化工批处理过程建模与控制优化[J].控制与决策,2000(4).

[3] Girault C.系统工程petri网[M].北京:电子工业出版社,2005.

[4] 袁崇义.Petri网原理[M].北京:机械工业出版社,2006.

[5] 李慧芳.基于Petri网仿真的批处理过程动态调度[J].系统仿真学报,2002.

[6] French S.Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop[M].New York:John Wiley & Sons,2002.

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”