（计算机软件与理论专业论文）基于cftwfnets的工作流调度优化研究.pdf

基于c f t w f - n e t s 的工作流调度优化研究 计算机软件与理论专业 硕士生：徐吉安 指导老师：汤庸教授 摘要 随着企业的市场竞争的日趋激烈和业务环境的不断变化，对业务流程管理的 要求也变得越来越高，在多流程多实例并行执行的工作流管理系统中，存在各种 各样的约束条件和资源竞争，一个多流程多实例执行的任务以最优的方案利用资 源完成任务，是工作流调度优化要研究解决的问题，它对企业的资源配置和生产 效率有非常重要的现实意义。 目前关于工作流调度方面的研究主要集中于可调度性方面，对调度优化的研 究较少，而制造业领域( 如f m s 、半导体制造、车间作业等) 在调度优化方面 有较丰富的研究成果，同时工作流与制造业领域在资源竞争方面有很大的相似 性，本文参考制造业领域调度优化方面的研究成果，提出一个适合工作流的调度 优化解决方案。 时间是工作流中的重要属性，由于工作流的活动和资源具有动态特性，工作 流中的时问是非确定性的，难以被精确描述，本文采用文献 1 1 】提出的有很强描 述能力的模糊时态工作流网( f t w f n e t ) ，同时考虑到本文描述的是多流程多实 例的工作流调度优化，对f t w f n e t 进行着色扩展，得到着色模糊时态工作流网 ( c f t w f n e t ) 来描述流程信息。 在调度优化方面，本文采用遗传算法来指导优化的进行，在参考文献 1 9 的 基础上，提出适合多流程多实例的工作流调度优化的染色体和遗传算子。 本文采用c + + 编程语言和美国麻省理工大学的遗传算法类库g a l i b ，对本 文采用的工作流网模型和调度优化方法进行了编程实现。 关键词：工作流网，着色p e t r i 网，模糊时间p e t r i 网，调度优化，遗传算 t h es t u d yo fw o r k f l o ws c h e d u l i n go p t i m i z a t i o nb a s e do nc f t w f - n e t s c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：x uj i a n s u p e r v i s o r ：p r o f e s s o rt a n gy o n g a b s t r a c t m a n a g e m e n to fw o r k f l o wi sm o r ea n dm o r ee m p h a s i z e da sm a r k e tc o m p e t i t i o n g r o w sa n db u s i n e s se n v i r o n m e n tc h a n g e s i nt h em u l t i p r o c e s sa n dm u l t i i n s t a n c e w o r k f l o ws y s t e m ，t h e r ea l ea l lk i n d so fc o n s t r a i n sa n dr e s o u r c ec o n f i c t s ot h e w o r k _ f l o ws c h e d u l i n go p t i m i z a t i o nf o c u s e so nt h er e s e a r c ho fa l l o c a t i n gr e s o u r c e st o b e a e rs c h e d u l em u l t i p r o c e s sa n dm u l t i i n s t a n c et a s k s t h i sr e s e a r c hi sr e a l l y s i g n i f i c a n tt ot h er e s o u r c ea l l o c a t i o na n di m p r o v e m e n to f p r o d u c t i v i t yf o re n t e r p r i s e s a tp r e s e n t ，t h er e s e a r c ho fw o r k f l o ws c h e d u l i n gf o c u s e so ns c h e d u l a b i l i t ya n d t h er e s e a r c ho fw o r k f o ws c h e d u l i n go p t i m i z a t i o ni sr a r e ，w h i l ei nt h ea r e ao f m a n u f a c t u r es u c ha sf m st h e r ea r em a n yr e s e a r c h e so ns c h e d u l i n go p t i m i z a t i o n ， b e c a u s et h e r ea r es i m i l a r i t i e sb e t w e e nw o r k f l o wa n dm a n u f a c t u r ei nt h ea s p e c to f r e s o u r c ec o n f l i c t ，t h i sa u t h o rg i v e sas o l u t i o nw h i c hi ss u i t a b l et ow o r k f o w s c h e d u l i n go p t i m i z a t i o n t i m ei n f o r m a t i o ni sa ni m p o r t a n ta t t r i b u t ei nw o r k f l o w b e c a u s eo ft h ed y n a m i c c h a r a c t e r i s t i e so fr e s o u r c e sa n da c t i v i t i e si nw o r k f l o w , m u c ht i m ei n f o r m a t i o ni s u n c e r t a i na n dc a n tb ed e s c r i b e dp r e c i s e l y t h i sa u t h o rm o d e l sw o r k f o wp r o c e s s e s w i t hc o l o r e df u z z yt e m p o r a lw o r k f l o wn e tf c f t w f n e t ) w h i c hi sb a s e do nt h e f t w f n e ti i t la n dc o l o r e dp e t r in e t i nt h ea s p e c to fs c h e d u l i n go p t i m i z a t i o n ，t h i sa u t h o ru s e st h eg e n e t i ca l g o r i t h mt o g e to p t i m a ls c h e d u l i n gs o l u t i o n ，b a s e do nt h ew o r ko fr e f e r e n c e 【1 9 】，t h i sa u t h o r d e s i g n sg e n o m ea n dg e n e t i co p e r a t o r sw h i c ha r es u i t a b l et ot h em u l t i - p r o c e s sa n d m u l t i i n s t a n c ew o r k f l o w f i n a l l y , t h i sa u t h o rd e v e l o p sap r o g r a mf o rt h ec f t w f - n e ta n dm e t h o d so f s c h e d u l i n go p t i m i z a t i o nb yc + + a n dg a l i bo f m i t k e y w o r d s ：w o r k f l o wn e t ，c o l o r e dp e t r in e t ，f u z z yt i m ep e t r in e t ，s c h e d u l i n g o p t i m i 瘟t i o n ，g e n e t i ca l g o r i t h m i i 第1 章绪论 1 1 引言 工作流的概念最早起源于生产组织和办公自动化领域，它通过将工作分解成 定义良好的任务、角色，根据一系列过程规则，文档、信息或任务能够在不同的 执行者之间传递、执行【1 1 ，以达到提高工作效率、降低生产成本、提高企业生产 经营管理水平和企业竞争力的目标。 工作流经历了8 0 年代的萌芽期，9 0 年代的繁荣期，现在它进入了广泛应用 的时期，近年来，工作流技术逐渐成为了计算机应用领域中的最为活跃的研究热 点之一。人们对于工作流的研究往往集中于工作流体系结构的研究，工作流模型 与工作流过程定义语言的研究，工作流事务的研究，等等。随着企业的市场竞争 的日趋激烈和业务环境的不断变化，对业务流程管理的要求也变得越来越高，在 多实例执行的工作流系统中，由于资源竞争的存在制约着工作流任务的执行过 程，如何合理分配资源，使多实例的任务以最快的时间执行完成，是工作流调度 优化要解决的问题。 时间是自然界无所不在的客观属性，所有的信息都具有相应的时态属性，工 作流也不例外。工作流中的资源和活动具有动态特性，因而它们的时间常常是非 确定的，难以被精确描述，因此在进行调度优化之前，用一个合适的模型描述工 作流中的难以精确描述的非确定的时态信息变得同样重要。 1 2 国内外研究现状 1 2 1 工作流建模 由于工作流的特征是资源( 物质资源和信息资源) 的流动反映系统的动态行 为，而1 9 6 2 年p e t r i 博士提出的p e t f i 网同样是用来描述具有这样特征的系鲥2 1 ， 因此上世纪8 0 年代咀来，基于p e t f i 网的工作流建模技术逐渐成为了工作流领域 的研究热点之一。近年来，工作流系统中的时间信息管理问题普遍受到人们的关 注，研究者提出了许多基于p e t r i 网的时间工作流模型。 在文献 3 e p ，荷兰学者wm ev a i ld e ra a l s t 为了建模、分析和评价工作流 的控制结构，在p e t r i 网的基础上提出了工作流网( w f n e t ) 以及工作流网合理 性( s o i l r l d i l e s s ) 的概念。 在文献【4 】中，s e al i n g 等考虑到变迁的有效时间，提出了时间工作流网 ( t w f n e t ) 以及t w f n e t 的时问安全性的概念。他们在w f n e t 的基础上进行 扩展，为每一个变迁引入一个有效时间区间，规定了变迁的执行时间必须在该有 效时间区间中取值。 在文献【5 】中，杜栓柱等为了描述工作流过程中的并行时问约束，在时间工作 流网( t w f n e t ) 的基础上，提出了扩展时问工作流网( x t w f n e t ) 的概念，他 们通过一定的构建规则，将多个t w f n e t 合并为一个x t w f ，n e t 。为了描述分布 于不同时区的工作流程，他们在x t w f n e t 中引入了与时区相关的时间映射函 数。 在文献【6 】和【7 】中。李慧芳等为了描述工作流系统中业务实例的到达时间、 活动的使能时间、活动可执行的时间区间以及活动的执行延迟，提出了时间约束 工作流网( t c w f n e t ) 。 但是，在上述这些模型中，时间信息都是确定性的，缺乏对不确定性时间信 息的描述能力。而在实际的工作流应用中，由于资源和活动具有动态特性，使得 各种时间信息常常是非确定性的，难以被精确描述。i n 在文献 8 】和 9 中，m u r a t a 等为了支持对不确定性时问的描述，结合模糊集 合理论，提出了模糊时间p e t r i 网( f t n ) 。在f t n 中有4 个模糊时间函数：模 糊时间戳、模糊使能时间、模糊触发时间和模糊延迟。使用f t n 能很好地对工 作流过程中的非确定性时间信息进行描述和分析，但它缺乏对时间约束的描述能 力。 在文献 1 0 l 中，y z h o u 等为了描述变迁的有效时问约束i 对f t n 进行扩展， 引入有效时间区间，对f t n 中的四个模糊时间函数进行重新推理，提出了扩展 模糊时间p e t r i 网( e f t n ) 。但e f t n 只考虑了变迁的有效时问约束，而忽略了 资源的有效时间约束。 在文献【1 1 冲，潘炎、汤庸等为了描述资源和变迁的有效时问约束，对f t n 进行扩展，引入资源的有效时间区间和变迁的有效时间区间，提出了一种新的工 作流模型模糊时态工作流网( f t w f n e t ) 。利用f t w f n e t ，可以有效地对 工作流过程中的时态行为进行建模和时间可能性分析，与已有的时间工作流的模 型相比，f t w f n e t 具有以下特点：( 1 ) 它可以描述工作流系统中的不确定的时间 2 信息，并进行计算和分析】。( 2 ) 它引入资源的有效时间和变迁的有效时间，可 以更加全面地描述工作流系统中的时态现象和规律。但是f t w f - n e t 没有考虑 变迁的优先级，而且不能描述多工作流程多个实例并行执行的情况。 1 2 2 调度 调度主要分为两类： ( 1 ) 可调度性分析 可调度性分析是分析当前状态下或在规定的约束下，有没有可行的调度方案 使得流程能正常结束。目前工作流调度方面的研究主要集中在这一块。 在文献 1 2 】中，j u l i a ，s 和d eo l i v e i r a , ff 提出了一个基于p - t i m eh y b r i dp e t r i 网的方法来解决工作流管理系统的调度问题，首先用u m l 中的活动图来描述具 体的工作流程，然后对每一个活动加上一个有效时间区间，把活动图映射为 p - t i m e p e t r i 网，此文还把工作流程中的资源分为两类：离散资源( 如打印机) 和 连续资源( 如工作人员) ，提出了一种混合资源分配机制：对于离散资源，用库 所中的t o k e n 表示，一个t o k e n 表示一个离散资源；对于连续资源，用百分比来 表示资源的可用性，例如一个护士在工作日内能照顾1 0 个病人，那么对于每一 个病人库所引发出来的变迁，得到的这个护士的t o k e n 是1 0 。最后提出t o k e n p l a y e r 算法来分析可调度性。 在文献【2 0 中，李慧芳和范玉顺针对工作流管理系统中对时间管理支持不够 的缺点，提出基于p e t r i 网的工作流时间约束建模方法，分析了工作流网的时间 特性，并提出时间约束工作流网的可调度性分析方法。 在文献 6 】中，李慧芳和范玉顺为了集成业务过程的时间约束，扩展工作流 网元素的时间属性，提出时间约束工作流网，然后基于对业务活动的可调度性分 析，提出时序一致性验证方法，确保工作流执行中活动之间时间交互的安全性。 ( 2 ) 调度优化 调度优化是指在给定的初始状态下，利用遗传算法、启发式搜索等策略，找 出一个到达结束状态的最佳调度方案。目前对这一块的研究主要集中在f m s ( 柔 性制造系统) 、半导体制造、车间作业等制造领域上，对工作流的调度优化问题 研究很少。 对调度优化的研究主要分为两类： 基于遗传算法的调度优化 在文献 1 3 中提到m u t h 和t h o m p s o n 最早就i o x1 0 的j o b - s h o p 问题使用遗 传算法对其进行优化。 在文献【1 4 】中，l i ns h u n y u 和f ul i - c h e n 等使用着色时间p e t r i 网对w a f e r p r o b ec e n t e r 进行建模，在调度阶段，结合分配机器给工件和分配工件给机器的 策略，用遗传算法调度优化。 在文献 15 】中，c h u n gy u n g - y i 和f ul i c h e n 等使用t p p n 对f m s 进行建模， t p p n 包括运输子模型和加工流子模型两个模型，然后结合遗传算法提出一种自 适应的调度算法对f m s 系统进行调度，同时这种调度算法还允许加工阶段有不 同的优先级。 在文献【1 6 】中，h u a n g a n c h i h 和f ul i c h e n 等把着色时间p e t r i 网和队列系 统结合起来，提出用q c p n ( q u e u e i n gc o l o r e dp e t r in e t ) 对w a f e r 制造系统进行建 模，同时应用遗传算法对系统的大量启发式规则进行搜索，求出最佳组合进行调 度，适用于快速改变的环境。 在文献【1 7 ，1 8 】中，x ug a n g 和w u z h i - m i n g 使用p e t r i 网对f m s 系统进行建 模，然后提出一个有效的死锁检测算法，最后利用遗传算法提出一种无死锁的调 度方法。 上述研究成果与具体问题联系较紧密，通用性不足，为此，在文献【1 9 】中郝 东和蒋昌俊等针对以上不足，在基于增强确定时问p e t r i 网的基础上，提出简化 模块的方法来避免死锁，在遗传算法方面，用p e t r i 网的变迁序列作为染色体， 期望值作为选择算子，染色体的总加工时间作为适应度函数，交叉算子很好地利 用了p e t r i 网的标识m ，选择两条染色体中两个标识相同的位置，交换其间的变 迁序列得到两条新的染色体，变异算予随机从染色体上选择一点作为变异点，然 后生成一条可行的时间最小的变迁序列作为新的染色体，该文提出的方法可以处 理典型的j o b s h o p 问题以及小批量多品种的f m s 调度问题，有较高的通用性。 基于启发式搜索的调度优化 启发式搜索的最大问题是存在状态爆炸，会导致搜索速度变慢。 在目前研究中，s h i hh 和s e k i g u c h it 在利用p e t r i 网仿真柔性制造系统f m s 功能的过程中，利用局部调度解决冲突，l e ed y 和d i c e s a r ef 用人工智能的算法 给出了一个解决生产调度问题的框架，s u nt i e n h s i a n g 和c h e n gc h a o w e n g 等 对l e e 的方法进行了改进，提出了有限扩展的a 算法，薛雷和郝跃利用增强确 定时间p e t r i 网对集成电路制造系统进行建模，并提出多目标评价函数，用类a t 算法进行调度优化。1 1 9 由上所述，以上两种调度优化的方法目前主要用于制造业领域的研究，制造 业领域和工作流领域有相同的地方，例如两者都存在资源冲突的问题。也有明显 的不同之处，例如制造业的加工时间是能预先确定的，而工作流的资源和活动具 有动态特性，难以精确描述。把制造业领域的调度优化方法应用于工作流上，需 要作一定的修改。 1 3 本文的研究思路及创新点 1 3 1 问题的提出 由前所述，目前工作流领域的调度研究主要集中在可调度性分析方面，很少 涉及调度优化的研究，与工作流有较多相同点的是制造业领域的生产流程，目前 这一领域有较多的调度优化研究成果。 但是在多实例并行执行的工作流管理系统中，存在各种各样的约束条件和资 源竞争，一个多实例执行的任务能以最优的方案完成，对企业的资源配置和生产 效率有非常重要的现实意义。 本文尝试借用制造业领域的调度优化方法，结合工作流模型作一定的改进， 提出一种基于工作流模型的调度优化解决方案。 1 3 2 研究思路 本文的研究主要分为两方面：工作流建模和调度优化。 ( 1 ) 工作流建模 考虑到工作流资源和活动的动态特性，更恰切地描述工作流的非确定的时态 信息，本文采用文献【l l 】提出的有很强描述能力的模糊时态工作流网f t w f n e t ， 同时作如下改动，得到着色模糊时态工作流网c f t w f - n e t ： 为了描述多个实例并行执行的资源分配情况，把f t w f n e t 扩展成着色 f t w f n e t ，用颜色来区分不同的实例。 为了方便描述，把库所分为两类：私有库所和共享库所。作如下约定： 对私有库所来说，某一颜色实例的变迁只能产生该颜色的t o k e n ：某一颜色实例 的变迁产生的私有库所t o k e n 只能被同一颜色的实例所使用，而产生的共享库所 t o k e n 可以被其它颜色的实例所使用。 由于一个工作流程对应一个工作流网，为了方便描述多流程的调度优化， 本文采用一个形式上把多个工作流网合并为单个工作流网的方法，在第3 章第4 节有详细叙述。 ( 2 ) 调度优化 本文采用遗传算法来优化调度序列，主要借鉴文献【1 9 】的两个思想：染色体 为变迁序列以及交叉算子在标识m 相同的两个位置间交换变迁序列。同时本文 作如下改动： 染色体的选择 染色体是遗传算法中遗传算子的操作单位。借鉴文献【1 9 】的做法，本文也采 用变迁序列t x t 2 t 。作为遗传算法的染色体，一条染色体就是一个可行的调度方 案。不同的是，文献 1 9 】中没有指出变迁序列作为染色体的缺点：不能描述并行 执行的结构。因为变迁的先后顺序反映了执行的先后顺序，因而同时执行的两个 变迁不能反映在单一的变迁序列中。此外，因为并行结构的存在，染色体的执行 时间不能是变迁序列中所有变迁的执行时间的简单相加。 本文研究的是工作流的调度优化，而工作流模型中存在四种结构：并行结构、 顺序结构、选择结构和循环结构。而本文研究的更是多流程多实例的情况，各个 实例的并行执行也是一种并行结构。根据本文的实际情况，对染色体设计如下： 一个染色体是一个n 元组( g l ，9 2 ，岛) ，其中n 表示实例的个数，对于i n ， 舀表示实例i 的一个变迁执行序列。 适应度函数 由于并行结构和多实例的存在，本文不能采取把变迁时问简单相加的方法来 衡量染色体的好坏，而采取如下方法来计算：在调度过程中，对于每一个触发的 变迁，记录使它使能的库所前集p r e s e t ，得到一条染色体后，对于每个实例的变 迁序列g i = t i t 2 t 。，根据t g ，中的p r e s e t ，可以知道q 的模糊触发时间戳， 再根据t j 的模糊触发延迟，就可以计算出t j 触发后的模糊时间，进而可以计算出 整个舀的模糊时间t i ，由于各个实例是并行执行的，泼染色体的总时间就是t = m a x ( t o ，i n 。用t 可以衡量染色体的优劣。 6 种群的生成 种群是染色体的集合。本文生成种群的方法：根据初始标识m o ，可以求出 所有使能的变迁，随机选择一个变迁触发，得到标识m 1 ，再由m l 求出所有下 一步使能的变迁，再随机选择一个变迁触发，依此下去，直到到达结束标识m 。d 。 这样可以得到一条染色体，加到种群中。循环执行上述过程，直到种群数目达到 设定的值。 只要该流程的p e t r i 网满足合理性 3 】，那么由上述方法得到的种群的每一个个 体都是可行的，都是一个调度方案。 交叉算子 文献 1 9 】的做法是：取出两条染色体，在标识相同的两个位置间交换变迁序 列。由于这种做法可以保证交叉后的染色体也是可行的，不会产生可行的解，本 文借用这种方法，但是在多实例并行执行的情况下，不同的实例执行顺序产生的 标识是不一样的，可能会造成交叉算子找不到两个标识相等的位置而无法交叉产 生后代，这样遗传算法进行下去就没有意义了。根据本文的染色体结构，结合并 行结构和多实例的情况，设计如下： 对于两条染色体【g l ，9 2 ，g n 】和【g 1 ，g 2 ，g 。】，随机选出g l 和g i ，i n ， 再在g 。和g 。的变迁序列中，选择两个标识相等的位置，交换这两个位置间的变 迁序列s 和s 。由于s 或s 之内的变迁可能会输出共享库所的t o k e n 为其它实 例所用，交换s 和s 后，要对其它实例中的变迁的时间戳进行相应的更新，这在 第4 章会有详细的叙述。 变异算子 本文的变异算子利用种群生成方法中的生成单个染色体的方法，随机选择一 个变异位置，求出此时的标识m ，利用此标识，重新生成一个新的可行的染色体。 1 3 3 本文的创新点 参考已有的研究成果，本文的创新点如下： ( 1 ) 在调度模型的选择上，用模糊时间能更准确的反映工作流资源和活动 的动态特性，能更好地描述工作流非确定的时态信息。 ( 2 ) 根据实际研究情况，对文献 1 l 】的模糊时态工作流网f t w f n e t 进行 扩展，引入颜色区分不同实例，把库所分为两类：私有库所和共享库所。 ( 3 ) 为描述多流程的情况，本文采用一种把多个工作流网合并的方法。 ( 4 ) 参考文献 1 9 】的两个思想：染色体为变迁序列以及交叉算子在标识m 相同的两个位置间交换变迁序列。为了描述工作流中的并行结构和多实例并行执 行的情况，采用n 元组的染色体以及基于其上的适应度函数计算方法和交叉算子 操作方法。 1 4 本文的组织结构 本文分为六章，其组织结构如下： 第1 章为概述，描述工作流调度的国内外研究现状，提出本文的研究思路和 创新点。 第2 章介绍文中所涉及的基础理论知识，包括p e t r i 网基础理论、工作流和 模糊数学基础理论。 第3 章详细介绍本文采用的工作流网模型。 第4 章详细介绍本文采用的调度优化方法及其设计。 第5 章详细介绍本文的工作流网模型及调度优化方法的实现算法及数据结 构，最后用一个具体例子进行实验。 第6 章对本文进行了总结，并提出了进一步的研究工作。 第1 章绪论 1 1 引言 工作流的概念最早起源于生产组织和办公自动化领域，它通过将工作分解成 定义良好的任务、角色，根据一系列过程规则，文档、信息或任务能够在不同的 执行者之间传递、执行【1 1 ，以达到提高工作效率、降低生产成本、提高企业生产 经营管理水平和企业竞争力的目标。 工作流经历了8 0 年代的萌芽期，9 0 年代的繁荣期，现在它进入了广泛应用 的时期，近年来，工作流技术逐渐成为了计算机应用领域中的最为活跃的研究热 点之一。人们对于工作流的研究往往集中于工作流体系结构的研究，工作流模型 与工作流过程定义语言的研究，工作流事务的研究，等等。随着企业的市场竞争 的日趋激烈和业务环境的不断变化，对业务流程管理的要求也变得越来越高，在 多实例执行的工作流系统中，由于资源竞争的存在制约着工作流任务的执行过 程，如何合理分配资源，使多实例的任务以最快的时间执行完成，是工作流调度 优化要解决的问题。 时间是自然界无所不在的客观属性，所有的信息都具有相应的时态属性，工 作流也不例外。工作流中的资源和活动具有动态特性，因而它们的时间常常是非 确定的，难以被精确描述，因此在进行调度优化之前，用一个合适的模型描述工 作流中的难以精确描述的非确定的时态信息变得同样重要。 1 2 国内外研究现状 1 2 1 工作流建模 由于工作流的特征是资源( 物质资源和信息资源) 的流动反映系统的动态行 为，而1 9 6 2 年p e t r i 博士提出的p e t f i 网同样是用来描述具有这样特征的系鲥2 1 ， 因此上世纪8 0 年代咀来，基于p e t f i 网的工作流建模技术逐渐成为了工作流领域 的研究热点之一。近年来，工作流系统中的时间信息管理问题普遍受到人们的关 注，研究者提出了许多基于p e t r i 网的时间工作流模型。 在文献 3 e p ，荷兰学者wm ev a i ld e ra a l s t 为了建模、分析和评价工作流 的控制结构，在p e t r i 网的基础上提出了工作流网( w f n e t ) 以及工作流网合理 性( s o i l r l d i l e s s ) 的概念。 给出了一个解决生产调度问题的框架，s u nt i e n h s i a n g 和c h e n gc h a o w e n g 等 对l e e 的方法进行了改进，提出了有限扩展的a 算法，薛雷和郝跃利用增强确 定时间p e t r i 网对集成电路制造系统进行建模，并提出多目标评价函数，用类a t 算法进行调度优化。1 1 9 由上所述，以上两种调度优化的方法目前主要用于制造业领域的研究，制造 业领域和工作流领域有相同的地方，例如两者都存在资源冲突的问题。也有明显 的不同之处，例如制造业的加工时间是能预先确定的，而工作流的资源和活动具 有动态特性，难以精确描述。把制造业领域的调度优化方法应用于工作流上，需 要作一定的修改。 1 3 本文的研究思路及创新点 1 3 1 问题的提出 由前所述，目前工作流领域的调度研究主要集中在可调度性分析方面，很少 涉及调度优化的研究，与工作流有较多相同点的是制造业领域的生产流程，目前 这一领域有较多的调度优化研究成果。 但是在多实例并行执行的工作流管理系统中，存在各种各样的约束条件和资 源竞争，一个多实例执行的任务能以最优的方案完成，对企业的资源配置和生产 效率有非常重要的现实意义。 本文尝试借用制造业领域的调度优化方法，结合工作流模型作一定的改进， 提出一种基于工作流模型的调度优化解决方案。 1 3 2 研究思路 本文的研究主要分为两方面：工作流建模和调度优化。 ( 1 ) 工作流建模 考虑到工作流资源和活动的动态特性，更恰切地描述工作流的非确定的时态 信息，本文采用文献【l l 】提出的有很强描述能力的模糊时态工作流网f t w f n e t ， 同时作如下改动，得到着色模糊时态工作流网c f t w f - n e t ： 为了描述多个实例并行执行的资源分配情况，把f t w f n e t 扩展成着色 f t w f n e t ，用颜色来区分不同的实例。 为了方便描述，把库所分为两类：私有库所和共享库所。作如下约定： 对私有库所来说，某一颜色实例的变迁只能产生该颜色的t o k e n ：某一颜色实例 ( 3 ) 为描述多流程的情况，本文采用一种把多个工作流网合并的方法。 ( 4 ) 参考文献 1 9 】的两个思想：染色体为变迁序列以及交叉算子在标识m 相同的两个位置间交换变迁序列。为了描述工作流中的并行结构和多实例并行执 行的情况，采用n 元组的染色体以及基于其上的适应度函数计算方法和交叉算子 操作方法。 1 4 本文的组织结构 本文分为六章，其组织结构如下： 第1 章为概述，描述工作流调度的国内外研究现状，提出本文的研究思路和 创新点。 第2 章介绍文中所涉及的基础理论知识，包括p e t r i 网基础理论、工作流和 模糊数学基础理论。 第3 章详细介绍本文采用的工作流网模型。 第4 章详细介绍本文采用的调度优化方法及其设计。 第5 章详细介绍本文的工作流网模型及调度优化方法的实现算法及数据结 构，最后用一个具体例子进行实验。 第6 章对本文进行了总结，并提出了进一步的研究工作。 第2 章相关理论基础 2 1p e t r i 网基础理论 本文所使用的工作流模型是通过对经典p e t r i 网进得扩展而得的，因此本章 在参考文献 2 的基础上，对p e t r i 网的基本概念、术语与标记进行简要的介绍。 2 1 1p e t r i 网的形式化定义 p e t r i 网是1 9 6 2 年由德国的c a l a d a mp e t r i 教授在他的博士论文中提出来的， 其时的p e t r i 网是一种经典的p e t r i 网。 一般系统的模型均由两类元素构成：表示状态的元素和表示变化的元素【甜。 p e t r i 网系统也不例外，结构上，它是一类特殊的有向图，p e t r i 网由两种元素组 成： ( 1 ) 状态元素。也称s 元素，s 元或库所( p l a c e ) ，表示一种资源【2 】。在 p e t r i 网中，库所用圆圈表示，资源的数量用圆圈中黑点的个数表示，这种黑点 叫做托肯( t o k e n ) 。 ( 2 ) 变化元素。在p e t r i 网中称为t - 元素，t 一元，也称变迁( t r a n s i t i o n ) ， 用矩形表示 2 】。 p e t r i 网是一个有向图，库所和变迁交替地出现在由有向弧连接而成的路径 上，有向弧可以从库所指向变迁，也可以从变迁指向库所。每条有向弧上都标明 该弧的权值，表示使用或产生t o k e n 的数量。没有标明权值的弧表示它的权重为 l 。 定_ 义2 - 1 1 2 1 三元组n = ( s ，t ，f ) 称为有向网，简称网的充分必要条件是： ( 1 ) s n t = 中 ( 2 ) s u t 巾 ( 3 ) f s x t u t xs 、 ( 4 ) d o m ( f ) u c o d ( f ) = s u t 其中，d o m ( f ) = x l3y ：( x ，y ) f ) ，c o d ( f ) = f y 3x ：( x ，y ) f ) 。 s 和t 分别称为n 的库所集和变迁集，f 为流关系。 定义2 - 2 2 】 设x x 为n 的任一一元素， x = y l ( y ，x ) f ) 称为x 的前集( p r e s e t ) 或输入集， x = z i ( x ，z ) f 称为x 的后集( p o s t s e t ) 或输出集 定义2 - 3 【2 i ( 1 ) 若v x x ：x f 3x = 中，则n 为单纯网。 ( 2 ) 若v x x ：。x = y a x 。= y + j x = y ，则n 为简单网。 以上只是有向网的定义，是系统的结构框架，还不是p e t r i 网系统。从网到 网系统的过程必须指明资源的初始分布，规定框架上的活动规则，即库所的容量 和变迁与资源之间的数量关系。 记i n 。= 0 ，1 ，2 ，) ，i n = f 1 ，2 ，3 ，- - - ，u 表示无穷 定义2 - 4 1 2 1 ( 1 ) k ：s 斗l n u ( i ) ) 称为有向网n = s ，t ：f 的容量函数 ( 2 ) 对给定的容量函数k ， m ：s l n 。称为n 的一个标识( m a r k i n g ) 的条件是：vs s ：m ( s ) k ( s ) ( 3 ) w ：f 专i n 称为n 上的权函数对( x ，y ) f ，w ( x ，y ) = w ( ( x 。y ) ) 称为 ( x ，y ) 上的权。 权函数规定了每个变迁发生一次引起的有关资源数量上的变化，对任何的 ( x ，y ) f ，o ，则t 在m 可以发生( 被触发) ，将标识m 改变为m 的后继m ，m 的定义是，对于任何s s ： m ( s ) = 彳( s ) 一w ( s ，) 若s r 一， m ( s ) + ( f ，s ) 若s t 一f m ( s ) 一w ( s ，) + 矽( ，s ) 若j t n t m ( s 、 若j 萑f 标识由m 变化到m 的后继m 记作m t m 。 2 1 2 行为特性 根据是否与初始标识有关的规则，p e t r i 网的性质可以分为两种类型口1 1 ：与初 始标识相关的性质称为行为特性：与初始标识无关的性质称为结构特性。下面对 p e t r i 网的几种重要的行为特性进行定义，包括可达性( r e a c h a b i l i t y ) 、有界性 ( b o u n d e d n e s s ) 以及活性( 1 i v e n e s s ) 。 ( 1 ) 可达性 定义2 - 7 【2 l 】 在p e t r i 网系统= ( s ，t ；f ，k ，w ，m 。) 中，当存在触发序列o = t - t z t 。可以使 得标识m o 变成m n 时，则称m n 是从m 0 可达的。所有从m 0 可达的标识称为m 0 的可达 集合 m 0 。所有能够从m 0 启动的变迁序列记为l ( m 0 ) a ( 2 ) 有界性 定义2 - 8 1 2 1 1 对于p e t r i 网系统= ( s ，t ：f ，k ，w ，m 。) ，如果存在一个整数k ，使得对于v m m 。 以及vs s ，均有 i ( s ) k ，则称是k 有界的或简称有界的。如果k 2 l ， 则称是安全的。 ( 3 ) 活性 活性与无死锁两个概念是紧密相关的。一个p e t r i 网系统= ( s ，t ：f ，k ，w ，m 0 ) 具备活性，指的是对于v m e 以及v t t ，存在一个m m 。 ，使得t 在m 下是使能的。这意味着一个活的p e t r i 网系统保证了完全没有死锁的操作。 2 q 活性是很多系统的理想特性，但实际上这是很难实现的。为此，可以放宽对 活性的限制，定义不同的活性级别： 定义2 - 9 在p e t r i 网系统= ( s ，t ：f ，k ，w ，m 。) 中，称一个变迁t 为 死的或l 0 活的( l 0 1 i v e ) ，如果对于vo l ( m 。) ，o 中均不出现t ，即 对于v m e m 0 ，t 都不是使能的。 l 1 活的( l 1 1 i v e ) ，如果存在o l ( m o ) ，使得t 在o 中至少出现一次。 l 2 活的( l 2 1 i v e ) ，如果给定一个任意正整数k ，总是存在o l ( m 。) ， 使得t 在。中至少出现k 次。 l 3 活的( l 3 一l i v e ) ，如果存在o l ( m 0 ) ，使得t 在。中无限经常地出现。 l 4 活的( l 4 一l i r e ) 或活的( 1 i v e ) ，如果对于v m e m o ，t 都是l 1 活的。 一个p e t r i 网系统称为l k 活的，如果对于v t t ，t 是l k 活的( k = 0 ，l ， 2 ，3 ，4 ) 。 2 1 3 四种标识网子类型 若一个p e t f i 网中每一条有向弧的权重都是1 ，则该p e t r i 网称为平凡p e 廿i 网 或标识网1 2 l 】。下面简单介绍四种特殊的标识网，它们分别是状态机、标识图、 自由选择网和扩展自由选择网。 定义2 1 0 1 2 1 】 在标识网e = ( s ，t ：f ，k ，w ，m o ) 中，如果对于v t t ，均有l t l = l t l = l ，则 称为状态机。即状态机是每个变迁都只有一个输入库所与一个输出库所的标识 网，如图2 一l 所示。 图2 i 状志机示例 定义2 1 1 2 1 】 在标识网e = ( s ，t ：f ，k ，w ，m o ) 中，如果对于v p e p ，均有。p = | p 。f = 1 ，则 2 n 叫j 称为标识图。即标识图是每个库所都只有一个输入变迁与一个输出变迁的标识 网，如图2 2 所示。 圈2 2 标识图示例 定义2 1 2 【2 l 】 在标识网= ( s ，t ：f ，k ，w ，m 。) 中，如果对于v p e p ，均有ip l 1 或者( p 。) = p ) ，则称为自由选择