petri网定义与两种时间添加策略

2PETRI网定义与两种时间添加策略摘要本章首先阐述了炼油企业级优化的意义与重要性。在此基础上对炼油厂供应链的背景和研究现状做了介绍。关键字PETRI网21PETRI网基础定义PETRI网最初由德国CARLADAMPETRI博士于上世纪60年代提出，针对当时自动机理论缺乏并发概念，无法研究现代物理学理论中典型问题，如狭义相对论，不确定性原理。PETRI博士提出了一种新的离散事件建模工具与方法PETRI网。PETRI博士在博士论文用自动机通信中首次使用网状结构模拟通信系统，该系统模型后来以PETRI网为流传。现在我们看到的PETRI网既指这种模型和衍生模型，又指各种以这种模型为基础发展起来的理论。PETRI网是一个状态变迁模型，可用来描述系统中各异步成分之间的关系，而且允许同时发生多个状态变迁，PETRI网是1个并发模型。在分析并行系统的状态行为的技术中，PETRI网模型具有自然，直观，简单易懂等特点。目前在有限状态机、通信协议、同步控制、生产系统、形式语言、多处理器系统建模与分析中都取得了广泛的应用。本文主要使用PETRI网对生产系统，尤其是化工批处理系统（过程），FLOWSHOP问题，FMS（柔性制造系统）进行问题建模，同时采用了网的可达树模型进行了上述系统调度问题的分析和研究。PETRI网框架由以下几个基本元素组成库所，变迁和有向弧组成。在图形上分别用圆圈、矩形和带箭头的连接线表示。在网模型通常建模对象的变动，例如柔性制造系统中的机器可以处于加工状态和闲置状态，生产线上的子部件流转均用PETRI网中的TOKEN表示（TOKEN，也翻译作令牌）。图21显示了一个最基本的PETRI网模型。该模型在化工批处理过程中即可以作为一个加工装置的生产过程元模型，也可以作为FMS中的一台机器的加工操作元模型。通过对该模型在规模上的拓展和时间上的衍生，就可以得到一般性调度问题的模型。一个不具有时间属性的通用PETRI网模型Z可以定义如下定义21,其中为基础模型结构，称为基网，,0,1）是有限库所集合；1,2,2）是有限变迁集合，同时和；1,2,3）是定义连接库所到变迁有向弧的输入函数，其中0是正整数集；4）是定义连接变迁到库所有向弧的输出函数；05）是初始标识；00另有一种六元组形式化的定义，。该定义多了,0,一个库所容量函数，按K函数的取值可将PETRI网分为无界网和有界网。如果取，则无界网，而,则为有界网。KK在系统状态变化上，PETRI网给出了详细的变迁激发规则定义22变迁激发规则当且仅当，变迁T能够被激发，,0,。,其中，表示标识M下变迁可以被激发，表示和不能同,时被激发。变迁冲突在多数情况下是由于加工资源有限引起的，我们将在相关章节中详细讨论这一问题。22时间PETRI网为了分析时间相关问题，例如通信系统中迟滞和制造系统中的调度问题，具有时间属性的PETRI网被提出来，本文正是采用时间PETRI网对所研究调度问题进行建模。PETRI网添加时间属性的方式主要分为两类库所延迟时间PETRI网PLACETIMEDPETRINET，以下简称PTPN以及变迁延迟时间PETRI网TRANSITIONTIMEDPETRINET,TTPN。下面分别PTPN和TTPN的相关定义与变迁激发规则。221PTPNPTPN顾名思义，即在库所上添加延迟来表示网的时间属性。在被建模系统中，例如FMS，通常带有延迟的库所表征的是一个加工状态。同时，建模系统可能存在某些库所并不需要延迟，例如FMS中的中间缓存BUFFER。所以PTPN的库所可以分为两类带有时间延迟的库所和不带时间延迟的库所（也可以理解库所延迟为0）。定义24PTPN是一个六元组，其中，,0,1）是有限库所集合；1,2,2）是有限变迁集合，同时和；1,2,3）是定义连接库所到变迁有向弧的输入函数，其中0是正整数集；4）是定义连接变迁到库所有向弧的输出函数；05）是初始标识；006）是分配变迁延迟的函数。0图21是本文研究调度问题中一个基本操作（或加工步骤、处理过程）的PTPN模型。采用PTPN对该过程建模，一个基本操作将需要输入输出库所,对应着一台机器的输入输出缓存，中TOKEN对应待加工和加工完中间1,21,2件可能是最终产品，机器资源库所对应加工机器状态，加工开始结束变迁。,由于库所具备时间延迟，为了表示网时间属性，PTPN多采用一个全局时钟来表征网到达当前标识的时间。222PTPN网的全局时钟计算方法PTPN网采用全局时钟来表征网到达当前标识（状态）的时刻，在PTPN下，变迁是立即触发的。触发后将消耗输入库所的TOKEN，并立即在输出库所添加TOKEN。库所延迟体现在，输出库所新产生的TOKEN将在时延结束后才能用于后继变迁的激发。时钟的计算方法与库所延迟以及相关输入输出变迁相关，如果不人为的干预变迁激发，例如在库所后继变迁使能后，强制延迟变迁激发时间。网的全局时钟计算方法如下GM,由于库所延迟描述对象的原子性，所以状态B在后继算法中并不存在，只是为了便于理解而添加的中间过渡状态。P2P1TSTEP21TSTETIME0TIME0P2P1TSTETIME22P1TSTETIME2P开始计时图21PTPN模型223TTPN网的时间属性添加方法TTPN网为每一个TOKEN分配独立的时间戳，其定义如下定义23TTPN是一个六元组，其中,0,1）是有限库所集合；1,2,2）是有限变迁集合，同时和；1,2,3）是定义连接库所到变迁有向弧的输入函数，其中0是正整数集；4）是定义连接变迁到库所有向弧的输出函数；05）是初始标识，其中是包含TOKEN数量和时间属性的多重0集；006）是分配变迁延迟的函数。0TTPN下模型一个库所中TOKEN的记录方法如下1122其中，表示从时刻开始可行的TOKEN数量为，在TTPN下，变迁激发除了满足定义22在输入TOKEN数量上的限制，每一个用于激发变迁的TOKEN还应满足时间戳不大于当前激发时间。定义25TTPN使能规则,|,|,0,转至步骤4；步骤7判断当前标识M是否为目标标识。如果,则进行如下计算判断；否则，进行步骤8；A计算从到时间,0B如果,对上限进行更新,0,0则称直接相连，记为,定义432如果存在库所和满足以下条件1,2,则称是相连的，中表示加工状态的库所则构12,1,2,成连接的加工路径S。,定义43RCR矩阵RCR|0,0,1,2,其中，,为连接库所到库所的机器资源路径。12为这些加工库所消耗时间之和。定义432,即为加工库|0所P所使用的机器资源集合定义431；RS0|其中，为加工库所P使用的机器资源数量。例如，上图中连接和|10之间的加工路径有两条15和；2111,132211,14R211113R221114；R10,15MIN,R21,R22再如，因为和之间不存在加工路径。0,15015表1例1所示FMS模型RCR矩阵123456789101112131415123456789101112131415由于YU在文献中采用的是TTPN建模方法，用延迟变迁表示加工步骤，而PTPN用延迟库所表示加工步骤，所以启发式RCR需要做一定的调整。调整后定义如下定义,其中，为JOBI的终止库所，,/|为各条最小加工路径上所使用的机器资源集合。432LBR启发式函数LEE在RCR矩阵的基础上提出了LBR（LOWERBOUNDRESOURCES）矩阵，用于计算JOB剩余加工步骤所占用的机器资源时间。,0,库所到库所的没有加工路径,1,2,其中，S0定义LBR函数启发式函数值，为的结束库所。,计算单个JOB的剩余时间，选取最大值作为整个加工过程的剩余时间。当JOB中存在多个未完成工件时，为了综合利用多个包含TOKEN的库所LBR值，HUANG提出了一种改进的LBR启发式函数定义改进的LBR函数,其中为拥有的JOB中的未完成,的工件数量433启发式函数通过单个机器未加工操作计算剩余时间并选取最大值作为整个过程剩余时间下限8。定义，其中,是机器MAX,1,2,未开始加工操作库所集合REMAININGOPERATIONSET,ROS。434综合启发式函数为了综合性的使用以上几种启发式函数，HUANG在文献中对以上启发式函数取最大值进行使用,提出综合启发式函数定义6。,显然综合性启发式函数可以进一步减少搜索次数，但是由于需要计算多个启发式函数值，会增加单次迭代算法运算量。44PTPN框架下现有机器启发式函数关于在加工操作步骤问题LEE在文献10中指出在计算启发函数值时需要考虑在加工操作剩余时间问题，否则无法保证算法最优性。441在加工操作步骤剩余时间的计算方法假设当前标识下，机器R关联加工库所为在加工操作库所，则库所需满足以下条件。此时剩余时间计算法方法如下00,000,其他其中为加工库所输出变迁的激发时间。因同一时刻，机器R只能加工一个任务，所以满足条件的库所至多只有一个。此外受搜索算法限制，这保证了。0442启发式函数的修正在考虑在加工操作问题后，PTPN下，启发式函数需要做以下调整。,0,0,当存在在加工操作时，在加工操作库所中TOKEN数量为1，此时，需要计算后继缓存库所的RCR值，加上当前在加工操作时间，计算JOB剩余时间。改进后，启发式函数值为,/|442启发式函数的修正类比，的改进型函数为,0,0,改进后的启发式函数为,443启发式函数的问题和修正以上ROS中仅包括未开始的剩余加工操作集合，对于在加工操作忽略不计。同时，现有文献中对于ROS定义较为模糊，在通用FMS模型下，没有给出剩余加工操作集合计算的具体方法。针对以上情况，本文提出一种改进的机器启发式函数。首先，需要准确区分当前标识下机器R剩余未完成加工操作。现以图1中模型和初始标识中为例,计算机器的过程中，虽然作为操作均R22P3，P5，P17使用了机器，但是由于存在并行加工操作库所，中TOKEN可能不R2P2P14P1P12经过（到达，所以我们不能将和列入机器剩余操作集合中，P3P13P4P15P3P17R2因此初始标识下，。针对以上情况，本文对机器R未开始关联加工25库所集合进行以下区分A必经库所IOSINEVITABLEOPERATIONSET,其中表示P属于R相关|,|1,加工状态库所，表示当前任务只有一个加工路径,表示当前|1标识下所有未开始加工操作库所集合。B选择性库所OOSOPTIONALOPERATIONSET|,|1,其中表示当前任务存在选择性路径。|1在计算剩余操作集合元素时，因无法确定最优调度策略在路径多样性下的执行情况，所以只能计算IOS中的剩余操作，从而保证结果的最优性。其次，我们需要计算在加工任务的剩余时间。此时，只要是使用R的操作都应进行考虑。综上，本文提出一种PTPN框架下新的机器启发式函数构建方法。定义,其中45有效性和最优性的证明文献给出了关于启发式函数效率比较的方法，可以作为判断启发式函数是否更有效的通用标准。现给出其定义定义5如果对于任一非目标标识，,则比更有1212信息量MOREINFORMED。由于文献已经证明了RCR,LBR等启发式函数的最优性问题，所以在此，主要证明的有效性和最优性问题。根据定义和定义关于有效性和最优性的表述，需要证明以下定理。定理1。证明1）；对于机器R，如果存在加工操作则,1,2,如果不存在加工操作则0,1,2,所以，选取最大值作为输出，。（为便于比较启发式函数效率，本文进行比较的在通用FMS下是最优的，所以。）2）；现假设为从M到最小剩余时间激发策略下机器R的加工操作集合,显然，所以对于机器R，如果存在加工操作，则；如果不存在在加工操作，则。同时，实际中可能包含了变迁竞争带来的机器等待时间，所以。MAX综上，。46测试模型461固定测试模型XIONG在文献中提出了一种规模为（4个JOB,3台机器）的固定模型进43行算法测试，该模型被众多学者使用进行对比（在后续章节中，涉及到该模型统一称为固定模型）。OPERATION/JOBS123411,23,41,32,322,31,23,53,433,42,22,31,3按照第二章所述的PTPN建模方法，能够得到固定模型的PN网模型。P1T2P45P6TT3TT7T7P9P12P13T0T8T90429R18T2T13P6P189P20T177T4T561T19P23P256P27T34T0T18T45T8P30R2P31R1R329R30R3R2R0R0R3R2R该固定模型较为简单，存在以下特点1）每个JOB内，单个任务不存在路径选择；2）每个JOB内，单个加工步骤只使用一台机器；3）每个JOB内，加工步骤使用的加工机器不重复。该模型更接近于FLOWSHOP调度问题，但是在此作为一种FMS模型特例进行使用。462随机FMS模型产生器为了进一步确认在随机模型的执行效率。本文采用文献11中标准的随机FMS调度问题产生器进行测试。该产生器随机产生机器资源数量M，JOB数量N，每个JOB的批量和加工序列数量,序列中的任务数,每个任务的操作数,以及操作的执行时间和所需机器资源数。操作所需机器资源集合中机器必须互不相同，同时不能超过总的机器数量。以上随机产生的数值均服从界于1和相应设定值之间的均匀分布。的最大值被设定为M,N,L,S,T,O,R,P。在后续章节中，统一,称为随机FMS模型产生器。47改进的机器启发式函数试验471固定模型实验参数和结果如表2所示，表中MS是总完成时间MAKESPAN，EM是算法扩展出的可达树的状态数EXPANDEDMARKING，CT是CPU运行时间CPUTIME。表2文献11中固定模型实验数据TABLE2EXPERIMENTPARAMETERSANDRESULTSOFFIXEDMODELFROMXIONG11（1,1,1,1）（2,2,1,1）（5,5,2,2）（8,8,4,4）（10,10,6,6）MSEMCTMSEMCTMSEMCTMSEMCTMSEMCT1710713725101110671710299259278211750642511114958626761100149321771342332392417383825554258145110100261170134376264174663251111045862368110014931802134233239241738372555465814593100261166134376301因为所测试的启发式函数均是容许的，所以得到的调度策略MS相同且是最优的。表3中数据同时表明，在此固定模型中，的效率较低，当批,量增长到5,5,2,2时，算法已经无法在合理时间内获得最优解。而现有启发式函数中，占用的计算资源最少。虽然需要同时计算占用了更多,的计算资源，对算法执行效率产生了影响，但是从仿真结果看，该影响可以忽略。能够进一步降低计算需求，所需的EM和CT最小。当采用本文提出的后，算法执行效率有了较为明显的提升，所需的状态数和运行时间是各个单独启发式函数中是最低的。同时，采用了综合性方法后，较在算法性能也有明显提升。表3中数据指出此固定模型下，由于要多计算的函数值，增加了运算量，而本身效率已经很高，因此相,比，优势并不明显，部分实验中甚至需要更多CT。472随机模型测试本文首先测试50组规模较小的随机模型，平均测试结果如表3所示，表中为不同启发式函数A和LB的MAKESPAN误差率。计算方法如,下（2）,100同时，以下实验中，函数LBLOWERBOUND使用,即不使用任何启0发式函数，保证了算法结果最优。和固定模型一致，表3中各栏说,0明各启发式函数均是最优的。本组随机实验中，在三者中，效率最高。综合使用以上启发式函数之后，将平均EM和CT降至3286和24，而本文提出的较在算法性能上又有了一定提升，同时结合，能够在最少计算资源下获得最优解。,表3小规模随机FMS实验参数和数据TABLE3EXPERIMENTRESULTSOFSMALLSCALERANDOMFMSSMRN3,TSOL2,P50,TIMES50AVERAGERDA,LBAVERAGEEMAVERAGECT061584638045483294047485078040343280328624031121836表4中等规模随机FMS实验参数和数据（一）TABLE4EXPERIMENTRESULTSOFMIDDLESCALERANDOMFMSSMR4,TNLO3,S2,P50；TIMES50AVERAGERDA,LBAVERAGEEMAVERAGECT0567169380804760278260686229790606303488296035426413060307733568表5中等规模随机FMS实验参数和数据（二）TABLE5EXPERIMENTRESULTSOFMIDDLESCALERANDOMFMSSMR5,NT4,LT3,SO2,P50；TIMES50AVERAGERDA,LBAVERAGEEMAVERAGECT0239564741602408439670141962638101320525178010125173530917614327然后我们又测试了两组中等规模的随机模型，同样每组实验进行了50次。实验参数和结果如下表4和表5所示，表4数据表明，在独立启发式函数中效率最高，较有了一定的性能提升。同样，作为综合使用方法，和显著提高了算法执行效率。随着问题规模的变大，表5中EM和CT有了明显的增长，但实验数据比较结果和表3类似。多组随机实验证明了本文提出的能够保证算法最优性，同时又提升了机器启发式函数的性能。在实际运用中，虽然需要计算不同启发式函数值，占用了更多的计算资源，但是整体的算法性能提升较为明显，是效率最高的启发式函数。48本章小结本章主要讨论了PTPN框架的启发式函数，LEE在文献中指出了启发式函数需要考虑在加工操作问题，但是现有的机器启发式函数并没有考虑这一问题，本章针对这一问题主要改进了现有文献中的机器启发式函数，较原有算法，我们对剩余加工操作进行合理分类，为了保证最优性，明确提出只能计算必经加工库所中的剩余加工操作，同时在计算过程中，考虑了在加工操作的剩余时间，提高了剩余时间预测值下限，较有了较明显的性能提升。在结合之后，算法能够在最少的计算资源下获得最优调度策略。固定，和随机模型实验均验证了本文提出方法的正确性和有效性。在下一章节中，我们将讨论TTPN搜索框架下的启发式函数问题，对启发式函数进行改进。第五章TTPN下启发式函数设计51TTPN框架下启发式函数的特点TTPN框架和PTPN框架最大的不同之处在于时间属性的添加上，由于TTPN框架有独立的TOKEN时间戳，所以不需要全局时钟控制标识的变化。在TTPN下，并不存在加工状态。加工变迁一旦触发，TOKEN的时间戳变化可以直接继续计算。这一特点决定了TTPN框架下启发式函数具有以下特点1）无在加工操作状态无在加工操作状态使得启发式函数计算时，不用考虑LBR,RCR,MIU等启发式函数在PTPN下的在加工状态问题。2）可以设计更加精细的启发式函数TTPN每一个TOKEN都包含有可行时间信息，相对于PTPN，模型信息更加丰富，可以基于此设计更加精细的启发式函数。本章将详细介绍新构建的一种JOB和机器启发式函数。52TTPN下的JSP问题建模521JSP问题一般性描述JSP车间调度问题是制造系统传统调度问题，同样属于组合约束优化和典型NP男问题。和FMS调度问题一样，JSP也可以采用数学规划方法，但是数学规模不可能太大，且实用性比较差。目前主要采用领域搜索和智能算法进行调度问题求解，例如TABUSEARCH,灭火法等。而本文提供另外一种求解思路，利用时间PETRI网进行调度问题求解。JSP问题一般可被描述为M台不同的机器，L台不同的工件，每个工件有躲到供需，每到供需由指定的机器在固定的时间内完成。一道工序一旦开始，就无法中断，具备原子性。每台机器一次只能加工一道工序。最小时间调度问题便是决定每台工序的加工顺序，使得机器完成所有工件的时间最短。具体数来，该问题就是要求在满足工件加工次序要求和制定机器约束的条件下，确定每台机器上工序的顺序，使得从所有加工过程开始到结束的时间间隔最小。522JSP问题的TTPN模型相对于FMS调度，JSP问题相对简单，不需要考虑路径多样性问题，同时也不需要考虑机器在相同工件中重复使用问题，可视为一类特殊FMS调度问题加以研究。现以一条简单的JSP调度问题说明TTPN建模过程，表21给出了该JSP加工要求。123工序12,51,51,4工序23,33,42,1工序31,32,53,3现以BNET方法对以上JSP问题进行建模，可以得到如图1所示的TTPN模型。JSP问题可以转换为相应的TTPN变迁激发次序安排问题，和PTPN下模型类似，不要对算法进行修改即可通过搜索获得调度策略，在此不再赘述。M1M2M3P21P2P23T21T2P24T23P31P32P3T31T32P34T3121TT114T131MMM2123ODELSIZ353TTPN框架下的启发式函数,531TTPN下启发式函数由于每个TOKEN都具备独立时间戳，表征机器当前可行时间，所以计算每台机器的剩余加工时间不能和PTPN下一样，仅计算剩余加工步骤，而不考虑当前机器可行时间。定义31其中，表示机器的剩余加工操作集合，和PTPN下不同的是，此处的计算方法较为简单，不需要考虑路径多样性问题。表示剩余加工操作对于变迁会激发的次数。532TTPN下启发式函数JSP问题的TTPN启发式函数对应LBR矩阵需要做以下变动定义32,0,库所到库所的没有加工路径由于不存在路径多样性问题，从至多可能存在一条路径。库所到库所此处需注意的是的计算方法有了小的变动定义330即计算路径S中的所有的变迁时间之和。和一样，由于独立时间戳的设置，需要独立计算每一个JOB的完成时间。在批量为1情况下，启发式函数组织形式如下定义34MAX,1,2,库所为中拥有TOKEN的库所，而则为结束库所。在批量大于1的情况下，需要考虑最优性问题，对于单个JOB，只能选取最大的TOKEN进行计算，定义如下定义34MAX,1,2,533TTPN下启发式函数不用考虑路径多样性问题，JSP问题的TTPN启发式函数使用的RCR矩阵和LBR矩阵一致，在此不在赘述。由于RCR方法考虑的是机器平均剩余时间，和PTPN下的PTPN类似。给出定义定义35,/|54TTPN新构建的启发式函数541无路径选择和重复机器选择情况下启发式函数FLOWSHOP问题现有TTPN启发式函数仅通过标识TOKEN数量信息和PETRI网模型结构求解JOB或者机器资源剩余加工时间，而作为TTPN的一个重要特征，独立时间戳并没有被考虑。本节将着重介绍一种充分利用这一特征的启发式函数设计方法，并证明其有效性和最优性。5411JOB函数根据TTPN激发规则，变迁必须等待所有输入库所中TOKEN满足变迁弧上数量要求后才能进行激发。现假设代表待加工的工件到达缓存库所的时间为，接下来将完成变迁所代表加工操作，使用的机器资源为，那11么在没有其他JOB变迁竞争的情况下，激发以及工件到达的时间可以11按照以下估计；1MAX,11进一步分析，现假设有加工路径如图所示。按照以上无竞争原则，则中TOKEN到达的时间可以按照以下方法进行估计PSP1PIT1T2PI1TIPFTF12IF1MAX,112MAX1,22MAX1,至此，我们可以总结出一个计算连接起始库所和目标库所的最小剩余时间估计方法。,1,11,222,公式1那么在单批量（每个JOB待加工工件数量至多为1）问题下的JOB启发式函数为公式2MAX,1,2,其中表示中包含有TOKEN的剩余加工操作开始库所，为为结束库所；启发式函数的特点便是除了考虑剩余加工步骤的时延，还应考虑所使用的机器资源的可行时间，比现有算法更加合理高效，我们将在后续部分中证明的有效性和最优性。5412MACHINE函数对于机器启发式函数，我们可以采用的形式进行改进，机器资源的加工操作完成时间估计为，但是在TTPN下，我们能够进一步提高该下限。假设存在如图所示情况，加工机器对应的操作为,但是的输入库所当前标识下并没有TOKEN，所以的剩余加工时间需要考虑这一时延。同样的，我们先考虑单批量问题，假设位于同一JOB的库所拥有TOKEN，那么在没有其他JOB竞争的情况下，中TOKEN到达的时间可以按照公式1进行估计。,将这种情况进行推广，假设是使用机器资源的所有加工操作。对于任一，我们都要计算器前置库所出现TOKEN的最早时间，然后选取最小值，并综合考虑机器本身的可行时间，作为下一个加工步骤的开始时间进行预估，即。,那么机器的完成时间预估方法则调整为。单批量情况下的机器启发式函数则可以调整为公式35413多批量情况的拓展在多批量情况下，需要考虑加工操作的并行问题，否则无法保证最优性。启发式函数的处理方式是选取最大的TOKEN计算或者取多个TOKEN的平均来保证最优性。式4MAX,或者，平均方法没有最,/大值方法有效因为；,/MAX,其中是中有TOKEN的库所。当批量为1时，式4和式1没有什么不同，故可以作为统一的LBR方法进行下面的讨论。而本文的JOB启发式函数则可以充分利用TOKEN时间戳这一特性对并发现象进行考察。在中，我们仅承认JOB间的最大并行性，一个JOB能够在没有竞争的情况下完成所有操作，但是在JOB内部，我们必须要考虑操作间的并发问题以获得一个更加准确的下限。而我们的计算方法并不复杂只需重复利用上述公式一计算过程即可。例如，现有加工流程如图所示，该JOB有两个未完成的工件，TOKEN分别存在于库所和中，我们需按照，的顺序对整个JOB进行完成时间计算，1212而中TOKEN到达目标库所的时间就为JOB完成时间。2计算过程如下1）中TOKEN的完成时间为；11,2）更新从到中间的变迁使用的机器的时间戳为11MAX,13）中TOKEN的完成时间为；22,从另一角度解释，在计算中TOKEN完成时间时，需要用更新“使用2过的”机器资源。这样整个加工过程可以被分为两个部分，第一部分包含从到的机器，该部分的12121,11,222,第二部分为从到的机器，这部分机器已经使用过。1；211,综上，JOB完成时间估计可以按一下方式进行计算1,2当未完成工件数量大于2时，计算过程和上述过程类似，但是需要遵循以下原则1）计算顺序“由深到浅，由小到大”，即从离目标库所最近的库所开始计算起，对于相同库所，则需要先计算时间戳小的TOKEN完成时间，再计算时间戳较大的TOKEN；2）完成一次计算后，需要立即更新被使用过的机器时间戳。3）最浅库所最大时间戳的TOKEN完成时间为整个JOB完成时间。PPIPI1TIPTT1T以上便是在对于多批量情况的拓展，机器启发式函数的多批量拓展相对简单，只需注意以下问题。4）计算延迟时，需要计算离最近的库所时间戳最小的TOKEN抵达相应前置库所的时间，以此作为最小开始时间依据。5）在计算时注意多批量的加工操作需要重复计数问题。此时，加工变迁的前置库所拥有TOKEN的时间变为,为离变迁T最近的包含TOKEN的库所。而在单批量情况下，拥有TOKEN的库所即为离变迁最近的库所，所以从这一点上是一致的。如此我们便可总结出TTPN根据TOKEN时间戳设计的启发式函数MAX,MAX,2在迭代中，我们考虑的机器可行时间1MAX,1是当前标识下，并且假设其他JOB并没有参与到竞争中来，如果其他JOB使用了路径上的机器，,表示实际情况下，当变迁激发时，机器的可行时间。所以，作为迭代结果多批量情况下也是如此。启发函数定理41,其中表示当前标识下，实际能够获得的最小完成时间。1）；是最小开始时间因为我们仅承认由,之间的变迁激发导致的延迟，在理想情况下即当前,标识前置库所即存在TOKEN。所以，MAX,故；2）同样的，由于竞争的存在，同时，也是理想情况下的连续激发。故55针对TTPN模型的激发策略改进551单个变迁激发策略在现有的搜索算法忽视了PETRI网的并发现象，在迭代过程中，多选择单个变迁进行触发。但是，在特定情形下，同时激发多个非冲突变迁将不会影响搜索结果的最优性，并且能够直接搜索到更深的节点，减少算法运算量。然后，对非冲突变迁进行随意组合激发可能会因为最优路径上的标识丢失，导致搜索结果非最优。例如如图所示，和是当前标识下的使能的非冲突变14迁。对于变迁，存在以下激发次序1，2（其他激发顺序1,2,41,2,41,4,2将和这两者产生相同的后继标识）。同时激发和将会损失第二种情况，但是无法保证激发次序1优于次序142。因而，对非冲突变迁不能进行随意组合。图显示了该情形。经过组合，和会丢失，在未获得前，不知道完成时间小于。46667任意可行调度策略均可被分解成多台机器来自不同JOB的操作排序组合，而最优调度策略则是从中选取最优的一种组合可能。在搜索过程中，选取不同冲突变迁激发顺序实际上是选择不同操作排序可能。在可达树搜索过程中，每一个标识的信息包含了已经完成的部分操作，以及这些操作的排序。启发式搜索对应于通过启发式规则来优先探索部分排序可能，或者放弃部分排序可能。定理能够一起激发并且不影响最优性，如果满足以下条件,1）,。是所属JOB所有后续加工操作相应变迁集合。2）,；3）；证明即以及后续变迁将不会竞争任何机器资源，由于属于,不同JOB，又不会使用相同的缓存库所。因此，激发中的操作排序将不会,影响中的操作排序可能，反之也是如此。进而，同时激发来和的变迁将不会影响获得最优调度策略。单个变迁激发策略使得算法能够探查所有排序可能，然后搜索速度较慢。两个变迁如果满足以上条件，合并激发将不会影响后续对于机器排序的可能，所丢失的状态实际上搜索过程中的部分重复冗余标识。以图所示模型为例，变迁能够同时激发，13,241313，14，15，,2424，251313,14,15,16,3,4,52424,25,26,1,2表示相互独立，是否激发将对的输入库所和后继库所132413,241324中TOKEN变化不产生任何影响。推论如果，,，则也能同时激发而不影响算，法最优性。证明如果两个变迁满足定理1，显然他们的后续变迁均满足定理1条件。变迁组合算法步骤1初始化,1,2,1,2,WHILE,SELECTFOR,FOR,IF,IF,THENFOR,IF,BREAKOUTPUTASTHEGROUP变迁随机组合算法,1,2,STEP1初始化,1,2,WHILE,SELECT,FOR,IF,TCTCWHILE|FOR1_IF,SELECTFROM,OUTPUTASTHEFIRINGGROUP作为对比，我们同样给出非冲突变迁随机组合算法。在实施中，我们用变迁激发组来代替单个变迁产生后继标识。56实验例证561FLOWSHOP模型产生器SIZEMNNUMBEROFPLACEMN1NP1_1T1_1P1_2T1_2T1_NP1_N1T2_1P2_2T2_2T2_NP2_N1P2_1TM_1PM_2TM_2TM_NPM_1PM_N1NOPERATIONSMJOBSNUMBEROFTRANSITIONSMNNUMBEROFMACHINESN