（计算机应用技术专业论文）基于soa的流水作业分布式优化方法.pdf

东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 盎垒篮 日期： 超堡垒鲴坦目 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相 一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括以电子信息形式刊登) 论文的全部内容或中、英文摘要等部分内容。论文的公布( 包括以电子信息形式刊登) 授权东南大 学研究生院办理。 研究生签名：越导师签名：研究生签名：主錾型堕导师签名：日期：塑丝：竺：! 乡 摘要 摘要 车间流水作业调度问题是生产、调度领域的一个热点、难点，是许多实际生产调度问题的典型 调度简化模型。总完工时间是一个重要的衡量指标，它的最小化能有效提高设备利用率、缩短生产 周期、降低成本。最小化总完工时间流水作业调度问题是一类典型的n p 难问题，对它的研究具有 重要的理论意义和应用价值。 本文利用面向服务的架构s o a 的分布式计算的思想，将调度算法基本运算步封装成服务并部署 到分布式计算资源上，客户端通过访问这些服务完成调度算法的服务计算过程。w e b 服务的响应时 间是影响w e b 服务访问的重要因素，通过实验分析出调用w e b 服务的开销主要在于s o a p 消息解析 时间以及初始化w e b 服务的时间。结合资源池模式和缓存模式，提出基于服务缓冲池的调度算法， 通过缓存w e b 服务的链接，减少w e b 服务的初始化次数，降低w e b 服务的初始化开销，缩短w e b 服务的响应时间。实验分析计算资源数对算法性能的影响，确定出分布式环境下大规模组合优化问 题的有效资源数。基于t a i l l a r d 标准测试实例，将该算法与集中式算法以及不加入缓存机制的分布式 算法进行比较，实验结果表明，本文提出的具有缓存机制的分布式计算方法比集中式算法效率更高， 且比不加入缓存机制分布式算法能更快地访问w e b 服务。 本文设计并实现基于s o a 的分布式算法原型系统，测试了不同的调度实例，给出了相应的甘特 图、展现了所提出的基于服务缓冲池的调度算法的有效性和实用性。 关键词：流水作业调度，s o a ，响应时间，服务缓冲池 a b s t r a c t a b s t r a c t f l o w s h o ps c h e d u l i n gp r o b l e mi s o n eo ft h em o s td i f 五c u l tp r o b l e m si nt h ef i e l do fp r o d u c t i o n s c h e d u l i n g ，w h i c hi sas i m p l i f i e dm o d e lo fm a n yp r a c t i c a lp r o d u c t i o ns c h e d u l i n gp r o b l e m s t o t a lf l o w t i m e i sa l li m p o r t a n tp e r f o r m a n c em e a s u r ei np r a c t i c e m i n i m i z i n gt h et o t a lf l o w t i m ec a l li m p r o v et h er e s o u r c e u t i l i z a t i o n ，s h o r t e nt h ep r o d u c t i o nc y c l ea n dr e d u c et h ec o s t t h ef l o w s h o ps c h e d u l i n gp r o b l e mw i t ht h e o b j e c t i v eo f t h et o t a lf l o w t i m em i n i m i z a t i o ni saw e l l - k n o w nn p h a r dp r o b l e m b ya d o p t i n gt h ed i s t r i b u t e dc o m p u t i n gf r a m e w o r ks o a t ot h ec o n s i d e r e dp r o b l e m ，b a s i co p e r a t o r so f t h ep r o p o s e ds c h e d u l i n ga l g o r i t h ma r ee n c a p s u l a t e di n t os e r v i c e sa n dd e p l o y e do nd i s t r i b u t e ds y s t e m s c l i e n t sc a l la c c e s st h e s es e r v i c e st oc o m p l e t et h es c h e d u l i n gp r o c e s s e s r e s p o n s et i m eo fw e bs e r v i c e si s c r u c i a lt ot h ep e r f o r m a n c eo fc o o p e r a t i v es e r v i c e s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h es o a pm e s s a g e p a r s i n gt i m ea n dt h ei n i t i a ls e r v i c ea c c e s s i n gt i m ea r et h em a j o rt i m eo v e r h e a do f t h ew e bs e r v i c ec a l l i n g t od e c r e a s et h et i m ec o n s u m i n g ，s b p ( s e r v i c eb u f f e r i n gp o o lb a s e ds c h e d u l i n ga l g o r i t h m ) i sp r o p o s e db y i n t e g r a t i n gar e s o u r c ep o o lw i t hac a c h e b yc a c h i n gw e bs e r v i c e sl i n k , t h en u m b e ro fi n i t i a l i z i n gw e b s e r v i c ec a nb er e d u c e d a sw e l l ，t h ei n i t i a l i z a t i o nc o s ta n dt h er e s p o n s et i m eo fw e bs e r v i c e sc a nb e s h o r t e n e x p e r i m e n t a la n a l y s i s o fi n f l u e n c eo nt h ea l g o r i t h mp e r f o r m a n c e ，a na p p r o p r i a t en u m b e ro f c o m p u t i n gr e s o u r c e sc a nb ed e t e r m i n e df o rl a r g e s c a l eo p t i m i z a t i o np r o b l e m s 1 1 1 ep r o p o s e da l g o r i t h mi s t e s t e do nw e l l k n o w nt a i l l a r db e n c h m a r ki n s t a n c e sa n dc o m p a r e dw i t hac e n t r a l i z e da l g o r i t h ma n da d i s t r i b u t e da l g o r i t h mw i t h o u tc a c h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi sm o r e e f f i c i e n tt h a nt h ec e n t r a l i z e da l g o r i t h m ，a n dh a sal o w e ro v e r h e a dt h a nt h ed i s t r i b u t e da l g o r i t h mw i t h o u t c a c h e as o a - b a s e dd i s t r i b u t e da l g o r i t h mp r o t o t y p es y s t e mi sd e s i g n e da n di m p l e m e n t e dt ov e r i f yt h e e f f e c t i v e n e s sa n da p p l i c a b i l i t yo ft h es b pa l g o r i t h mp r o p o s e di nt h i st h e s i s b yi n p u t t i n gd i f f e r e n t s c h e d u l i n gc a s e s ，t h ec o r r e s p o n d i n gg a n t tc h a r t sa r ed i s p l a y e db yt h ep r o t o t y p es y s t e mt od e m o n s t r a t et h e c o r r e c t n e s sa n df e a s i b i l i t yo ft h ep r o p o s e da l g o r i t h m k e y w o r d s ：f l o ws h o ps c h e d u l i n g ，s o a ，r e s p o n s et i m e ，s e r v i c eb u f f e r i n gp o o l i i 目录 目录 摘要i a b s t r a c t i i 目录i i i 第1 章 绪论1 1 1 研究背景l 1 1 1s o a 架构及其思想概述l 1 1 2w e b 服务概述3 1 】3w e b 服务实现方式5 1 2 流水作业调度问题7 1 2 1 问题简介7 1 2 2 问题描述8 1 2 3 国内外研究现状8 1 3 课题来源和主要研究内容9 1 3 1 课题来源9 1 3 2 主要研究内容9 1 4 论文组织结构1 0 第2 章基于s o a 的任务分配1 1 2 1 调度算法的并行性1 l 2 1 1 局部搜索算法1 l 2 1 2 邻域变换策略1 2 2 1 3 启发式搜索算法的并行特性1 3 2 2 运算步的服务封装。1 4 2 3w e b 服务调用时间分析1 5 2 3 1s o a p 消息解析1 5 2 3 2w e b 服务初始化1 6 2 4 任务的静态和动态负载均衡1 6 2 4 1 导致负载不平衡的原因1 7 2 4 2 影响动态负载平衡效能的因素1 7 2 4 3 确定负载平衡的粒度1 8 第3 章基于服务缓冲池的调度算法1 9 3 1 基于w e b 服务的调度算法1 9 3 2 缓存服务算法2 l 3 3 算法实验结果分析2 2 第4 章基于s o a 的分布式算法原型系统的设计和实现2 5 4 1 系统体系架构：2 5 4 2 系统实验平台2 5 4 3 系统运行结果2 6 i i i 目录 第5 章结论3 0 j 2 疋谢31 参考文献3 2 附录3 4 攻读硕士学位期间发表的学术论文3 8 i v 第1 章绪论 第1 章绪论 1 1 研究背景 调度在制造、信息和服务业的决策过程中起关键作用，其实质是利用一些资源( 处 理机、机器、服务等等) 在满足指定约束条件下最优地完成给定作业( 工件、工序、活 动或任务) ，达到目标函数( 最长完工时间、总完工时间、成本、利润、机器利用率等 等) 最小或最大。流水作业调度( f l o ws h o ps c h e d u l i n g ) 是其中一类重要的生产系统【l 】【2 】， 它可以描述为n 个工艺路线完全相同的作业在m 台设备上加工。流水作业调度问题广泛 存在于批量生产企业的流水线车间、多处理机等系统：总完工时间是流水作业排序问题 重要的性能指标，可以促使资源稳定有效地利用、作业的快速周转和在制品库存最小【3 1 ， 所以目前通常选取总完工时间为优化目标。g r a y 等【4 】已经证明最小化总完工时间流水作 业调度问题( 根据文献【1 】可记为f m p r m uf 乏：c ，) 是n p 难问题，多年来一直引起国 内外大量学者的广泛关注，目前仍然为调度领域的一个研究热点。 这些年来，国内外已经提出了很多的复合启发式算法来解决f mlp r m ui 罗c ，f - j 题， 然而这些算法基本上是采用扩大搜索范围来提高算法性能( e f f e c t i v e n e s s ) ，但同时也降 低了算法效率( e f f i c i e n c y ) 。如何在保证算法性能高的前提下大幅度缩短计算时间、提 高算法效率一直难以解决，根本原因在于目前的求解方法基本采用集中式计算，多数在 单台机器上运行，其缺点是对于规模稍大的问题运行时间较长。虽然目前计算机的速度 在不断提高，但这种提高相对于问题的复杂性而言毕竟很有限。 分布式计算是求解复杂问题的有效方法，传统方法是将复杂问题分解为多个子问题 进行分布处理，子问题的解汇集为原问题的解；然而，f m ip r m ui 罗c ，调度问题不能 分解为规模更小的子问题。因此，不能用传统方法分解问题，只能寻求算法本身的分解， 即将求解问题方法的基本运算步并行化并分摊到多个计算资源上并行执行，然后汇集各 个计算资源上的解。同时，传统的实现技术难以实现这种分布处理过程，新出现的基于 s o a ( s e r v i c e o r i e n t e da r c h i t e c t u r e ) 的服务计算s o c 5 】1 6 】( s e r v i c e o r i e n t e dc o m p u t i n g ) 为该问题提供了技术保障，可将分解后的计算分布到多个服务( s e r v i c e s ) 上去执行。 通过分解问题的求解方法而不是分解问题本身、实现基本运算步的并行化是一个崭 新的复杂问题求解方法；基于s o a 的服务计算模式为这种方法的具体实现提供技术支 持和保障。 1 1 1s o a 架构及其思想概述 ( 1 ) s o a 的基本思想 目前面向服务的编程，由于服务组件可以和各种传输协议自由绑定。这样作为服务 的消费者，就不需要特别关心服务提供者的具体的技术细节，只需要知道有这么一个完 全和技术无关的业务接口，称为“服务接口”。作为客户，不需要去理解这到底是w e b 东南大学硕士学位论文 s e r v i c e 的接口，还是e j b 的接口等。这个接口，只和业务相关，而和技术无关。 s o a 正是以服务为导向的架构。而s o a 和w e bs e r v i c e 的区别在于：s o a 是在w e b s e r v i c e 的基础上发展起来的；而w e bs e r v i c e 实现了松散耦合的服务和粗粒度的服务。 但是w e bs e r v i c e 本质上只是一个服务组件，因而它需要运行于一个特定的应用服务器 上。w e bs e r v i c e 服务组件的实现也是和应用服务器紧密相关的，是和应用程序紧密相 关的。客户端如果调用w e bs e r v i c e 组件时，需要知道应用服务器的位置和具体的传输 协议，尽管w e bs e r v i c e 采用了标准的s o a p 传输协议。这样一旦应用服务器的位置或 者传输协议发生改变时，相应的客户端调用程序也需要做相应的修改。 s o a 是为软件集成而服务的，它实现了技术和架构的完全分离，消除了软件服务集 成的所有障碍。s o a 使得软件集成不必受任何标准的限制，使得s o a 可以集成任何标 准的软件服务。不管服务组件采用的是n e t 、j 2 e e ，还是w e bs e r v i c e ；不管是基于 h t t p s o a p 的传输协议，还是基于j m s ，都可以通过s o a 架构进行集成。w e bs e r v i c e 由于其支持s o a p 和h t t p 的传输协议，已经成为主流的标准服务组件。 s o a 的服务的理念思想，本质上是一种业务和技术的完全分离，业务又能和技术资 源组合的思想。它达到了目前软件设计思想的最高境界。s o a 的出现，预示着一个以服 务为导向的新的i t 时代的到来。 ( 2 ) s o a 架构 w e bs e r v i c e s 的体系结构面向服务的体系结构( s o a ) ，如图1 1 所示。 作： w s d 图1 - 1w e b 服务体系结构 从图中可以看出，s o a 结构【8 】共有3 种角色： 服务提供者：发布自己的服务，并且对服务请求进行响应。 服务注册中心：注册已发布的w e bs e r v i c e s ，对其进行分类，并提供搜索服务。 服务请求者：利用服务注册中心查找所需的服务，然后使用该服务。 s o a 体系结构中的组件必须具有上述一种或多种角色，这些角色之间使用三种操 发布操作：使服务提供者可以向服务注册中心注册自己的功能及访问接口。 查找操作：使服务请求者可以通过服务注册中心查找特定种类的服务。 绑定操作：使服务请求者能够真正使用服务提供者提供的服务。 由此可见，服务描述和服务实现是分离的，这使得服务请求者可以在服务提供者的 2 第1 章绪论 一个具体实现正处于开发阶段、部署阶段或完成阶段时，对具体实现进行绑定。另外， s o a 中的组件之间必须能够进行交互，才能进行上述三种操作。所以w e bs e r v i c e s 中的 体系结构的另一个基本原则就是使用标准的技术，包括服务描述、通信协议以及数据格 式等，因此，开发者就可以开发出平台独立、编程语言独立的w e bs e r v i c e s ，从而能够 充分利用现有的软硬件资源和人力资源。 另外，s o a 体系结构没有对w e bs e r v i c e s 的粒度进行限制，因此一个w e bs e r v i c e 既可以是一个组件( 小粒度) ，也可以是一个应用程序( 大粒度) 。 1 1 2w e b 服务概述 ( 1 ) w e b 服务的主要功能及特点 w e b 服务是种部署在w e b 上的对象或者组件，简单来说，w e bs e r v i c e s 就是一个 向外界暴露出的能够通过i n t e m e t 调用的a p i 或者说应用程序。w e b 服务提供了一种分 布式的计算技术。对于外部w e b 服务使用者而言，w e b 服务是一种部署在w e b 上的对 象或者组件，它们具有良好的封装性、松散耦合性、跨平台等特性。w e b 服务可以大大 减少e a i ( 企业应用集成) 和b 2 b 集成的成本，并且使软件重用变得容易，是目前互联 网的发展热点。 如今，w e bs e r v i c e s 采用基于x m l 的接i z l 和通信技术，只要w e bs e r v i c e s 符合相 应的接口就可以将任何两种应用程序组合在一起，并自由地创建和更改应用程序。 ( 2 ) w e b 服务的支撑技术 要以一种互操作的方式执行发布、发现和绑定这三个操作，必须有一个包含每一层 标准的w e bs e r v i c e s 协议栈。最简单的协议栈【8 】包括网络层的h t t p ，基于x m l 的消息 传递层的s o a p 协议以及服务描述层的w s d l 。所有企业间或公用w r e bs e r v i c e s 都应该 支持这种可互操作的基础协议栈，同时，w e bs e r v i c e s ，特别是企业内部或专用w e b s e r v i c e s ，也应支持其他的网络协议和分布式计算技术。图1 2 描述了可互操作的基础协 议栈。 w s d l s o a p h t t p 图1 - 2 可互操作的基础w e bs e r v i c e s 协议栈 在w e b 服务体系中，使用w s d l 来描述服务，u d d i 来发布、查找服务，s o a p 来执行服务调用，在w r e b 服务之间进行消息传递，它们是w e b 服务最基本的三项技术。 下面主要介绍本文用到的s o a p 和w s d l 技术。 钔s o a p s o a p 是一个基于x m l 的、在分散或分布式环境中交换信息的简单协议。它主要 包括四个部分： 东南大学硕士学位论文 s o a p e n v e l o p e 定义一个描述消息中的内容、发送者、接受者、处理者以及如 何处理的框架。 s o a p 编码规贝, i j ( e n c o d i n gr u l e ) 用于表示应用程序需要使用的数据类型的实 例。 s o a pr p c 表示( r p c p r e s e n t a t i o n ) 表示远程过程调用和应答的协定。 s o a p 绑定( b i n d i n g ) 使用底层协议交换信息。任何传输协议都可以用来交换 s o a p 消息，只要发送和接收消息的应用程序理解该协议即可。 b ) w s d l w s d l 是一种基于x m l 的用来描述w e b 服务接口的标准，用以指明w e b 服务中 使用的方法、数据类型、使用的传输协议和w e b 服务宿主的终点u r l 9 1 。 w s d l 文档将w e bs e r v i c e s 定义为服务访问点或端口的集合。w e bs e r v i c e s 的w s d l 文档把服务访问点和消息的抽象定义与具体的服务部署和数据格式的绑定分离开来，因 此可以对抽象定义进行重用。w s d l 文档中的消息是指对数据的抽象描述，而端口类型 是指操作的抽象集合，端i s l 类型使用的具体协议和数据格式规范构成了一个绑定，将 w e b 访问地址与可再次使用的绑定相关联来定义一个端口，而端口的集合则定义为服 务。 w s d l 的设计完全继承了以x m l 为基础的开发设计理念，它允许通过扩展使用其 他的类型定义语言，允许使用多种传输协议和消息格式( s o a p h t t p 、h t t p g e t p o s t 以及m i m e 等) ，同时也应用了软件复用概念，把抽象定义层和具体部署层分离开来， 增加了抽象定义层的复用性。 ( 3 ) 基于x m l 消息传递的分布式计算 w e bs e r v i c e s 体系结构的基础是x m l 消息传递，当前x m l 消息传递的行业标准是 s o a p 。s o a p 是一种简单的、轻量级的基于x m l 的机制，用于在网络应用程序之间进 行结构化数据交换，它包括三部分： 一个定义描述消息内容的框架的信封。 一组表示应用程序定义的数据类型实例的编码规则。 表示远程过程调用和响应的约定。 s o a p 采用了已经广泛使用的两个协议：h t t p 和x m l 。h t t p 用于s o a p 消息传 输，而x m l 是s o a p 的编码模式。h t t p 作为底层通信协议，因而可以很好地使用请 求响应机制来传送消息。s o a p = i 冲c + h t t p + x 】l 。它采用h t t p 作为底层通信协 议，以r p c 作为一致性的调用路径，用x m l 作为数据传输格式，允许服务提供者和服 务请求者通过防火墙在i n t e m e t 环境下进行通信交互。s o a p 使用h t t p 传送x m l ，尽 管h t t p 不是有效率的通信协议，而且x m l 还需要额外的文件解析，使得交易的速度 大大低于其他方案。但x m l 是一个开放、健全、有语义的信息机制，而h t t p 是一个 广泛又能避免许多关于防火墙的问题，从而使s o a p 得到了广泛的应用。 网络节点在基于x m l 消息传递的分布式计算中扮演提供者和请求者的角色，它具 有构建、解析s o a p 消息的能力，以及在网络上通信的能力( 包括接收、发送消息) 。 4 第1 章绪论 应用程序与s o a p 的集成可以通过使用四个基本步骤来实现： a ) 在图1 - 3 中，服务请求者的应用程序创建一条s o a p 消息，服务请求者将此信 息和服务提供者的网址一起提供给s o a p 基础结构，s o a p 基础结构与一个底 层网络协议交互，然后在网络上将s o a p 消息发送出去。 请求 图1 - 3 使用s o a p 的x m l 消息传递 b ) 网络基础结构在将消息传送到服务提供者的s o a p 基础结构( 例如一个s o a p 服务器) ，s o a p 基础结构负责将x m l 消息转换为特定于编程语言的对象，这 个转换由消息中可以找到的编程模式来控制。 c ) w e bs e r v i c e s 负责处理请求信息并生成一个响应，该响应也是一条s o a p 消息。 响应的s o a p 消息被提供给s o a p 基础结构，其目的地是服务请求者，将s o a p 消息响应发送到网络上的服务请求者。 d ) 响应消息会经过整个s o a p 基础结构，可能会将x m l 消息转换为目标编程语 言中的对象，然后，响应消息会被提供给应用程序。 本示例使用了请求响应传送基本原理，这种原理在大多数分布式计算环境中都很常 见。请求响应交换可以是同步的，也可以是异步的，其他传送基本原理，如“单向消息 传递 ，“通知”也可能用到s o a p 。 1 1 3w r e b 服务实现方式 ( 1 ) j a v as o a p 服务引擎的工作原理 w e b 服务的实现架构实际上就是围绕约定的消息格式，提供特定消息( 如s o a p ) 的传递与解析的协议栈。w | e b 服务的引擎为客户端提供服务的机制其实就是这些协议栈 的具体实现。典型的w e b 服务的应用场景是从另一个现有应用程序发出请求，获得服 务器所提供的业务应用程序的服务。这样的服务请求，可以跨越h t t p 、j a v a 消息服务 ( j m s ) 等传输协议，以s o a p 的消息格式抵达给定的w e b 服务监听地址，再由监听者启 动后台实际运作的业务模块，例如e n t e r p r i s ej a v a b e a n s ( e j b ) 完成服务调用的过程。 因此，通常可以把这个过程的必要参与者划分成服务的请求方( 客户端) 与服务的提供 方( 服务端) 。如图l 4 所示的消息传递层次，基本上涵盖了一个w e b 服务的简单应用 场景所涉及的方方面面 1 0 l 。 东南大学硕士学位论文 墨产端 凝癸嚣愿 广= = = = ：= 一i广一一一一一一一一一一 。i 巴 ：匦 ；匡 i 孵缀务谆琏 1 i， 豸数炎掣沌魉 j ；1 1 1 j l 娃堙端l j 莪i 。l ii 图1 - 4 w e b 服务的两端 如图1 5 所示，是以j a v a 为例的w e b 服务类型转化过程，由于s o a p 消息流是x m l 形式，因此，在发送服务请求的时候，在客户端，有必要将j a v a 类型的数据转化成x m l 类型，而服务端要将收到的x m l 再转化成j a v a 数据类型。在发送相应消息的时候则相 反，服务端先将j a v a 类型转换成x m l ，客户端再将收到的x m l 转化成j a v a 类型。 图l - 5w e b 服务两端的数据类型映射 ( 2 ) 开发w e b 服务的方式 完整的w e b 服务开发包括3 个阶段：开发、部署和发布。 开发阶段：此阶段包括逻辑模块( 如j a v ab e a n 或e j b ) 的开发与部署，w s d l 服务定义文件的设计或生成。 部署阶段：指定w 曲服务的传输协议( 绑定) ，明确服务的终端地址( e n d p o i n t a d d r e s s ) ，创建w e b 的附属文件，以平台可识别的方式将w e b 服务注册到相应 服务描述部署文件。 发布阶段：将w e b 服务的接口和调用地址公开供客户端调用，常用的发布方式 为基于w e b 提供w s d l 的链接，当然，u d d i 也是一个选择。 在w e b 服务的开发阶段，有两种可以实施的方案，可以先设计w s d l ，即服务的 接口定义，然后生成服务逻辑代码，即自上而下( t o p d o w n ) 的方式；还可以先完成业 务逻辑代码的开发或者使用已经存在的逻辑代码，再根据代码暴露出服务的接口w s d l ( 自底向上，b o t t o m u p ) ，包装w e b 服务。这两种方式无所谓绝对的好坏，要根据实际 情况来定，但至少在现阶段，自底向上的模式更常见些。本文主要采用b o t t o m u p 方式 开发w r e b 服务。 本文开发w e b 服务的方式为如图1 - 6 所示的自底向上的方式。这种方式至少在目前更 为常见，大多数的s o a 应用都是基于当前的应用创建服务。因此，总是先有应用，再有 6 第1 章绪论 服务。而且，一般企业比较有自主权来制定服务的接口而不必受到标准化定义的限制。 以j 2 e e 平台为例，通常先准备好服务用于发布w e b 服务的f a c a d e 会话b e a n ，然后使用工 具自动生成w e b 服务的代码、定义文件和部署描述文件。本文开发w e b 服务的方式为自 底向上。j a v a b e a n s 是j a v a 的可重用组件技术，它可以用来执行复杂的计算任务，或负责 与数据库的交互以及数据提取等。j 2 e e 平台提供了一个基于组件的方法，来设计、开发、 装配及部署企业应用程序。j 2 e e 平台提供了多层的分布式的应用模型、组件再用、一致 化的安全模型以及灵活的事务控制。 玩地上争 定义乏释 图l - 6 自底向上的w e b 服务开发方式 1 2 流水作业调度问题 1 2 1 问题简介 流水作业调度问题又称同顺序作业排序问题，它是一类常见的车间作业排序问题， 也是一类重要的车间作业排序问题。在流水作业排序问题中，通常把任务称为作业，设 有作业集，= “，j 2 ，d 。) ，处理机集p = 置，最，巴 ，每个作业j j 有m 道工序： 互，乏，工序乙的加工时间为p o p f ，0 。各作业依次在处理机日，巴上完 成各道工序。常见的目标函数是极小化排序时间总长和加权总完工时间。流水作业排序 问题绝大多数问题都是n p 难的。 在流水作业调度问题中，各作业依次在处理机# ，最，己上完成各道工序。但对于 同一台处理机来说，各作业在其上的加工顺序可能不同。如果在全部处理机上各作业的 加工顺序也相同，则称为排列排序( p e r m u t a t i o ns c h e d u l e ) 。对于 个作业，m 台处理机 的流水作业排序问题，由于每台处理机上n 道工序的可能排序数为疗! ，因此全部的可能 排序数为( n ! ) ”。如果仅考虑排列排序，则排序数为刀! 。 流水作业调度问题要确定多个工件在多台机器上被加工的一个序列，以使性能指标 ( 例如，最长完工时间( m a k e s p a n ) ，总完工时间( t o t a lf l o w t i m e ) ，延迟工件的数量， 机器利用率等等) 得到优化。在流水作业调度中，对于所有的工件，加工的路径都应是 相同的。t o t a lf l o w t i m e 是流水作业调度问题重要的性能指标，它可以促使资源稳定有 效地利用、作业的快速周转和在制品库存最小，所以目前通常选取总完工时间为优化目 标。g r a y 等已经证明最小化总完工时间流水作业调度问题( 根据文献【1 】可记为 f 朋ip r m ui ：c ，) 是n p 难问题。 7 东南大学硕士学位论文 1 2 2 问题描述 对于流水作业调度问题，有如下假设： ( 1 ) 任务或作业和处理机都是有限的。 ( 2 ) 在任一时刻，任何处理机只能加工一个任务或一道工序。 ( 3 ) 极小化单一目标函数。 最小化总完工时间流水作业调度问题巴ip r m uf c j 中， e 表示m 个处理机，流水作业； p r m u 表示作业按先进先出的顺序( f i f o ) 的原则加工，即所有作业的每一工序的 加工顺序都相同； c ，表示总完工时间，即目标函数。 一个简单的3 台机器，4 个任务的流水作业调度如图1 7 所示。其中的总完工时间 y c ，为5 9 。 r f l m l m 2 m 3 图1 - 73 台机器的简单的流水作业调度 1 2 3 国内外研究现状 随着计算机应用的日益普遍和系统规模的扩大，分布式计算得到了长足的发展。具 有代表性的模型有远程过程调用r p c 、面向过程的分布式计算环境d c e ，和面向对象的 c o r b a l l 、c o m d c o m 等。分布式对象计算实现了对象之间的透明互操作，解决了 企业计算中的诸多问题，已经在通信、金融等行业得到了广泛的应用。但近年来，随着 i n t e m e t 在各个领域应用的普及和深化，人们迫切需要能够方便地实现i n t e m e t 上跨平台、 语言独立、松散耦合的异构应用的交互和集成，这对分布式计算提出了新的要求。w e b s e r v i c e s 作为一种新的技术应运而生，提出了面向服务的分布式计算模式。学术界和业 界技术厂商如i b m ，s u n ，m i c r o s o f t 等都对其表示了密切的关注，纷纷加入到w e bs e r v i c e s 的研究和开发中。目前，w e bs e r v i c e s 已成为计算机领域的一个研究热点。 国内对服务计算的研究越来越深入，中科院计算研究所李伟等【1 2 l 【1 3 l 【1 4 1 自然科学基 金和国家8 6 3 计划基金资助下，通过分布式虚拟机解决网格服务计算中的应用开发和部 署问题，主要针对织女星网格系统，提出了面向服务的层次化软件结构，引入网格资源 空间的概念，实现了网格资源的虚拟化。台湾科技大学的谢佑明等【1 5 1 ( 2 0 0 9 ) 为自动化 监控系统提出了一个基于分布式计算技术的可扩展的i t 架构，这个分布式计算技术基于 s o a pw e b s e r v i c e s 实现。 国外正式提出服务计算是在2 0 0 3 年【1 6 1 ，f l j p a p a z o g l o u 和g e o r g a k o p o u l o s 提出。h u b r i s 8 第1 章绪论 和s i n g h ( 2 0 0 5 ) 对其做了深入研究和推广【1 7 】【1 8 ”】，d u s t d a r l 2 0 并f l t a i 等【2 l 】分别将服务计 算应用于工作流和事务处理。z h a o 等1 2 2 j ( 2 0 0 7 ) 对s e r v i c e o r i e n t e dc o m p u t i n g ( s o c ) 进行了概述，s o c 被认为是一种把服务作为基本要素来进行应用开发的计算模式。2 0 0 8 年，g e o r g a k o p o u l o s 等1 2 3 1 对s e r v i c e o r i e n t e dc o m p u t i n g 进行了更详尽的研究和阐述。y u 等1 2 4 l ( 2 0 0 9 ) 在一个基于s o a 网格环境的应用集成框架中实现了一个更有效的服务调 度算法，并且实现了一个服务重调度机制。 综上所述，目前，尽管与服务技术紧密相关的网格环境下资源管理和调度有较多研 究，但应用s o c 求解调度或排序问题的研究成果相对而言比较少。而且国内外已经提 出了很多的复合启发式算法【2 5 】【2 6 】【2 7 1 来解决f mip r m u 罗c ，问题，然而这些算法基本上 是采用扩大搜索范围来提高算法性能( e f f e c t i v e n e s s ) ，但同时也降低了算法效率 ( e f f i c i e n c y ) 。如何在保证算法性能高的前提下大幅度缩短计算时间、提高算法效率具 有重要的理论意义和应用价值。 1 3 课题来源和主要研究内容 1 3 1 课题来源 本文研究得到国家自然科学基金：“基于服务计算的不可分解调度问题自适应算法 ( n o 6 0 6 7 2 0 9 2 ) 的资助。 1 3 2 主要研究内容 在充分理解s o a 架构，w e b 服务相关标准和w e b 服务的构建、发布、发现和调用 机制后，分析并充分理解f 珑ip r m ui c j 问题的复合启发式算法的操作步的并行性， 并将其封装成服务，实现基于s o a 的分布式算法服务计算过程。 具体的研究内容有： ( 1 ) 调度算法基本运算步的并行化处理 通过分析局部搜索算法以及相应的邻域变换策略，$ e i f m p r m ul c j 复合启发式 算法的基本运算步进行了分析，可以得出这些基本运算步间没有依赖关系，可以并行化。 ( 2 ) 调度算法基本运算步的服务封装 把f 聊ip r m ui c j 调度算法并行化后的基本运算步，封装成带参数的w r e b 服务， 通过w e b 发布、定位和调用。利用w s d l ( w e bs e r v i c e sd e s c r i p t i o nl a n