（机械制造及其自动化专业论文）基于独立队列的业务过程调度优化关键技术研究.pdf

摘要 摘要 随着以过程为中心( p r o c e s sc e n 钯r e d ) 的各种先进制造管理模式及过程意识信息 系统( p r o c e s s a w a r ei i 面m l a t i o ns y s t e m ) 的广泛应用，业务过程建模和优化已成为业界 所关注的热点问题。本文结合国家自然科学基金叫o 5 0 6 7 5 2 1 0 ) 和省科技计划项目 ( n o 2 0 0 9 c 3 1 0 3 6 ) ，对业务过程调度优化中的一些关键技术进行了研究。论文的主要 工作如下： 第一章是绪论。阐述了论文的研究背景，介绍了业务过程调度优化相关概念，阐 述了论文研究的问题、对象和假设，对业务过程调度优化的相关研究现状进行了回顾， 分析总结了其存在的主要问题，并在此基础上，提出了本文研究目标、意义、主要内 容及论文的体系结构。 第二章研究了面向调度执行的业务过程建模方法。基于w 伽c 定义的过程参考 模型，分析了业务过程的调度执行模式，形式化业务过程模型，增加一些业务过程调 度执行性能分析和优化所需的信息。基于结构化程序设计思想构建了确保业务过程模 型具有正确良好逻辑结构的3 个基本规则，并提出了相应的判断检验算法；定义了期 望执行率以及给出了其计算方法。建立的面向调度执行的具有正确良好结构的结构化 扩展业务过程模型为后续的业务过程调度优化研究奠定了基础。 第三章研究了业务过程任务分配优化方法。根据第二章建立的结构化扩展业务过 程模型，采用独立队列模式，基于最优化生产技术和m h 1 排队系统理论建立了业 务过程最大生产能力和执行时间的计算方法，构建了任务分配优化的数学模型，设计 了相应的求解算法，获得了面向生产能力最大化和执行时间最小化的过程任务随机分 配优化方案，实现了基于全局的任务分配优化，然后设计了任务的动态再分配策略以 改善基于独立队列的任务分配方法所固有的延迟调度缺点，最后进行了仿真实验，验 证了提出的两种方法的有效性。同时在仿真实验中，针对建立业务过程仿真模型需要 较高的技巧、仿真模型质量容易受建模者主观因素影响等问题，提出了一种基于g p s s 的业务过程仿真模型的自动生成方法，减少了业务过程仿真建模的工作量、提高了业 务过程仿真模型的质量。 第四章进行了支撑软件系统开发和实例应用研究。首先进行了支撑软件系统的需 求分析，分析设计了相应的数据库概念模型，提出了业务过程模型的相似性算法，建 浙江大学博士学位论文 立了支撑软件系统的功能体系结构，设计了各功能模块实现的关键核心算法，实现了 系统原型。然后，对锅炉制造企业的某型号燃煤式蒸汽锅炉的炉胆制造过程进行了实 例应用研究，进一步验证本文提出的业务过程调度优化理论方法及其支撑软件系统的 可操作性、可行性和有效性。 第五章对论文进行了总结，指出了论文的创新点，并对未来研究工作进行了展望。 关键词：业务过程；工作流；独立队列；调度优化；执行优化；建模仿真；最优化生 产技术；排队论；任务分配优化；资源配置优化；执行时间；最大生产能力 a b s t r a c t a b s t r a c t w i m 、 ，i d e 印p l i c a t i o n so fp r o c e s sc e n t e r e da d v a i l c e dm a n u f - a c 砌n m a n a g e m e n t m o d e s锄dp r o c e s sa w a r ci i l f 0 肌a t i o n s y s t e m ， b u s i n e s s p r o c e s sm o d e l i n g a n d o p t 油i z a t i o n1 l a sr e c e i v e dm u c ha t t e m i o n s u p p o r t e db yt h en a t i o n a ln 删s c i e n c e f o u l l d a t i o n ( n o 5 0 6 7 5 2 1o ) a n dt l l ep r o v i n c i a ls c i e n c ea i l dt e c l l i l o l o g yp l a l lo fz h e j i a n g p r o 、，m e ( n o 2 0 0 9 c 310 3 6 ) ，“sd i s s e n a t i o nm a k e sas y s t e m a t i c a lr e s e a r c ho n 此k e y t e c h n o l o g i e so fb u s i n e s sp r o c e s ss c h e d u l i n go p t i m i z a t i o n t h em a i l ls 仇l c t u r e o ft l l e d i s s e n a t i o ni i l c l u d e s ： c h a p t e r1 i si n t r o d u c t i o n n er e s e a r c hb a c k g r o u i l do ft 1 1 i sd i s s e r t a t i o ni se l a b o r a t e d f i r s n y t h e nt l l e r e l a t e dc o n c e p t so fb u s i n e s sp r o c e s s e ss c h e d u l i n go p t i m i z a t i o na r e i i i 仃o d u c e da n dt h er e s e a r c hp f o b l e m ，o b j e c ta n da s s u m p t i o n so ft t l i sd i s s e n _ a t i o na r e d i s c u s s e d 蹦r d l y ，t h er e l a t e dr e s e a r c h e so nb u s i n e s sp r o c e s s e ss c h e d u l i n go p t i m i z a t i o n a r er e v i e w e da 1 1 dt h ee ) 【i s t i i 培p r o b l e m sa r es u m m 撕z e d f i i l 越l y ，r e s e a r c ht a 略e t ， s i g m 丘c a i l c e ，c o m e n ta i l dm l m e w o r k o fm ed i s s e 僦i o na r ed e s c r i b e d b u s i n e s sp r o c e s sm o d e l i i l gf 浙s c h e d u l i i l ge x e c u t i o ni ss t u d i e d _ h lc h 印t e r2 f i r s t l y ， s c h e d u l 堍e x e c u t i o nm o d e so f b u s i n e s sp r o c e s sa r ea n a l y z e da i l dm eb u s i n e s sp r o c e s s m o d e li sf o m a l i z e dw h i c ha d d ss o m e1 1 e c e s s a r yi i l f o m a t i o nf o rs c h e d u l i i 玛e x e c u t i o n b a s e do n 也ep r o c e s sr e f e r e n c em o d e ld e f i n e db yw f m c t h e nt h et h i e eb a s i cm l e sf o r p r o d u c i n gb u s i n e s sp r o c e s sm o d e l 诵t t lg o o dl o g i c a ls 们t u r e a r ep r e s e n t e db a s e do n s t r u c t u r e dp r o 殍锄d e s i g ns p e c i f i c a t i o l l ，t h ea l g o r i t h mf o rv e r i 匆i n gl o g i c a l 鳓r u c 眦o f b u s i n e s sp r o c e s sm o d e li sd e v e l o p e da c c o r d i i l g l y f i i l a l l y e x p e c t e df k q u e n c yi sd e f i m e d a 1 1 di t sc a j c u l a t i o nm e 廿l o di sp r 0 1 ) o s e d ni sn e c e s s a r yt 0b u i l de x t e n d e db u s i n e s sp r o c e s s m o d e l 谢血g o o dl o g i c a ls 仃u c t u r ef o r b u s i n e s sp r o c e s ss c h e d u l i n go p t i m i z a t i o n b l l s i n e s sp r o c e s st a l s k 嬲s i 孕皿e n to p t i m i z a t i o ni sr e s e a r c h e dmc h a p t e r3 a c c o r d i i l g t ob u s i l l e s sp r o c e s sm o d e lw i 廿lg o o dl o g i c a ls 仃1 j c t u r eb u i l ti nc h a p t e r2 ，b a s e do no p ta n d m h r 1 q u e u e i i l gt l l e o 巧t h e m e m o d sf o r c a l c u l a t i n g b u s i n e s s p r o c e s sm a x i m u m 啪u g h p u ta l l dc y c l et i i n ea r ep r o p o s e df i r s t l yu s i n gi i l d i v i d u a lq u e u em o d e s e c o n d l y ，位 m a 也e m a t i c a lt a s ka s s i g 衄e mm o d e l sa i l dt h e i rs o l m i o i l sf o rm a x i m 讫i i l g l r o u 曲p u ta n d v 浙江大学博士学位论文 m i i l i m i z i n gc y c l et i m ea r ep r e s e n t e d t h i r d l y ，d y n 锄i cr e - 部s i g i 加e n tp o l i c yo ft a s k si s d e v e l o p e df o rf 时t l l e ri m p r o v i i 坞b u s i i l e s sp r o c e s sp e r f 0 肌a n c e f m a l l y ，as e to fs i m u l a t i o n e x p e r i m e n t sa r ec o n d u c t e d ，w l l i c hv e r i f i e st h e e 任e c t i v e r l e s sa i l d 缸l v 觚t a g e so fn l e p r o p o s e dm e t h o d s i i ln l es i m u l a t i o ne x p e r i m e m ，l ep r i n c i p i e sa n dm e 也o d st h a tc a i lb e u s e dt oa u t o m a t i c a l l y 位m s l a t ee x t e n d e db u s i n e s sp r o c e s sm o d e li 1 1 t ot l l eg p s ss i m u l a t i o n m o d e la r ep r o p o s e d ，、) l ，：h i c hr e d u c e st l l ew o r k l o a do n 也ed e v e l o p e r so fb u s i n e s sp r o c e s s s i i n u l a t i o nm o d e l s 觚di n l p r o v e sm o d e lq u a l i 够 t h es u p p o n i v es o 小v a r es y s t e mi sd e v e l 叩e da 1 1 dac a s es t u d yi sc o n d u c t e di nc h a p t e r 4 f i r s t l y ，t h er e q u i r e m e m so fs u p p o n i v es o 行w a 舱s y s t e ma r ea n a l y z e da l l dt h ed 乏也l b 嬲e c o n c e p 棚a lm o d e li sa l s od e s i g n e d t h e 玛ai m m e r i c a la l g o r i t h mi sp r o p o s e df o rc a l c u l a t i n g s i m i l a r i 哆o fb u s i n e s sp r o c e s sm o d e l t l l i r d l y ，t l l e 劬c t i o n a la r c l l i t e c t u r eo ft l l es u p p o n i v e s o 小a r es y s t e mi se s t a b l i s h e da n dm ek e y 劬c t i o r l a lm o d u l ea l g o r i t l l m sa r ed e s i g n e d a c c o r d i n g l y f i n a l l y ，t 1 1 ep r o p o s e dm e t l l o d s 孤d l e i rs u p p o n i v es o f s y s t e mf o r b u s i i l e s s p r o c e s ss c h e d u l i n go p t i m i z a t i o n a r e印p l i e dt 0m 锄u f a c 砌n gp r o c e s so f c o a l f i r e ds t e 锄b o i l e r 缸1 1 a c e ，w 1 1 i c hi l l u s 缸- a t e st 1 1 ep r a c t i c a l 印p l i c a b i l 崎a n de 伍c i e n c y o ft l l ep r o p o s e dm e t l l o d s 1 1 1c h 印t e r5 ，m ew h o l er e s e a r c h e si i l l i sd i s s e n a t i o na r es u m m a r i z e da r i dt l l e i 1 1 i l o v a t i o i l sa r ep o i n t e do u t l a s t l yt l l ed i s s e r t a t i o ng i v e ss o m es u g g e s t i o l l sf o r 如t u r e r e s e 铷c hw o r k s k e y w o r d s ：b u s i n e s sp r o c e s s ；w o r k n o w ；i n d i v i d u a lq u e u e ；s c h e d u l i i l go p t i m i z a t i o n ； e x e c u t i o no p t i m i z a t i o n ；m o d e l i n gs i m u l a t i o n ；o p t i m i z e dp r o d u c t i o nt e c l l n o l o g y ；q u e u i n g 也e o 巧；t a s k勰s i g l l i l l e n to 砸m 娩a t i o n ； r e s o u r c ea l l o c a t i o n o p t i m i z a t i o n ； c y c l et i m e ； m a x i n l l l n lt l l r o u g h p u t v l 致谢 致谢 感谢导师唐任仲教授在多年求学生涯中给予的悉心指导和帮助! 唐老师严谨的治 学态度、渊博的学识、敏捷的思维和敏锐的洞察力给我深刻的印象，他的诚信做人、 用心做事和严谨做学问的精神使我受益匪浅，是我可以享用一生的宝贵财富。 感谢浙江大学! 感谢现代制造工程研究所的祁国宁教授、潘晓弘教授、顾新建教 授、方水良副教授、王正肖副教授等各位老师的指导和帮助! 感谢实验室里的许虹、 汤洪涛、丁祥海、黄喜、余志伟、贾东浇、叶范波、盛文露、王志国、王国栋、刘运 通、何正为、白翱、吕景祥、江俊、王慧、刘伟星、陈晓明、李俊峰、杨旭东、隋鹏 飞、赵英、唐文东、金伶、贾顺、郑军、张昕、吕青、朱榆璇、王林玉等师兄师弟师 姐师妹们，感谢他们在课题研究、工作和学习中给我的帮助和支持! 感谢所有关心支 持我的老师和同学! 感谢我工作单位的同事们! 在我工作与求学的两难中给予了很多理解、关心和帮 助。 感谢我的岳父、岳母、姐姐和姐夫，感谢他们在我生活和学习中给予的关心、支 持和照顾! 深深感谢我的父母，正是他们给了我生命，他们的殷切期盼是我不断前进的动力， 他们的无私关心和支持是我取之不尽的上进力量! 特别感谢我的夫人，生活上帮助、精神上慰籍、相濡以沫共同呵护家的温馨，同 时希望曾经耕耘中的所有感怀能与女儿分享，愿她健康快乐成长! 值此论文完成之际，我希望与他们共享这份来之不易的成功和喜悦! 最后，衷心感谢所有关心和支持过我的人! 谢般 二口一一年一鼻亏浙讧大学玉1 1 绪论 1 绪论 1 1 研究背景 随着人类科技的进步、经济的发展、全球化的加速以及信息和知识经济时代的到 来，2 1 世纪世界各国制造业都面临着产品生命周期缩短、交货期缩短、用户需求客 户化和多样化、多品种小批量生产要求直线上升、定单数时大时小、以及无国际国内 之分的单一的全球化大市场和大竞争的动态变化环境【1 羽。为了提高综合竞争力，制 造企业必须要以最快的时间、最好的质量、最低的成本和最优的服务来满足不同类型 顾客对产品的多样化需求。面对如此激烈不确定的市场竞争环境，许多研究者从各种 不同的角度提出了各种不同的先进制造模式【l 】【5 1 ，如：计算机集成制造( c o m p u t e r i n t e 铲a t e dm a n u f a c t u r e ，c 刀m ) 、并行工程( c o n c u r r e n te n g i i l e e r i n g ，c e ) 、绿色制造 ( 陆e nm a l l u f a c t 嘶n g ，g m ) 、精良生产( l e a i lp r o d u c t i o n ，l p ) ，敏捷制造( a g i l e m a i l u f a c t u r e ，a m ) 及敏捷虚拟企业( a g i l e m l a le n t e 删s e ，a v e ) 、供应链管理( s u p p l y c h a i nm a i l a g e m e n t ，s c m ) 等。同时越来越多的企业也相应地把以职能为基础的组织 机构和运行机制转变为以过程为中心( p r o c e s sc e n t e r e d ，p c ) 的管理模式，如：业 务过程管理( b u s i n e s sp r o c e s sm a i l a g e m e n t ，b p m ) 、业务过程重组( b u s i n e s sp r o c e s s r e e n g i n e e r i n g ，b p r ) 、业务过程改进( b u s i n e s sp r o c e s si i l l p r o v e m e n t ，b p i ) 、工作流 管理( w b r k n o wm a n a g e m e m ，w 蹦) 等，采取了各种过程意识信息系统( p r o c e s sa a 鹏 i n f o m a t i o ns y s t e m ，p a i s ) 【“引，如：企业资源规划( e n t e r p r i s er e s o u r c ep l a n n i n g ， e i 冲) 、客户关系管理系统( c u s t o m e rr e l a t i o n s l l i pm a n a g e m e n ts y s t e m ，c i 洲s ) 、供 应链管理系统( s u p p l yc h a i nm a n a g e m e ms y s t e m ，s c m s ) 、制造执行系统 ( m a n u f a c t u r i n ge x e c u t i o ns y s t e m ，m e s ) 、业务过程管理系统( b u s i i l e s sp r o c e s s m 猢g e m e n ts y s t e m ，b p m s ) 以及工作流管理系统( w o 衄o wm a n a g e m e n ts y s t e m ， w 伽s ) 等。这些先进制造管理模式和p a i s 都十分强调业务过程( 也称为企业过程、 经营过程或业务流程，简称过程) ；理解业务过程，进行业务过程优化是成功实施这 些以过程为中心的先进制造管理模式和p a i s 的前提基础和内在要求【5 】【9 】。 业务过程( 例如客户订单处理过程、零部件生产加工过程等) 是企业为完成某一 目标而进行的一系列逻辑上相关的活动任务的有序集合。业务过程中活动任务的执 浙江大学博士学位论文 行通常需要资源的支持1 2 】【l3 1 。随着新技术特别是信息技术的广泛采用，为了快速响 应客户需求、适应动态多变的市场环境，当前业务过程变得越来越敏捷化、柔性化和 复杂化1 14 1 ，呈现出以下一些特点： ( 1 ) 涉及的资源众多而且资源与活动之间的支持关系复杂，存在多对多的关系。 支持业务过程中活动任务执行的资源可以是任何实体，如：人员、物理设备、文件、 应用系统程序等。为了提高业务过程的敏捷性、鲁棒性，通常会要求降低资源的专 业化程度、提高业务过程的柔性化程度( 如要求员工掌握多种技能、能承担多种角色， 加工中心能加工多种类型零件或多道工序，一个活动任务工序可以由不同的资源来 承担完成等) ，导致在业务过程中活动与资源之间存在大量的多对多的支持关系，即 某种资源可以执行多项活动，而某项活动也可以由不同的资源来完成。 ( 2 ) 涉及的活动繁多而且活动与活动之间的逻辑控制关系复杂，除顺序逻辑控 制结构外，还存在选择、并行、循环等逻辑控制结构。如：半导体晶圆制造过程、锅 炉制造过程等有成千上百道工序活动，有质量检测和返工( 选择和循环) 、装配( 并 行) 等工序。 ( 3 ) 业务过程执行中存在大量的随机和不确定因素。这主要是由过程活动实例 到达的连续性、随机性( 如：面向订单的生产过程中客户订单的到达具有一定的随机 性) 、活动的执行时间的不确定性及执行路径的不确定性( 存在选择和循环结构) 等 因素造成的。 特点( 1 ) 企业业务过程中资源与活动之间存在复杂的多对多支持关系决定了企 业在以过程为中心的先进制造管理模式中存在业务过程的调度优化( 也称为执行优 化) 问题，即在业务过程的执行中合理确定活动由哪种资源执行及何时执行的问题【1 5 】， 同时企业也迫切需要通过对其业务过程的调度优化，提高企业生产和运营的效率。业 务过程调度优化可以借鉴一些在车间作业调度、项目管理和计算网格等领域已得到 广泛应用的传统调度理论和方法【1 6 以4 1 ，然而特点( 2 ) 和( 3 ) 业务过程结构的复杂性 ( 如存在着选择和循环结构) 及其执行过程中的诸多随机和不确定因素使得这些传统 的调度理论和方法一般不能直接应用于业务过程的调度执行优化，需要对这些传统 的调度优化理论方法在业务过程调度执行优化中的有效应用开展一些新的研究 【3 5 3 7 】 业务过程调度优化是成功实施p a i s 的前提基础，反之，当前很多企业已建立的 l 绪论 p a i s 记录了大量的业务过程工作流日志。这些日志文件通常包括过程实例的编号、 过程实例的名称、过程实例中活动任务的名称、活动任务的执行者( 所需的资源) 、 活动任务的开始与结束时间等信息。这又为业务过程调度优化提供了大量的数据基 础【3 8 】。 综上所述，本文的研究背景如图1 1 所示，因此开展业务过程调度优化的研究有 着重要的理论和现实意义。 过程意识信患系统 p ，m s ，c r m s s c s 删f m 黝b p m s 数据支持 以过程为中心 p f o 镏s sc e n 自e 豫d ) 塑垄苎型兰堡登篓参 1 磊 0 蕊。，o 黧譬露 。，调度优亿，q 刁、髭兰接确卿 f 企业需求t 歉务过程的敏捷讫，黍性f ，复京化( 员工承担多种角 色设备能加工多种零往 图1 1 研究背景 1 2 业务过程调度优化概述 1 2 1 基本概念和术语 业务过程( b u s i n e s sp r o c e s s ) ：业务过程的含义很广，在相关文献中对于业务过 程并没有完全精确和统一的定义3 9 1 。如：h 卸珊e r 将业务过程定义为“使用一种或多 种输入创造对客户有价值的输出的一系列活动的集合”【柏1 ；d a v e n p o r t 定义业务过程 是“为特定顾客或市场产生特定输出的活动链”【4 1 1 ；h a n m e r 和c h 锄p y 认为业务过 程是一个由许多业务活动组成的整体，它由活动、活动间的逻辑关系、活动的实现方 式和活动的承担者四个要素组成【4 2 】【4 3 1 ；工作流管理联盟( w 僦c ) 将业务过程定义为 “为实现共同业务目标而相互联系的一个或多个步骤活动的集合”【4 4 1 ；r u t hs a r a a 撕l a r s a v e n 认为业务过程是活动集合与描述活动逻辑顺序和依赖关系的结合体，其 目标是产生期望的结果【4 5 1 ；甘华呜和朱海平等把企业中的业务过程定义为社会分工演 变的产物，它是为了实现企业某个经营目标的一个过程，即在部分或者全部组织机构 和人员的参与下，利用企业资源( 包括所需的处理设备、计算机软硬件、信息库和知 浙江大学博士学位论文 识库等) ，按照预先确定的业务规则，在参与者和组织机构之间进行文档、信息和任 务的传递，并进行日常任务处理和经营决策，从而实现预定的经营目标【4 6 1 【4 7 1 尽管 不同的领域中关于业务过程的定义不尽相同，但概括起来业务过程至少应该具有如下 特点【4 3 】【4 8 1 ：业务过程的最基本要素是一系列有规律的动作或活动；组成业务过 程的最基本要素活动之间存在一定的逻辑控制关系，即连接作用方式，他们之间的 连接作用方式具有一定的结构性，最常见的过程结构有【1 3 1 ：串连( 顺序) 结构、并 联( 选择或并发) 结构和反馈( 循环) 结构；业务过程是为完成某一目标而产生的， 即某特定结果的实现；业务过程是动态的，总是从一种活动状态集转变为另一种活 动状态集，通过活动状态的转变实现业务过程目的。综上所述，本文对业务过程定义 如下：业务过程是企业为完成某一目标而进行的一系列逻辑上相关的活动任务的有 序集合。 活动( a c t i v 时) ：指的是业务过程中的一个逻辑步骤或环节，是业务过程中能够 作为一个整体被执行的最小逻辑工作单元。 过程实例( p m c e s si i l s t a n c e ) 和活动实例( a c t i v i 够i n s t 锄c e ) ：过程实例即服务请 求，指的是某个业务过程的一次具体执行，而活动实例( 本文也称之为任务) 是指某 个活动的一次具体执行。一个活动实例只和一个过程实例相关，并使用过程实例的数 据，一个过程实例可能由若干个活动实例组成，但一个活动实例不能同时属于几个过 程实例4 9 】【5 0 1 。 业务过程中活动的执行通常需要资源的支持，资源可以是人员、物理设备、文件、 应用系统程序等任何实体。根据资源的访问性质业务过程中的资源可以分成：共享 型资源和独占型资源【5 1 1 。共享型资源是指在业务过程执行中能被多个活动实例同时访 问使用的资源，如文件、数据库、应用程序等，而独占型资源是指在业务过程执行 中同时只能被一个活动实例访问使用的资源，如人员、物理设备等。对于共享型资 源可以进一步分成两类：无限共享型资源和有限共享型资源。无限共享型资源是指可 以同时访问使用的活动实例的数量是无限的，有限共享型资源是指可以同时访问使 用的活动实例的数量是有限的。根据资源的可更新性，业务过程中的资源可以分成： 可更新型资源( 非消耗性资源) 和不可更新型资源( 消耗性资源) 。其中，可更新型 资源是指在活动的执行中不会被消耗掉的，能被重复使用的，如人员、设备等；不可 更新型资源是指在活动的执行中会被消耗掉的，不能被重复使用的，如原材料等。此 4 1 绪论 外，活动与资源之间存在的支持关系包括一对一、一对多、多对一、和多对多。一对 一指的是某个活动的实例只能由某个资源处理，而某个资源也只能处理这个活动的实 例；一对多指的是某个活动的实例能由多个资源处理，但某个资源只能处理某个活动 的实例；多对一指的是某个资源能处理多个活动的实例，但某个活动的实例只能由某 个资源处理；多对多指的是某个活动的实例能由多个资源处理，而某个资源也能处理 多个活动的实例。 业务过程优化可分为业务过程建模构建( b u i l d t i m e ) 阶段的静态优化( 如业务 过程结构优化、功能角色设计优化、资源的数量配置优化等) 和业务过程执行 ( n i n t i m e ) 阶段的动态优化即业务过程调度优化。 业务过程调度优化：是指根据一定的优化目标，在业务过程的执行中合理地把活 动实例任务分配给有能力执行的资源，及资源合理地从等待队列中选择活动实例任 务执行，以获得期望的最佳业务过程执行性能1 5 】。业务过程调度优化的目标主要有提 高响应( 缩短执行时间) 、提高吞吐量( 生产处理能力) 、提高资源利用率、均衡负 载、减少成本等。 1 2 2 业务过程的分类 关于业务过程的分类目前还没有完全统一的分类标准，可以从不同的角度对其进 行分类5 】【4 7 】【5 2 】： ( 1 ) 根据业务过程逻辑结构规范性划分：工作流管理联盟( w 蹦c ) 定义了描述 业务过程中活动之间逻辑控制关系的四种基本模型结构：顺序、选择、并发、和循环， 根据能否由这四种基本模型结构描述业务过程的逻辑结构( 即活动之间的逻辑控制关 系) ，分为结构化业务过程和非结构化业务过程。其中结构化业务过程的逻辑结构能 由这四种基本模型结构描述，而非结构化业务过程的逻辑结构不能完全由这四种基本 模型结构描述。 ( 2 ) 根据业务过程性质可划分为：生产型业务过程、管理型业务过程、特定型 业务过程和协作型业务过程。它们的特点和实例如表1 1 所示，结构化和面向过程的 程度如图1 2 所示。其中生产型业务过程和管理型业务过程一般属于结构化业务过程， 业务过程的结构化程度比较好，具有高度的逻辑结构规范性，通常完全可以由顺序、 选择、并发和循环等四种基本模型结构描述。 浙江大学博士学位论文 表1 1 管理型、生产型、特定型和协作型业务过程的特点及实例 类型特点实例 生产型业务过程高度结构化，模型变种很少，每天需要处 零件加工过程、 ( p r o d u c t i o nb u s i n e s sp r o c e s s ) 理大量过程实例。 保险索赔过程。 管理型业务过程 存在若干预先定义好的选择路由，结构良o a 中的文档评 ( a d m i n i s 廿眦i v eb u s i n e s sp r o c e s s )好，实例驱动，过程实例数量较多。审过程。 特定型业务过程流程的结构难以完全精确定义，过程实例 软件项目开发 ( a dh o cb u s i n e s sp r o c e s s ) 执行时可能需要动态调整结构，需要处理 管理过程。 异常情况。 协作型业务过程难以定义过程模型，主要偏重于通讯和信协同设计过程。 ( c o n a b o r a t j v eb u s i n e s s p r o c e s s ) 息共享。 结构化 非结构化 以信息为中心以过程为中心 图1 2 四种业务过程的不同性质 1 3 研究的问题、对象与假设 本文对业务过程调度优化展开研究，为此主要研究解决以下三方面的问题是： 如何建立面向调度执行的具有正确良好逻辑结构的扩展业务过程模型，为后续的过程 调度优化和分析评价研究奠定基础；如何求得业务过程的最优化任务分配调度方 案，使其某些性能指标( 如执行时间、最大生产能力等) 在执行过程中达到最优，并 进行有效性验证；如何实现支撑软件系统，为提出的业务过程调度优化理论、方法 和技术的有效应用提供软件工具的支持。 由于制造企业处理的大多数是属于生产型或管理型业务过程，而且当前大多数业 务过程管理系统( b p m s ) 和工作流管理系统( w f m s ) 也只支持这些类型的业务过 1 绪论 程。因此本文主要研究逻辑结构规范性比较好( 完全可以由w m c 定义的顺序、选 择、并发和循环等四种基本控制结构描述) 的结构化业务过程。 在以上的研究工作中做以下假设： 活动是原子的，即一个活动实例任务的执行需要支持的资源类型不超过1 种，且执行是不可中断的。因为当前大多数b p m s 脚舢s 支持多任务的协同 而不支持多资源的协同 5 3 1 。事实上，如果一个活动不是原子的，那么可以把 这个活动进一步分解成相互协同的多个原子活动。 业务过程中的资源都是独占型的。原因之一是无限共享型资源不会造成资源 冲突，而对于有限共享型资源，可以转化为数量为共享容量的多个独占型资 源；原因之二对于不可更新资源，从活动使用资源的角度来说其作用与可更 新资源的作用是相同的，而资源的调度优化只涉及如何合理地分配使用资 源，因此从资源调度优化的角度来研究，可以不必区分是不可更新资源还是 可更新资源，不可更新资源对业务过程性能的影响主要体现在一旦调度优化 方案确定后其资源补充的模式( 如库存水平的设置、进货的时间间隔数量的 确定等) ，这将是一个库存论的问题，已超出了本文的研究内容。 图1 3 显示了某制造企业的网上订单接收处理过程，它由4 个活动组成，每个活 动需要的资源及对应的处理时间均值标注在其下方，每种资源处理相应的活动实例 任务需要的单位时间服从指数分布，订单( 过程实例) 以一定的速率随机到达。这个 业务过程是一个结构化的、生产型业务过程，业务过程中的活动与资源存在多对多的 支持关系，满足以上的条件与假设。 主管( 2 ) 图1 3 某制造企业的网上订单接收处理过程 浙江大学博士学位论文 现假设开始两份订单的到达时刻分别为0 和2 ，所有资源处理活动实例的随机采 样时间取其均值，两个处理这两份订单的任务分配实例如图1 4 和图1 5 所示，其中 图1 4 采用基于传统共享队列谁有空谁服务的模式，没有采用任务分配优化方法，而 图1 5 采用一定的任务分配优化方法( 基于独立队列模式面向最大处理能力最短执行 时间) ，两个案例中的任务选择规则都采用先来先服务的规则。图1 4 所示的任务分 配案例完成这两份订单的时间需要1 9 个单位时间，图1 5 所示的任务分配案例完成 这两份订单的时间只需要1 5 个单位时间，这两个分配案例说明了不恰当的任务分配 会降低业务过程的执行性能。 图1 4 没有任务分配优化的任务分配实例 图1 5 存在任务分配优化的任务分配实例 1 4 研究现状、发展趋势及存在的主要问题 1 4 1 过程建模的国内外相关研究现状及发展趋势 通过过程建模建立正确合理的业务过程模型是理解业务过程，进行业务过程分析 优化的基础和前提条件。 当前比较成熟的可支持过程建模方法工具主要有：d e f 3 、e e p c e p c 、d f d 、 眦、d s m 等。如：o v i d i us n o r 觚【5 4 1 等对眦和i d e f 在过程建模中的应用进行 了比较分析研究，试图集成过程建模和信息系统建模；砒c 砌om b a s t o s 【5 5 1 等利用 眦的扩展机制对u m l 活动图进行了扩展，以实现对过程的建模；p e t e rl o o s 【5 6 1 等 研究了集成e p c 和眦的过程建模方法；吴雪琴【5 7 1 等研究了基于u m l 的a s p 业 窟 1 绪论 务过程建模，将呲应用到应用服务提供商业务过程建模中，建立起跨越多个企业 的应用服务提供商业务过程模型；关晓光【5 8 】等研究了解释结构建模方法在业务过程建 模中的应用；李锡祚【5 9 】等研究一种结构化的工作流过程建模方法，并给出了相应的过 程建模算法和过程模型分析；这些研究以静态的过程建模方法为研究对象，基本上都 是以图形的方式来描述过程的逻辑工作流程、功能等，具有使用方便简单、建立的模 型易于理解、交流和维护等优点。但这些方法是对动态过程的静态描述，一般只能描 述发生什么( w h a th a p p e n ) 而不能描述如何发生( h o wh 印p e n ) ，也不能描述过程中 各实体、资源的动态随机行为和随机事件，进行“w h a t 扩分析唧】。此外，由于这些 方法本身不提供有效的确保业务过程模型正确性的建模机制、方法或规则，因此在过 程建模中为确保建立的业务过程模型的正确性通常需采用一些事后检测或验证方法 如：基于p e t r i 网及化简技术、化简规则、仿真、过程逻辑、语义推理、矩阵计算、 整数规划、状态空间等方法对建立的业务过程模型进行正确性检验【6 卜7 5 1 。 p a u l r j 【删和k e t t i n g e r f 7 6 1 等认为业务过程仿真( b p s ) 也是一种建模方法与技术， 而且是一种动态的业务过程建模方法与技术，k e t i m1 、l i n a y 【7 7 】等研究了业务过程仿真 建模的基本元素、基本模块；s r n i d u i n o l u 【7 8 】等研究了面向对象的基于离散事件方 法的业务过程仿真建模技术；刘铁铭【7 9 l 等研究了基于工作流的企业过程建模和仿真技 术，介绍了一种将工作流模型转化为集控p e t r i 网来实现企业过程仿真的方法；乔非【8 0 】 等研究了p e t r i 网在企业过程仿真建模中的应用；董志斌、周秋珍、严隽薇引l 【8 2 】等研 究构件化企业过程模型和面向对象的过程仿真建模技术。这些研究基本上都是基于离 散事件方法和p e 仃i 网，因为离散事件方法具有很强的描述能力，而p e 扛i 网具有很强 的数学理论基础；另外，也强调在b p s 中结合使用对象技术。这些建模方法及一些 当前可得的仿真建模软件工具( 如基于离散事件方法的如w i n 旺s s ，触e n a ；基于 p e t r i 网的i c o m e 等) 能在物理层次上动态地模拟业务过程，在业务过程实施前对各 种方案进行定量的分析评价和比较。但它们与当前一些常用的业务过程静态建模工具 之间缺乏有效的集成，使用相对比较复杂，需要较高的技巧( 甚至需要编写计算机代 码) ，可操作性差，通常需专业人员来使用【8 3 1 ，而且用这些方法建立的业务过程模型 也比较专业、抽象，难以理解、交流和维护，模型质量容易受建模者主观因素影响。 此外，当前的这些建模仿真工具都不提供模型的查询和匹配功能，使用这些工具进行 建模仿真时，用户常常会感到每次仿真建模都需要从头再来，都是一次彻底的设计瞰】。 浙江大学博上学位论文 由于实施b p r 项目的技术人员或企业管理者一般不可能都是这方面的专业人员，所 以直接使用这些技术有一定困难，限制了b p s 在b p r 项目中的广泛使用，例如在当 前的b p r 项目中8 0 使用的是静态建模方法工具，这在很大程度上导致了超过5 0 的b p r 项目的失败删。 1 4 2 过程优化的国内外相关研究现状及发展趋势 国内外已有许多学者分别采用图论、排队论等多种方法对工作流过程优化进行 了相关的研究，基于图论的方法如：张晓光【8 5 】等提出了面向工作流过程结构优化的扩 展关键路径来分析工作流过程模型时间性能的方法，孙雪冬【跏8 8 】等研究了基于有向超 图的企业过程结构优化