基于工作流模型的资源配置优化方法

《基于工作流模型的资源配置优化方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于工作流模型的资源配置优化方法1,231刘胜，范玉顺，尹朝万（1．中国科学院沈阳自动化研究所辽宁沈阳110016；2．中国科学院研究生院北京100039；3．清华大学自动化系，北京100084）摘要：工作流模型在执行过程中所引用的资源数量可以被优化；当业务实例在工作流模型中逗留时间受约束时，假设每一活动的业务实例逗留时间服从负指数分布，给出了以资源单位时间消耗成本最小化为目标的求解最优资源数量的方法。分析了业务实例在工作流4种基本结构的逗留时间分布与在每一活动的逗留时间分布的关系，给出了业务实例在工作流模型中总逗留时间与

2、各资源数量的关系，最后给出了一个基于工作流模型的资源优化示例。关键词：工作流；资源配置优化；分布函数；排队问题中图分类号：TP166TP311.1381引言[1][2]工作流模型可以由4种基本结构构成。李建强等讨论了工作流系统的资源负载状况。1[3]KYLEY.LIN等人定性讨论了单服务台系统中事务到达、处理和等待时间之间的关系。JinHyunSon等人讨论了在排队模型中系统容量有限的情况下，单服务台和双服务台两种模型[4]在不同策略下、系统服务水平和服务成本之间的关系。刘丽文讨论了1人双机情况下采用[5]不同策略时系统的

3、产出率及其关系。RenaudLeper等人讨论了存在优先限制情况下弹性完[6]成时间的任务调度的近似算法。目前已有很多文献在服务台数量确定且小于3的情况下对客户服务台模型进行了讨论，但是在多种服务台轮流对客户服务，每种服务台数量可变的模型中讨论每种服务台数量的优化问题目前还未见文献报道，基于以上模型，在用工作流模型描述的业务过程中，本文将研究事务的逗留时间与配置资源数量间的优化问题。本文假设事务到达间隔服从泊松分布，资源处理事务时间服从负指数分布。优化问题的约束条件为给定比例（通常98%以上）的事务在工作流模型中总逗留时间

4、小于给定值，目标为单位时间资源消耗成本最低，优化对象为各个资源的数量。研究的成果可以用来指导服务类行业合理安排各类窗口（或服务台）数量，在顾客到达情况和逗留时间不变的情况下降低员工和设备的使用成本。还可以用来指导以手工生产为主的企业合理安排各类工种的数量，在单件加工时间不变的情况下，降低企业的资源消耗成本，提高订单的处理速度。为便于讨论，作如下定义：逗留时间：事务从进入特定活动（或有多个活动组成的结构）等待资源处理至处理完毕的时间间隔。等待时间：事务在特定活动（或结构）等待资源处理的时间。处理时间：事务在特定活动（或结构）

5、被资源处理的时间。资源利用率：资源对事务处理时间占该资源对事务处理时间和该资源无事务可处理时间之和的比率。为了优化各资源数量，必须得出事务逗留时间与配置资源数量间的关系，本文将这一关系分解为以下三种关系：1.事务在特定活动和在工作流模型基本结构逗留时间的关系。2.特定活动可调用资源数量与事务在该活动逗留时间的关系。3.所有活动调用各类资源数量与单位时间总资源消耗成本关系。基金项目：国家863/CIMS主题资助项目（2003AA412210）。作者简介：刘胜（1978－），男，安徽合肥人，中国科学院沈阳自动化研究所博士研究生

6、，主要从事工作流技术研究、企业综合过程建模等。E－mail：liusheng@sia.cn。在讨论上述关系基础上本文在第5节给出了基于工作流模型的资源配置优化示例。2事务在特定活动和在工作流模型基本结构逗留时间的关系模型工作流模型主要包括四种基本结构：串联结构、并联结构、选择结构、循环结构。复杂的工作流模型可由这四种基本结构组合而成，为了得出整个工作流模型对事务的服务水平，本文分类讨论四种基本结构的等价排队算法。工作流模型中事物在所有活动的逗留时间、处理时间互不相干，所以是相互独立的，图1列出了四种基本结构的模型图。活动1

7、λ1活动1λ1λµ1λλµ1λλ2λ2活动2活动2λµ2µ23λ3活动3活动3µ3µ3λ=λ1=λ2=λ3λ=λ1+λ2+λ3(a)并联结构(c)选择结构λ1λ2λ3λ活动1活动2活动3λλ1µ1λ2λµ1µ2µ3活动1λ1=λ2=λ3λ1=λ+λ2(b)串联结构(d)环形结构图1工作流模型的四种基本结构Fig1fourbasicstructuresofworkflowmodel在图1(a)、图1(b)、图1(c)中，分别以f(t)、f(t)、f(t)表示活动1、活动2、活l1l2l3动3的事务逗留时间概率密度函数，T1、

8、T2、T3表示在活动1、活动2、活动3的事务逗*留时间，以E()T表示事务在相应结构的平均逗留时间，以f(t)表示相应结构的事务逗留时间概率密度函数。2.1并联结构并联结构中事务同时进入各个活动，事务在所有活动执行完毕后，下一个事务才能进入并联结构，模型如图1(a)所示。事务在并联结构中的逗留时间等于在