网格任务调度中服务质量保证相关问题研究
|
摘要
网格是一种先进的信息技术基础设施,目的是有效整合Internet上广泛分布的各种计算资源、存储资源、通信资源、信息资源等,向用户提供虚拟、统一、透明的计算环境。网格的重要性已经受到多个国家和政府的关注,并吸引了大量的研究。合理、有效地调度网格任务可以充分利用网格资源,提高系统效率,更好地完成用户的网格应用,因此网格任务调度问题成为网格研究的重要内容之一。随着开放网格服务体系结构(OGSA)标准的确立,“面向服务”成为近些年网格发展的方向,服务质量(QoS)成为网格任务调度过程中必须要考虑的一个重要因素。“网格之父”Ian Foster更是把提供非平凡的服务质量作为网格的判断标准之一。由于网格具有动态性和自治性的特点,QoS保证是一项非常复杂和具有挑战性的工作。资源预留是实现QoS保证的有效手段,但也会产生“资源碎片问题”,影响非预留任务的完成效果。如何在有效使用资源预留的同时减少它所带来的不良后果成为一个很有意义的研究内容。网格经济(Grid Economy)的出现为网格资源管理提供了一个公共的解决方案,其中双向拍卖模型被广泛地应用于网格资源分配中。但目前基于双向拍卖的网格资源分配和任务调度大多直接使用经济学领域中已有的拍卖理论,仅仅关注于用户的经济收益,而对服务质量的有效保证重视不够。目前,服务网格是网格构建的主流方向之一。在服务网格环境下,调度器需要根据用户的即时要求,动态地把大量临时性的网格服务组合为可增值的复合服务。因此,需要一种服务调度机制来实现网格服务的组合、匹配,同时向用户提供所需的服务质量。
本文针对在网格任务调度过程中与服务质量保证相关的若干问题进行了研究,具体工作从对服务质量保证的“事先规划”和“事中注意”两个方面开展。前者涉及了与资源预留相关的任务调度问题；后者聚焦于如何把用户服务质量需求映射到基于经济机制的资源分配和网格服务调度中。本文取得的主要创新成果如下：
1.提出了一种模糊的网格资源预留机制FRRM。传统的资源预留机制在预留任务实际使用资源之前就完成了资源分配,无法应对在预留提前时间内资源的动态变化。FRRM能够感知预留提前时间内资源状态的变化,根据资源的运行时信息动态地调度已接纳的预留请求。引入了资源-预留图对FRRM下的预留请求接纳控制以及预留任务调度策略进行描述,分析了FRRM对资源故障的容错性。分别在模拟任务集和真实任务集上进行了FRRM和传统预留机制的对比实验。实验结果表明FRRM能够显著减小任务抢占代价,有效提高资源利用率,对网格的动态环境具有更好的适应性。
2.给出了当存在资源预留时,针对于抢占式任务和非抢占式任务的调度策略。前者可以通过对已有调度策略的改进来实现；后者则被建模为一个多组装箱(Multi-line Bin Packing, MBP)问题。提出了Multi2Single算法把MBP问题转化为具有相同最优化目标的单组装箱(Single-line Bin Packing, SBP)问题,并在经典装箱(Bin Packing, BP)问题研究的基础上给出了解决SBP问题的启发式装箱算法。通过理论分析和模拟实验对装箱算法的最坏情况渐近性能比和平均性能比进行了分析。与传统的调度算法Mim-min和Suffrage相比,我们提出的算法可以明显减小非预留任务的最大调度长度(makespan),有效缓冲了预留任务对非预留任务调度目标的不良影响。
3.提出了一种面向可量化网格资源的贪心双向拍卖协议GDAP和一种面向网格服务的服务质量可保证的双向拍卖协议QDAP。证明了GDAP具有策略性防伪、个人理性和弱预算平衡的特点。与传统的基于MDA (Multi-unit Double Auction)的拍卖策略相比,GDAP在兼顾经济效益的同时能够大大提高网格资源利用率及用户满意率,有利于实现网格大规模资源共享的目标。QDAP首次把服务质量引入到双向拍卖协议中,在最大化服务利用率的同时向消费者提供有效的服务质量支持。把QDAP与传统的双向拍卖策略PMDA和CDA进行了实验对比,结果表明QDAP具有更好的拍卖公平性、较高的服务利用率,更加适应于服务网格环境。
4.研究了具有多QoS约束的网格服务调度问题。以移动Agent作为应用的载体,通过移动Agent在不同服务实例之间的迁移来满足用户对复合网格服务的访问需求。提出了一种多QoS约束下基于蚂蚁算法的移动Agent路由算法(MRBAA), MRBAA支持移动Agent对多个服务的并行访问,并考虑了服务间的数据交互。在MRBAA下,移动Agent以最大化用户效用为目标进行迁移,同时兼顾用户的QoS需求。与快速贪心算法和随机选择算法的对比实验表明,MRBAA在调度成功率和提供的效用方面都具有更好的效果。
Grid is an advanced infrastructure of information technology. It aims at efficiently integrating computational resources, storage resources, communication resources and information resources to provide a virtual, uniform and transparent computing envi-ronment for users. The importance of Grid has drawn much attention from many countries and governments and has attracted lots of research. Scheduling grid tasks properly and efficiently can make full use of grid resources, improve system efficiency and satisfy users'applications. Thus, task scheduling has become one of the most im-portant areas of grid research. With the foundation of Open Grid Service Architecture (OGSA), Grid technology has been developing to the "service-oriented" direction and service of quality (QoS) becomes an important factor that should be considered when scheduling grid tasks. Moreover, Ian Foster, "the father of the Grid", takes providing non-trivial QoS as an important judging criterion of grid. Because of the dynamic and autonomous features of grid, it is a hard and challenging problem to guarantee QoS. Though resource reservation is an effective means to provide QoS guarantee, it will cause the problem of "resource fragmentations" and influence the completion of non-reservation tasks. It is meaningful to study how to make use of resource reservations while decreasing their negative impacts. Grid economy provides a general solution for resource management and especially double auction model has been applied to grid resource allocation widely. However, most double auction based resource allocation and task scheduling use the auction theory in economy area directly, only caring about users'economic profit rather than effective QoS guarantee. Recently, service grid is the mainstream direction to construct grid system. In the service grid environment, the scheduler needs to dynamically integrate lots of temporary grid services into com-posite services according to users'immediate requirements. Thus, we need a service scheduling mechanism to realize the matching and composition of grid services and provide users with the required QoS. We have done research on the problems related to QoS guarantee during task scheduling and the actual work develops in two aspects: "planning in advance" and "attention in process". The former is concerned with task scheduling related to resource reservation; the latter focus on how to map the users' QoS requirements into economy based resource allocation and grid service scheduling. The achievements of this paper are as follows.
1. A fuzzy grid resource reservation mechanism, FRRM, is put forward. Under tra-ditional resource reservation mechanism the resource allocation happens before the reservation tasks actually use the resources, which can not deal with the dy-namic change of resources during the book-ahead time. FRRM is able to perceive the resource change during the book-ahead time, schedule the accepted reserva-tion requests dynamically according to the resources' run-time information. The resource-reservation graph is introduced to describe the admission control and reservation scheduling strategy under FRRM, and FRRM's fault tolerance to resource error is also studied.
2. The scheduling strategies for preemptable and non-preemptable tasks are pre-sented. The former can be obtained by modifying the existing scheduling strat-egy while the latter is modeled as a Multi-line Bin Packing (MBP) problem. Multi2Single algorithm is put forward to transform the MBP problem to a Single-line Bin Packing (SBP) problem. Based on the existing research on the classic BP problem, we put forward heuristics to solve the SBP problem. Moreover, theo-retical analysis and experimental simulation have also been performed to analyze and compare the worse-case and average-case performances of these algorithms. Compared with traditional Min-min and Suffrage, our algorithms can reduce the makespan considerably and buffer the negative impacts of reservation tasks on non-reservation tasks effectively.
3. A Greedy Double Auction Protocol (GDAP) is presented to deal with quan-tifiable grid resources and a Qos-enabled Double Auction Protocol (QDAP) is presented to deal with grid services. We have proven that GDAP has the fea-tures of strategy-proof, individual rational and weak budget-balance. Compared with traditional auction strategy based on MDA, GDAP can improve the resource utilization and user satisfaction percentage considerably, in accordance with the large scale resource sharing target of grid. QDAP first introduces QoS into double auction protocol and aims at maximizing the service utilization while providing effective QoS guarantee for consumers. Experiments have been performed to compare QDAP with PMDA and CDA and the results show that QDAP leads to a better auction fairness and a higher service utilization; thus, it is more suitable for the service grid.
4. We have researched the service scheduling problem under multi QoS constraints. We use mobile agent as the application carrier and the user's requirements for composite grid services are met through the migration of mobile agent between service instances. A routing algorithm with QoS constraints based on ant al-gorithm for mobile agent (MRBAA) is put forward. MRBAA supports mobile agent's parallel access to grid services and takes into account the data exchange between services. Under MRBAA, the mobile agent migrates in the purpose of maximizing the user's utility while considering the user's QoS requirements. Compared with the fast greedy algorithm and the random selection algorithm, MRBAA outperforms them in the aspects of both successful scheduling percent-age and utility.
本文针对在网格任务调度过程中与服务质量保证相关的若干问题进行了研究,具体工作从对服务质量保证的“事先规划”和“事中注意”两个方面开展。前者涉及了与资源预留相关的任务调度问题；后者聚焦于如何把用户服务质量需求映射到基于经济机制的资源分配和网格服务调度中。本文取得的主要创新成果如下：
1.提出了一种模糊的网格资源预留机制FRRM。传统的资源预留机制在预留任务实际使用资源之前就完成了资源分配,无法应对在预留提前时间内资源的动态变化。FRRM能够感知预留提前时间内资源状态的变化,根据资源的运行时信息动态地调度已接纳的预留请求。引入了资源-预留图对FRRM下的预留请求接纳控制以及预留任务调度策略进行描述,分析了FRRM对资源故障的容错性。分别在模拟任务集和真实任务集上进行了FRRM和传统预留机制的对比实验。实验结果表明FRRM能够显著减小任务抢占代价,有效提高资源利用率,对网格的动态环境具有更好的适应性。
2.给出了当存在资源预留时,针对于抢占式任务和非抢占式任务的调度策略。前者可以通过对已有调度策略的改进来实现；后者则被建模为一个多组装箱(Multi-line Bin Packing, MBP)问题。提出了Multi2Single算法把MBP问题转化为具有相同最优化目标的单组装箱(Single-line Bin Packing, SBP)问题,并在经典装箱(Bin Packing, BP)问题研究的基础上给出了解决SBP问题的启发式装箱算法。通过理论分析和模拟实验对装箱算法的最坏情况渐近性能比和平均性能比进行了分析。与传统的调度算法Mim-min和Suffrage相比,我们提出的算法可以明显减小非预留任务的最大调度长度(makespan),有效缓冲了预留任务对非预留任务调度目标的不良影响。
3.提出了一种面向可量化网格资源的贪心双向拍卖协议GDAP和一种面向网格服务的服务质量可保证的双向拍卖协议QDAP。证明了GDAP具有策略性防伪、个人理性和弱预算平衡的特点。与传统的基于MDA (Multi-unit Double Auction)的拍卖策略相比,GDAP在兼顾经济效益的同时能够大大提高网格资源利用率及用户满意率,有利于实现网格大规模资源共享的目标。QDAP首次把服务质量引入到双向拍卖协议中,在最大化服务利用率的同时向消费者提供有效的服务质量支持。把QDAP与传统的双向拍卖策略PMDA和CDA进行了实验对比,结果表明QDAP具有更好的拍卖公平性、较高的服务利用率,更加适应于服务网格环境。
4.研究了具有多QoS约束的网格服务调度问题。以移动Agent作为应用的载体,通过移动Agent在不同服务实例之间的迁移来满足用户对复合网格服务的访问需求。提出了一种多QoS约束下基于蚂蚁算法的移动Agent路由算法(MRBAA), MRBAA支持移动Agent对多个服务的并行访问,并考虑了服务间的数据交互。在MRBAA下,移动Agent以最大化用户效用为目标进行迁移,同时兼顾用户的QoS需求。与快速贪心算法和随机选择算法的对比实验表明,MRBAA在调度成功率和提供的效用方面都具有更好的效果。
Grid is an advanced infrastructure of information technology. It aims at efficiently integrating computational resources, storage resources, communication resources and information resources to provide a virtual, uniform and transparent computing envi-ronment for users. The importance of Grid has drawn much attention from many countries and governments and has attracted lots of research. Scheduling grid tasks properly and efficiently can make full use of grid resources, improve system efficiency and satisfy users'applications. Thus, task scheduling has become one of the most im-portant areas of grid research. With the foundation of Open Grid Service Architecture (OGSA), Grid technology has been developing to the "service-oriented" direction and service of quality (QoS) becomes an important factor that should be considered when scheduling grid tasks. Moreover, Ian Foster, "the father of the Grid", takes providing non-trivial QoS as an important judging criterion of grid. Because of the dynamic and autonomous features of grid, it is a hard and challenging problem to guarantee QoS. Though resource reservation is an effective means to provide QoS guarantee, it will cause the problem of "resource fragmentations" and influence the completion of non-reservation tasks. It is meaningful to study how to make use of resource reservations while decreasing their negative impacts. Grid economy provides a general solution for resource management and especially double auction model has been applied to grid resource allocation widely. However, most double auction based resource allocation and task scheduling use the auction theory in economy area directly, only caring about users'economic profit rather than effective QoS guarantee. Recently, service grid is the mainstream direction to construct grid system. In the service grid environment, the scheduler needs to dynamically integrate lots of temporary grid services into com-posite services according to users'immediate requirements. Thus, we need a service scheduling mechanism to realize the matching and composition of grid services and provide users with the required QoS. We have done research on the problems related to QoS guarantee during task scheduling and the actual work develops in two aspects: "planning in advance" and "attention in process". The former is concerned with task scheduling related to resource reservation; the latter focus on how to map the users' QoS requirements into economy based resource allocation and grid service scheduling. The achievements of this paper are as follows.
1. A fuzzy grid resource reservation mechanism, FRRM, is put forward. Under tra-ditional resource reservation mechanism the resource allocation happens before the reservation tasks actually use the resources, which can not deal with the dy-namic change of resources during the book-ahead time. FRRM is able to perceive the resource change during the book-ahead time, schedule the accepted reserva-tion requests dynamically according to the resources' run-time information. The resource-reservation graph is introduced to describe the admission control and reservation scheduling strategy under FRRM, and FRRM's fault tolerance to resource error is also studied.
2. The scheduling strategies for preemptable and non-preemptable tasks are pre-sented. The former can be obtained by modifying the existing scheduling strat-egy while the latter is modeled as a Multi-line Bin Packing (MBP) problem. Multi2Single algorithm is put forward to transform the MBP problem to a Single-line Bin Packing (SBP) problem. Based on the existing research on the classic BP problem, we put forward heuristics to solve the SBP problem. Moreover, theo-retical analysis and experimental simulation have also been performed to analyze and compare the worse-case and average-case performances of these algorithms. Compared with traditional Min-min and Suffrage, our algorithms can reduce the makespan considerably and buffer the negative impacts of reservation tasks on non-reservation tasks effectively.
3. A Greedy Double Auction Protocol (GDAP) is presented to deal with quan-tifiable grid resources and a Qos-enabled Double Auction Protocol (QDAP) is presented to deal with grid services. We have proven that GDAP has the fea-tures of strategy-proof, individual rational and weak budget-balance. Compared with traditional auction strategy based on MDA, GDAP can improve the resource utilization and user satisfaction percentage considerably, in accordance with the large scale resource sharing target of grid. QDAP first introduces QoS into double auction protocol and aims at maximizing the service utilization while providing effective QoS guarantee for consumers. Experiments have been performed to compare QDAP with PMDA and CDA and the results show that QDAP leads to a better auction fairness and a higher service utilization; thus, it is more suitable for the service grid.
4. We have researched the service scheduling problem under multi QoS constraints. We use mobile agent as the application carrier and the user's requirements for composite grid services are met through the migration of mobile agent between service instances. A routing algorithm with QoS constraints based on ant al-gorithm for mobile agent (MRBAA) is put forward. MRBAA supports mobile agent's parallel access to grid services and takes into account the data exchange between services. Under MRBAA, the mobile agent migrates in the purpose of maximizing the user's utility while considering the user's QoS requirements. Compared with the fast greedy algorithm and the random selection algorithm, MRBAA outperforms them in the aspects of both successful scheduling percent-age and utility.
引文
[1]I. Foster, C. Kesselman. The Grid:Blueprint for a Future Computing Infras-tructure. Morgan Kaufmann Publishers,1999.
[2]I. Foster. Grid technologies & applications:Architecture & achievements. In International Conference on Computing in High Energy and Nuclear Physics. 2001.
[3]I. Foster, C. Kesselman, J. M. Nick, et al. The physiology of the grid:An open grid serivices architecture for distributed systems integration. In Grid computing: Making the global infrastructure a reality, pages 217-250. John Wiley & Sons, 2003.
[4]徐志伟,冯百明,李伟.网格计算技术.电子工业出版社,北京,2004.
[5]D. D. Roure, M. A. Baker, N. R. Jennings, et al. The evolution of the grid. In Grid Computing:Making The Global Infrastructure a Reality, pages 65-100. John Wiley & Sons,2003.
[6]FAFNER:Factoring via Network-Enabled Recursion. http://cs-www.bu.edu/cgi-bin/FAFNER/factor.pl.
[7]I. Foster, J. Geisler, S. Tuecke. Mpi on the i-way:A wide-area, multimethod implementation of the message passing interface. In Proceedings of the 1996 MPI Developers Conference, pages 10-17.1996.
[8]I. Foster, J. Geisler, B. Nickless, et al. Software infrastructure for the i-way high-performance distributed computing experiment. In Proceedings of the 5th IEEE International Symposium on High Performance Distributed Computing, page 562. IEEE Computer Society,1996.
[9]SETI@home. http://setiathome.ssl.berkeley.edu/.
[10]Distributed.net. http://www.distributed.net/.
[11]I. Foster, C. Kesselman. Globus:A metacomputing infrastructure tookit. The International Journal of Supercomputer Applications,11(2):115-128,1997.
[12]Legion. http://www.cs.virginia.edu/legion/.
[13]I. Foster, C. Kesselman, J. Nick, et al. The physiology of the grid:An open grid services architecture for distributed systems integration. http://www. globus. org/research/papers/ogsa.pdf,2002.
[14]S. Tuecke, K. Czajkowski, I. Foster, et al. Open grid service infrastructure(ogsi). Technical report, OGSI-WG, Global Grid Forum,2003.
[15]K. Czajkowski, D. Ferguson, I. Foster, et al. From open grid ser-vices infrastructure to ws-resource framework:Refactoring & evolution. http://www.globus. org/wsrf/,2004.
[16]European Data Grid.http://www.eu-datagrid.org/.
[17]http://ninf.apgrid.org/.
[18]Bricks.http://ninf.apgrid.org/bricks/.
[19]http://www.gridlab.org/WorkPackages/wp-1/collaboration.html#N*Grid.
[20]J. N. Cao, A. T. S. Chan, Y. D. Sun, et al. A taxonomy of application scheduling tools for high performance cluster computing. In Cluster Computing. Nether-lands:Kluwer Academic Publishers,2004.
[21]J.Nabrzyski, J. M. Schope, J. Weglarz. Grid Resource Management:State of the Art and Future Trends. Springer-Verlag:Kluwer Academic Publishers,2003.
[22]W. Smith, I. Foster, V. Taylory. Scheduling with advanced reservations. In J. D. P. Rolim, editor, Proceedings of the 14th International Parallel and Distributed Processing Symposium, pages 127-132. Cancun, Mexico, May 2000.
[23]U. Farooq, S. Majumdar, E. W. Parsons. Efficiently scheduling advance reser-vations in grids. Technical Report SCE-05-14, Dept. of Systems and Computer Engineering, Carleton University, August 2005.
[24]H. Casanova, A. Legrand, et al. Heuristics for scheduling parameter sweep appli-cations in grid environments. In Proceedings of the 9th Heterogeneous Computing Workshop(HCW), pages 349-363.2000.
[25]R. f. Freund, M. Gherrity, et al. Scheduling resources in multi-user,heterogeneous,computing environments with smartnet. In Proceedings of HCW'98, pages 184-199. March 1998.
[26]T. D. Braun, H. J. Siegel, N. Beck. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing,61(6):810-837,2001.
[27]M. Maheswaran, S. Ali. Dynamic matching and scheduling of a class of inde-pendent tasks onto heterogeneous computing syetems. In Proceedings of the 8th IEEE Heterogeneous Computing Workshop(HCW'99). IEEE Computer Society Press, San Juan, Puerto Rico, April 1999.
[28]J. E. Biegel, J. J. Davern. Genetic algorithms and job shop scheduling. Computers & Industrial Engineering,19(1-4):81-91,1990.
[29]I. Ahmad, K. Dhodhi. Multiprocessor scheduling in a genetic paradigm. Parallel Computing,22(3):395-406,1996.
[30]K. Steinofel, A. Albrecht, C. K. Wong. Two simulated annealing-based heuristics for the job shop scheduling problem. European Journal of Operational Research, 118(3):524-548,1999.
[31]Y. Liu, H. He. Multi-unit combinatorial auction based grid resource co-allocation approach. In Proceedings of the 3rd International Conference on Semantics, Knowledge, and Grid.2007.
[32]R. Gonen, D. Lehmann. Optimal solutions for multi-unit combinatorial auc-tions:Branch and bound heuristics. In Proceedings of the ACM Conference in Electronic Commerce, pages 13-20.2000.
[33]H. Topcuoglu, S. Hariri, M. Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems,13(3):260-274,2002.
[34]A. Radulescu, A. J. C. van Gemund. On the complexity of list scheduling algo-rithms for distributed memory systems. In Proceedings of the 13th International Conference on Super computing, pages 68-75. Portland, Oregon, USA, November 1999.
[35]S. Darbha, D. P. Agrawal. Optimal scheduling algorithm for distributed memory machines. IEEE Trans, on Parallel and Distributed Systems,9(1):87-95,1998.
[36]S. Ranaweera, D. P. Agrawal. A task duplication based scheduling algorithm for heterogeneous systems. In Proceedings of the 14th International Parallel and Distributed Processing Symposium, pages 445-450. Cancun, Mexico, May 2000.
[37]R. Bajaj, D. P. Agrawal. Improving scheduling of tasks in a heterogeneous envi-ronment. IEEE Transactions on Parallel and Distributed Systems,15(2):107-118, 2004.
[38]T. Yang, A. Gerasoulis. Dsc:Scheduling parallel tasks on an unbounded number of processors. IEEE Trans. on Parallel and Distributed Systems,5(9):951-967, 1994.
[39]J. Liou, M. A. Palis. An efficient task clustering heuristic for scheduling dags on multiprocessors. In Proceedings of Workshop on Resource Manage-ment, Symposium of Parallel and Distributed Processing.1996.
[40]R. Buyya. Economic-based distributed resource management and scheduling for grid computing. Ph.D. thesis, Monash University, Melbourne, Australia,2002.
[41]A. Dogan, F. Ozgiiner. Scheduling of a meta-task with qos requirements in het-erogeneous computing systems. Journal of Parallel and Distributed Computing, 66(2):181-196,2006.
[42]K. Guo, L. Sun, S. Jia. Utility function based fair data scheduling algorithm for ofdm wireless network. Journal of Systems Engineering and Electronics, 18(4):731-738, December 2007.
[43]C. S. Yeo, R. Buyya. A taxonomy of market-based resource management sys-tems for utility-driven cluster computing. Software:Practice and Experience, 36(13):1381-1419,2006.
[44]F. Berman, R. Wolski. The apples project:A status report. In Proceedings of the 8th NEC Research Symposium. May 1997.
[45]F. Berman, R. Wolski, S. Figueira, et al. Application level scheduling on dis-tributed heterogeneous networks. In Proceedings of Supercomputing'96.1996.
[46]R. Wolski. Forecasting network performance to support dynamic scheduling using the network weather service. In Proceedings of 6th IEEE International Symposium on High Performance Distributed Computing.1997.
[47]R. Buyya, D. Abramson, J. Giddy. Nimrod/g:An architecture for a resource management and scheduling system in a global computational grid. In Pro-ceedings of 4th International Conference on High Performance Computing in Asia-Pacific Region.2000.
[48]R. Buyya, M. Murshed. Gridsim:a toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. The Jour-nal of Concurrency and Computation:Practice and Experience(CCPE),14(13-15):1175-1220,2002.
[49]J. Frey, T. Tannenbaum, M. Livny, et al. Condor-g:A computation management agent for multi-institutional grids. In Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing.2001.
[50]I. Foster. What is the grid? a three point checklist. Grid Today,1(6):22, July 2002.
[51]R. Buyya, D. Abramson, S. Venugopal. The grid economy.93(3):698-714, March 2005.
[52]I. Foster, C. Kesselman, e. a. C. Lee. A distributed resource management architecture that supports advance reservations and co-allocation. In Proceedings of the International Workshop on Quality of Service (IWQoS'99), pages 27-36. London,1999.
[53].沃天宇,雷磊.一种支持端到端qos的服务网格体系结构.软件学报,17(6)：1448-1458,2006.
[54]J. Leigh, T. A. DeFanti, A. E. Johnson, et al. Global tele-immersion:Better than being there. In Proceedings of the 7th International Conference on Artificial Reality and Tele-Existence, pages 10-17. Dec 1997.
[55]L. C. Wolf, R. Steinmetz. Concepts for resource reservation in advance. Multi-media Tools and Applications,4(3):255-278,1997.
[56]U. Schwiegelshohn, R. Yahyapour, P. Wieder. Resource management for future generation grids. Technical Report TR-0005, Institute on Resource Management and Scheduling, CoreGRID-Network of Excellence, May 2005.
[57]J. Cao, F. Zimmermann. Queue scheduling and advance reservations with cosy. In Proceedings of the 18th Intl. Parallel and Distributed Processing Symposium. April 2004.
[58]S. McGough, L. Young, A. Afzal, et al. Workflow enactment in iceni. In Proceed-ings of the UK e-Science All Hands Meeting. September 2004.
[59]Load Sharing Facility platform. http://www.platform.com/products/LSF/.
[60]D. Jackson, Q. Snell, M. Clement. Core algorithms of the maui scheduler. Job Scheduling Strategies for Parallel Processing,2221:87-102,2001.
[61]LoadLeveler. http://publib.boulder.ibm.com/epubs/pdf/c2366810.pdf.
[62]A. Sulistio, R. Buyya. A grid simulation infrastructure supporting advance reser-vation. In Proceedings of the 16th International Conference on Parallel and Dis-tributed Computing and Systems. Nov 2004.
[63]A. W. Mu'alem, D. G. Feitelson. Utilization, predictability, workloads, and run-time user estimates in scheduling the ibm sp2 with backfilling. IEEE Transac-tions on Parallel and Distributed Systems,12(6):529-543, June 2001.
[64]U. Farooq, S. Majumdar, E. W. Parsons. Impact of laxity on scheduling with advance reservations in grids. In Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecom-munication Systems, pages 319-324. Atlanta, GA, USA, September 2005.
[65].沃天宇,雷磊.一种基于松弛时间的服务网格资源能力预留机制.计算机研究与发展,44(1)：20-28,2007.
[66]S. Naiksatam, S. Figueira. Elastic reservations for efficient bandwidth utilization in lambdagrids. Future Generation Computer Systems,23(1):1-22,2007.
[67]G. W. Group. Grid Resource Allocation Agreement Protocol. http://forge. gridforum. org/projects/gr aap-wg/.
[68]J. MacLaren. Advance reservations:State of the art. Technical Report ggf-draft-sched-graap-2.0, Global Grid Forum,2003.
[69]D. Kuo, M. Mckeown. Advance reservation and co-allocation protocol for grid computing. In Proceedings of the International Conference on e-Science and Grid Technologies, pages 164-171.2005.
[70]S. Tangpongprasit, T. Katagiri, K. Kise, et al. A time-to-live based reservation algorithm on fully decentralized resource discovery in grid computing. Parallel Computing,31(6):529-543,2005.
[71]PBS Professional, http://www.altair.com/software/pbspro.htm.
[72]T. Roblitz, F. Schintke, A. Reinefeld. Resource reservations with fuzzy re-quests. Concurrency and Computation:Practice and Experience,18(13):1681-1703,2006.
[73]G. M. Amdahl. Validity of the single-processor approach to achieving large scale computing capabilities. In Proceedings of the AFIPS Conference, pages 483-485. Atlantic City, N.J., USA, April 1967.
[74]R. Bajaj, D. P. Agrawal. Improving scheduling of tasks in a heterogeneous envi-ronment. IEEE Transactions on Parallel and Distributed Systems,15(2):107-118, 2004.
[75]M. Aggarwal, R. Kent, A. Ngom. Genetic algorithm based scheduler for compu-tational grids. In Proceedings of the 19th Annual International Symposium on High Performance Computing Systems and Applications, pages 209-215. Guelph, Ontario Canada, May 2005.
[76]http://www.cs.huji.ac.il/labs/parallel/workload/Losc/OSC-Clust-2000-2.1-cln.swf.gz.
[77]SWF. http://www.cs.huji.ac.il/labs/parallel/workload/swf.html.
[78]X. He, X. Sun, V. L. Gregor. Qos guided min-min heuristic for grid task schedul-ing. Journal of Computer Science and Technology,18(4):442-451,2003.
[79]L. Eyraud-Dubois, G. Mounie, D. Trystram. Analysis of scheduling algorithms with reservations. In Proceedings of 21st IEEE International Parallel and Dis-tributed Processing Symposium, pages 1-8. March 2007.
[80]F. Dong, S. G. Akl. Scheduling algorithms for grid computing:State of the art and open problems. Technical Report 2006-504, School of Computing, Queen's University, January 2006.
[81]E. Sanlaville, G. Schmidt. Machine scheduling with availability constraints. Acta Informatica,35(9):795-811,1998.
[82]G. Schmidt. Scheduling with limited machine availability. European Journal of Operational Research,121(1):1-15,2000.
[83]C. Y. Lee. Machine scheduling with an availability constraint. Journal of Global Optimization,9(3-4):395-416,1996.
[84]I. Kacem, C. Chu, A. Souissi. Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times. Computers and Operations Research,35(3):827-844,2008.
[85]P. Mauguiere, J. C. Billaut, J. L. Bouquard. New single machine and job-shop scheduling problems with availability constraints. Journal of Scheduling,8:211-231,2005.
[86]C. Castillo, G. N. Rouskas, K. Harfoush. On the design of online scheduling algorithms for advance reservations and qos in grids. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium, pages 1-10. Long Beach, California, USA, March 2007.
[87]B. Li, J. Chen, D. Zhao. Looking-ahead algorithms for single machine schedulers to support advance reservation of grid jobs. In Proceedings of the 10th IEEE In-ternational Conference on High Performance Computing and Communications, pages 335-341.2008.
[88]M. S. Netto, K. Bubendorfer, R. Buyya. Sla-based advance reservations with flexible and adaptive time qos parameters. In Lecture Notes in Computer Sci-ence (LNCS), proceedings of the International Conference on Service Oriented Computing, volume 4749. Springer Verlag, Vienna, Austria, September 2007.
[89]E. G. Coffman, M. R. Garey, D. S. Johnson. Approximation algorithms for bin packing:A survey, pages 46-93. Boston:PWS Publishing,1996.
[90]E. G. Coffman, G. Galambos, e. a. S. Martello. Bin packing approximation al-gorithms:Combinatorial analysis, pages 1-47. Norwell:Kluwer Academic Pub-lishers,1998.
[91]D. S. Johnson, A. Demers, J. D. Ullman, et al. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4):299-325,1974.
[92]G. Zhang. A new version of on-line variable-sized bin packing. Discrete Applied Mathematics,72(3):193-197,1997.
[93]E. G. Coffman, C. Courcoubetis, e. a. M. R. Garey. Perfect packing theorems and the average case behavior of optimal and online bin packing. SIAM Review, 44(1):95-108,2002.
[94]J. Csirik, D. S. Johnson. Bounded space on-line bin packing:Best is better than first. Algorithmica,31(2):115-138,2001.
[95]D. P. Anderson, J. Cobb, E. Korpela, et al. Seti@home:An experiment in public-resource computing. Communications of the ACM,45(11):56-61, November 2002.
[96]Rosetta@home. http://boinc.bakerlab.org/rosetta/.
[97]LHC@home. http://lhcathome.cern.ch/.
[98]E. Elmroth, P. Gardfjall. Design and evaluation of a decentralized system for grid-wide fairshare scheduling. In Proceedings of the First International Conference on e-Science and Grid Computing. December 2005.
[99]I. Foster, C. Kesselman, S. Tuecke. The anatomy of grid:Enabling scalable virtual organizations. International Journal of Supercomputer Applications, 15(3):200-222,2001.
[100]H. Casanova, J. Dongarra. Netsolve:A network server for solving computational science problems. International Journal of Supercomputing Applications and High Performance Computing, 11(3):212-223,1997.
[101]N. Kapadia, J. Fortes. Punch:An architecture for web-enabled wide-area network-computing. Cluster Computing:The Journal of Networks, Software Tools and Applications,2(2):153-164,1999.
[102]R. Buyya, D. Abramson, J. Giddy. Design and evaluation of a decentralized sys-tem for grid-wide fairshare scheduling. In Proceedings of the International Paral-lel and Distributed Processing Symposium:Heterogeneous Computing Workshop. San Francisco, California, USA,2001.
[103]D. Fudenberg, J. Tirole. Game Theory. MIT Press, Cambridge, Massachusetts, 1991.
[104]W. Vickrey. Counter-speculation, auctions, and competitive sealed tenders. Jour-nal of Finance,16(1):9-37,1961.
[105]I. E. Sutherland. A futures market in computer time. Communications of the A CM,11(6):449-451,1968.
[106]O. Regev, N. Nisan. The popcorn market-an online markets for computational resources. In Proceedings of the 1st International Conference on Information and Computation Economies, pages 148-157.1998.
[107]C. A. Waldspurger, T. Hogg, B. A. Huberman, et al. Spawn:A distributed computational economy. IEEE Transactions on Software Engineering,18(2):103-117,1992.
[108]S. Lalis, A. Karipidis. Jaws:An open market-based framework for distributed computing over the internet. In Proceedings of the 1st IEEE/ACM International Workshop on Grid Compuing. Bangalore, India,2000.
[109]K. Lai, L. Rasmusson, E. Adar, et al. Tycoon:an implemention of a distributed market-based resource allocation system. Technical report, HP Labs, USA, De-cember 2004.
[110]M. Frank. The ocean project:The open computation exchange & auctioning network. http://www.cise.uft.edu/research/ocean.
[111]S. Mark, W. Steven. The rate of convergence to efficiency in the buyer's bid double auction as the market becomes large. The Review of Economic Studies, 56(4):477-498,1989.
[112]W. Steven. Existence and convergence of equilibria in the buyer's bid double auction. The Review of Economic Studies,58(2):351-374,1991.
[113]R. Mcafee. A dominant strategy double auction. Journal of Economic Theory, 56(2):434-450,1992.
[114]P. Huang, A. Scheller-Wolf, K. Sycare. Design of a multiunit double auction e-market. Computational Intelligence,18(4):596-617,2002.
[115]翁楚良,陆鑫达.一种基于双向拍卖机制的计算网格资源分配方法.计算机学报,29(6)：1004-1009,6 2006.
[116]U. Kant, D. Grosu. Double auction protocols for resource allocation in grids. In Proceedings of the International Conference on Information Technology:Coding and Computing.2005.
[117]C. Satayapiwat, R. Egawa, H. Takizawa, et al. A utility-based double auction mechanism for efficient grid resource allocation. In Proceedings of the Inter-national Symposium on Parallel and Distributed Processing with Applications, 2008, pages 252-260.2008.
[118]M. Wieczorek, S. Podlipnig, R. Prodan, et al. Applying double auctions for scheduling of scientific workflows on the grid. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. 2008.
[119]R. P. McAfee. A dominant strategy double auction. Journal of Economic Theory, 56(2):434-450,1992.
[120]Z. Tan. Market-based Grid Resource Allocation Using a Stable Continuous Double Auction. Ph.D. thesis, The University of Manchester, Manchester, UK,2007.
[121]Simple object access protocol(SOAP). http://www.w3.org/tr/soap/.
[122]W. Binder, I. Constantinescu, B. Faltings. Decentralized orchestration of compos-iteweb services. In Proceedings of the International Conference on Web Services, pages 869-876.2006.
[123]岳昆,王晓玲,周傲英.Web服务核心支撑技术：研究综述.软件学报,15(3)：428-442,2004.
[124]张伟哲,方滨兴,胡铭曾,张宏莉.基于信任qos增强的网格服务调度算法.计算机学报,29(7)：1157-1166,72006.
[125]L. Yutu, H. H. N. Anne, L. Zeng. Qos computation and policing in dynamic web service selection. In Proceedings of WWW, pages 66-73. York, USA,2004.
[126]A. Gramm. Ws-qos-a framework for qos-aware web services. Technical Report B-04-11, Preie Universitat Berlin,2003.
[127]T. Yu, K. Lin. Service selection algorithms for web services with end-to-end qos constraints. In Proceedings of IEEE International Conference on E-Commerce Technology, pages 129-136.2004.
[128]J. Cardoso. Quality of service and semantic composition of workflows. Ph.D. thesis, University of Georgia,2002.
[129]X. Gu, K. Nahrstedt, R. Chang, et al. Qos-assured service composition in man-aged service overlay networks. In Proceedings of 23rd IEEE International Confer-ence on Distributed Computing Systems, pages 19-22. Providence, Rhode Island, May 2003.
[130]S. Chandrasekaran, S. Madden, M. Ionescu. An architecture for compos-ing service over wide area networks. CS262 Class Project Write up, http://ninja.cs.berkekey.edu/pubs/pubs.html,2002.
[131]谷青范.网格环境下的服务调度机制研究.Ph.D. thesis,东南大学,2006.
[132]王勇,胡春明,杜宗霞. 服务质量感知的网格工作流调度. 软件学报,17(11)：2341-2351,112006.
[133]M. P. Singh. Distributed enactment of multiagent workflows:Temporal logic for web service composition. In Proceedings of the 2nd International Join Confer-ence on Autonomous Agents and Multiagent Systems, pages 907-914. Melbourne, Australia,2003.
[134]F. Ishikawa, N. Yoshioka, Y. Tahara, et al. Behavior descriptions of mobile agents for web services integration. In Proceeding of International Conference on Web Services, pages 342-349. San Diego, USA,2004.
[135]G. Chafle, S. Chandra, V. Mann, et al. Decentralized orchestration of composite web services. In Proceedings of the 13th International Conference on World Wide Web. USA,2004.
[136]S. W. Loke, A. B. Zaslavsky. Towards distributed workflow enactment with itineraries and mobile agent management. Lecture Notes in Computer science 2033, pages 283-294,2001.
[137]徐伟,金蓓弘,李京,曹建农.一种基于移动agent的复合web服务容错模型.软件学报,28(4)：558-567,42005.
[138]J. N. Cao, W. Xu, et al. A reliable multicast protocol for mailbox-based mobile agent communications. In proceedings of the 7th IEEE International Symposium on Autonomous Decentralized Systems.2005.
[139]S. P. Ran. A model for web services discovery with qos. ACM SIGecom Ex-changes,4(1):1-10,2003.
[140]A. Mani, A. Nagarajan. Understanding quality of service for Web services. IBM, http://www-106. ibm. com/developerworks/library/ws-quality.html,2002.
[141]C. Lee, J. Lehoczky, D. Siewiorek, et al. A scalable solution to the multi-resource qos-problem. In Proceedings of IEEE Real-Time Systems Symposium, pages 315-326. Phoenix, AZ, December 1999.
[142]C. Irvine, T. Levin. Toward a taxonomy and costing method for security services. In Proceedings of the 15th Annual Computer Security Applications Conference. December 1999.
[143]B. Sabata, S. Chatterjee, M. Davis, et al. Taxonomy for qos specifications. In Proceedings of WORDS, pages 100-107. Newport Beach, CA, February 1997.
[144]骆正虎.移动Agent统若干关键技术问题研究.Ph.D. thesis,合肥工业大学,2002.
[145]M.Dorigo, L. Gambardella. Ant colony system:a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary com-putation, 1(1):53-66,1997.
[146]T. Stutzle, H. H. Hoos. Max-min ant system. Future Generation Computer System,16(8):889-914,2000.
[147]B. Bullnheimer, R. F. Hartl, C. Strauss. A new rank-based version of the ant system:A computational study. Technical Report POM-03/97, Institute of Management Science, University of Vienna, Austria,1997.
[148]V. Maniezzo, A. Colorni, M. Dorigo. The ant system applied to the quadratic assignment problem. Technical Report IRIDIA/94-28, Universite Libre de Brux-elles, Belgium,1994.
[149]B. B. B, R. F. Hartl, C. Strauss. An improved ant system algorithm for the vehicle routing problem. Technical Report POM-10/97, Institute of Management Science, University of Vienna, Austria,1997.
[150]R. Schoonderwoerd, O. Holland, J. Bruten. Ant-based load balancing in telecom-munications networks. Adaptive Behavior,5(2):169-207,1996.
[151]L. M. Gambardella, M. Dorigo. An ant colony system hybridized with a new local search for the sequential ordering problem. INFORMS Journal on Computing, 12(2):237-255,2000.
[152]G. Leguizamon, Z. Michalewicz. A new version of ant system for subset problems. In Proceedings of 1999 Congress on Evolutionary Computation.1999.
[153]TSPLIB. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
[2]I. Foster. Grid technologies & applications:Architecture & achievements. In International Conference on Computing in High Energy and Nuclear Physics. 2001.
[3]I. Foster, C. Kesselman, J. M. Nick, et al. The physiology of the grid:An open grid serivices architecture for distributed systems integration. In Grid computing: Making the global infrastructure a reality, pages 217-250. John Wiley & Sons, 2003.
[4]徐志伟,冯百明,李伟.网格计算技术.电子工业出版社,北京,2004.
[5]D. D. Roure, M. A. Baker, N. R. Jennings, et al. The evolution of the grid. In Grid Computing:Making The Global Infrastructure a Reality, pages 65-100. John Wiley & Sons,2003.
[6]FAFNER:Factoring via Network-Enabled Recursion. http://cs-www.bu.edu/cgi-bin/FAFNER/factor.pl.
[7]I. Foster, J. Geisler, S. Tuecke. Mpi on the i-way:A wide-area, multimethod implementation of the message passing interface. In Proceedings of the 1996 MPI Developers Conference, pages 10-17.1996.
[8]I. Foster, J. Geisler, B. Nickless, et al. Software infrastructure for the i-way high-performance distributed computing experiment. In Proceedings of the 5th IEEE International Symposium on High Performance Distributed Computing, page 562. IEEE Computer Society,1996.
[9]SETI@home. http://setiathome.ssl.berkeley.edu/.
[10]Distributed.net. http://www.distributed.net/.
[11]I. Foster, C. Kesselman. Globus:A metacomputing infrastructure tookit. The International Journal of Supercomputer Applications,11(2):115-128,1997.
[12]Legion. http://www.cs.virginia.edu/legion/.
[13]I. Foster, C. Kesselman, J. Nick, et al. The physiology of the grid:An open grid services architecture for distributed systems integration. http://www. globus. org/research/papers/ogsa.pdf,2002.
[14]S. Tuecke, K. Czajkowski, I. Foster, et al. Open grid service infrastructure(ogsi). Technical report, OGSI-WG, Global Grid Forum,2003.
[15]K. Czajkowski, D. Ferguson, I. Foster, et al. From open grid ser-vices infrastructure to ws-resource framework:Refactoring & evolution. http://www.globus. org/wsrf/,2004.
[16]European Data Grid.http://www.eu-datagrid.org/.
[17]http://ninf.apgrid.org/.
[18]Bricks.http://ninf.apgrid.org/bricks/.
[19]http://www.gridlab.org/WorkPackages/wp-1/collaboration.html#N*Grid.
[20]J. N. Cao, A. T. S. Chan, Y. D. Sun, et al. A taxonomy of application scheduling tools for high performance cluster computing. In Cluster Computing. Nether-lands:Kluwer Academic Publishers,2004.
[21]J.Nabrzyski, J. M. Schope, J. Weglarz. Grid Resource Management:State of the Art and Future Trends. Springer-Verlag:Kluwer Academic Publishers,2003.
[22]W. Smith, I. Foster, V. Taylory. Scheduling with advanced reservations. In J. D. P. Rolim, editor, Proceedings of the 14th International Parallel and Distributed Processing Symposium, pages 127-132. Cancun, Mexico, May 2000.
[23]U. Farooq, S. Majumdar, E. W. Parsons. Efficiently scheduling advance reser-vations in grids. Technical Report SCE-05-14, Dept. of Systems and Computer Engineering, Carleton University, August 2005.
[24]H. Casanova, A. Legrand, et al. Heuristics for scheduling parameter sweep appli-cations in grid environments. In Proceedings of the 9th Heterogeneous Computing Workshop(HCW), pages 349-363.2000.
[25]R. f. Freund, M. Gherrity, et al. Scheduling resources in multi-user,heterogeneous,computing environments with smartnet. In Proceedings of HCW'98, pages 184-199. March 1998.
[26]T. D. Braun, H. J. Siegel, N. Beck. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing,61(6):810-837,2001.
[27]M. Maheswaran, S. Ali. Dynamic matching and scheduling of a class of inde-pendent tasks onto heterogeneous computing syetems. In Proceedings of the 8th IEEE Heterogeneous Computing Workshop(HCW'99). IEEE Computer Society Press, San Juan, Puerto Rico, April 1999.
[28]J. E. Biegel, J. J. Davern. Genetic algorithms and job shop scheduling. Computers & Industrial Engineering,19(1-4):81-91,1990.
[29]I. Ahmad, K. Dhodhi. Multiprocessor scheduling in a genetic paradigm. Parallel Computing,22(3):395-406,1996.
[30]K. Steinofel, A. Albrecht, C. K. Wong. Two simulated annealing-based heuristics for the job shop scheduling problem. European Journal of Operational Research, 118(3):524-548,1999.
[31]Y. Liu, H. He. Multi-unit combinatorial auction based grid resource co-allocation approach. In Proceedings of the 3rd International Conference on Semantics, Knowledge, and Grid.2007.
[32]R. Gonen, D. Lehmann. Optimal solutions for multi-unit combinatorial auc-tions:Branch and bound heuristics. In Proceedings of the ACM Conference in Electronic Commerce, pages 13-20.2000.
[33]H. Topcuoglu, S. Hariri, M. Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems,13(3):260-274,2002.
[34]A. Radulescu, A. J. C. van Gemund. On the complexity of list scheduling algo-rithms for distributed memory systems. In Proceedings of the 13th International Conference on Super computing, pages 68-75. Portland, Oregon, USA, November 1999.
[35]S. Darbha, D. P. Agrawal. Optimal scheduling algorithm for distributed memory machines. IEEE Trans, on Parallel and Distributed Systems,9(1):87-95,1998.
[36]S. Ranaweera, D. P. Agrawal. A task duplication based scheduling algorithm for heterogeneous systems. In Proceedings of the 14th International Parallel and Distributed Processing Symposium, pages 445-450. Cancun, Mexico, May 2000.
[37]R. Bajaj, D. P. Agrawal. Improving scheduling of tasks in a heterogeneous envi-ronment. IEEE Transactions on Parallel and Distributed Systems,15(2):107-118, 2004.
[38]T. Yang, A. Gerasoulis. Dsc:Scheduling parallel tasks on an unbounded number of processors. IEEE Trans. on Parallel and Distributed Systems,5(9):951-967, 1994.
[39]J. Liou, M. A. Palis. An efficient task clustering heuristic for scheduling dags on multiprocessors. In Proceedings of Workshop on Resource Manage-ment, Symposium of Parallel and Distributed Processing.1996.
[40]R. Buyya. Economic-based distributed resource management and scheduling for grid computing. Ph.D. thesis, Monash University, Melbourne, Australia,2002.
[41]A. Dogan, F. Ozgiiner. Scheduling of a meta-task with qos requirements in het-erogeneous computing systems. Journal of Parallel and Distributed Computing, 66(2):181-196,2006.
[42]K. Guo, L. Sun, S. Jia. Utility function based fair data scheduling algorithm for ofdm wireless network. Journal of Systems Engineering and Electronics, 18(4):731-738, December 2007.
[43]C. S. Yeo, R. Buyya. A taxonomy of market-based resource management sys-tems for utility-driven cluster computing. Software:Practice and Experience, 36(13):1381-1419,2006.
[44]F. Berman, R. Wolski. The apples project:A status report. In Proceedings of the 8th NEC Research Symposium. May 1997.
[45]F. Berman, R. Wolski, S. Figueira, et al. Application level scheduling on dis-tributed heterogeneous networks. In Proceedings of Supercomputing'96.1996.
[46]R. Wolski. Forecasting network performance to support dynamic scheduling using the network weather service. In Proceedings of 6th IEEE International Symposium on High Performance Distributed Computing.1997.
[47]R. Buyya, D. Abramson, J. Giddy. Nimrod/g:An architecture for a resource management and scheduling system in a global computational grid. In Pro-ceedings of 4th International Conference on High Performance Computing in Asia-Pacific Region.2000.
[48]R. Buyya, M. Murshed. Gridsim:a toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. The Jour-nal of Concurrency and Computation:Practice and Experience(CCPE),14(13-15):1175-1220,2002.
[49]J. Frey, T. Tannenbaum, M. Livny, et al. Condor-g:A computation management agent for multi-institutional grids. In Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing.2001.
[50]I. Foster. What is the grid? a three point checklist. Grid Today,1(6):22, July 2002.
[51]R. Buyya, D. Abramson, S. Venugopal. The grid economy.93(3):698-714, March 2005.
[52]I. Foster, C. Kesselman, e. a. C. Lee. A distributed resource management architecture that supports advance reservations and co-allocation. In Proceedings of the International Workshop on Quality of Service (IWQoS'99), pages 27-36. London,1999.
[53].沃天宇,雷磊.一种支持端到端qos的服务网格体系结构.软件学报,17(6)：1448-1458,2006.
[54]J. Leigh, T. A. DeFanti, A. E. Johnson, et al. Global tele-immersion:Better than being there. In Proceedings of the 7th International Conference on Artificial Reality and Tele-Existence, pages 10-17. Dec 1997.
[55]L. C. Wolf, R. Steinmetz. Concepts for resource reservation in advance. Multi-media Tools and Applications,4(3):255-278,1997.
[56]U. Schwiegelshohn, R. Yahyapour, P. Wieder. Resource management for future generation grids. Technical Report TR-0005, Institute on Resource Management and Scheduling, CoreGRID-Network of Excellence, May 2005.
[57]J. Cao, F. Zimmermann. Queue scheduling and advance reservations with cosy. In Proceedings of the 18th Intl. Parallel and Distributed Processing Symposium. April 2004.
[58]S. McGough, L. Young, A. Afzal, et al. Workflow enactment in iceni. In Proceed-ings of the UK e-Science All Hands Meeting. September 2004.
[59]Load Sharing Facility platform. http://www.platform.com/products/LSF/.
[60]D. Jackson, Q. Snell, M. Clement. Core algorithms of the maui scheduler. Job Scheduling Strategies for Parallel Processing,2221:87-102,2001.
[61]LoadLeveler. http://publib.boulder.ibm.com/epubs/pdf/c2366810.pdf.
[62]A. Sulistio, R. Buyya. A grid simulation infrastructure supporting advance reser-vation. In Proceedings of the 16th International Conference on Parallel and Dis-tributed Computing and Systems. Nov 2004.
[63]A. W. Mu'alem, D. G. Feitelson. Utilization, predictability, workloads, and run-time user estimates in scheduling the ibm sp2 with backfilling. IEEE Transac-tions on Parallel and Distributed Systems,12(6):529-543, June 2001.
[64]U. Farooq, S. Majumdar, E. W. Parsons. Impact of laxity on scheduling with advance reservations in grids. In Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecom-munication Systems, pages 319-324. Atlanta, GA, USA, September 2005.
[65].沃天宇,雷磊.一种基于松弛时间的服务网格资源能力预留机制.计算机研究与发展,44(1)：20-28,2007.
[66]S. Naiksatam, S. Figueira. Elastic reservations for efficient bandwidth utilization in lambdagrids. Future Generation Computer Systems,23(1):1-22,2007.
[67]G. W. Group. Grid Resource Allocation Agreement Protocol. http://forge. gridforum. org/projects/gr aap-wg/.
[68]J. MacLaren. Advance reservations:State of the art. Technical Report ggf-draft-sched-graap-2.0, Global Grid Forum,2003.
[69]D. Kuo, M. Mckeown. Advance reservation and co-allocation protocol for grid computing. In Proceedings of the International Conference on e-Science and Grid Technologies, pages 164-171.2005.
[70]S. Tangpongprasit, T. Katagiri, K. Kise, et al. A time-to-live based reservation algorithm on fully decentralized resource discovery in grid computing. Parallel Computing,31(6):529-543,2005.
[71]PBS Professional, http://www.altair.com/software/pbspro.htm.
[72]T. Roblitz, F. Schintke, A. Reinefeld. Resource reservations with fuzzy re-quests. Concurrency and Computation:Practice and Experience,18(13):1681-1703,2006.
[73]G. M. Amdahl. Validity of the single-processor approach to achieving large scale computing capabilities. In Proceedings of the AFIPS Conference, pages 483-485. Atlantic City, N.J., USA, April 1967.
[74]R. Bajaj, D. P. Agrawal. Improving scheduling of tasks in a heterogeneous envi-ronment. IEEE Transactions on Parallel and Distributed Systems,15(2):107-118, 2004.
[75]M. Aggarwal, R. Kent, A. Ngom. Genetic algorithm based scheduler for compu-tational grids. In Proceedings of the 19th Annual International Symposium on High Performance Computing Systems and Applications, pages 209-215. Guelph, Ontario Canada, May 2005.
[76]http://www.cs.huji.ac.il/labs/parallel/workload/Losc/OSC-Clust-2000-2.1-cln.swf.gz.
[77]SWF. http://www.cs.huji.ac.il/labs/parallel/workload/swf.html.
[78]X. He, X. Sun, V. L. Gregor. Qos guided min-min heuristic for grid task schedul-ing. Journal of Computer Science and Technology,18(4):442-451,2003.
[79]L. Eyraud-Dubois, G. Mounie, D. Trystram. Analysis of scheduling algorithms with reservations. In Proceedings of 21st IEEE International Parallel and Dis-tributed Processing Symposium, pages 1-8. March 2007.
[80]F. Dong, S. G. Akl. Scheduling algorithms for grid computing:State of the art and open problems. Technical Report 2006-504, School of Computing, Queen's University, January 2006.
[81]E. Sanlaville, G. Schmidt. Machine scheduling with availability constraints. Acta Informatica,35(9):795-811,1998.
[82]G. Schmidt. Scheduling with limited machine availability. European Journal of Operational Research,121(1):1-15,2000.
[83]C. Y. Lee. Machine scheduling with an availability constraint. Journal of Global Optimization,9(3-4):395-416,1996.
[84]I. Kacem, C. Chu, A. Souissi. Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times. Computers and Operations Research,35(3):827-844,2008.
[85]P. Mauguiere, J. C. Billaut, J. L. Bouquard. New single machine and job-shop scheduling problems with availability constraints. Journal of Scheduling,8:211-231,2005.
[86]C. Castillo, G. N. Rouskas, K. Harfoush. On the design of online scheduling algorithms for advance reservations and qos in grids. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium, pages 1-10. Long Beach, California, USA, March 2007.
[87]B. Li, J. Chen, D. Zhao. Looking-ahead algorithms for single machine schedulers to support advance reservation of grid jobs. In Proceedings of the 10th IEEE In-ternational Conference on High Performance Computing and Communications, pages 335-341.2008.
[88]M. S. Netto, K. Bubendorfer, R. Buyya. Sla-based advance reservations with flexible and adaptive time qos parameters. In Lecture Notes in Computer Sci-ence (LNCS), proceedings of the International Conference on Service Oriented Computing, volume 4749. Springer Verlag, Vienna, Austria, September 2007.
[89]E. G. Coffman, M. R. Garey, D. S. Johnson. Approximation algorithms for bin packing:A survey, pages 46-93. Boston:PWS Publishing,1996.
[90]E. G. Coffman, G. Galambos, e. a. S. Martello. Bin packing approximation al-gorithms:Combinatorial analysis, pages 1-47. Norwell:Kluwer Academic Pub-lishers,1998.
[91]D. S. Johnson, A. Demers, J. D. Ullman, et al. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4):299-325,1974.
[92]G. Zhang. A new version of on-line variable-sized bin packing. Discrete Applied Mathematics,72(3):193-197,1997.
[93]E. G. Coffman, C. Courcoubetis, e. a. M. R. Garey. Perfect packing theorems and the average case behavior of optimal and online bin packing. SIAM Review, 44(1):95-108,2002.
[94]J. Csirik, D. S. Johnson. Bounded space on-line bin packing:Best is better than first. Algorithmica,31(2):115-138,2001.
[95]D. P. Anderson, J. Cobb, E. Korpela, et al. Seti@home:An experiment in public-resource computing. Communications of the ACM,45(11):56-61, November 2002.
[96]Rosetta@home. http://boinc.bakerlab.org/rosetta/.
[97]LHC@home. http://lhcathome.cern.ch/.
[98]E. Elmroth, P. Gardfjall. Design and evaluation of a decentralized system for grid-wide fairshare scheduling. In Proceedings of the First International Conference on e-Science and Grid Computing. December 2005.
[99]I. Foster, C. Kesselman, S. Tuecke. The anatomy of grid:Enabling scalable virtual organizations. International Journal of Supercomputer Applications, 15(3):200-222,2001.
[100]H. Casanova, J. Dongarra. Netsolve:A network server for solving computational science problems. International Journal of Supercomputing Applications and High Performance Computing, 11(3):212-223,1997.
[101]N. Kapadia, J. Fortes. Punch:An architecture for web-enabled wide-area network-computing. Cluster Computing:The Journal of Networks, Software Tools and Applications,2(2):153-164,1999.
[102]R. Buyya, D. Abramson, J. Giddy. Design and evaluation of a decentralized sys-tem for grid-wide fairshare scheduling. In Proceedings of the International Paral-lel and Distributed Processing Symposium:Heterogeneous Computing Workshop. San Francisco, California, USA,2001.
[103]D. Fudenberg, J. Tirole. Game Theory. MIT Press, Cambridge, Massachusetts, 1991.
[104]W. Vickrey. Counter-speculation, auctions, and competitive sealed tenders. Jour-nal of Finance,16(1):9-37,1961.
[105]I. E. Sutherland. A futures market in computer time. Communications of the A CM,11(6):449-451,1968.
[106]O. Regev, N. Nisan. The popcorn market-an online markets for computational resources. In Proceedings of the 1st International Conference on Information and Computation Economies, pages 148-157.1998.
[107]C. A. Waldspurger, T. Hogg, B. A. Huberman, et al. Spawn:A distributed computational economy. IEEE Transactions on Software Engineering,18(2):103-117,1992.
[108]S. Lalis, A. Karipidis. Jaws:An open market-based framework for distributed computing over the internet. In Proceedings of the 1st IEEE/ACM International Workshop on Grid Compuing. Bangalore, India,2000.
[109]K. Lai, L. Rasmusson, E. Adar, et al. Tycoon:an implemention of a distributed market-based resource allocation system. Technical report, HP Labs, USA, De-cember 2004.
[110]M. Frank. The ocean project:The open computation exchange & auctioning network. http://www.cise.uft.edu/research/ocean.
[111]S. Mark, W. Steven. The rate of convergence to efficiency in the buyer's bid double auction as the market becomes large. The Review of Economic Studies, 56(4):477-498,1989.
[112]W. Steven. Existence and convergence of equilibria in the buyer's bid double auction. The Review of Economic Studies,58(2):351-374,1991.
[113]R. Mcafee. A dominant strategy double auction. Journal of Economic Theory, 56(2):434-450,1992.
[114]P. Huang, A. Scheller-Wolf, K. Sycare. Design of a multiunit double auction e-market. Computational Intelligence,18(4):596-617,2002.
[115]翁楚良,陆鑫达.一种基于双向拍卖机制的计算网格资源分配方法.计算机学报,29(6)：1004-1009,6 2006.
[116]U. Kant, D. Grosu. Double auction protocols for resource allocation in grids. In Proceedings of the International Conference on Information Technology:Coding and Computing.2005.
[117]C. Satayapiwat, R. Egawa, H. Takizawa, et al. A utility-based double auction mechanism for efficient grid resource allocation. In Proceedings of the Inter-national Symposium on Parallel and Distributed Processing with Applications, 2008, pages 252-260.2008.
[118]M. Wieczorek, S. Podlipnig, R. Prodan, et al. Applying double auctions for scheduling of scientific workflows on the grid. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. 2008.
[119]R. P. McAfee. A dominant strategy double auction. Journal of Economic Theory, 56(2):434-450,1992.
[120]Z. Tan. Market-based Grid Resource Allocation Using a Stable Continuous Double Auction. Ph.D. thesis, The University of Manchester, Manchester, UK,2007.
[121]Simple object access protocol(SOAP). http://www.w3.org/tr/soap/.
[122]W. Binder, I. Constantinescu, B. Faltings. Decentralized orchestration of compos-iteweb services. In Proceedings of the International Conference on Web Services, pages 869-876.2006.
[123]岳昆,王晓玲,周傲英.Web服务核心支撑技术：研究综述.软件学报,15(3)：428-442,2004.
[124]张伟哲,方滨兴,胡铭曾,张宏莉.基于信任qos增强的网格服务调度算法.计算机学报,29(7)：1157-1166,72006.
[125]L. Yutu, H. H. N. Anne, L. Zeng. Qos computation and policing in dynamic web service selection. In Proceedings of WWW, pages 66-73. York, USA,2004.
[126]A. Gramm. Ws-qos-a framework for qos-aware web services. Technical Report B-04-11, Preie Universitat Berlin,2003.
[127]T. Yu, K. Lin. Service selection algorithms for web services with end-to-end qos constraints. In Proceedings of IEEE International Conference on E-Commerce Technology, pages 129-136.2004.
[128]J. Cardoso. Quality of service and semantic composition of workflows. Ph.D. thesis, University of Georgia,2002.
[129]X. Gu, K. Nahrstedt, R. Chang, et al. Qos-assured service composition in man-aged service overlay networks. In Proceedings of 23rd IEEE International Confer-ence on Distributed Computing Systems, pages 19-22. Providence, Rhode Island, May 2003.
[130]S. Chandrasekaran, S. Madden, M. Ionescu. An architecture for compos-ing service over wide area networks. CS262 Class Project Write up, http://ninja.cs.berkekey.edu/pubs/pubs.html,2002.
[131]谷青范.网格环境下的服务调度机制研究.Ph.D. thesis,东南大学,2006.
[132]王勇,胡春明,杜宗霞. 服务质量感知的网格工作流调度. 软件学报,17(11)：2341-2351,112006.
[133]M. P. Singh. Distributed enactment of multiagent workflows:Temporal logic for web service composition. In Proceedings of the 2nd International Join Confer-ence on Autonomous Agents and Multiagent Systems, pages 907-914. Melbourne, Australia,2003.
[134]F. Ishikawa, N. Yoshioka, Y. Tahara, et al. Behavior descriptions of mobile agents for web services integration. In Proceeding of International Conference on Web Services, pages 342-349. San Diego, USA,2004.
[135]G. Chafle, S. Chandra, V. Mann, et al. Decentralized orchestration of composite web services. In Proceedings of the 13th International Conference on World Wide Web. USA,2004.
[136]S. W. Loke, A. B. Zaslavsky. Towards distributed workflow enactment with itineraries and mobile agent management. Lecture Notes in Computer science 2033, pages 283-294,2001.
[137]徐伟,金蓓弘,李京,曹建农.一种基于移动agent的复合web服务容错模型.软件学报,28(4)：558-567,42005.
[138]J. N. Cao, W. Xu, et al. A reliable multicast protocol for mailbox-based mobile agent communications. In proceedings of the 7th IEEE International Symposium on Autonomous Decentralized Systems.2005.
[139]S. P. Ran. A model for web services discovery with qos. ACM SIGecom Ex-changes,4(1):1-10,2003.
[140]A. Mani, A. Nagarajan. Understanding quality of service for Web services. IBM, http://www-106. ibm. com/developerworks/library/ws-quality.html,2002.
[141]C. Lee, J. Lehoczky, D. Siewiorek, et al. A scalable solution to the multi-resource qos-problem. In Proceedings of IEEE Real-Time Systems Symposium, pages 315-326. Phoenix, AZ, December 1999.
[142]C. Irvine, T. Levin. Toward a taxonomy and costing method for security services. In Proceedings of the 15th Annual Computer Security Applications Conference. December 1999.
[143]B. Sabata, S. Chatterjee, M. Davis, et al. Taxonomy for qos specifications. In Proceedings of WORDS, pages 100-107. Newport Beach, CA, February 1997.
[144]骆正虎.移动Agent统若干关键技术问题研究.Ph.D. thesis,合肥工业大学,2002.
[145]M.Dorigo, L. Gambardella. Ant colony system:a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary com-putation, 1(1):53-66,1997.
[146]T. Stutzle, H. H. Hoos. Max-min ant system. Future Generation Computer System,16(8):889-914,2000.
[147]B. Bullnheimer, R. F. Hartl, C. Strauss. A new rank-based version of the ant system:A computational study. Technical Report POM-03/97, Institute of Management Science, University of Vienna, Austria,1997.
[148]V. Maniezzo, A. Colorni, M. Dorigo. The ant system applied to the quadratic assignment problem. Technical Report IRIDIA/94-28, Universite Libre de Brux-elles, Belgium,1994.
[149]B. B. B, R. F. Hartl, C. Strauss. An improved ant system algorithm for the vehicle routing problem. Technical Report POM-10/97, Institute of Management Science, University of Vienna, Austria,1997.
[150]R. Schoonderwoerd, O. Holland, J. Bruten. Ant-based load balancing in telecom-munications networks. Adaptive Behavior,5(2):169-207,1996.
[151]L. M. Gambardella, M. Dorigo. An ant colony system hybridized with a new local search for the sequential ordering problem. INFORMS Journal on Computing, 12(2):237-255,2000.
[152]G. Leguizamon, Z. Michalewicz. A new version of ant system for subset problems. In Proceedings of 1999 Congress on Evolutionary Computation.1999.
[153]TSPLIB. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.