已阅读5页,还剩61页未读, 继续免费阅读
(计算机应用技术专业论文)新型工作流资源调度器的研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要 伴随着竞争的日益加剧,企业想要在市场中获得优势地位必须考 虑降低生产成本、提高生产效率的问题。在这种需求的驱动下,以实 现业务处理自动化为目的的工作流管理系统应运而生。企业采用工作 流管理系统对自身的信息、业务进行自动化管理,不仅可以使企业的 业务处理流程无纸化,从而缩减了人工的投入,节约了生产成本、提 高了生产效率;而且也可以有效避免手工误操作的发生,从而提高了 企业业务处理的质量。资源调度模块作为工作流管理系统的一个核心 组成部分,负责将企业的资源合理分派到各个业务处理流程( 即工作 项) 上。随着企业业务的不断发展,快速增加的业务量与有限的企业 资源之间的矛盾日益突出。如何让资源进行优化调配从而有效地缓解 这种矛盾就成为了业界研究的一个热点。通过对现有资源调度系统的 研究,本文提出了一种新型的资源调度器。该调度器基于“二阶段调 度”的资源调度框架并结合了“投标一定标”的优化调度方式,从而 在一定程度上提升了资源调度的质量,使得调度系统更灵活、更高效 而且更具柔性。 论文首先简要地回顾了当今工作流研究的热点,重点介绍了资源 调度方面的相关进展。接着,指出了当前工作流资源调度系统中存在 的主要问题,并提出了“二阶段调度”的资源调度框架。然后结合 w f m c ( w o r k f l o wm a n a g e m e n tc o a l i t i o n ) 定义的工作流参考模型, 给出了新型资源调度器的体系结构,并详细地讨论了二阶段调度框架 中的两个子模块:资源发现模块和优化调度模块的相关理论、算法及 其性能评价。最后,本文基于j 2 e e 架构实现了资源调度器,并在一 个模拟的调度案例中进行了实验。实验结果一方面证明了新型资源调 度器的现实可行性及其调度灵活性;另一方面,证明了调度器产生的 调度方案具有实时优化性,从而能有效逼近资源调度问题的全局最优 解。总体上说,该论文不仅是对解决工作流管理系统中资源调度问题 的一种创新,更是对资源调度理论的一次深入探索。 关键词工作流,资源调度,二阶段调度,资源发现,优化调度 a b s t r a c t w i t ht h e i n c r e a s i n gm a r k e tc o m p e t i t i o n ,t h ec o r p o r a t i o n sm u s t c o n s i d e rh o wt or e d u c ec o s ta n du p g r a d et h ew o r ke f f i c i e n c y t os a t i s f y t h ep r a c t i c a ld e m a n d s ,w o r k f l o wm a n a g e m e n ts y s t e m ( w f m s ) w h i c h t a k e sa u t o - t r a n s a c t i o na st a r g e th a se m e r g e d a p p l y i n gw f m st om a n a g e i n f o r m a t i o na n do p e r a t i o n s ,c o r p o r a t i o n sw i l lb ea b l et on o to n l yi n d u c e m a n n a lw o r k sa n du p g r a d ew o r ke f f i c i e n c yb u ta l s oi m p r o v eo p e r a t i o n s q u a l i t yb yr e d u c i n gm i s t a k e sw h i c ha r i s e sf r o mm a n u a lw o r k s r e s o u r c e s c h e d u l i n gm o d u l ei st h ec o l eo ft h ew f m s ,w h i c ht a k e sc h a r g eo f a l l o c a t i n g t h er e s o u r c e si n t oe v e r yw o r ki t e m s w i t hc o r p o r a t i o n s d e v e l o p m e n t 。t h ec o n f l i c tb e t w e e nt h ei n c r e a s i n ga m o u n to ft r a n s a c t i o n a n dt h e1 i m i t e da m o u n to fr e s o u r c e sm a yb em o l ea n dm o r es e r i o u s h o w t oc o n q u e rt h i sc o n f l i c th a sb e c o m et h eh o t s p o t b ys t u d y i n ge x i s t e n t s c h e d u l i n gs y s t e m si nw f m s ,an e wt y p eo f r e s o u r c es c h e d u l i n gs y s t e m w h i c hb a s e so nt w o p h a s es c h e d u l i n gf r a m e w o r ki sp r o p o s e di nt h et h e s i s c o m b i n i n g t h e s c h e d u l i n g m a n n e rw h i c hs i m u l a t e s b i d d i n g - d e t e r m i n i n g p r o c e s s ,t h er e s o u r c es c h e d u l i n gs y s t e mw i l lb ea b l et og e t b e t t e rs c h e d u l ea n db em o r ef l e x i b l ea n de f f i c a c i o u s f i r s t l y , t o d a y s r e s e a r c h h o t s p o t s a b o u tw o r k f l o wa r e b r i e f l y i n t r o d u c e di nt h i st h e s i s t h er e s o u r c es c h e d u l i n gi se s p e c i a l l yd i s c u s s e d t h e nt h es h o r t a g e so ft h e s et r a d i t i o n a ls c h e d u l i n gs y s t e m si sp o i n t e do u t a n dan e wt y p eo fr e s o u r c es c h e d u l i n gf r a m e w o r ki sp r o p o s e dw h i c h b a s e so nt w o p h a s es c h e d u l i n g s e c o n d l y , t h ea r c h i t e c t u r eo ft h er e s o u r c e s c h e d u l i n gs y s t e mw h i c hb a s e so nt h ew o r k f l o wr e f e r e n c e dm o d e li s p r e s e n t e di nt h et h e s i s t h e nt w op a r t so ft h es y s t e m :r e s o u r c e - f i n d i n g m o d u l ea n ds c h e d u l e o p t i m i z i n gm o d u l ea r ed e t a i l e d t h ec o r r e l a t i v e t h e o r i e s ,a l g o r i t h m sa n dp e r f o r m a n c ea r es t u d i e d f i n a l l y , t h er e s o u r c e s c h e d u l i n gs y s t e mw h i c hb a s e so nj 2 e ep l a t f o r mi si m p l e m e n t e da n d t h e e x p e r i m e r i ti sc a r r i e do u t a c c o r d i n gt or e s u l t so ft h ee x p e r i m e n t , i ti s p r o v e dt h a tt h en e wt y p eo fs c h e d u l i n gs y s t e m i sf e a s i b l ea n dt h e s c h e d u l ei so p t i m u n li nr e a l t i m e w h i c ha p p r o a c h e st h eo v e r a l lo p t i m u m s c h e d u l e i nb r i e f , 也et h e s i si sn o to n l yt h ei n n o v a t i o no fr e s o u r c e s c h e d u l i n gs y s t e mi nw f m s b u ta l s ot h ee x p l o r a t i o ni ns c h e d u l i n gt h e o r y k e yw o r d s w o r k f l o w , r e s o u r c e s c h e d u l i n g ,t w o - p h a s es c h e d u l i n g , r e s o u r c e - f i n d i n g ,s c h e d u l e - o p t i m i z i n g i i l 原创性声明 本人声明,所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知,除了论文中特别加以标注和致谢 的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名:样 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定,即:学校 有权保留学位论文,允许学位论文被查阅和借阅;学校可以公布学位 论文的全部或部分内容,可以采用复印、缩印或其它手段保存学位论 文;学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名:垡雌导师签名垃日期:上壁五年也日 硕士学位论文第一章绪论 1 1 课题研究背景 第一章绪论 为了提高服务质量、提升产品水平以及不断降低生产成本,工作流管理系 统已经被广泛地应用在诸如电信、保险、制造、金融、政府机构和银行等许多行 业里。借助工作流管理系统,企业不仅可以将自身信息进行集成,更重要的是它 能将企业的业务流程、业务规则信息化,并使整个业务处理过程自动化。随着企 业业务的不断发展,业务量的激增与企业资源的有限性之间的矛盾开始显现。如 何在现有的条件下最大程度地缓解这种矛盾,就成了业界研究的热点。工作流资 源调度的问题由此提出。 资源调度模块是工作流管理系统中的一个核心模块,它负责为业务流程中 的各个工作项寻找合适的执行资源。对资源调度问题的研究可谓是百家争鸣:不 同的研究组织在开发自己的工作流管理系统时都对其中的资源调度模块进行了 精心设计,以求克服这种业务量与资源量不匹配的矛盾,并由此得到了许多解决 资源调度问题的方法。虽然这些方法都各具特点,但它们也都存在了不少问题。 这些问题或多或少地制约着工作流系统的发展。在这种背景下,本文将对资源调 度问题展开一个深入探讨。 1 2 工作流技术的研究现状 1 2 1 概述 由企业信息化,业务处理自动化催生的工作流技术及其管理系统在世界范 围内得到了广阔的发展。同时,在企业需求的不断推动下,工作流技术的研究在 广度、深度上都得到了长足的进步。作为工作流研究的一个里程碑,一九九三年 八月,国际工作流管理联盟w i m c ( w o r k f l o w m a n a g e m e n t c o a l i t i o n ) 成立了。 该联盟作为一个标准化组织,为了实现不同工作流产品之问的互操作,提出了标 准化的工作流参考模型,并在工作流管理系统的相关术语、体系结构及应用编程 接口( w a p i ) 等方面制定了一系列的标准。基于此标准,世界上许多软件开发 商以及研究机构已经开发出了具有不同特点,不同功能的工作流管理系统。其中 主要包括:美国g e o r g i a 大学计算机系m e t e o r ( m a n a g i n ge n d - t o e n do p e r a t i o n ) 研 究所开发出的,基于c o r b a 的分布式的工作流系统o r b w o r k n l ;m ma l m a d e m 研究中心开发的基于永久消息队列的分布式工作流管理系统e x o t i c a f m q m 硕+ 学位论文 第一章绪论 ( f l o w m a r k o nm e s s a g eq u e u em a n a g e r ) 嘲以及d 鲫h i l o l | 1 1 m 大学计算机系设计的基 于可移动代理的工作流管理系统d a r t f l o w 伽等等。这些各具特色的工作流产品 的推出,标志着工作流的相关研究已经进入了一个高速发展的时期,并推动着企 业生产力的快速提升。为了更详细地讨论工作流技术的发展状况,论文首先介绍 工作流相关的基本概念。 1 2 2 工作流的相关概念 什么是工作流? 工作流管理系统应该具备什么样的特征? 虽然工作流技术 的相关研究已经进行了将近2 0 年了,但是由于对工作流描述的出发点和关注点不 同,业界仍然没有为工作流系统的概念达成一致。下面,本文给出几个有代表性 的工作流定义: ( 1 ) m ma l m a d e nr e s e a r c hc e n t e r 给出的定义“1 工作流是经营过程中的一 种计算机化的表示模型,以及完成整个过程所需用的各种参数集合。这些参数包 括对过程中每一个单独步骤的定义、步骤间的执行顺序、条件以及数据流的建立、 每一步骤由谁负责以及每个活动所需要的应用程序。 ( 2 ) a m i ts h e t h 给出的定义旧工作流是涉及到多任务协调执行的活动,这些 任务分别由不同的处理实体来完成。一项任务定义了需要做的某些工作。它可用 各种形式来进行定义,包括在文件或电子邮件中的文本描述、一张表格、一条消 息以及一个计算机程序。用来执行任务的处理实体可以是人,也可以是计算机系 统。 ( 3 ) w i lv a i l d o r a a l s t 给出定义0 1 工作流是一系列工作的偏序集。 ( 4 ) c i g a rg r o u p 给出的定义啪工作流是经营过程中可运转的部分,包括任 务的顺序以及由谁来执行、支持任务的信息流、评价与控制任务的跟踪、报告机 制。 上述的定义将工作流的一些必要元素描绘了出来,包括工作流流程的定义, 工作流执行的施动者、受动者以及相关的行为规则。作为一个国际标准化组织, 工作流联盟综合各家观点,得到一个折中的工作流概念:工作流是一类能够完 全或者部分自动执行的经营过程,根据一系列过程规则。文档、信息或任务能够 在不同的执行者之间传递、执行。在此基础上,w f m c 进一步提出了工作流管理系 统的概念嗍:将现实世界中企业的业务过程转化为某种计算机化的形式表示,并 在此形式表示的驱动下完成工作流的创建、执行和管理的系统。 讨论了工作流的相关概念后,接下来的一节将对当今工作流技术的发展现状 以及热点做一个简要的介绍。 2 硕士学位论文第一章绪论 1 2 3 工作流技术的研究热点以及发展状况 企业界对工作流管理系统的需求不断地推动着工作流技术的发展。在全球 范围内,工作流相关技术的研究呈现一个不断细化、深化的趋势。从8 0 年代萌芽 时期主要应用于某些特定领域的、相对独立的应用系统到9 0 年代具有底层的通信 基础结构,能够实现任务协作的应用系统,再到如今具备了图形用户界面、过程 定义工具,并将用户定义与任务执行完全分离的应用系统,工作流管理系统经历 了一个从简单到复杂的过程。今天的工作流管理系统不仅性能更加强大、操作更 加人性化而且涉及的技术也日益增多。总体上来看,相关的研究主要体现在如下 几个方面: ( 1 ) 工作流模型方面的研究 工作流模型方面的研究主要集中在模型表达方面。工作流模型是对业务流程 的计算机化描述,概括了实现流程所需的各种必要信息:如流程开始和结束条件、 组成该流程的各个步骤、步骤问的信息传递规则以及所需调用的应用工具等。工 作流模型的表达不仅关系到系统的识别能力而且影响系统的柔性以及拓展性。将 p e t r i 网运用于工作流模型的描述是业界的共识。相关的研究者在此基础上进行了 改进,得到了许多的研究成果。e l l i s 和n u t t 在p e t r i 网的基础上提出了 i c n ( i n f o r m a t i o nc o n t r o ln e t s ) 叫来对工作流过程模型进行描述;文献“”则提出了 采用着色的p e t r i 网来描述过程模型的观点;v a n d e r a a l s t 在p e t r i 网的基础上定义 了w f n c t “”,它通过“变迁”来表示活动,用“库所”来表示活动触发的条件。 除了p e t r i 网,文献o ”用树状结构来表述工作流的过程模型:从根节点开始,业务 过程被逐层地分解为由各级子节点所代表的活动,而活动间的执行则按从左至右 的顺序,逐个分支地进行。同时,a n d d r e a sg e p p e r t 等人也从另一个视角着手, 提出了用代理服务结构来表示工作流模型“”的观点。其理念是;用代理来表示 工作流执行过程中的处理实体、用服务来表示所要执行的活动。代理的行为采用 e c a ( e v e n - c o n d i t i o n - a c t i o n ) 规则来描述。随着工作流系统的应用范围不断拓宽, 为了将不同的工作流模型进行一个统一的抽象,从而解决工作流系统间的模型交 互问题,w f m c 制定了工作流系统的参考模型“”,规范了工作流模型的表达结构 和规则。本文相信,随着研究的不断深入,工作流模型的表达将向一个更高的元 层推进,并呈现出更强的融合性以及交互性。 ( 2 ) 工作流柔性、适应性方面的研究 随着企业的发展,业务过程常常会发生变化,从而导致工作流管理系统的变 更和异常。一个良好的工作流系统必须能够灵活、动态地适应这些变化。工作流 的这种性质就称为柔性或适应性。当前,业界对工作流柔性的研究已经取得了很 大的进展。k a n l n l c r “”详细分析了导致工作流变化的原因。在此基础上将工作流 3 硕士学位论文 第一章绪论 变化影响的范围分成三类:噪音、特殊异常、演进异常,并对每种异常提出了相 应的解决方法。此外还有许多关于提高工作流管理系统柔性的方法“”“”。这里由 于篇幅关系,就不做一一介绍了。 ( 3 ) 工作流安全、认证方面的研究 由于工作流管理系统在企业业务流程管理中起着举足轻重作用,因此其安全 性自然就成为一个关注点。工作流安全性研究起步比较晚,但是也取得了一些成 果其中有:v a l i a 等人基于j a v ar i v l i 和j a v ab e a n s 技术给出了安全工作流管理系统 的j a v a 解决方案“”;w u 讨论了工作流管理中应用数据的访问控制需求并提出了 一个包含了角色、用户组以及数据内容的访问控制以及授权机制。”。这些方案在 很大程度上提升了工作流管理系统的安全性能。 ( 4 ) 工作流底层基础通信结构的研究 在基础通信结构方面,远程过程调用r p c 、面向对象的分布计算环境c o r b a 、 基于t c p i p 的w e b 、各类消息传递系统以及代理系统等均被广泛地运用到了工 作流管理系统中。例如o r b w o r k 就是基于c o r b a 技术开发的工作流产品; w e b w o r k 例则是基于w e b 技术实现的工作流产品;还有基于代理系统的d a r t f l o w 嘲 等等。 ( 5 ) 工作流事务管理方面的研究 工作流事务管理的主要目的是保证工作流系统所处理的业务过程及其任务 执行具有a c i d 特性,即原子性( a t o m i e i t y ) ,一致性( c o n s i s t e n c y ) 、独立性 ( i s o l a t i o n ) 和持续性( d u r a b i l i t y ) ,从而提升工作流系统的可靠性和实用性。事务 管理主要借鉴了数据库事务管理的理论成果,产生了许多的事务控制模型,包括 分支汇合事务模型o “、a c t a 魄1 等等。 上面列举的五个方面是当今工作流主要的研究方向,但这只是一个部分。大 体上讲,工作流的研究存在于工作流管理系统的每一个方面。其中还包括:工作 流时态特性研究、执行服务的研究等等。总的说来,工作流是应企业业务处理自 动化的要求而产生的。只要企业有需求,那么工作流的研究将不断地深入进行。 结合本文主题,接下来的一节重点讨论一下工作流系统中的一类重要问题资 源优化调度问题的相关研究情况。 1 3 工作流系统中资源调度问题的研究进展 资源调度模块作为工作流管理系统的重要组成部分,负责为业务流程中一系 列相互关联的任务分配资源,从而保障各项任务得以按时执行、业务流程得以持 续并最终完成。资源调度的好坏将直接影响到工作流管理系统的工作效率、服务 4 硕士学位论文第一章绪论 质量以及系统的柔性。 工作流资源调度的研究主要集中在优化方面。随着工作流技术的进步以及企 业对工作流产品性能要求的不断提升,资源调度的理论与实现技术都得到了快速 发展。从单资源调度的研究到多资源调度研究,从单纯的数学优化方法到结合了 人工智能等更多学科的优化方法、从单纯的静态调度到适应企业业务过程不断变 化需要的动态调度,工作流的资源调度研究不断地贴近业务的实际需要,向着更 高效,更灵活、更具柔性的方向发展。本文对当今工作流任务调度的研究状况作 了一个简单的总结,主要概括如下: ( 1 ) 基于数学约束满足理论的静态调度方法的研究 众所周知,工作流的调度问题是由于各种客观条件的约束导致的。其中包括 执行时间的约束、资源性能以及数量方面的约束。利用数学方法解决工作流中调 度问题的一般步骤可以归纳为:1 将约束条件用各种方程表示出来,最终得到 一个线性( 或非线性) 方程组。2 根据工作流的需求得到目标函数。3 利用优化 理论采用单纯型法等运筹学方法求解方程组,最终得到资源调度的解,即一系列 的“资源一任务”映射。这方面的研究与约束满足问题的求解结合得比较紧密, 其中主要包括嘲等。基于约束满足理论的方法比较适合对静态的多资源调度问 题进行求解,即在工作流程开始前就通过建立方程来得到最终的资源调度表。但 是对于动态的多资源调度问题,由于约束条件的动态变化性,文献汹1 已经证明了 它是一类n p 完全问题。因此单纯的采用静态约束满足方法来求解动态的多资源 调度问题是不可行的。所以,为了提升工作流管理系统的灵活性,静态的约束满 足解法渐渐被动态调度的研究所替代。 ( 2 ) 基于多学科的动态调度研究 动态资源调度的研究是当今工作流调度的研究重点。简单地讲,动态调度 就是在工作流过程建模的时候不将具体的任务与具体的资源进行绑定,而是绑定 任务对资源的描述,直到任务实际运行的时候再结合资源使用情况,安排最合适 的资源来执行相应的任务。这种方法可以有效地提高工作流资源调度的灵活性以 及适应性。 工作流管理系统的动态调度在实现方案上主要有两种:首先是结合了策略 的实现方案,即基于策略的资源调度。策略是对资源调度行为的指导规则的集合, 主要表示为“条件一操作”的二元组形式。调度时主要依据策略的描述来完成 资源的分配过程。文献提出了资源调度的三种策略:需求策略、资格策略以及 替换策略。当任务提出资源需求时,工作流引擎通过策略匹配得到满足条件的调 度策略,然后结合类s q l i 询语句r q l 啪1 得到最终的资源分配结果。文献 嘲在此基础上增加了情景策略以及优先策略并结合重写技术从而提高了资源调 5 硕士学位论文 第一章绪论 度的柔性。第二种动态调度的实现方法是基于仿真技术的方法。这类方法的特点 是a g e n t 的应用。即对资源调度的各个阶段中所用到的规则、方法、决策过程进 行封装得到若干个a g e n t ,然后将资源的调度交f l a a g e n t 进行全权处理。文献矧 提出了资源分配器a g e n t 。该a g e n t 能自主地将系统资源进行静态和动态的分配, 并将分配的结果通过路由器传递给工作流引擎代理,并在该代理中将特定的资源 分配到特定的工作项上。文献1 也提出了新的观点:利用a g e n t 来协调工作流系 统中多工作流程( 或案例) 同时进行而导致的抢占公共资源的问题。 与此同时,在工作流资源调度的方案制定方面也存在着许多的研究热点,其 中包括:( 1 ) 利用遗传算法来得到优化的资源调度方案。”嘲嘲。遗传算法是一种 搜索算法,通过对表示调度优化问题候补解的“染色体群”中的“染色体”进行 选择、复制、交叉和变异等一系列操作最终得到最适合客观环境的一个染色体, 即一个最优的调度方案。( 2 ) 利用基于规则的启发式算法来得到资源的优化调度 方案。规则是表示在进行调度时需要遵守的法则。资源调度只有按照这些规 则进行调度才能被认为是合乎要求的。活动的调度规则有很多,较常见的有f c f s 等,文献“1 做了个调度规则的总结。根据给定的规则,启发算法通过对调度的所 有可能进行“预测”,并对“预测”结果进行筛选,最终得到一个最接近调度目 标调度方案。 1 4 论文研究的目的与意义 随着工作流管理系统被广泛地运用于各个行业,同时各行业对各自工作流 系统的要求日益提高,如何开发出灵活高效、高适应性、高可靠度的工作流管理 系统就成了相关研究的重点。资源调度系统是工作流管理系统下的一个重要子模 块,负责为案例中的任务寻找并分配资源,使得任务得以完成,从而推进整个案 例的执行。工作流调度系统的好坏直接影响着整个管理系统的效率、灵活性以及 服务质量。总的来讲,当今的诸多工作流调度系统或多或少的存在着一些问题, 主要表现在: ( 1 ) 灵活性差 灵活性的问题主要体现在调度的动态性上。由于企业的业务过程、资源状 况等客观条件并不是一成不变的。在静态调度中,资源调度方案在案例执行过程 开始前就已经完成了。这样一来,调度过程就不能即时地适应调度环境的变化, 进而引导调度方案进行相应地改变,容易造成调度系统的“僵硬” a t lo 这种“僵 硬”很可能造成业务流程的意外中断从而影响整个调度系统中其他案例的执行。 提高资源调度的灵活性是关系到整个工作流系统适应性的一个重要环节。 6 硕士学位论文第一章绪论 ( 2 ) 整体服务质量不高 工作流管理系统是为企业业务服务的,而资源调度模块则主要负责为业务 流程中的所有任务寻找合适的资源以供执行。资源选择的好坏直接影响到业务的 完成质量。当今的工作流管理系统大多采用单一的调度评判规则:要么单纯从资 源的角度出发来评判调度的好坏,要么单纯从任务的角度出发。从而使得调度系 统的整体服务质量向某个方面倾斜。例如,单纯从资源的角度出发,以系统的资 源利用率作为调度质量的唯一评判标准。那么系统很有可能为了提高资源的利用 率而将不“胜任”某个任务的资源分配给该任务,从而造成该任务得不到“满意” 的服务,最终影响了系统的整体服务质量。 ( 3 ) 模块可重用性不强 扩展性是组件重用方面的重要指标。一个健壮的工作流调度系统能容易地随 着业务流程、资源状况以及评价规则的变化而改变,并应用于新的业务过程。现 在的大多数工作流调度系统把资源调度和过程模型紧密地结合起来,这在很大的 程度上牺牲了调度系统的独立性和重用性。如果过程模型、评价规则过多地渗透 到调度系统中,那么当业务流程、评价体系发生改变时,调度模型、算法将很可 能都必须重新构造。这种情况无疑增加了企业的成本。所以,一个重用性高的资 源调度组件是工作流管理系统好坏的重要标准。 ( 4 ) 调度方案的制定速度慢 资源调度方案制定的速度问题一度被忽视。如今大家都在研究如何优化调度 方案,从而使得各种优化过程十分的复杂,为了找到一个方案而花费过多的时间; 同时当业务量巨大的时候,资源的调度将更耗时。众所周知,调度系统的动态性 需要通过减少系统的响应时问来体现。如果资源调度速度很慢,那么当所谓的“优 化”方案被制定出来时它很可能在新的环境中已经不再是优化的了。所以,提高 资源调度的速度应该得到更多的重视。 以上几条是本文总结出的当今工作流调度系统中或多或少存在的问题。为 此,本文在工作流参考模型的基础上提出了一个新型的资源调度框架,并深入讨 论了该框架下的调度方式和实现方法。这些讨论的创新点主要体现在; ( 1 ) 提出了“二阶段调度”的整体调度框架。“二阶段调度”将整个工作流 调度过程分成了资源发现和优化调度两个阶段。这样做的好处是:将优化调度和 资源发现相分离,提高了调度模块的可重用性;另一个方面,资源发现为优化调 度缩小了资源考察的范围,而不象现在的调度系统那样对所有的系统资源都进行 搜索,从而在很大程度上提高了调度方案制定的速度。 ( 2 ) 提出了基于“投标一定标”的优化调度方式。在资源调度模块中,本文 模拟了招标过程,提出了“投标一定标”的资源调度方式。该调度方式引入了竞 7 硕士学位论文第一章绪论 争机制,通过变换调度过程中的决策主体来得到一个“资源”和“任务”都认可 的调度方案。这种方案是一种均衡的方案,它避免了单纯从资源或从任务出发来 衡量调度好坏的片面性,从而提升了系统的整体调度质量。 ( 3 ) 构造了相关的启发函数。本文首先通过分析,尽可能多地归纳出影响调 度质量的因素。然后将这些影响因素以加权的形式构造出引导资源调度的启发函 数。这样一来,本文所构造的调度系统将更全面,同时用户可以通过自行配置影 响因素的权重来得到不同的调度标准,从而提高了调度系统的适应性。 以上三点都是首次提出的观点。此外,本文在资源发现模块中还引入了策略 系统,用以提升调度的灵活性;采用了动态触发的机制提升了调度系统的动态性。 以上措施不但在很大程度上提高了整个调度系统的效率、质量而且使得调度系统 的可重用性,灵活性得到提升。 1 5 论文结构安排 论文将按照下面的顺序进行编排:第二章结合工作流管理联盟提出的工作 流参考模型,提出了工作流资源调度器的“二阶段调度”框架。第三章详细地讨 论了资源调度的第一个模块:资源发现模块的原理,实现技术。第四章介绍了基 于“投标一定标”的优化调度模块的原理,调度流程,并分析了影响资源调度性 能的因子,构造了启发函数,给出了相关的调度算法。第五章将结合前三章的内 容,基于j 2 e e 平台设计并实现了新型资源调度器,并对该调度器进行了实验。 通过对实验结果的分析,本文证明了新型资源调度器的现实可行性以及调度结果 的优化性。最后一章对整个论文做了总结并对今后的研究进行了展望。 硕士学位论文 第二章调度框架设计 2 1 引言 第二章调度框架设计 上一章简要地介绍了工作流领域相关的研究进展、总结了当前工作流调度系 统中存在的一些不足。为了改进这些缺陷,本章在工作流参考模型的基础上提出 了一个新型的资源调度框架:“二阶段调度”框架。该框架基于“资源发现优 化调度”的二阶段调度过程。它能有效地提升资源调度的速度、提高调度系统的 灵活性并有利于调度组件的重构。接下来,将对该框架进行探讨。 2 2 工作流参考模型 从上一章可知,不同的研究机构对工作流模型的研究导致了工作流模型千差 万别。在信息整合,资源共享成为主流的今天,为了实现工作流技术的标准化和 开放性使得不同的工作流管理系统之间能够进行信息交换和协作, w f m c 提出了 一个共同的“参考模型”即工作流参考模型“”( 图2 - 1 ) 。该模型明确了工作流管 理系统的特性、术语以及各个功能组件,使得工作流管理系统的开发有了一个统 一的标准。由于本文所设计的资源调度系统是整个工作流管理系统的有机组成部 分,因此它也必须符合工作流参考模型的规范。下面,简要地介绍一下该模型的 主要接口和部件。 图2 - 1 工作流参考模型 根据图2 1 并参考相关文献“”可知:工作流参考模型包括五个基本组件和五 个基本接口。其中,五个组件的功能分别如下: 9 硕七学位论文 第二章调度框架设计 ( 1 ) 工作流执行服务。它为系统提供执行时服务,是工作流管理系统的核心, 由一个或多个工作流引擎组成。工作流引擎是一个为工作流实例的执行提供运行 服务环境的软件,是工作流执行服务的核心。 ( 2 ) 过程定义工具。它主要负责分析、建模、描述业务过程以及对业务过程 的建档,给出工作流程的定义,并以一定的数据格式提供给工作流引擎解释。 ( 3 ) 工作流管理工具。它负责对工作流的流动状况进行监视,并提供一系列 管理功能,实现安全性、过程控制和授权操作等方面的管理。 ( 4 ) 3 - 作流客户应用。它由用户操作和工作流任务表管理器共同完成。工作 流任务表是指分配给一个特定用户( 或一组用户) 处理的,由任务项组成的队列。 工作流任务表管理器是一个软件模块,负责管理工作流任务表,并完成与最终用 户操作的交互。 ( 5 ) 应用程序。它是指提供了工作流引擎接口的应用程序,可以是本地的应 用,也可以是远程的应用。 模型中的五个接口分别是: ( 1 ) 接口1 为在不同物理或电子介质之间传递过程定义的信息提供了交互的 形式和a pi 调用; ( 2 ) 接d 2 定义了通信建立、工作流定义操作等功能; ( 3 ) 接i ;3 3 激活应用程序的a pi 函数应覆盖的几个方面的功能; ( 4 ) 接e 1 4 完成工作流执行服务之间需要提供大量的w a p i 来实现互操作,无 论是在两个工作流执行服务之间的直接调用还是通过网关函数; ( 5 ) 接e 1 5 主要实现对工作流的管理和监视。 2 3 “二阶段调度”框架设计 工作流资源调度的目的是为每个案例中的任务( 即工作项,以下同) 寻找合 适的资源供其执行,从而推动该案例的最终完成。结合上一节所介绍的工作流参 考模型可知;资源调度属于工作流执行服务中的一项功能。为了提升工作流系统 的构件重用性,本文将资源调度的功能独立出来成为一个单一组件。该组件称为 工作流资源调度器。与此同时,本文对工作流资源调度过程进行了分析,发现它 的流程总体上包含两个部分:找到满足任务申请的资源以及从这些资源中找到最 优的一个分配给提出申请的当前任务。为此,本文提出了工作流资源调度的“二 阶段调度”框架。 定义2 1 本文将“二阶段调度”框架定义为:将资源调度分割为资源发现 以及优化调度两个有序阶段的操作框架。 1 0 硕士学位论文 第二章调度框架设计 在此基础上,本文也根据功能的不同将工作流资源调度系统器划分成两个大 的模块:资源发现模块和优化调度模块。为了对资源调度器有一个整体的认识, 下图( 图2 2 ) 按层次给出了调度器及其周边组件的整体结构: 图2 - 2 资源调度器整体结构 从图2 2 我们知道,资源调度器主要与工作流管理系统中的过程定义工具以 及工作流管理工具交互。当客户定义了一个案例的工作流程之后,相关的工作流 引擎将根据过程定义部件定义的业务流程顺序不断地向资源调度器提出资源申 请,触发资源调度器工作。而工作流管理工具则对资源调度器运行状态的进行监 视。当业务执行发生意外情况时,管理工具可以向资源调度器重新发送资源请求, 从而提高系统的柔性。下面本文就资源调度器的内部组件进行一个简要的说明: ( 1 ) 资源发现模块 资源发现模块的主要职责是从资源数据库中找到所有满足资源申请要求的 资源,从而为接下来的优化调度做好准备。在本文的设计中,资源的发现使用了 策略驱动的方式,即该模块接收来自案例任务发过来的资源申请,然后根据申请 的格式,从策略库中寻找匹配的策略表达式并生成相应的s q l 查询语句。最后, 模块根据该s q l 查询语句对资源数据库进行搜索,找到所有满足需求的资源 ( 组) ,并将该资源( 组) 发往优化调度模块进行下一步的调度。从上面的描述 不难看到,资源发现是调度的第一阶段,它通过策略驱动不仅克服了以往非策略 驱动方式所带来的灵活性不足的问题;另一个方面,它为优化调度模块进行了一 硕士学位论文 第二章调度框架设计 次初选,缩小了优化调度需要考察的资源范围,在一定程度上提高了系统的性能。 ( 2 ) 优化调度模块 该模块的任务是对资源发现模块得到的资源( 组) 进行考察,最终得到一个 最优的资源从而生成一个“资源一任务”映射并将其放入工单数据库,指导工作 流管理系统的运行。如何对资源( 组) 进行考察是优化调度的一个重点。众所周 知,在以前的工作流管理系统中由于调度评价标准的出发点单一而导致了总体调 度质量不高。为了克服这个缺陷,本文在新型资源调度系统中创新性地提出了模 仿“投标一定标”的调度方式,使用资源满意度和任务满意度两个评价体系来共 同评价和指导工作流资源的调度。相应地,在优化调度模块中又形成了两个相互 独立的子模块:“任务排序”模块和“资源选择”模块。“任务排序”予模块中, 资源作为调度评判的主体。每个资源根据最能发挥其性能的顺序来执行其任务队 列中的任务。这样一来,当前提出资源申请的任务就可以推算出它在该资源中的 预计等待时间。接下来,在“资源选择”子模块中,当前任务将根据在任务排序 中得到的预计等待时间并结合其他的一些评价因素,从资源( 组) 中选择其最满 意的资源。经过“任务排序”和“资源选择”两个步骤,调度器最终得到了一个 综合满意度最高的调度方案,并以“资源一任务”映射的形式存储于工单库中。 在新的资源调度器里,每个任务发起的一条资源申请都将导致一系列的调度 操作。整个资源调度过程通过时序图的形式表示如下( 图2 3 ) : 图2 - 3 资源调度时序图 注:时序图中r e s o u r c e f i n d e r 表示资源发现模块实体,p o l i c y b 嬲e 表示资源 1 2 硕士学位论文第二章调度框架设计 发现策略库,r e s o u r c e s c h e d u l e 表示优化调度模块实体,t a s k 表示发出资源申请 的当前任务;f i n d r e s o u r c e g r o u p ( ) 表示调度器根据资源发现策略产生的s o l 语句 从资源库中搜寻所有满足要求的资源组的操作,t a s k q u e u e ( ) 表示“任务排序” 子模块进行的操作,r e s o u r c e s e l e c t 0 表示“资源选择”子模块所进行的操作。 这些操作将在后面章节中进行深入的讨论。 2 4 “二阶段调度”框架的特点 上面两节结合工作流参考模型详细讨论了基于“二阶段调度”的资源调度整 体框架及其资源调度过程,下面就这种调度框架的特点做个总结,从而体现本文 提出的新型资源调度器的优点: ( 1 ) “二阶段调度”框架把资源发现模块独立出来并利用发现策略来进行资 源发现的操作从而使得调度系统拥有更加灵活的资源搜索能力。 以往的工作流资源调度系统采取的是“固定资源划分”的方法,即资源类的 划分是固定的( 例如很多系统是根据角色和组织进行资源分类) 。但事实上,随 着业务变更的需要,资源的分类方法可能是多样且可变的;同时,为了满足任务 对资源需求的多样性,资源的描述形式也应该是可变的。因此,如果资源调度系 统中任务的资源申请只能固定地按照某几个资源类来提出,那么该调度系统的资 源搜索是“僵化”的:一旦资源需求的形式或者资源划分的标准发生变化,该资 源调度系统将不能满足新的资源申请的需求。本文通过采用策略的形式来表达任 务提出的资源申请就可以解决这个问题。策略存储于策略库中。使用者不但可以 对资源发现策略进行查、删、改的操作来满足现实的资源申请方式的变更需要而 且也可以依据现有的资源分类规则来构造新的资源发现策略,从而提高了资源调 度系统搜索资源的灵活性。 ( 2 ) 。二阶段调度”框架将优化调度模块独立出来,从而使得调度系统专注 于提升资源的整体调度性能。 资源调度系统通过资源发现模块可以找到所有满足申请要求的资源。这些资 源都能用来执行提出申请的任务。如何对这些资源进行进一步选择就涉及到一个 优化的问题:如何使系统调度的整体性能最优。优化调度模块就负责这个方面的 工作。从上面的体系结构图可知,优化调度模块由“任务排序”和“资源选择” 两个连续的步骤构成。这两个过程分别从资源和任务两个角度来均衡调度系统的 整体调度性能,从而克服了以往资源调度系统中评价主体单一所带来的整体调度 性能单方面倾斜的缺陷。 ( 3 ) “二阶段调度”框架可以更方便地为系统进行重构和扩展。 1 3 硕士学位论文第二章调度框架设计 从上面的讨论可知,资源发现模块和优化调度模块在工作流管理系统的资源 调度过程中是作为一个有机体而出现的,但从结构以及功能上来看,这两个模块 又是相互独立。这种独立性对于我们进行系统重构以及扩展是十分有利的。拿资 源发现模块来说,作为一个独立的模块,它提供的功能是根据策略找到满足要求 的资源或是资源组。很显然,在本文所提出的资源调度系统中,它为优化调度进
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 预防跌倒坠床的护理完整版
- 支护锚喷工岗位学习应用考核试卷含答案
- 超重型汽车列车挂车工岗前综合专业考核试卷含答案
- 紫胶漂白工安全意识强化模拟考核试卷含答案
- 钎焊工安全生产基础知识能力考核试卷含答案
- 老年人心理护理全套教学课件
- 2026年马鞍山职业技术学院高职单招笔试职业适应性测验历年参考题库含答案解析
- 2026年青岛职业技术学院高职单招笔试语文历年参考题库含答案解析
- 2026年阜阳职业技术学院高职单招笔试语文历年参考题库含答案解析
- 海藻制醇工成果转化竞赛考核试卷含答案
- 2026福建福州旗山供水有限公司招聘2人考试模拟试题及答案解析
- 北京市朝阳区2026-2027学年度第一学期期中质量检测高三英语试卷(含答案)
- 2026山东省防疫安全协管员招聘考试(畜牧兽医)历年参考题库含答案详解
- 2026健康管理师考试理论知识真题及答案
- 2025 含聚谷氨酸有机水溶肥料在马铃薯种植中的应用技术规程
- 2026-2027学年清华附中九年级上册化学期中真题卷
- 2026年四川省成都市技能人才评价考评员考试题库(附答案)
- 正大集团人才评估行测题目
- 离散数学 (第七版) 课件 第二部分 集合论
- FMEA风险评估分析表实战培训
- 2025年进出口银行人员招聘笔试考试试题及答案详解
评论
0/150
提交评论