带截止期和服务时间窗约束的云服务工作流调度方法

《带截止期和服务时间窗约束的云服务工作流调度方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、隶．初大◆璺硕士学位论文万方数据带截止期和服务时间窗约束的云服务工作流调度方法专业名称：计算机应用技术研究生姓名：钱1ii4堕导师姓名：李小平教授万方数据WORKFLOWSCHEDULINGWITHDEADLINEANDTIMESLOTSCOINSTRAn町TSINCLOUDCOMPUTINGAThesissubmittedtoSoutheastUniversityFortheAcademicDegreeofMasterofEngineeringBYLihuaQianSupervisedbySupervisedby：Prof．XiaopingLiS

2、choolofComputerScience&EngineeringSoutheastUniversityJune7，2014万方数据东南大学学位论文独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他入已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。研究生签名：垒泣函玺日期：查!丝』：』东南大学学位论文使用授权声明东南大学、中国科

3、学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布(包括刊登)论文的全部或部分内容。论文的公布(包括刊登)授权东南大学研究生院办理。研究生签名：生勃亟笙导师签名期：逊：!：鱼万方数据摘要云计算工作流租户通常认为云服务的服务能力是无限的，即请求即可用；但对服务提供商而言，任务共享服务使得剩余服务能力随工作的负载不同而实时改变，难以在任何时刻都满足租户需求，即服务具有可用时间窗。因此，本文研

4、究带截止期和服务时间窗约束的云服务工作流调度(简称为DTCTP．TSC)问题，具有重要的理论意义和实际价值。考虑截止期和服务时间窗等约束因素并根据问题特征，建立DTCTP．TSC问题的数学模型；通过实例分析发现，若采用服务执行时间越短代价越大的计费模型，DTCTP的最快调度代价最大，但DTCTP．TSC的最快调度不一定代价最大。提出包括生成初始解、改进解和重构解等阶段的迭代启发式方法架构IDH。基于不同的优先级规则设计了三种初始解生成策略；结合问题的特点，提出基于贪心和公平规则的改进过程；构造重构解策略。基于IDH不同阶段的策略，组合出6个启发式算

5、法：FFDH、AFDH、CFDH、FGDH、AGDH、CGDH。通过大量测试数据验证所提出策略和算法的效率和有效性，实验表明：不同的初始解生成和改进解策略对解的质量产生不同影响；启发式方法FFDH在大部分情况下最好；当代价函数为凸函数时，CFDH算法的性能最好。关键词：工作流调度，DTCTP，最小化总成本，时间区间，云计算万方数据AbstractCloudservicecapacityincloudcomputingisbasedontheassumptionthatitisunlimitedandcanbeusedatanytimebytenan

6、ts．HoweveLfromcloudprovider’sperspective，theremainingservicecapabilitychangeswithworkloadandcannotsatisifytenants’requestsatanytimebe—causeofmulti—taskssharingcloudservice．CloudserviceCanprovidesomeavailabletimeslotsfornewcomingtenantsbasedonremainingcapabilities．Therefore，Wor

7、kflowSchedulingwithDeadlineandTimeSlotsConstraintsincloudcomputing(calledDTCTP·TSCforshort)whichisfulloftheoreficalsignificanceandpracticalvalueisconsideredinthethesis．TheobjectiveofDTCTP—TSCisminimumtotalcostsatisfyingthegivendeadlineandamathematicsmodelisestablishedforthecon

8、sideredproblem．AsDTCTP—TSCisNP-hard，aneffectiveandefficientit