（计算机软件与理论专业论文）基于仿真优化的工作流资源配置.pdf

中山大学硕士论文基于仿真优化的工作流资源配置 论文题目 专业 硕士生 指导教师 基于仿真优化的工作流资源配置 计算机软件与理论 邝国桑 余阳副教授 摘要 随着工作流技术的发展，工作流系统在企业的运作中起着越来越重要的作 用。在工作流技术中，业务流程案例的平均执行时间是系统最重要的性能指标， 体现着企业的运行效率。而执行业务流程的资源数目，则在很大程度上决定了企 业的运营成本。这两者都是影响企业竞争力的关键因素。然而，在现实当中，业 务流程案例的平均执行时间和资源数目是一对矛盾。因此，在保证企业运营成本 不超过一定上限的前提下，最大限度地通过优化资源配置实现最低的业务流程案 例平均执行时间是大多数企业的迫切需求。 目前，由于受到数学分析手段的限制，大多数针对工作流资源配置优化的研 究都在特殊的约束下进行。这无疑极大地限制了这些研究的应用范围和精度。少 数针对更一般情况的研究只是在起步阶段，没有深入研究算法本身。 为了解决当前研究在适用范围上的问题，本文以仿真优化技术为基础，解决 在成本约束下，工作流的资源配置优化问题。首先，通过排队论和一系列的仿真 实验，对工作流资源配置优化问题的可行域性质进行了分析，并得出相关结论； 在此基础上，为禁忌搜索算法设计了一系列的启发式规则，使禁忌搜索算法能够 在仿真优化中更高效地求解工作流的资源配置问题。最后，通过实验证明了本文 所提出的算法的有效性。 本文的研究通过优化仿真优化中禁忌搜索算法的启发式规则，有效地提高了 利用仿真优化求解工作流资源配置问题的效率。对企业在过程改进和业务流程重 构阶段进行资源配置优化有一定的应用价值。 关键词：工作流；资源配置；仿真优化；禁忌搜索；启发式规则 中山大学硕士论文基于仿真优化的工作流资源配置 t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： s i m u l a t i o no p t i m i z a t i o nb a s e dw o r k f l o wr e s o u r c ec o n f i g u r a t i o n c o m p u t e rs o f t w a r ea n dt h e o r y k u a n gg u o s h e n y uy a n g ( a s s o c i a t ep r o f e s s o r ) a b s t r a c t w i t ht h ep r o g r e s so fw o r k f l o wt e c h n o l o g y , w o r k f l o ws y s t e mp l a y sam o r ea n d m o r ei m p o r t a n tr o l ei nc o r p o r a t i o no p e r a t i o n i nw o r k f l o wt e c h n o l o g y , a v e r a g e e x e c u t i o nt i m eo fp r o c e s si n s t a n c ei sak e yp e r f o r m a n c ei n d i c a t o ro ft h es y s t e m ， w h i c hr e f l e c t st h ee f f i c i e n c yo ft h ec o r p o r a t i o no p e r a t i o n m e a n w h i l e ，t h en u m b e ro f t h eh u m a nr e s o u r c e se x e c u t i n gt h eb u s i n e s sp r o c e s sd e c i d e st h eo p e r a t i o n a lc o s t st oa l a r g ee x t e n t t h e s et w oe l e m e n t sa r eb o t l lk e yf a c t o r so fe n t e r p r i s ec o m p e t i t i v e n e s s h o w e v e r , i nr e a l i t y , t h e s et w oe l e m e n t sa r ec o n t r a d i c t o r y h e n c e ，o nt h ep r e m i s eo f n o te x c e e d i n gag i v e nc o s t ，m i n i m i z i n gt h ea v e r a g ee x e c u t i o nt i m eo fp r o c e s si n s t a n c e t h r o u g ho p t i m i z i n gr e s o u r c ec o n f i g u r a t i o ni st h en e e do fm o s te n t e r p r i s e s c u r r e n t l y , r e s t r i c t e db yt h em a t h e m a t i c a la n a l y s i sm e t h o d s ，m o s tr e s e a r c h e so n w o r k f l o wr e s o u r c ec o n f i g u r a t i o na r eu n d e r t a k e nu n d e rp a r t i c u l a rc o n s t r a i n t s t h i s u n d o u b t e d l yr e s t r i c t st h e i ra p p l i c a t i o ns c o p ea n dp r e c i s i o n af e wr e s e a r c h e sw h i c h f o c u so nm o r eg e n e r a lc a s e sa r ej u s ta tb e g i n n i n gs t a g e ，a n dh a v en o tm a d ead e e p s t u d yo nt h eo p t i m i z a t i o na l g o r i t h m i no r d e rt os o l v et h ep r o b l e mi na p p l i c a t i o ns c o p eo ft h ec u r r e n tr e s e a r c h e s ，t h i s p a p e rs o l v e dt h ew o r k n o wr e s o u r c ec o n f i g u r a t i o np r o b l e mb a s e do ns i m u l a t i o n o p t i m i z a t i o n f i r s t l y , t h r o u g hq u e u i n gt h e o r ya n das e r i e so fs i m u l a t i o ne x p e r i m e n t , f e a s i b l er e g i o no fw o r k f l o wr e s o u r c ec o n f i g u r a t i o np r o b l e mw a sa n a l y z e d ，a n dr e l a t e d c o n c l u s i o n sa l eg i v e n o nt h a tb a s i s ，as e to fh e u r i s t i c sw e r ed e s i g n e df o rt a b us e a r c h t os o l v et h ep r o b l e mm o r ee f f e c t i v e l y f i n a l l y , c o n t r a s te x p e r i m e n t sw e r em a d et o p r o v et h ee f f e c t i v e n e s so f t h ea l g o r i t h mp r o p o s e di nt h i sp a p e r t h er e s e a r c hi nt h i sp a p e rh a sp r o p o s e das e to fh e u r i s t i c sf o rt a b us e a r c hf o r 1 1 1 中山大学硕士论文基于仿真优化的工作流资源配置 s o l v i n gt h ew o r k f l o wr e s o o r c ec o n f i g u r a t i o np r o b l e mu s i n gs i m u l a t i o no p t i m i z a t i o n m o r ee f f e c t i v e l y i th a sc e r t a i na p p l i c a t i o nv a l u ei nr e s o u r c ec o n f i g u r a t i o na d j u s t m e n t i np r o c e s si m p r o v e m e n ta n d p r o c e s sr e e n g i n e e r i n gp h r a s e k e yw o r d s ：w o r k f l o w , r e s o u r c ec o n f i g u r a t i o n ，s i m u l a t i o no p t i m i z a t i o n ，t a b us e a r c h ， h e u r i s t i c s 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：加，d 年多 唧目粜 月 弓 日 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：啷日粜翩签名：拿毛 日期：2 口，d 年占月弓e j日期：肋d 年多月弓日 中山大学硕士论文 基于仿真优化的_ i 作流资源配置 1 1 研究背景 第一章引言 工作流，是指业务流程在计算机系统支持下的部分自动化或全自动化【l 】。 工作流可以从三个维度进行观察：流程、案例以及资源 2 】。流程定义了组成业 务流程的任务以及任务之间的路由关系。案例即流程的实例，它反映了各个流程 实例之间的相对独立性。而资源则是任务的执行者。 目前，工作流技术在各种企业和组织中已经得到了广泛的应用，它有效地降 低了办公人员的强度，提升了工作效率。然而，为了能够适应不断变化的外部环 境，企业和组织往往需要改进在成本、品质和服务等方面的绩效。为此，在工作 流管理系统的支持下，“业务过程再造”( b p r ，b u s i n e s sp r o c e s sr e e n g i n e e f i n g ) 和“持续过程改进 ( c p i ，c o n t i n u o u sp r o c e s si m p r o v e m e n t ) 作为改善企业运营 水平，提升企业竞争力的方法被提出。前者是一种革命性的手段，它在诊断现有 工作方式的基础上，推倒已有的一切，进行“白手起家”式的重新设计，因此同 时涉及到业务过程的重新构造和资源的重新配置；而后者则是一种较为温和的手 段，它可能牵涉到对业务过程或者资源配置的轻微改进【3 】。 由此可知，无论是b p r 还是c p i ，都可能涉及到提升企业的关键性能指标 ( k p i ，k e yp e r f o r m a n c ei n d i c a t o r s ) 和资源的重新配置问题。这两者在现实中往 往是一对矛盾：提升企业的关键性能指标通常需要加大在资源方面的投入，而这 意味着企业运营成本的增加。一般而言，企业更希望在保证成本在其可承受范围 内的前提下，通过优化资源的配置方案而提升关键性能指标。 因此，研究在成本受限的情况下，如何通过优化资源配置提升企业关键性能 指标有重大的现实意义。然而，由于企业的关键性能指标在现实中是多种多样的， 因此，目前大多数研究都挑选一个广泛适用，并且在很大程度上反映企业运行效 率的指标流程案例的平均执行时间作为优化的目标。在保证成本不超上限的 情况下，通过资源配置的调整对该目标进行优化。 中山大学硕士论文基于仿真优化的工作流资源配置 然而，当前研究大多数在优化算法中使用了数学分析手段评估流程案例的平 均执行时间。鉴于业务流程结构本身所具有的特点，以及数学分析手段在应用条 件上的严格要求，使得这些方法在适用范围受到了很大的限制，而精度也受到了 一定的影响。而少数针对更一般情况的研究仅仅处于起步阶段，尚未有深入地研 究优化算法。 为了解决上面提及的在适用范围和精度上的问题，本文的研究基于仿真优化 技术，重点研究在结合了仿真优化技术以后，禁忌搜索算法的启发式规则，从而 达到提高求解成本约束下资源优化配置问题的效率这一目标。本文的研究成果将 有助于企业更好地解决在b p r 或c p i 过程中所遇到的性能与成本的矛盾，有一 定的实用价值。 1 2 问题描述 本文所研究的，在成本约束下，工作流的资源配置优化问题可以描述为：对 于一个可以由工作流四种基本路由结构建模的业务流程p r o c e s s ，它由r 1 个任务 组成，分别为t 。，t ：，t 。流程案例的到达时间间隔和每个任务的执行时 间服从某个已知的概率分布。假定每个任务t ；都对应唯一一个可以执行它的角 色r ”并且每个可以担任角色r ；的单个资源的成本为c 。在给定工作流引擎的 任务分配规则和资源执行任务的策略的前提下，工作流资源配置的优化问题可以 表述为：找出每个角色r 。具体的资源数目x 使得在总成本不超过一个上限c 的同时，业务流程案例的平均执行时间最短。即： m i n i m i z e a e t ( x l ，x 2 ，x 。) = e ie x e c u t i o n t i m e ( x l ，x 2 ，x 。) l y c ，幸葺sc j i， j = i 其中，e e x e c u ti o n t i m e ( x l ，x 2 ，x 。) 表示在资源配置为( x ，x 2 ，x 。) 时，流程案例的平均执行时间。 2 中山大学硕士论文基于仿真优化的工作流资源配置 1 3 研究现状 求解问题( 1 1 ) 涉及两项关键技术： 1 在特定的资源配置下，流程案例平均执行时间的获取( 即函数a e t ( x 1 ， x 2 ，) ( 1 1 ) 的计算问题) ，这是一个工作流性能分析方面的问题； 2 在l 的基础上，设计一种优化算法对资源配置进行优化，以找出使流程 案例平均执行时间最短的解，这是一个优化算法的设计问题。 鉴于此，本节将首先对工作流的性能分析研究现状进行分析，再对目前在资 源配置优化方面的研究进行总结。 1 3 1 工作流性能分析研究现状分析 工作流性能分析是获取用户所感兴趣的性能指标，例如案例的完成时间、资 源利用率等的手段。其中，流程案例的平均执行时间作为反映系统吞吐量和企业 效率的重要指标，受到了学术界的关注。 从传统的系统性能分析技术而言，数学分析( a n a l y t i c a lm o d e l i n g ) 、仿真 ( s i m u l a t i o n ) 和测量( m e a s u r e m e n t ) 是性能分析的三大手段【4 】。结合到工作流 领域，三者都可以用于获取流程案例的平均执行时间。然而，这三种手段的应用 对系统所处的生命周期有着不同的要求：前两者可以用于系统生命周期的任意阶 段，而测量方法仅适用于已经存在原型系统的场合【4 】。因此，测量方法明显不 适用于比较多种可行系统的设计。所以，在b p r 或c p i 过程中，较多应用的是 数学分析和仿真手段，目前对工作流性能分析的研究也主要集中在这两方面。 在数学分析方面，目前工作流性能分析主要用到的工具是随机p e t r i 网及其 变种以及排队论【5 】。文献【6 】详细讨论了对p e t r i 网进行时间扩展的多种可能，并 在此基础上，结合工作流流程模型中的四种基本结构，给出了离散时间随机p e t r i 网的性能分析方法。利用该方法可以有效地计算流程案例执行时间的概率密度函 数。文献【7 ，8 】仍然以随机p e t r i 网模型为基础，但是将研究的重点放在流程案例 的平均执行时间上，针对变迁的执行时间服从负指数分布的情况，提出了工作流 流程模型四种基本结构的等价性能分析方法，利用该方法可以有效地求解基于 3 中山大学硕士论文基于仿真优化的工作流资源配置 p e t r i 网的工作流模型的平均执行时间。文献 5 】同样基于p e t r i 网，并将重点放在 求解流程案例平均执行时间的上下界方面，该研究适用于任务的处理时间服从任 意概率分布的情况。文献【9 】则更进一步，在没有对任务执行时间和流程结构做 出任何限制的前提下，利用流体随机p e t r i 网计算流程案例执行时间的概率分布。 利用随机p e t r i 网进行工作流性能分析的一个重要问题在于，这些方法绝大 部分基于资源数目是无限的这一假定 6 】，这明显与实际情况有着重大的差异， 因而也不能应用于求解工作流的资源配置优化问题。 作为另一种数学分析手段，排队论 4 f f j 以弥补这方面的不足。结合工作流 模型的四种基本结构，文献 1 0 】和文献【1 1 针对流程案例到达时间间隔和任务执 行时间都服从负指数分布的情况，提出了流程案例平均执行时间的计算方法。在 相似的约束下，文献 1 2 ，1 3 提出了流程案例执行时间概率分布的获取方法。文 献 1 4 】的研究使排队论能够不受业务流程四种基本结构的限制，而适用于范围更 广的自由选择p e t r i 网，同时也考虑了同一类资源可以执行多种任务的情况。文 献【1 5 】则在资源方面更进一步，将基于排队论的性能分析推广到同一类资源可以 执行不同工作流的不同任务的情况。由于以上研究都用到排队网络的相关结论， 因而它们都做出了流程案例到达时间间隔和任务执行时间都服从负指数分布的 假定。同时，正如文献【3 】所指出的那样，由于排队论在应用条件上的限制，使 得上述研究在处理四种工作流基本结构之一的并行结构时，需要进行近似处理或 者做出其它假设。这无疑影响了这些研究结果的适用范围和精度。 作为一种灵活的分析技术，仿真可以弥补随机p e t r i 网和排队论在工作流性 能分析上的不足。目前，大部分工作流管理系统都带有仿真工具以方便用户进行 性能分析。例如，p a l l a s a t h e n a 公司的p r o t o s 1 6 ，i b m 公司的f i l e n e t 1 7 ，i d s s h e e r a g 的俐s 【1 8 】以及开源工具w o r k f l o w s i m 1 9 等。文献【2 0 】对一些较为著 名的工作流仿真工具进行了分析和对比。文献 2 1 l 贝t j 给出了有关工作流仿真的概 述。文献【2 2 1 讨论了工作流仿真分析的基本过程，利用资源约束的随机工作流网 建立仿真模型，并给出了相关的性能指标。文献 2 3 1 基于随机p e t r i 网和事件调度 策略讨论了工作流的仿真中的关键技术问题。文献 2 4 1 对业务流程仿真与分析系 统的理论基础和实现方案进行了研究。文献 2 5 】提出了一种工作流仿真方法，该 方法对工作流仿真中的不确定性进行了处理，并将虚拟现实技术用于仿真动画的 4 中i j i 大学硕士论文基于仿真优化的工作流资源配置 显示。 1 3 2 工作流资源配置优化研究现状分析 在对工作流的资源配置进行调整，以优化流程案例平均执行时间方面，文献 【lo 】提出了针对业务流程中的关键路径，计算每个任务的最小资源数目的方法， 通过该方法能够以一定的概率保证流程案例的甲均执行时间在某个阈值之下。文 献【2 6 】则从另外一个角度进行研究：在保证流程案例平均执行时间小于某个指定 值的前提下，通过优化资源配置以实现单位时间成本最低。这些研究的关注点与 问题( 1 1 ) 有所不同。 文献【2 7 】是关于通过调整资源配置以获取最低流程案例平均执行时间的早 期研究，该文献提出了m a r g i n a la l l o c a t i o n 算法进行工作流的资源配置，并证明 了该算法对于到达过程是泊松过程，所有任务的服务时间都服务负指数分布的状 态机随机工作流网( s t a t e - m a c h i n e s t o c h a s t i cw o r k f l o wn e t ) 可以实现最优的资源 配置。然而，该研究没有考虑资源费用和成本上限的问题。同时，状态机随机工 作流网是工作流网的一个真子集，对于一般工作流网而言，该算法无法实现最优 资源分配【2 7 】。 而最近研究普遍考虑了资源费用和成本上限，文献 2 8 3 0 是其中的代表，它 们以排队论求解在特定资源配置下，流程的平均执行时间，并在此基础上采用遗 传算法求解最优的资源配置。文献【31 】同样基于排队论进行流程案例平均执行时 间计算，但采用了p i s i n g e r 算法求解最优资源配置。文献【3 2 】则更进一步，将资 源的专业化一般化程度也考虑到资源优化配置问题中，并提出分层嵌套遗传算 法以求解该问题。 以上研究在优化算法方面都取得了较大的进展，然而，正如1 3 1 节的分析 所描述的那样，基于排队论的流程平均执行时间求解方法有特定的要求，这使得 这些研究必须假定流程案例的到达时间间隔和所有任务的执行时间都服从负指 数分布，并且对并行结构进行近似处理或者只考虑业务流程的关键路径。这无疑 影响了这些研究的适用范围和精确度。因而无法用于求解问题( 1 1 ) 。 作为对基于数学分析的优化算法的补充，仿真优化【3 3 ，3 4 】可以弥补上面的 研究存在的问题。文献【3 5 】总结了工作流领域中的参数优化问题，并提出可以使 中山大学硕士论文基于仿真优化的工作流资源配置 用仿真优化方法求解该类问题。文献 3 6 茭j - ! - 作流的参数优化问题挑选了参数和 指标，并提出了一个基于遗传算法的多层迭代仿真优化方法。文献 3 7 】提出利用 f r + t s 仿真优化算法求解工作流中的参数优化问题。在文献 3 6 ，3 7 】中，虽然也 将资源作为工作流的参数之一，但是优化的参数以及目标与问题( 1 1 ) 有明显区 别。文献 3 4 ，3 8 1 拘研究采用仿真优化手段求解与问题( 1 1 ) 相似的资源配置问题， 但是其中的问题定义与( 1 1 ) 相反在保证流程平均响应时间的前提下降低费 用或减少总的员工数，同时也并未深入研究算法本身。 1 4 本文的研究目标和意义 针对问题( 1 1 ) ，本文研究结合了仿真优化的禁忌搜索算法。文章的主要关注 点是禁忌搜索算法的启发式规则，目的是使结合了仿真优化的禁忌搜索算法能够 更有效地求解该问题。具体体现在利用了本文所提出的启发式规则以后，禁忌搜 索算法的收敛速度对比基本的禁忌搜索算法有明显提升，同时能够保持智能算法 能够收敛到全局最优的性能，使其能够找到比爬山法等局部优化算法更优的解。 本文的研究意义有以下几点： 1 ) 增强工作流资源管理系统在优化资源配置方面的能力，为企业用户提供 更好的资源配置方案。现有的工作流管理系统往往带有业务流程仿真工具，可以 让用户对其设计的流程进行仿真分析以预测真实系统的性能指标，这为对工作流 进行仿真优化提供了条件。一旦将仿真优化算法引入工作流管理系统，将不但允 许用户预测真实系统的性能指标，还将允许用户利用计算机自动地对资源等进行 配置，以获取最佳性能。 2 ) 针对问题( 1 1 ) 这一具体问题，引入了仿真优化技术进行求解，弥补了基 于数学分析法的优化技术在应用范围和精确度上的不足。正如1 3 节分析的那样， 目前大多数针对工作流资源配置的研究使用基于数学分析手段的算法求解该问 题，使得它们在适用范围和精确度上都有一定的不足。而使用仿真优化手段则可 以很好地解决该问题。 3 ) 为利用工作流的资源配置的仿真优化问题提出相关的启发式规则，从而 使优化过程有更高的效率。仿真优化的一个重要的特点就是耗时很长，这是因为 6 中山大学硕士论文 基于仿真优化的工作流资源配置 在优化过程中，需要利用仿真器对每一个候选解进行仿真评价。因此，结合了仿 真优化的智能算法在收敛速度上的要求甚至比一般以数学分析作为候选解评价 手段的智能算法还高。这就使得提高仿真优化过程的效率显得异常重要。 1 5 本文的组织结构 本文正文部分分为六章。 第一章为引言，介绍了本文的研究背景，定义了本文所要研究的问题，分析 了相关领域的研究现状，并指出了本文的研究的目标和意义。 第二章，介绍了本文所应用到的相关理论和技术，包括工作流的性能分析技 术，以及仿真优化技术等。 第三章，对要求解的成本约束下的资源优化配置问题进行了分析，为禁忌搜 索算法的启发式规则设计奠定基础。 第四章，详细描述了为使用结合了仿真优化的禁忌搜索算法求解工作流资源 配置优化问题所设计的一系列启发式规则，分别从初始解产生规则，邻域结构和 采样规则，短期记忆和藐视规则，中期记忆，和长期记忆几个方面描述。 第五章，通过实验证明本文所设计的算法的有效性，具体包括实验数据的选 取，实验数据的呈现及分析等。 第六章，总结与展望，总结了本文的主要贡献，并指出了可能的进一步研究 工作。 7 中山大学硕士论文 基于仿真优化的工作流资源配置 第二章相关理论与技术 2 1 工作流技术简介 工作流，是指业务过程在计算机系统支持下的半自动化或全自动化【3 】。作 为在工作流领域最活跃的学者之一，w i lv a nd e ra a l s t 在文献【2 】中提出了工作流 的三维视图，如图2 1 所示。 r e s o u r c ed i m e n s i o n d i m e n s i o n c a s ed i m e n s i o n 图2 1 工作流的三维视图 从图2 1 ，可以看到工作流中的三个基本概念： 业务过程( p r o c e s s ) ：也称业务流程，一个过程由许多要执行的任务( t a s k ) 和一系列决定任务执行次序的条件构成【3 】，表示处理同一类事情的公共流程。 资源( r e s o u r c e ) ：在工作流术语中，资源特指执行任务的实体【3 】，可以是 人或者机器。在本文中，资源特指执行任务的人力资源。通常，每个人力资源都 属于一个或者多个角色，而每个任务也对应一个或多个角色以表明该任务只能由 属于该角色的人力资源执行。 案例( c a s e ) ：即流程实例，根据同一个流程可以创建多个流程实例。案例 9 中山大学硕士论文基于仿真优化的工作流资源配置 之间是相对独立的，但是由于资源争用的存在而会有相互间的间接影响。 目前，在学术界，对业务流程的建模的研究主要集中在p e t r i 网及其变种上。 文献【2 】列出了四种工作流基本路由结构：顺序、并行、选择和循环。如图2 - 2 所示【2 】。 t 1t 2t 3 a ) 顺序路由 t 2 b ) 并行路由 t 3 c ) 选择路由( 隆式) d ) 选择路由( 显式) 1 2 e ) 循环路由 图2 - 2 工作流的四种基本路由结构 通过四种基本路由结构，可以对大多数流程进行建模，因此，许多工作流相 关的研究也以此为基础进行。然而，在现实的工作流产品中，更多地使用的是与 自由选择p e t d 网等价的模型，部分可以在现实工作流产品中建立的业务流程并 不能够使用以上四种基本路由结构表示【3 】。 1 0 中山大学硕士论文基于仿真优化的工作流资源配置 2 2 工作流性能分析方法 由于需要在优化过程中获取每个候选的资源配置对应的平均流程案例执行 时间，因此，工作流性能分析技术是工作流资源配置优化的基础。虽然本文研究 的是摹于仿真优化的工作流资源配置( 即，在优化过程中会使用仿真而非数学分 析手段获取工作流性能) ，但是，基于排队论的数学分析方法在可行域的确定及 其分析上仍然存在价值。所以，这里将首先介绍基于排队论的数学分析方法，然 后再介绍基于仿真的分析方法。 2 2 1 基于排队论的数学分析方法 排队论是研究服务系统中排队现象随机规律的学科，广泛地应用于计算机网 络、生产、运输、库存等各项资源共享的随机服务系统【3 9 】。图2 3 是摘自文献 【3 3 1 的多；i n 务台排队系统模型：顾客不断地到达，加入等待队列，然后接受服务 台( s e r v e r ) 的服务，最后离开系统，重新成为一名潜在顾客。 c a l l i n gp o p u l a t i o n o fp o t e n t i a lc u s t o m e r s n 雌1 i 鹏 由 cp a r a l l e l s e r v e r s 图2 - 3 多服务台排队系统模型 在一个排队系统中，关键的元素包括以下几点【4 ，3 3 ： 1 ) 拟到达总体( c a l l i n gp o p u l a t i o n ) ：拟到达总体即潜在顾客。在排队系统 模型中，主要关注的是拟到达总体的数目。在许多真实系统中，拟到达总体都是 有限的，但在拟到达总体的数目足够大时，为方便分析，通常假定是无限的。 2 ) 到达过程：即顾客的达到所满足的模式，通常使用一个概率分布进行描 述。最常用的到达过程是泊松过程，即顾客的到达时间间隔是独立同分布的随机 变量并且服从负指数分布。其它概率分布，例如超指数分布和e r l a n g 分布，在 某些场合下也会用到。通常使用f 表示顾客的到达时间间隔，而用名= l e ( f ) 表 中山大学硕上论文 基于仿真优化的工作流资源配置 示平均到达率。 3 ) 系统容量：即系统中正在等待和接受服务的顾客的最大数目。在大多数 系统中，一旦系统中的顾客数目到达某个上限，新来的顾客将会被拒绝服务。但 如果系统容量很高，那么可以将系统容量近似看作是无限的以方便分析。 4 ) 服务规则：在等待队列中的顾客按照什么顺序接受服务。常用的有f c f s ( 先来先服务) ，l c f s ( 后来先服务) 等。 5 ) 服务台数目：服务台的数目是影响排队系统中顾客等待时间的关键因素， 通常用m 表示。