摘要
随着越来越多科学计算项目的提出与开展,用户对网格环境下的科学工作流管理系统服务质量的问题日益重视。作为科学工作流管理系统中的核心组件,调度策略的优劣对系统的执行效率、资源利用率以及对用户的QoS保障程度有直接而重要的影响。然而,科学应用的多样化导致工作流调度目标呈现多样性。一方面,用户的各种QoS需求之间往往相互联系且相互制约;另一方面,用户的QoS需求与网格系统性能之间的矛盾难以协调与平衡。如何对这些QoS指标进行权衡以提升系统服务质量是工作流调度领域的研究热点。此外,网格系统的动态性和自治性等问题使得资源的可用性、可靠性和负载压力难以准确判断和预测,已有的工作流调度策略经常难以有效适应于现实网格环境,例如保证用户QoS需求中的各种不同的约束性条件。因此,对网格系统中工作流调度策略的研究具有良好的理论价值和实用意义。
本文围绕面向QOS约束的工作流优化调度以及如何增强动态环境下的用户QOS满意度两个方面展开研究。论文的主要研究内容和创新包括:
(1)提出了时间约束下基于CRO的工作流费用优化算法
传统的基于分层思想的工作流费用优化算法为工作流任务设定固定的时间窗口,在一定程度上限制了算法的搜索范围。本文将化学反应优化算法应用于时间约束下的科学工作流费用优化调度问题中并与启发式算法GreedyCost-TD相结合,提出了工作流费用优化算法CROTD。针对该优化问题,构建了四种化学分子反应操作的实施规则并基于正交试验给出了算法的优化参数设置。为了避免求解过程中产生不满足工作流时序约束的无效解,提出了基于任务依赖度的初始随机分子构造方法。通过对不同规模的Montage和LIGO工作流的实验结果表明,CROTD算法在费用优化方面具有较好的性能。
(2)提出了费用约束下基于性能评估的工作流动态调度算法
针对资源上网格任务及本地任务负载的动态性导致任务执行时间难以预测而影响做出有效调度决策的问题,提出以M/M/C型随机服务系统建模资源的执行性能,给出了任务在资源节点上的执行时间的估算方法。基于列表调度的思想和所建立的资源性能评估模型,提出了费用约束下基于性能评估的工作流动态调度算法SSWC_PE。通过对不同规模的Montage和LIGO工作流的实验结果表明,与GreedyTime-CD、LOSS算法相比,SSWC_PE算法在执行时间方面具有较好的性能表现。
(3)提出了时间约束下的工作流可靠调度模型与算法
网格环境中资源失效情况较为普遍,对资源可靠性以及资源上任务负载状况的感知将极大地增加应用在资源上执行的可靠性。在考虑本地任务对资源服务能力影响的基础上,本文提出采用随机服务模型建模资源的动态服务能力和负载压力,给出了任务在资源上的“执行可靠性”的定义及其计算方法。然后,结合“资源可靠度”和“执行可靠性”建立了一个新的资源节点可靠性评估模型。在此基础上,提出了一种时间约束下的工作流可靠性调度算法RSA_TC。算法将用户时间约束划分到每个子任务中,将整个工作流的全局优化问题转化为单个任务的局部优化问题,降低了问题的复杂度。实验结果表明,提出的可靠性模型能够准确反映网格资源的任务执行特征,RSA_TC算法在执行可靠性方面优于HEFT、PRMS算法。
(4)提出了时间保障度增强的科学工作流管理系统架构及相应的工作流调度策略
针对资源预留、任务迁移和任务副本等资源管理策略仍然依赖于动态不可靠的网格资源而不能有效应对任务执行时间不可预测的问题,提出了一种时间保障度增强的科学工作流系统架构EDGESA,利用云服务来增强工作流管理系统对应用截止时间的保障能力。针对系统架构中工作流调度这一核心模块,提出以任务违约风险来量化网格资源对工作流任务的时间保障度,使用时间序列模型预测云服务的响应时间。通过实验对EDGESA的截止时间保障能力进行了分析,表明EDGESA能够有效保证应用的执行时间需求,为下一代工作流管理系统的实施提供了参考。
Nowadays, Grid technology is still an important supporting environment for scientific workflow management system. In such a decentralized, dynamic and autonomous environment, providing non-trivial QoS for end users is a major challenge, which has gained more and more attention. As a core component of scientific workflow management system, scheduling strategies have important and direct impact on the performance of system, resource utilization and QoS guarantee. However, some QoS metrics are contracted and restricted with each other. How to optimize the operation efficiency among these aspects is still a hot topic. Because of the dynamicity and autonomy of Grid system, existing scheduling strategies cannot to be applied into real Grid environment and provide an effective and efficient QoS guarantee service. As a result, the studies for workflow scheduling strategy are helpful for accelerating the pace of scientific progress in both theory and practice.
Based on the discussion of the current studies and drawbacks of scientific workflow management system and scheduling strategies, this thesis deeply investigates efficient and effective workflow scheduling strategies in Grid environments. The main contribution of this thesis can be summarized as follows:
(1) Research on the cost optimization problems for scientific workflow with deadline constraint. Leveling technology is a popular method in solving the problem, which has been researched by many researchers. However, leveling technology need to set fixed time period for workflow tasks and restrict the search scope. In the paper, a novel cost optimization algorithm, called CROTD is proposed, which combine CRO algorithm and a heuristic algorithm called GreedyCost-TD. Aimed at the optimization problem, a construction method of random initial molecule based on task dependency and detail implementation for four different molecules reaction are proposed. Orthogonal experiment is introduced into the parameter selection of algorithm. Experimental result show CROTD algorithm can obtain better performance.
(2) Research on the on-line workflow scheduling algorithm based performance evaluation. Because of the autonomy and task completion of Grid resource, it is difficult to predict the execute time of task in dynamic Grid environment. Based on the analysis of task characteristic in Grid resource, M/M/C stochastic service model is used to model the service capacity and workload status of Grid resource. Then, the calculating method approximately for task execution time is presented. Aimed at the minimizing the makespan of workflow with cost constraint, a dynamic workflow scheduling algorithm based on performance evaluation, called SSWC_PE, is proposed. Compared with Greedytime-CD and LOSS, SSWC_PE performs better on makespan.
(3) Research on the reliable workflow scheduling algorithm with time constraint. In order to improve the execution reliability of workflow and enhanced user satisfaction, a stochastic service model considering the impact of local tasks is adopted to describe dynamic workloads of Grid resources. A definition called execution reliability of task is presented to evaluate the probability that meeting deadline of task. Then, combined with the traditional definition for resource reliability, a novel resource reliability evaluation model is introduced. Based on the model, a reliability scheduling algorithm for scientific workflow with cost constraint called RSA_TC is presented. The results of extensive simulation experiments show that the proposed algorithm outperforms PRMS and HEFT, with respect to guarantee deadline and adaptability to dynamic Grid environment.
(4) Research on the deadline guarantee enhanced scientific workflow management system architecture and corresponding scheduling strategy. Current workflow management system usually adopt following different techniques to alleviate this problem:resource reservation, rescheduling, task migration, task duplication, which cannot solve the problem efficiently. Aimed at the time sensitive scientific workflow, a novel workflow orchestrating system architecture called EDGESA is presented, which enforces the deadline guarantee of e-science applications by leasing reliable Cloud services. Aimed at the scheduling strategy of deadline-sensitive scientific workflow, metric called Default Risk of Task is provided to judge whether Cloud services should be used. Time Series Model is adopted to evaluate the reponse time of Cloud service. The experimental results show that EDGESA can achieve better performance than other strategies on user's deadline guarantee.
引文
[1]刘灿灿.科学工作流管理及调度研究[D].长沙:国防科技大学,2011.
[2]I.Foster, C.Kesselman, S.Tuecke. The Anatomy of the Grid:Enabling Scalable Virtual Organizations [J]. International Journal of High Performance Computing Applications,2001,15(3):200-222.
[3]M.Armbrust, A.Fox, R.Griffith, et al. Above the Clouds:a Berkeley View of Cloud Computing [R]. University of California, Berkeley,2009.
[4]孙坦.数字化科研:e-Science研究[M].北京:电子工业出版社,2009:1-5.
[5]刘应波.科学工作流系统-Nebulas的设计与实现[D].昆明:昆明理工大学,2011.
[6]S.Shankar, A.Kini, D.J.Dewitt, et al. Integrating databases and workflow systems [J]. ACM SIGMOD Record,2005,34(3):5-11.
[7]P.Hut.Dense stellar systems as laboratories for fundamental physics [J]. New Astronomy Reviews,2010,54(3-6):163-17.
[8]I.Foster, C.Kesselman. The Grid:Blueprint for a New Computing Infrastructure [M]. San Francisco, CA:Morgan Kaufmann,1999.
[9]B.Fran, F.Geoffrey, J.G.H. Anthony. Grid Computing:Making the Global Infrastructure a Reality[M]. New York:John Wiley & Sons,2003:65-100.
[10]I.Foster, C.Kesselman.The Globus Project:A Status Report[J]. Future Generation Computer Systems,1999,15(5-6):607-621.
[11]A.S. Grimshaw, W.A. Wulf.The Legion Vision of a Worldwide Virtual Computer[J]. Communications of the ACM,1997,40(1):39-45.
[12]C.Catlett. Standards for Grid Computing:Global Grid Forum[J]. Journal of Grid Computing,2003,1(1):3-7.
[13]I.Foster, C.Kesselman, J.Nick, et al.The Physiology of the Grid:An Open Grid Services Architecture for Distributed System Integration[R/OL].http://www.globus.org/alliance/publications/papers/ogsa.pdf, 2002-06.
[14]C.E. Catlett. TeraGrid:A Foundation for US Cyberinfrastructure [C].In Proceedings of Network and Parallel Computing,2005:1.
[15]D.Bernholdt, S.Bharathi, D.Brown,et al.The Earth System Grid:Supporting the Next Generation of Climate Modeling Research[J]. Proceedings of the IEEE, 2005,93(3):485-495.
[16]F.Gagliardi, B.Jones, M.Reale,et al. European DataGrid Project:Experiences of Deploying a Large Scale Testbed for E-science Applications[J]. Lecture Notes in Computer Science,2002,2459:480-499.
[17]B.Rochwerger, D.Breitgand, E.Levy,et al.The Reservoir model and architecture for open federated cloud computing[J]. IBM Journal of Research and Development,2009,53(4):1-11.
[18]Amazon Elastic Compute Cloud[EB/OL]. http://aws.amzaon.com/ec2/.
[19]D.Milojicic, I.M. Llorente, R.S. Montero. OpenNebula:A Cloud Management Tool[J].IEEE Internet Computing,2011,15(2):11-14.
[20]P.Jakovits, S.N.Srirama,I.Kromonov. Stratus:A Distributed Computing Framework for Scientific Simulations on the Cloud[C]. In Proceedings of 14th International Conference on High Performance Computing and Communication,2012,1053-1059.
[21]I.Foster, Z.Yong, I.Raicu, et al. Cloud computing and grid computing 360-degree compared[C]. In Proceedings of Grid Computing Environments Workshop,2008:1-10.
[22]L.M.Vaquero, L.Rodero-Merino, J.Caceres, et al. A break in the clouds: Towards a cloud definition [J]. ACM SIGCOMM Computer Communication Review,2008,39(1):50-55.
[23]Z.Qi, C.Lu, B.Raouf. Cloud computing:State of the Art and Research Challenges [J]. Journal of Internet Services and Applications,2010,1(1):7-18.
[24]R.Prodan, M.Sperk, S. Ostermann. Evaluating High-Performance Computing on Google App Engine[J].IEEE Software,2012,29(2):52-58.
[25]刘鹏.云计算[M].北京:电子工业出版社,2011.
[26]E.Deelman, G. Singh, M.Livny, et al. The cost of doing science on the Cloud: The montage example[C]. In Proceedings of ACM/IEEE Conference on Supercomputing,2008,1-12.
[27]WfMC, Workflow management coalition specification[R],1999.
[28]Y.Jia, R.Buyya. A taxonomy of scientific workflow systems for grid computing[J]. ACM SIGMOD Record,2005,34(3):44-49.
[29]Z.Guan, F.Hernandez, P.Bangalore, et al. Grid-Flow:A Grid-Enabled Scientific Workflow System with a Petri Net-Based Interface[J]. Concurrency and Computation:Practice and Experience,2006,18(18):1115-114.
[30]B.Ludascher, B. Bowers, S.McPhillips.Encyclopedia of Database Systems[J]. 2009:2507-2511.
[31]C.Lin, S.Lu, X.Fei, et al. A Reference Architecture for Scientific Workflow Management Systems and the VIEW SOA Solution [J]. IEEE Transaction on Service Computing,2009,2(1):79-92.
[32]S.Kim, H.Kang, Y.Kim. A scientific workflow supported environment over hybrid infrastructure for aerodynamics design[C].In Proceedings of 24th International Conference on Network Operations and Management Symposium, 2012,1-6.
[33]A.Iosup, C.Dumitrescu, D. H. J.Epema, et al. How are real grids used? the analysis of four grid traces and its implications [C]. In Proceedings of International Conference on Grid Computing Conference,2006:262-269.
[34]H.Topcuoglu, S.Hariri, M.Y. Wu. Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing[J]. IEEE Transaction on Parallel and Distributed Systems,2002,13(3):260-274.
[35]H.E.Rewini, T.GLewis. Scheduling Parallel Program Tasks onto Arbitrary Target Machines[J]. Journal of Parallel and Distributed Computing,1990,9: 138-153.
[36]R.Sakellariou, V.Yarmolenko. Job scheduling on the grid:Towards SLA-based scheduling[J]. In Proceedings of High Performance Computing and Grids in Action,2008,16:207-222.
[37]GC.Sih, E.A. Lee. A Compile time Scheduling Heuristic for Interconnection Constrained Heterogeneous Processor Architecture [J]. IEEE Transactions on Parallel and Distributed Systems,1993,4(2):175-187.
[38]M.Wu, D. Gajski. Hypertool:A Programming Aid for Message Passing Systems[J]. IEEE Transactions on Parallel and Distributed Systems,1990,1(3): 330-343.
[39]Y. Kwok,I.Ahmad. Dynamic Critical-Path Scheduling:An Effective Technique for Allocating Task Graphs to Multi-processors[J]. IEEE Transactions on Parallel and Distributed Systems,1996,7(5):506-521.
[40]M.A.Iverson, F.Ozguner, G.J.Follen. Parallelizing existing applications in a distributed heterogeneous environment[C]. In Proceedings of the 4th Heterogeneous Computing Workshop,1995,93-100.
[41]S.Ranaweera, D.P. Agrawal.A task duplication based scheduling algorithm for heterogeneous systems [C]. In Proceedings of International Conference on Parallel Processing,2000,383-390.
[42]S.Ranaweera, D.P. Agrawal. A scalable task duplication based scheduling algorithm for heterogeneous systems [C]. In Proceedings of the 14th International Parallel and Distributed Processing Symposium,2000,445-450.
[43]S. Baskiyar, C. Dickinson. Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication [J]. Journal of Parallel and Distributed Computing,2005,8(65):911-921.
[44]A. Dogan, R.Ozquner. LDBS:a duplication based scheduling for heterogeneous computing systems. In Proceedings of the International Conference on Parallel Processing,2002,352-359.
[45]B.Cirou, E.Jeannot.Triplet:A clustering scheduling algorithm for heterogeneous systems [C]. In Proceedings of the International Conference on Parallel Processing,2001,231-236.
[46]何琨,赵勇,黄文奇.基于任务复制的分簇与调度算法[J].计算机学报,2008,31(5):733-740
[47]王小乐,黄宏斌,邓苏.处理顺序约束的信息物理融合系统静态任务表调度算法[J].自动化学报,2012,38(11):1870-1879
[48]Z.Xu, X.Hou, J.Sun. Ant Algorithm-based Task Scheduling in Grid Computing [C]. In Proceediongs of 2003-Canadian Conference on Electrical and Computer Engineering,2003:1107-1110
[49]季一木,王汝传.基于粒子群的网格任务调度算法研究[J].通信学报,2007,28(10):60-66.
[50]曹鸿强,肖侬,卢锡城,等.一种基于市场机制的计算网格资源分配方法[J].计算机研究与发展,2002,39(8):913-916.
[51]蒋伟进,王璞.基于MAS市场机制的动态计算资源调度模型研究[J].计算机研究与发展,2007,44(1):29-36.
[52]P.Ghosh, N.Roy, S.K. Das, et al. A Game Theory based Pricing Strategy for Job Allocation in Mobile Grids. In Proceedings of 18th International Parallel and Distributed Processing Symposium,2004.
[53]R.Prodan, M.Wieczorek, H.M. Fard. Double Auction-based Scheduling of Scientific Applications in Distributed Grid and Cloud Environments. Journal of Grid Computing,2011,9(4):531-548.
[54]R. Duan, R.Prodan, X.Li. A Sequential Cooperative Game Theoretic Approach to Storage-Aware Scheduling of Multiple Large-Scale Workflow Applications in Grids[C].In Proceedings of 13th ACM/IEEE International Conference on Grid Computing,2012,31-39.
[55]李志洁,程春田,黄飞雪,等.一种基于序贯博弈的网格资源分配策略.软件学报,2006,17(11):2373-2383.
[56]李明楚,许雷,孙伟峰,等.基于非完全信息博弈的网格资源分配模型[J].软件学报,2012,23(2):428-438.
[57]李茂胜,杨寿保,付前飞,等.基于赔偿的网格资源交易模型[J].软件学报,2006,17(3):472-480.
[58]肖鹏,胡志刚.基于三方博弈的网格资源协同分配模型[J].华南理工大学学报(自然科学版),2009,37(4):13-17.
[59]T. Yu, Y.P.Yuan, J. Li,et al. A Multi-Agent Based Approach for Manufacturing Grid Workflow. In Proceedings of International Conference on Machine Learning and Cybernetics,2005,199-204.
[60]J.Cao, S.A.Jarvis, S. Saini. ARMS:An agent-based resource management system for grid computing[J]. Scientific Programming,2002,10(2):135-148.
[61]J.Cao. ARMSim:A Modeling and Simulation Environment for Agent-Based Grid Computing[J]. Simulation,2004,80(4-5):221-229.
[62]胡敏,李艳君,吴铁军.基于多边协商的分布式网格资源调度[J].浙江大学学报(工学版),2007,41(7):1073-1077.
[63]刘卫东,宋佳兴,林闯.基于价格时间Petri网的网格计算应用模型及分析[J].电子学报,2005,44(8):1416-1420.
[64]张绍华,顾宁,刘家茂,等.基于D. Petri Net和动态调度的网格工作流[J].计算机辅助设计与图形学学报,2005,17(6):1146-1151.
[65]胡志刚,谌任,陈华全.一种改进的网格资源调度算法及其有色Petri网建模和分析[J].小型微型计算机系统,2007,28(2):229-232
[66]T.Fahringer, R.Prodan, R.Duan,et al.ASKALON:a Grid application development and computing environment[C]. In Proceedings of 6th IEEE/ACM International Workshop on Grid Computing,2005.
[67]D.A.Caldwell. The Kepler Mission:Zeroing in on habitable Earths[C]. In Proceedings of 13th IEEE International Conference on Vacuum Electronics, 2012,3-6.
[68]E.Deelman, J. Blythe, Y. Gil, et al. Mapping Abstract Complex Workflows onto Grid Environments [J]. Journal of Grid Computing,2003,1(1):25-39.
[69]T. Oinn, M. Addis, J. Ferris,et al. Taverna:A Tool for the Composition and Enactment of Bioinformatics Workflows [J]. Bioinformatics,2004,20(17): 3045-3054.
[70]F. Berman, A. Chien, K. Cooper, et al. The GrADS Project:Software Support for High-Level Grid Application Development J]. International Journal of High Performance Computing Applications,2001,15(4):327-344.
[71]J. Cao, S.A. Jarvis, S. Saini, et al. GridFlow:Workflow Management for Grid Computing. In Proceedings of the 3rd International Symposium on Cluster Computing and the Grid,2003:198-205.
[72]DAGMan:A Directed Acyclic Graph Manager[EB/OL]. http://www.cs. wisc.edu/condor/dagman,2005.
[73]X. Liu, D.Yuan, G. Zhang, et al. SWindew-C:A peer-to-peer based cloud workflow system for managing instance intensive applications [J]. Handbook of Cloud Computing,2010,309-C332.
[74]A.Luckow, L.Lacinski, S. Jha. Saga bigjob:An extensible and interoperable pilot-job abstraction for distributed applications and systems[C]. In Proceedings of 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing,2010,135-144.
[75]L.Jie, M. Humphrey, D. Agarwal, et al. Escience in the cloud:A modis satellite data reprojection and reduction pipeline in the windows azure platform[C]. In proceedings of International Conference on Parallel and Distributed Processing, 2010,1-10.
[76]Science Clouds [EB/OL]. http://scienceclouds.org/.
[77]J.Zhao, C. Goble, R. Stevens, et al. Mining Taverna's semantic web of provenance [J]. Concurrency and Computation:Practice & Experience,2008, 20(5):463-472.
[78]M. Wieczorek, A. Hoheisel, R. Prodan. Towards a general model of the multi-criteria workflow scheduling on the grid[J]. Future Generation Computer System,2009,25(3):237-256.
[79]J.Yu, R.Buyya. A taxonomy of scientific workflow systems for grid computing[J]. ACM SIGMOD Record,2005,34(3):44-49.
[80]T. Ma, R.Buyya. Critical-path and priority based algorithms for scheduling workflows with parameter sweep tasks on global grids [C]. In Proceedings of the 17th International Symposium on Computer Architecture and High Performance Computing,2005.
[81]R. Buyya, D. Abramson. Market-Oriented Grid and Utility Computing[M], New York:Wiley Press,2009.
[82]I. Brandic, S. Benkner, G. Engelbrecht, et al. QoS support for time-critical grid workflow applications. In proceedings of the 1 st international conference on e-Science and Grid computing,2005,108-115.
[83]J.Yu, R.Buyya. Grid Computing:Infrastructure, Service and Applications[M]. New York:CRC Press,2009,119-146.
[84]L.V. Kale, S. Kumar, M. Potnuru, et al. Faucets:Efficient resource allocation on the computational grid[C]. In Proceedings of the International Conference on Parallel Processing,2004,396-405.
[85]E. Crawley, R. Nair, B. Rajagopalan. A Framework for QoS-based Routing in the Internet[S]. USA:IETF RFC 2386,1998:
[86]J. Cardoso, A. Sheth, J. Miller. Workflow Quality of Service[R]. Technical report, LSDIS Lab, University of Georgia, USA,2002.
[87]I. Foster, C.Kesselman, C. Lee, et al. A Distributed Resource Management Architecture that Supports Advance Reservations and Co-Allocation[C]. In Proceedings of International Workshop on Quality of Service,1999,27-36.
[88]R. J. Al-Ali, O. F. Rana, D. W. Walker, et al. G-QoSM:Grid Service Discovery Using QoS Properties[J]. Journal of Computing and Informatics,2002,21(6): 363-382.
[89]R. Sakellariou, H. Zhao, E. Tsiakkouri, et al. Scheduling Workflows with Budget Constraints [J]. Integrated Research in GRID Computing,2007, 189-202.
[90]苑迎春,李小平,王茜,等.基于优先级规则的网格工作流调度[J].电子学报,2009,37(7):1457-146.
[91]S. Abrishami. Cost-Driven Scheduling of Grid Workflows Using Partial Critical Paths[J]. IEEE Transactions on Parallel and Distributed Systems,2012, 23(8):1400-1414.
[92]刘灿灿,张卫民,骆志刚,等.基于改进优先级规则的工作流费用优化方法[J].计算机研究与发展,2012,49(7):1593-1600.
[93]王勇,胡春明,杜宗霞.服务质量感知的网格工作流调度[J].软件学报,2006,17(11):2341-2351.
[94]张晓东,王茜.多目标服务工作流混合粒子群调度算法[J].东南大学学报(自然科学版).2010,40(3):491-495.
[95]S. Pandey, L. Wu, S.M. Guru, et al. A Particle Swarm Optimization Based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments [C]. In Proceedings of 24th IEEE International Conference on Advanced Information Networking and Applications,2010,400-407.
[96]F. Dong, S.G. Ak1.PFAS:A Resource Performance Fluctuation Aware Workflow Scheduling Algorithm for Grid Computing[C].In Proceedings of 21st IEEE International Conference on Parallel and Distributed Processing,2007,1-9.
[97]L. Ramakrishnan, C. Koelbel, Y. Kee, et al. VGrADS:enabling e-Science workflows on grids and clouds with fault tolerance. In Proceedings of 22nd ACM/IEEE SuperComputing Conference,2009.
[98]H. Zhao, R. Sakellariou. Advance Reservation Policies for Workflows[C]. In Proceedings of 12th International Workshop on Job Scheduling Strategies for Parallel Processing,2007,46-67.
[99]M. Wieczorek, M. Siddiqui, A. Villazon, et al. Applying Advance Reservation to Increase Predictability of Workflow Execution on the Grid[C]. In Proceedings of the 2nd conference on e-Science and Grid computing,2006,82.
[100]P. Xiao, Z.G. Hu. Relaxed Resource Advance Reservation Policy in Grid Computing [J]. Journal of China Universities of Posts and Telecommunications, 2009,16(2):108-113.
[101]田东,陈蜀宇,陈峰.一种网格环境下的动态故障检测算法[J].计算机研究与发展,2006,43(11):1870-1875.
[102]金海,陈刚,赵美平.容错计算网格作业调度模型的研究[J].计算机研究与发展,2004,41(8):1382-1388.
[103]J. Yu, R. Buyya, C.K.Tham. Cost-based Scheduling of Scientific Workflow Applications on Utility Grids [C]. In Proceedings of the 1st IEEE International Conference on e-Science and Grid Computing,2005,140-147.
[104]Y.S.Lam Albert, O.K.Li Victor. Chemical-Reaction-Inspired Metaheuristic for Optimization[J]. IEEE Transactions on Evolutionary Computation. 2010,14(3):381-399.
[105]A. Dogan, R. Ozquner Biobjective scheduling algorithms for execution time-reliability trade-off in heterogeneous computing systems [J]. The Computer Journal,2005,3(48):300-314.
[106]R. Prodan, M. Wieczorek. Bi-Criteria Scheduling of Scientific Grid Workflows [J]. IEEE Transactions on Automation Science and Engineering,2010, 7(2):364-376.
[107]D. A. Menasce, E. Casalicchio. A framework for resource allocation in grid com-putting[C]. In Proceedings of the IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunica-tions Systems,2004,5-7.
[108]C. Akkan, A. Drexl, A. Kimms.Network decomposition-based benchmark results for the discrete time-cost tradeoff problem [J]. European Journal of Operational Research,2005,165(2):339-358
[109]J.Yu. QoS-based Scheduling of Workflows on Global Grids[D]. The University of Melbourne,2007.
[110]苑迎春,李小平,王茜,等.基于逆向分层的网格工作流调度算法[J].计算机学报,2008,31(2):282-289.
[111]苑迎春,李小平,王茜.基于串归约的网格工作流费用优化方法[J].计算机研究与发展,2008,45(2):246-253.
[112]F. Geoffrey, L.Maozhen. Enhancing genetic algorithms for dependent job scheduling in grid computing environments [J]. The Journal of Supercomputing, 2012,62(1):290-314.
[113]F. Pop, C. Dobre, V. Cristea. Genetic algorithm for dag scheduling in grid environments [C]. In Proceedings of IEEE 5th international conference on intelligent computer communication and processing 2009,299-305.
[114]X. Xue, Y. Gu. Global optimization based on hybrid clonal selection genetic algorithm for task scheduling[J]. Journal of Computational Information Systems, 2010,6(1):253-261.
[115]W. Chen, J. Zhang. An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem With Various QoS Requirements [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part C:Applications and Reviews,2009, 39(1):29-43.
[116]J. Xu, Y.S.Lam Albert, O.K.Li Victor.Chemical Reaction Optimization for Task Scheduling in Grid Computing[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(10):1624-1631.
[117]K.Li, Z.Zhang, Y.Xu.Chemical Reaction Optimization for Heterogeneous Computing Environments [C]. In Proceedings of 10th IEEE International Symposium on Parallel and Distributed Processing with Applications,2012,17-23.
[118]王淳.基于化学反应算法的配电网重构[J].电网技术,2012,36(5):209-214.
[119]郑肇葆,郑宏.化学反应优化(CRO)图像分割的研究与分析[J].武汉大学学报(信息科学版),2012,37(10):1224-1228.
[120]Y.S. Lam Albert, O.K. Li Victor. Chemical Reaction Optimization:A Tutorial (Invited paper)[J]. Memetic Computing,2012,4(1):3-17.
[121]雷英杰.Matlab遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005.
[122]G.Juve, A. Chervenak, E. Deelman, et al. Characterization and profiling scientific workflows. Future Generation Computation Systems, 2013,29(3):682-692.
[123]A.Iosup, C. Dumitrescu, D. H. J. Epema,et al."How are real grids used? the analysis of four grid traces and its implications," In Proceedings of IEEE Conference on Grid Computing,2006,262-269.
[124]R. Buyya, M. Murshed, D. Abramson,et al. Scheduling parameter sweep applications on global grids:a deadline and budget constrained cost-time optimization algorithm[J].Software Practice and Experiences,2005,35:491-512.
[125]苑迎春,李小平,王茜,等.成本约束的网格工作流时间优化方法[J].计算机研究与发展,2009,46(2):194-201.
[126]M. Lin, Z.Lin. A cost-effective critical path approach for service priority selections in grid computing economy[J]. Decision Support Systems,2006,42(3): 1628-1640.
[127]C. Akkan, A.Drexl, A. Kimms.Network decomposition-based benchmark results for the discrete time-cost tradeoff problem[J]. European Journal of Operational Research,2005,165(2):339-358.
[128]Z.Yu, W.Shi. A Planner-Guided Scheduling Strategy for Multiple Workflow Applications [C]. In Proceedings of the 37th International Conference on Parallel Processing Workshops,2008:1-8.
[129]Y.Yan, B.M.Chapman.Workflow Support in a GRACCE Meta-scheduling Architecture [EB/OL],http://www.cs.uh.edu/-yahyh/pubs/workflow-Support-icde.pdf,2009-02.
[130]D.Nurmi, A. Mandal, J. Brevik,et al.Evaluation of a Workflow Scheduler Using Integrated Performance Modelling and Batch Queue Wait Time Prediction. In Proceedings of the ACM/IEEE Conference on Supercomputing,2006:119.
[131]L. Slothouber. A Model of Web Server Performance[C]. In Proceedings of 5th International World Wide Web Conference,1996.
[132]T. Abdelzaher, K.G Shin, N. Bhatti. Performance Guarantees for Web Server End-systems[J]. A Control theoretical Approach. IEEE Transactions on Parallel and Distributed Systems,2002,13(1):80-96.
[133]R. Levy, J.Nagarajarao, GPacifici, et al. Performance Management for Cluster Based Web Services [C]. In Proceedings of IFIP/IEEE 8th International Symposium on Integrated Network Management,2003.
[134]D.Menasce. Web Server Software Architectures [J]. IEEE Internet Computing, 2003,7(6):78-81.
[135]A.Kamra, V.Misra, E.M.Y. Nahum. A Self-tuning Controller for Managing the Performance of 3-tired Web Sites [C]. In Proceedings of 12th International Workshop on Quality of Service,2004, Passau, Germany.
[136]P.Cremonesi, R. Turrin, V.N. Alexandrov.Modeling the Effects of Node Heterogeneity on the Performance of Grid Applications [J]. Journal of Networks,2009,4(9):837-854.
[137]Z.G. Hu, P. Xiao. A Novel Resource Co-allocation Model with Constraints to Budget and Deadline in Computational Grid [J]. Journal of Central South University of Technology,2009,16(3):458-466.
[138]李玺,胡志刚,胡周君,等.基于截止时间满意度的网格工作流调度算法.计算机研究与发展,2011,48(5):877-884.
[139]M. Wu, X.H. Sun, Y. Chen. QoS Oriented Resource Reservation in Shared Environments. In Proceedings of IEEE/ACM International Symposium on Cluster Computing and the Grid,2006.
[140]M.Kalantari, M.K. Akbari. A parallel solution for scheduling of real time applications on grid environments [J]. Future Generation Computer Systems, 2009,25:704-716.
[141]唐应辉,唐小我.排队论--础与分析技术[M].北京:科学出版社,2006:26-29.
[142]U.Lublin, D.G. Feitelson. The Workload on Parallel Supercomputers:Modeling the Characteristics of Rigid Jobs[J]. Journal of Parallel and Distributed Computing,2003,63(11):1105-1122.
[143]A.Iosup, M. Jan, O. O. Sonmez, et al. The Characteristics and the Performance of Groups of Jobs in Grids [J]. Lecture Notes on Computer Science,2007, 4641,pp.382-393.
[144]姚磊,戴冠中,张慧翔,等.QoS约束下基于双向分层的网格工作流调度算 法[J].计算机科学,2009,36(9):24-27.
[145]L.Ramakrishnan, C.Koelbel, Y.Kee, et al. VGrADS:enabling e-Science workflows on grids and clouds with fault tolerance. In Proceedings of ACM/IEEE SuperComputing Conference (SC), Portland, Oregon, USA,2009.
[146]Y. Zhang, A. Mandal, C. Koelbel, et al. Combined Fault Tolerance and Scheduling Techniques for Workflow Applications on Computational Grids. In proceedings of 9th IEEE/ACM International Symposium on Cluster Computing and the Grid,2009,244-251.
[147]Q.Kalim, GK. Fiaz, M.Paul, et al. A hybrid fault tolerance technique in grid computing system[J]. The Journal of Supercomputing,2011,56(1):106-128.
[148]秦啸,韩宗芬,庞丽萍.基于异构分布式系统的实时容错调度算法[J].计算机学报,2002,25(1):49-56.
[149]金海,陈刚,赵美平.容错计算网格作业调度模型的研究[J].计算机研究与发展,2004,41(8):1382-1388.
[150]Y.He, Z. Shao, B.Xiao, et al. Reliability driven task scheduling for heterogeneous systems [C].In Proceedings of the 15th IASTED International conference on Parallel and Distributed Computing and Systems,2003,465-470
[151]陶永才.网格环境下作业可靠调度机制的研究[D],华中科技大学,2009.
[152]G Levitin, Y.S. Dai, B.H.Hanoch.Reliability and Performance of Star Topology Grid Service with Precedence Constraints on Subtask Execution[J]. IEEE Transactions on Reliability,2006,55(3):507-515.
[153]Y.S. Dai, G. Levitin. Reliability and Performance of Tree Structured Grid Services[J].IEEE Transactions on Reliability,2006,55(2):337-349.
[154]S.C. Guo, H.Z. Huang, Z.L. Wang, et al. Grid service reliability modeling and optimal task scheduling considering fault recovery[J]. IEEE Transactions on Reliability,2011,60(1):263-273.
[155]肖鹏,胡志刚.一种扩展的虚拟树型网格可靠性评估模型[J].小型微型计算机系统,2009,30(8):1571-1575.
[156]R. Strijkers, W. Toorop, A. van Hoof, et al. AMOS:Using the Cloud for On-Demand Execution of e-Science Applications[C]. In Proceedings of the 6th International Conference on e-Science,2010:331-338.
[157]L.F. Bittencourt, C.R. Senna, E.R.M. Madeira. Enabling execution of service workflows in grid/cloud hybr id systems [C]. In Proceedings of International Conference on Network Operations and Management Symposium, 2010:343-349.
[158]S. Ostermann, R. Prodan, T. Fahringer. Resource Management for Hybrid Grid and Cloud Computing. In:Cloud Computing:Computer Communications and Networks[M]. Berlin:Springer Press,2010.
[159]L. Ramakrishnan, C. Koelbel, Y. Kee, et al. VGrADS:Enabling e-Science Workflows on Grids and Clouds with Fault Tolerance[C]. In Proceedings of the ACM/IEEE SC Conference on High Performance Computing, Networking, Storage and Analysis,2009:369-376.
[160]C. Vecchiola, R.N. Calheiros, D. Karunamoorthy, et al. Deadline-driven provisioning of resources for scientific applications in hybrid clouds with Aneka[J]. Future Generation Computer Systems,2012,28:58-65.
[161]H. Kim, Y.E1 Khamra, I.Rodero, et al. Autonomic management of application workflows on hybrid computing infrastructure[J]. Scientific Programming 19(2-3):75-89 (2011)
[162]M.A. Salehi, R.Buyya. Adapting Market Oriented Scheduling Policies for Cloud Computing[C]. In Proceedings of 10th International Conference on Algorithms and Architectures for Parallel Processing,2010:351-362.
[163]M. Assuncao, A.Costanzo, R. Buyya. Evaluating the cost-benefit of using cloud computing to extend the capacity of clusters[C]. In Proceedings of ACM. Symposium on High performance distributed computing,2009,141-150.
[164]Y.C. Lee, A.Y. Zomaya. Rescheduling for reliable job completion with the support of clouds[J]. Future Generation Computer Systems,2010,26:1192-1199.
[165]H. Kim, Y.el Khamra, I. Rodero, et al. Autonomic management of application workflows on hybrid computing infrastructure [J]. Scientific Programming, 2011,19:75-89.
[166]C.Vazquez, E. Huedo, R.S. Montero, et al. Dynamic provision of computing resources from grid infrastructures and cloud providers[C]. In Proceedings of the Workshop at the Grid and Pervasive Computing Conference,2009:113-120.
[167]L.F. Bittencourt, C.R. Senna, E.R.M. Madeira. HCOC:a cost optimization algorithm for workflow scheduling in hybrid clouds [J]. Journal of Internet Services and Applications,2011,2:207-227.
[168]L.F. Bittencourt, E.R.M. Madeira. A performance oriented adaptive scheduler for dependent tasks on grids[J]. Concurrency and Computation:Practice and Experience,2008,20(9):1029-1049.
[169]Web Services Architecture[EB/OL]. http://www.w3.org/TR/ws-arch/, 2004-2-11.
[170]K. Karasavvas, M. Antonioletti, M. Atkinson, et al. Introduction to OGSA-DAI Services[J].Lecture Notes in Computer Science,2005,3458,1-12.
[171]T. Metsch, A. Edmonds, R. Nyren,et al. Open Cloud Computing Interface Core[C].In Open Grid Forum,2010, http://forge.gridforum.org/sf/go/doc16161.
[172]Cloud Speed Test[EB/OL]. http://cloudharmony.com/speedtest
[173]Cloudsigma[EB/OL]. http://www.cloudsigma.com/.