工作流任务调度多目标优化-计算机软件与理论专业论文.docxVIP

万方数据 万方数据 Dissertation Submitted to Hangzhou Dianzi University for the Degree of Master Multi-Objective Task Scheduling Optimization for The Workflow Candidate: Liu xue yuan Supervisor: Prof. Hu hua Prof. Hu Haiyang March，2016 杭州电子科技大学 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明： 所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个 人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名： 日期： 年 月 日 学位论文使用授权说明 本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保 证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为杭州电子科技 大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布 论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 （必威体育官网网址论文在解密后遵守此规定） 论文作者签名： 日期： 年 月 日 指导教师签名： 日期： 年 月 日 杭州 杭州电子科技大学硕士学位论文 摘要 工作流是指部分或者整个业务过程在计算机支持下的全自动或者半自动。 工作流关注的核心是过程，它提炼出信息处理的过程，然后研究其性质、结构 和实现等。其主要解决的问题是能够自动执行多个参与者之间根据预定义的规 则传递文档、信息或者任务的过程，从而达到某个预期的业务目标，或者是促 进该目标的完成。近年来，工作流任务调度优化问题一直是工作流研究的热点， 如果对工作流任务调度有一个高效的调度算法，将大大地改善服务质量。 在工作流调度中，不同的任务被分配给不同的资源（例如虚拟机）。工作 流调度是由云代理商进行决策的，其功能作为云用户工作流应用和云提供商的 数据中心之间的中间人。调度算法就是代理商用来发现工作流任务和云资源间 的最优映射。工作流调度算法的作用是要找到满足用户目标的调度。用户们在 SLA（服务水平协议）文件上定义他们的目标，该文件是在一个云用户和一个 云服务提供商之间签署的。云服务提供商可能需要满足用户多目标例如成本优 化、完成时间优化、可靠性、最后期限约束、预算约束等等，找到最优的调度 来满足用户的目标就是调度算法的作用。 首先，本文对工作流任务调度多目标优化问题进行了详细阐述，分析了当 前对该问题所进行的研究现状。本文对负载均衡、数据处理时间总和、传输的 数据量、传输所花费的时间优化问题建立了模型和分析，粒子群算法作为现代 多目标优化算法的代表之一，本身具有很多优点，对于其容易陷入局部最优这 一缺点，文章也学习现有优秀的改善措施进行了优化，这样本文就给出了基于 粒子群算法的工作流调度多目标优化方法。 其次，本文根据该问题还提出了一个新的启发式方法 NHMFTS，该方法的 执行过程需要多次迭代，每次迭代都有具体的策略执行，而迭代次数和任务数 量相同，这样整个方法的执行占用可预估的很少时间。本文还结合 NHMFTS 和 PSO 的优势，将两个方法融合为一种综合性的方法。 最后，文章对上面所提出的方法进行了实现以及模拟实验，结合得到的实 验数据进行了分析、对比等，同时说明了本文提出的一种新方法 NHMFTS，可 以在一定条件下，很大的节省了时间，间接的实现了更好的服务。 关键词：工作流，多目标优化，任务调度，调度算法 I ABSTRACT Workflow is refers as part or whole business process’s automatic or semi-automatic under a computer. The core of workflow is process. It extracts the information processing process, and then studies its nature, structure and implementation, etc. The main problem is how to automatically execute tasks such as delivering documents or information according to a particular predefine