基于ECT的优先权约束的作业调度模型及算法研究与实现
|
摘要
随着科学技术的发展，Internet迅速蔓延到世界各地，成为人们沟通信息和协同工作的有效工具。其中，通过Internet连接的成千上万的计算资源、存贮资源、软件资源、信息资源等各种数字化设备共同构成了生产、传播和使用知识的重要载体。而网格作为一种新兴的计算基础设施，将这些物理上互连的众多资源汇聚起来，实现了资源共享、协同工作和联合计算的功能，并为广大用户提供了科学、工程、金融、军事等各种综合性服务。
由于Internet所提供的计算资源在地理上分布广泛，隶属于不同社区，而且这些资源从硬件架构到软件部署都不尽相同，因此，在采用网格计算为广大用户解决各种领域(比如：高能物理生物信息学、化学分子模拟以及数值天气预报等)中的超大规模、超级复杂的问题时，需要合理地将这些具有超级计算能力的分布式异构资源，分配给具有不同应用需求的用户，使得用户的问题既能够及时得到处理，同时也要确保资源使用过程中，各类资源能够平衡使用。因此需要一种可靠、高效率的调度算法来解决资源共享中作业调度、资源分配的问题。而根据解决问题的目的不同，调度算法有着不同的目标函数：面向资源和面向应用。例如目前一些流行的、基于应用QoS的网格调度管理算法就是以面向用户为主要目的，在调度过程中考虑用户对作业管理、资源分配的影响。对用户来说，他最关心的莫过于自己作业的执行效率(make span)和使用资源的总耗费(cost)。具体体现：要求作业必须要在特定时间内完成，或者完成作业的总费用不能超过预算上限等。还有一些更复杂的、结合资源的别的约束条件，如：容错性能不可低于某一下限，资源安全性能要高等。目前，网格环境中资源共享时，用户提交的作业，大都要根据实际目标附加各式各样的需求约束。
本文提出的基于ECT的优先权约束的作业调度模型和相关的调度算法，以网格中的异构资源为研究背景，采用随机Petri网(SPN)技术，借鉴现有的容错性网格作业调度模型，建模时，既考虑调度过程中用户优先权对作业调度、资源分配的影响，同时兼顾用户提出的期望完成时间(ECT)和作业实际完成时间二者的协调统一，既希望高优先权用户的作业得到高质量的服务(作业提早完成)，又保证绝大多数作业都能在各自用户期望的完成时间内完成，从而协调不同用户之间无冲突共享资源的矛盾。
本文以大规模科学与工程计算为背景，网格为基础环境，着力研究了网格过程中作业调度、资源分配、资源共享等相关问题，分别给出了满足实际需求的作业调度模型和相应的调度算法。前者诠释了调度过程中资源、用户以及作业之间的相互依赖关系和约束；后者则详细描述了调度过程中作业调度、资源分配的具体策略。最后给出与Min-min、Max-min、XSuffrage等多种经典调度算法的性能比较。结果表明，采用本文算法调度作业，可使得绝大部分用户所提交的作业都能在用户指定的期望完成时间内完成，尤其保证高优先权用户的作业远早于其期望完成时间完成，从而保障了高优先权用户的权益，也使用户总体上满意程度比较好，实现了多用户合理共享异构资源的目标。
With the development of science and technology, the Internet spread rapidly around the world. It has become an effective tool for information communication and cooperation among people. Through which, thousands of computing resources, storage resources, software resources, information resources, as well as other digital equipment together constitute the major carriers for production, transmittal and the use of knowledge. However, Grid just like a new computing infrastructure, it has covered all these resources geographically-connected and has implemented the function of resource sharing, cooperation and combined computing, and it has provided various of users with all kinds of services in science, engineering, finance, military etc.
Because the computing resources provided by the Internet are widely distributed geographically and belong to different users, the structure of hardware, the deployment of software and facilities are not quite the same, then when Grid computing is used as solutions for large-scale problems requiring super-computing power in various fields (such as high-energy physics, bioinformatics, chemical molecule simulation and digital weather prediction), we need to allocate these distributed heterogeneous resources with super computing power to users of different applications reasonably to make problems dealt with efficiently, meanwhile we also should ensure the resource utilization remain balance. Therefore, we need a reliable and efficient scheduling algorithm to help to solve the problem for job scheduling and resource allocation. There are different objective functions for scheduling algorithms according to distinct objectives in problem solution, such as resource-centric and application centric. For instance, some grid scheduling management algorithms based on QoS focus on application demanding, and during the scheduling process, the effects of users are taken into consideration in job scheduling and resource allocation. For users, the most important things they concern are the efficiency of job execution and the total cost in resource sharing. Such as jobs must be completed within deadline, or the total charge in resource sharing can't exceed some upper-limit, etc. What's more, there are other constraints for resource demanding, like fault tolerance and security. And now most jobs submitted by users are lodged with different requirements based on actual objectives in Grid resource sharing.
This paper presents priority constrained scheduling model based on ECT as well as the corresponding algorithm. The model regards the heterogeneous resources in Grid as the main environment, adopts stochastic Petri networks (SPN) technology, and takes the fault-tolerance grid job scheduling model for reference. And in modeling, we consider the effects of priorities of different users, as well as the coordination of the expected completion time (ECT) and the actual completion time of jobs, to guarantee the jobs of all users to be completed within ECT (Expected Completion Time), especially to ensure the jobs of users with high priorities to be dealt with as soon as possible, making these users get services of good quality, in order to coordinate the conflict of resource sharing between different users.
Based on the background of large-scale scientific and engineering computing, we take Grid as basic environment, and focus on the research of Grid scheduling, resource allocation and resource sharing etc. We have given a scheduling model meeting the actual needs and the corresponding scheduling algorithm. The former interprets the relationship between resources, tasks and user as well as some constraints among them in scheduling process; the latter describes the scheduling algorithm in detail. Finally, we compare our algorithm with Mm-min, Max-min and XSuffrage algorithms in performance, in our algorithm, can we ensure the majority of the jobs, in particular, whose users having high priorities, to be completed within ECT, so as to make users generally satisfied, thus achieving the goal of mult-users sharing heterogeneous resources reasonably and without conflict.
由于Internet所提供的计算资源在地理上分布广泛，隶属于不同社区，而且这些资源从硬件架构到软件部署都不尽相同，因此，在采用网格计算为广大用户解决各种领域(比如：高能物理生物信息学、化学分子模拟以及数值天气预报等)中的超大规模、超级复杂的问题时，需要合理地将这些具有超级计算能力的分布式异构资源，分配给具有不同应用需求的用户，使得用户的问题既能够及时得到处理，同时也要确保资源使用过程中，各类资源能够平衡使用。因此需要一种可靠、高效率的调度算法来解决资源共享中作业调度、资源分配的问题。而根据解决问题的目的不同，调度算法有着不同的目标函数：面向资源和面向应用。例如目前一些流行的、基于应用QoS的网格调度管理算法就是以面向用户为主要目的，在调度过程中考虑用户对作业管理、资源分配的影响。对用户来说，他最关心的莫过于自己作业的执行效率(make span)和使用资源的总耗费(cost)。具体体现：要求作业必须要在特定时间内完成，或者完成作业的总费用不能超过预算上限等。还有一些更复杂的、结合资源的别的约束条件，如：容错性能不可低于某一下限，资源安全性能要高等。目前，网格环境中资源共享时，用户提交的作业，大都要根据实际目标附加各式各样的需求约束。
本文提出的基于ECT的优先权约束的作业调度模型和相关的调度算法，以网格中的异构资源为研究背景，采用随机Petri网(SPN)技术，借鉴现有的容错性网格作业调度模型，建模时，既考虑调度过程中用户优先权对作业调度、资源分配的影响，同时兼顾用户提出的期望完成时间(ECT)和作业实际完成时间二者的协调统一，既希望高优先权用户的作业得到高质量的服务(作业提早完成)，又保证绝大多数作业都能在各自用户期望的完成时间内完成，从而协调不同用户之间无冲突共享资源的矛盾。
本文以大规模科学与工程计算为背景，网格为基础环境，着力研究了网格过程中作业调度、资源分配、资源共享等相关问题，分别给出了满足实际需求的作业调度模型和相应的调度算法。前者诠释了调度过程中资源、用户以及作业之间的相互依赖关系和约束；后者则详细描述了调度过程中作业调度、资源分配的具体策略。最后给出与Min-min、Max-min、XSuffrage等多种经典调度算法的性能比较。结果表明，采用本文算法调度作业，可使得绝大部分用户所提交的作业都能在用户指定的期望完成时间内完成，尤其保证高优先权用户的作业远早于其期望完成时间完成，从而保障了高优先权用户的权益，也使用户总体上满意程度比较好，实现了多用户合理共享异构资源的目标。
With the development of science and technology, the Internet spread rapidly around the world. It has become an effective tool for information communication and cooperation among people. Through which, thousands of computing resources, storage resources, software resources, information resources, as well as other digital equipment together constitute the major carriers for production, transmittal and the use of knowledge. However, Grid just like a new computing infrastructure, it has covered all these resources geographically-connected and has implemented the function of resource sharing, cooperation and combined computing, and it has provided various of users with all kinds of services in science, engineering, finance, military etc.
Because the computing resources provided by the Internet are widely distributed geographically and belong to different users, the structure of hardware, the deployment of software and facilities are not quite the same, then when Grid computing is used as solutions for large-scale problems requiring super-computing power in various fields (such as high-energy physics, bioinformatics, chemical molecule simulation and digital weather prediction), we need to allocate these distributed heterogeneous resources with super computing power to users of different applications reasonably to make problems dealt with efficiently, meanwhile we also should ensure the resource utilization remain balance. Therefore, we need a reliable and efficient scheduling algorithm to help to solve the problem for job scheduling and resource allocation. There are different objective functions for scheduling algorithms according to distinct objectives in problem solution, such as resource-centric and application centric. For instance, some grid scheduling management algorithms based on QoS focus on application demanding, and during the scheduling process, the effects of users are taken into consideration in job scheduling and resource allocation. For users, the most important things they concern are the efficiency of job execution and the total cost in resource sharing. Such as jobs must be completed within deadline, or the total charge in resource sharing can't exceed some upper-limit, etc. What's more, there are other constraints for resource demanding, like fault tolerance and security. And now most jobs submitted by users are lodged with different requirements based on actual objectives in Grid resource sharing.
This paper presents priority constrained scheduling model based on ECT as well as the corresponding algorithm. The model regards the heterogeneous resources in Grid as the main environment, adopts stochastic Petri networks (SPN) technology, and takes the fault-tolerance grid job scheduling model for reference. And in modeling, we consider the effects of priorities of different users, as well as the coordination of the expected completion time (ECT) and the actual completion time of jobs, to guarantee the jobs of all users to be completed within ECT (Expected Completion Time), especially to ensure the jobs of users with high priorities to be dealt with as soon as possible, making these users get services of good quality, in order to coordinate the conflict of resource sharing between different users.
Based on the background of large-scale scientific and engineering computing, we take Grid as basic environment, and focus on the research of Grid scheduling, resource allocation and resource sharing etc. We have given a scheduling model meeting the actual needs and the corresponding scheduling algorithm. The former interprets the relationship between resources, tasks and user as well as some constraints among them in scheduling process; the latter describes the scheduling algorithm in detail. Finally, we compare our algorithm with Mm-min, Max-min and XSuffrage algorithms in performance, in our algorithm, can we ensure the majority of the jobs, in particular, whose users having high priorities, to be completed within ECT, so as to make users generally satisfied, thus achieving the goal of mult-users sharing heterogeneous resources reasonably and without conflict.
引文
1 J Robert-Rivers, The Internet is happening: partly just hype and partly already happening, Telecommunication Journal of Australia, 2002-05(14), pp.45-54
2 Ian Foster, What is the Grid? A Three Point Checklist, htrp://www-fp.mcs.anl.gov/'foster/Articles/WhatIsTheGrid.pdf, 2002, pp. 1-23
3 Ian Foster，Carl Kesselman，《网格计算》，金海译，第2版，北京：电子工业出版社，2004-10，pp．1-30
4 都志辉，陈渝，刘鹏，网格计算，北京：清华大学出版，2002-08，pp．1-44
5 I. Foster and C. Kesselman (editors), The Grid: Bluepnnt for a Future Computing Infrastructure, Morgan Kaufmann Publishers, USA, 1999, pp.1-52
6 I. Foster and A. Iamnitchi, On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing, in Proc. of 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03), Berkeley, CA, USA, February 2003, pp.118-128
7 I. Foster, C. Kesselman and S. Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, in the International J. Supercomputer Applications, 15(3), 2001, pp.200-220
8 Y. Zhu, A Survey on Grid Scheduling'Systems, Department of Computer Science, Hong Kong University of science and Technology, 2003, pp.2-8
9 Dogan A, zguner F, Scheduling Independent Tasks with QoS Requirements in Grid Computing with Time-Varying Resource Prices, Grid Computing-GRID 2002 [C], 2002, pp.58-69
10 Fangpeng Dong and Setim G. Akl., Scheduling Algorithms for Grid Computing: State of the Art and Open Problems, Technical Report, 2006-504, School of Computing, Queen's University, Canada, 2006-01, pp.7-19
11 J. Schopf, Ten Actions When Super Scheduling, document of Scheduling Working Group, Global Grid Forum, http://ww.ggf.org/documents/GFD.4.pdf, 2001-07
12 Michael Litzkow, Miron Livny, and Matt Mutka, Condor-A Hunter of Idle Workstation, 8th International Conference of Distributed Computing Systems, San Jose, California, 1988-01, pp.204-111
13 F. Berman, R. Wolski, The AppLeS Project: A Status Report, 1997
14 David Abramson, Rok Sosic, J. Giddy and B. Hall, Nimrod: A tool for performing parameter simulations using distributed workstations, In HPDC, 1995, pp.112-121
15 F. Berman, R. Wolski, H. Casanova, W. Cime, H. Dail, M. Faerman, S. Figueira, J. Hayes, G. Obertelli, J. Schopf, G. Shao, S. Smallen, N. Spring, A. Su and D. Zagorodnov, Adaptive Computing on the Grid Using AppLeS, in IEEE Trans. on Parallel and Distributed Systems (TPDS), 2003, Vol.14, No.4, pp.369-382
16 F. Berman, R. Wotski, S. Figueria, J. Schopf and G Shao, Application-Level Scheduling on Distributed Heterogeneous Networks, in Proc. of the 1996 ACM/IEEE Conference on Supercomputmg, Article No: 39, Pittsburgh, Pennsylvania USA, 1996-11, pp.423-433
17 X. Sun and M. Wu, Grid Harvest Service: A System for Long-term Application-level Task Scheduling, in Proc. of 2003 International Parallel and Distributed Processing Symposium (IPDPS 2003), Nice, France, 2003-04, pp. 25-32
18 V. Hamscher, U. Schwiegelshohn, A. Streit, R. Yahyapour, Evaluation of Job-Scheduling Strategies for Grid Computing, in Proc. of GRID 2000 GRID 2000, First IEEE/ACM International Workshop, Bangalore, India, 2000-12, pp. 191-202
19 G. Mateescu, Quality of Service on the Grid via Meta scheduling with Resource Co-Scheduling and Co-Reservation, International Journal of High Performance Computing Applications, 2003, Vol. 17, No. 3, pp.209-218
20 F. Berman, High-Performance Schedulers, chapter in The Grid: Blueprint for a Furore Computing Infrastructure, Morgan Kaufmann Publishers, 1998
21 K. Czajkowski, I. Foster, N. Karonis, C. Kesselman, S. Martin, W. Smith, and S. Tuecke, A Resource Management Architecture for Metacomputing Systems, In D. G. Feitelson and L. Rudolph, editors, in Proc of the 4th Workshop on Job Scheduling Strategies for Parallel Processing, Orlando, Florida USA, LNCS, 1998-03, Vol. 1459, pp. 62-82
22 http://www.openpbs.org
23 http://www.cs.wisc.edu/condor
24 陈颖，杨寿保，基于网格计算市场模型的资源与作业描述语言的研究，计算机科学，2005，Vol．32，No．2，pp．90-92
25 Qianfei FU, Shoubao YANG, Maosheng LI, Junmao ZHUN, Decentralized Computational Market Model for Grid Resource Management, Lecture Notes in Computer Science, 2004, Vol. 3033, pp.227-230
26 张文博，陈宁江，魏峻，黄涛，QoS获益驱动的中间件调度框架研究，软件学报，2006-06，Vol．17，No．6，pp．1381-1390
27 张伟哲，胡铭曾，张宏莉，刘凯鹏，多QoS约束网格作业调度问题的多目标演化算法，计算机研究与发展，2006，Vol．43，No．11，pp．1855-1862
28 官荷卿，张文博，魏峻，黄涛，一种应用敏感的Web服务请求调度策略，计算机学报，2006-07，Vol．29，No．7，pp．1189-1198
29 沈卓炜，汪芸，基于EDF策略的端到端实时系统可调度性分析算法，计算机研究与发展，2006，Vol．43，No．5，pp．813-820
30 H. El-Rewini, T. Lewis, and H.. Ali, Task Scheduling in Parallel and Distributed Systems, ISBN: 0130992356, PTR Prentice Hall, 1994
31 王保进，李明树，王志刚，优先级有限时的单处理器静态优先级调度，软件学报，2006-03，Vol．17，No．3，pp．602-610
32 K. Cooper, A. Dasgupta, K. Kennedy, C. Koelbel, A. Mandal, G. Mann, M. Mazina, J. Mellor-Crummey, F. Berman, H. Casanova, A. Chien, H. Dail, X. Liu, A. Olugbile, O. Sievert, H. Xia, L. Johnsson, B. Liu, M. Patel, D. Reed, W. Deng, C. Mendes, Z. Shi, A. YarKhan and J. Dongarra, New Grid Scheduling and Rescheduling Methods in the GRADS Project, in Proc. of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04), Santa Fe, New Mexico USA, 2004-04, pp. 199-206
33 J. Gehring and T. Preiss, Scheduling a Meta computer with Uncooperative Sub-schedulers, in Proc. of the 5th Workshop on Job Scheduling Strategies for Parallel Processing, Lecture Notes on Computer Science, San Juan, Puerto Rico, Vol. 1659, 1999-04, pp. 179-201
34 S. J. Chapin, D. Katramatos, J. Karpovich and Andrew S. Grimshaw, The Legion Resource Management System, in Proc. of the 5th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP '99), in conjunction with the International Parallel and Distributed Processing Symposium (IPDPS '99), Lecture Notes in Computer Science, San Juan, Puerto Rico, 1999-04, Vol. 1659, pp.162-178
35 H. G. Rotithor, Taxonomy of Dynamic Task Scheduling Schemes in Distributed Computing Systems, in IEE Proc. on Computer and Digital Techniques, 1994-01, Vol. 141, No.1, pp.1-10
36 M, Arora, S. K. Das, R. Biswas, A Decentralized Scheduling and Load Balancing Algorithm for Heterogeneous Grid Environments, in Proc. of International Conference on Parallel Processing Workshops (ICPPW'02), Vancouver, British Columbia Canada, 2002-08, pp.499-505
37 E. Heymann, M. A. Senar, E. Luque and M. Livny, Adaptive Scheduling for Master-Worker Applications on the Computational Grid, in Proc. of the 1st IEEE/ACM International Workshop on Grid Computing, Lecture Notes In Computer Science, Bangalore, India, 2000-12, Vol. 1971, pp.214-227
38 D. P. Silva, W. Cirne and F. V. Brasileiro, Trading Cycles for Information: Using Replication to Schedule Bag-of-Tasks Applications on Computational Grids, in Proc of Euro-Par 2003, Klagenfurt, Austria, 2003-08, pp. 169-180
39 N. Fujimoto and K. Hagihara, Near-Optimal Dynamic Task Scheduling of Independent Coarse-Grained Tasks onto a Computational Grid, in Proc. of ICPP 2003, Kaohsiung, Taiwan, China, 2003-10, pp.80-87
40 N. Fujimoto and K. Hagihara, Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid, in Proc. of ISPDC 2003, Ljubljana, Slovenia, 2003-10, pp.80-87
41 G. Sabin, R. Kettimuthu, A. Rajan, and P. Sadayappan, Scheduling of Parallel Jobs in a Heterogeneous Multi-Site Environment, in the Proc. of the 9th International Workshop on Job Scheduling Strategies for Parallel Processing, Lecture Notes In Computer Science, Washington, U.S.A , 2003-06, Vol. 2862, pp.2-10
42 H. Shah, L. Oliker, R. Biswas, and W. Smith, Scheduling in Heterogeneous Grid Environments: The Effects of Data Migration, in Proc. of ADCOM2004: International Conference on Advanced Computing and Communication, Ahmedabad Gujarat, India, 2004-12
43 T. Casavant, and J. Kuhl, A Taxonomy of Scheduling in General-purpose Distributed Computing Systems, in IEEE Trans. on Software Engineering, 1988-02, Vol. 14, No.2, pp.141-154
44 R. Buyya, J. Giddy, and D. Abramson, An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications, in Proc. of the 2nd International Workshop on Active Middleware Services (AMS 2000), Pittsburgh, USA 2000-08, pp.221-230
45 R. Buyya and D. Abramson and J. Giddy and H. Stockinger, Economic Models for Resource Management and Scheduling in Grid Computing, in J. of Concurrency and Computation: Practice and Experience, Wiley Press, 2002-12, Vol.14, Issue. 13-15, pp.1507-1542
46 C. Ememann, V. Hamscher and R. Yahyapour, Economic Scheduling in Grid Computing, in Proc. of 8th Workshop on Job Scheduling Strategies for Parallel Processing, in conjunction with HPDC/GGF 5, Edinburgh, Scotland, UK, 2002-07, pp.128-152
47 Y. Zhu, L. Xiao, L. M. Ni and Z. Xu, Incentive-based P2P Scheduling in Grid Computing, in Proc. of the 3rd International Conference on Grid and Cooperative Computing (GCC2004), Wuhan, China, 2004-10, pp. 209-216
48 I. Foster, Globus Toolkit Version 4: Software for Service-Oriented Systems, in the Proc. of IFIP International Conference on Network and Parallel Computing, Springer-Verlag, Beijing, China, 2005-12, LNCS, Vol. 3779, pp. 2-13
49 N. Fujimoto and K. Hagihara, Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid, in Proc. of ISPDC 2003, Ljubljana, Slovenia, 2003-t0
50 X. He, X. Sun and G. Laszewski, A QoS Guided Min-Min Heuristic for Grid Task Scheduling, in J. of Computer Science and Technology, Special Issue on Grid Computing, 2003-07, Vol.18, No.4, pp.442-451
51 M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen and R. F. Freund, Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems, in J. of Parallel and Distributed Computing, 1999-10, Vol. 59, No. 2, pp.107-131
52 H. Casanova, A. Legrand, D. Zagorodnov and F. Berman, Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, in Proc. of the 9th hetero-geneous Computing Workshop (HCW'00), Cancun, Mexico, 2000-05, pp.349-363
53 陈东海，顾寅红，杨长生，网格计算中时间和费用限制下的任务调度算法，计算机应用，第24卷第8期 2004年8月，pp．94-97
54 Iverson MA Statistical Prediction of Task Executions Times Through Analytic Benchmarking for Scheduling in a Heterogeneous Environment [J] IEEE Trans Computers, 1999, 48(12), pp.1374-1379
55 Ziliang Zong, Adam Manzanares, Brian Stinar, and Xiao Qin, Energy-Aware Duplication Strategies for Scheduling Precedence-Constrained Parallel Tasks on Clusters, Proceedings of the 8th IEEE International Conference on Cluster Computing (Cluster 2006), 2006-09, pp.2-8
56 金海，陈刚，赵美平，容错计算网格作业调度模型的研究．计算机研究与发展，2004-08，Vol．41，No．8，p．22-24，27
57 Buyya R, Murshed M, Abramson D. A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Applications on Global Grids [A]. Proceedings of the 2002 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA02)[C], 2002, pp. 113-120
2 Ian Foster, What is the Grid? A Three Point Checklist, htrp://www-fp.mcs.anl.gov/'foster/Articles/WhatIsTheGrid.pdf, 2002, pp. 1-23
3 Ian Foster，Carl Kesselman，《网格计算》，金海译，第2版，北京：电子工业出版社，2004-10，pp．1-30
4 都志辉，陈渝，刘鹏，网格计算，北京：清华大学出版，2002-08，pp．1-44
5 I. Foster and C. Kesselman (editors), The Grid: Bluepnnt for a Future Computing Infrastructure, Morgan Kaufmann Publishers, USA, 1999, pp.1-52
6 I. Foster and A. Iamnitchi, On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing, in Proc. of 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03), Berkeley, CA, USA, February 2003, pp.118-128
7 I. Foster, C. Kesselman and S. Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, in the International J. Supercomputer Applications, 15(3), 2001, pp.200-220
8 Y. Zhu, A Survey on Grid Scheduling'Systems, Department of Computer Science, Hong Kong University of science and Technology, 2003, pp.2-8
9 Dogan A, zguner F, Scheduling Independent Tasks with QoS Requirements in Grid Computing with Time-Varying Resource Prices, Grid Computing-GRID 2002 [C], 2002, pp.58-69
10 Fangpeng Dong and Setim G. Akl., Scheduling Algorithms for Grid Computing: State of the Art and Open Problems, Technical Report, 2006-504, School of Computing, Queen's University, Canada, 2006-01, pp.7-19
11 J. Schopf, Ten Actions When Super Scheduling, document of Scheduling Working Group, Global Grid Forum, http://ww.ggf.org/documents/GFD.4.pdf, 2001-07
12 Michael Litzkow, Miron Livny, and Matt Mutka, Condor-A Hunter of Idle Workstation, 8th International Conference of Distributed Computing Systems, San Jose, California, 1988-01, pp.204-111
13 F. Berman, R. Wolski, The AppLeS Project: A Status Report, 1997
14 David Abramson, Rok Sosic, J. Giddy and B. Hall, Nimrod: A tool for performing parameter simulations using distributed workstations, In HPDC, 1995, pp.112-121
15 F. Berman, R. Wolski, H. Casanova, W. Cime, H. Dail, M. Faerman, S. Figueira, J. Hayes, G. Obertelli, J. Schopf, G. Shao, S. Smallen, N. Spring, A. Su and D. Zagorodnov, Adaptive Computing on the Grid Using AppLeS, in IEEE Trans. on Parallel and Distributed Systems (TPDS), 2003, Vol.14, No.4, pp.369-382
16 F. Berman, R. Wotski, S. Figueria, J. Schopf and G Shao, Application-Level Scheduling on Distributed Heterogeneous Networks, in Proc. of the 1996 ACM/IEEE Conference on Supercomputmg, Article No: 39, Pittsburgh, Pennsylvania USA, 1996-11, pp.423-433
17 X. Sun and M. Wu, Grid Harvest Service: A System for Long-term Application-level Task Scheduling, in Proc. of 2003 International Parallel and Distributed Processing Symposium (IPDPS 2003), Nice, France, 2003-04, pp. 25-32
18 V. Hamscher, U. Schwiegelshohn, A. Streit, R. Yahyapour, Evaluation of Job-Scheduling Strategies for Grid Computing, in Proc. of GRID 2000 GRID 2000, First IEEE/ACM International Workshop, Bangalore, India, 2000-12, pp. 191-202
19 G. Mateescu, Quality of Service on the Grid via Meta scheduling with Resource Co-Scheduling and Co-Reservation, International Journal of High Performance Computing Applications, 2003, Vol. 17, No. 3, pp.209-218
20 F. Berman, High-Performance Schedulers, chapter in The Grid: Blueprint for a Furore Computing Infrastructure, Morgan Kaufmann Publishers, 1998
21 K. Czajkowski, I. Foster, N. Karonis, C. Kesselman, S. Martin, W. Smith, and S. Tuecke, A Resource Management Architecture for Metacomputing Systems, In D. G. Feitelson and L. Rudolph, editors, in Proc of the 4th Workshop on Job Scheduling Strategies for Parallel Processing, Orlando, Florida USA, LNCS, 1998-03, Vol. 1459, pp. 62-82
22 http://www.openpbs.org
23 http://www.cs.wisc.edu/condor
24 陈颖，杨寿保，基于网格计算市场模型的资源与作业描述语言的研究，计算机科学，2005，Vol．32，No．2，pp．90-92
25 Qianfei FU, Shoubao YANG, Maosheng LI, Junmao ZHUN, Decentralized Computational Market Model for Grid Resource Management, Lecture Notes in Computer Science, 2004, Vol. 3033, pp.227-230
26 张文博，陈宁江，魏峻，黄涛，QoS获益驱动的中间件调度框架研究，软件学报，2006-06，Vol．17，No．6，pp．1381-1390
27 张伟哲，胡铭曾，张宏莉，刘凯鹏，多QoS约束网格作业调度问题的多目标演化算法，计算机研究与发展，2006，Vol．43，No．11，pp．1855-1862
28 官荷卿，张文博，魏峻，黄涛，一种应用敏感的Web服务请求调度策略，计算机学报，2006-07，Vol．29，No．7，pp．1189-1198
29 沈卓炜，汪芸，基于EDF策略的端到端实时系统可调度性分析算法，计算机研究与发展，2006，Vol．43，No．5，pp．813-820
30 H. El-Rewini, T. Lewis, and H.. Ali, Task Scheduling in Parallel and Distributed Systems, ISBN: 0130992356, PTR Prentice Hall, 1994
31 王保进，李明树，王志刚，优先级有限时的单处理器静态优先级调度，软件学报，2006-03，Vol．17，No．3，pp．602-610
32 K. Cooper, A. Dasgupta, K. Kennedy, C. Koelbel, A. Mandal, G. Mann, M. Mazina, J. Mellor-Crummey, F. Berman, H. Casanova, A. Chien, H. Dail, X. Liu, A. Olugbile, O. Sievert, H. Xia, L. Johnsson, B. Liu, M. Patel, D. Reed, W. Deng, C. Mendes, Z. Shi, A. YarKhan and J. Dongarra, New Grid Scheduling and Rescheduling Methods in the GRADS Project, in Proc. of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04), Santa Fe, New Mexico USA, 2004-04, pp. 199-206
33 J. Gehring and T. Preiss, Scheduling a Meta computer with Uncooperative Sub-schedulers, in Proc. of the 5th Workshop on Job Scheduling Strategies for Parallel Processing, Lecture Notes on Computer Science, San Juan, Puerto Rico, Vol. 1659, 1999-04, pp. 179-201
34 S. J. Chapin, D. Katramatos, J. Karpovich and Andrew S. Grimshaw, The Legion Resource Management System, in Proc. of the 5th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP '99), in conjunction with the International Parallel and Distributed Processing Symposium (IPDPS '99), Lecture Notes in Computer Science, San Juan, Puerto Rico, 1999-04, Vol. 1659, pp.162-178
35 H. G. Rotithor, Taxonomy of Dynamic Task Scheduling Schemes in Distributed Computing Systems, in IEE Proc. on Computer and Digital Techniques, 1994-01, Vol. 141, No.1, pp.1-10
36 M, Arora, S. K. Das, R. Biswas, A Decentralized Scheduling and Load Balancing Algorithm for Heterogeneous Grid Environments, in Proc. of International Conference on Parallel Processing Workshops (ICPPW'02), Vancouver, British Columbia Canada, 2002-08, pp.499-505
37 E. Heymann, M. A. Senar, E. Luque and M. Livny, Adaptive Scheduling for Master-Worker Applications on the Computational Grid, in Proc. of the 1st IEEE/ACM International Workshop on Grid Computing, Lecture Notes In Computer Science, Bangalore, India, 2000-12, Vol. 1971, pp.214-227
38 D. P. Silva, W. Cirne and F. V. Brasileiro, Trading Cycles for Information: Using Replication to Schedule Bag-of-Tasks Applications on Computational Grids, in Proc of Euro-Par 2003, Klagenfurt, Austria, 2003-08, pp. 169-180
39 N. Fujimoto and K. Hagihara, Near-Optimal Dynamic Task Scheduling of Independent Coarse-Grained Tasks onto a Computational Grid, in Proc. of ICPP 2003, Kaohsiung, Taiwan, China, 2003-10, pp.80-87
40 N. Fujimoto and K. Hagihara, Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid, in Proc. of ISPDC 2003, Ljubljana, Slovenia, 2003-10, pp.80-87
41 G. Sabin, R. Kettimuthu, A. Rajan, and P. Sadayappan, Scheduling of Parallel Jobs in a Heterogeneous Multi-Site Environment, in the Proc. of the 9th International Workshop on Job Scheduling Strategies for Parallel Processing, Lecture Notes In Computer Science, Washington, U.S.A , 2003-06, Vol. 2862, pp.2-10
42 H. Shah, L. Oliker, R. Biswas, and W. Smith, Scheduling in Heterogeneous Grid Environments: The Effects of Data Migration, in Proc. of ADCOM2004: International Conference on Advanced Computing and Communication, Ahmedabad Gujarat, India, 2004-12
43 T. Casavant, and J. Kuhl, A Taxonomy of Scheduling in General-purpose Distributed Computing Systems, in IEEE Trans. on Software Engineering, 1988-02, Vol. 14, No.2, pp.141-154
44 R. Buyya, J. Giddy, and D. Abramson, An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications, in Proc. of the 2nd International Workshop on Active Middleware Services (AMS 2000), Pittsburgh, USA 2000-08, pp.221-230
45 R. Buyya and D. Abramson and J. Giddy and H. Stockinger, Economic Models for Resource Management and Scheduling in Grid Computing, in J. of Concurrency and Computation: Practice and Experience, Wiley Press, 2002-12, Vol.14, Issue. 13-15, pp.1507-1542
46 C. Ememann, V. Hamscher and R. Yahyapour, Economic Scheduling in Grid Computing, in Proc. of 8th Workshop on Job Scheduling Strategies for Parallel Processing, in conjunction with HPDC/GGF 5, Edinburgh, Scotland, UK, 2002-07, pp.128-152
47 Y. Zhu, L. Xiao, L. M. Ni and Z. Xu, Incentive-based P2P Scheduling in Grid Computing, in Proc. of the 3rd International Conference on Grid and Cooperative Computing (GCC2004), Wuhan, China, 2004-10, pp. 209-216
48 I. Foster, Globus Toolkit Version 4: Software for Service-Oriented Systems, in the Proc. of IFIP International Conference on Network and Parallel Computing, Springer-Verlag, Beijing, China, 2005-12, LNCS, Vol. 3779, pp. 2-13
49 N. Fujimoto and K. Hagihara, Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid, in Proc. of ISPDC 2003, Ljubljana, Slovenia, 2003-t0
50 X. He, X. Sun and G. Laszewski, A QoS Guided Min-Min Heuristic for Grid Task Scheduling, in J. of Computer Science and Technology, Special Issue on Grid Computing, 2003-07, Vol.18, No.4, pp.442-451
51 M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen and R. F. Freund, Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems, in J. of Parallel and Distributed Computing, 1999-10, Vol. 59, No. 2, pp.107-131
52 H. Casanova, A. Legrand, D. Zagorodnov and F. Berman, Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, in Proc. of the 9th hetero-geneous Computing Workshop (HCW'00), Cancun, Mexico, 2000-05, pp.349-363
53 陈东海，顾寅红，杨长生，网格计算中时间和费用限制下的任务调度算法，计算机应用，第24卷第8期 2004年8月，pp．94-97
54 Iverson MA Statistical Prediction of Task Executions Times Through Analytic Benchmarking for Scheduling in a Heterogeneous Environment [J] IEEE Trans Computers, 1999, 48(12), pp.1374-1379
55 Ziliang Zong, Adam Manzanares, Brian Stinar, and Xiao Qin, Energy-Aware Duplication Strategies for Scheduling Precedence-Constrained Parallel Tasks on Clusters, Proceedings of the 8th IEEE International Conference on Cluster Computing (Cluster 2006), 2006-09, pp.2-8
56 金海，陈刚，赵美平，容错计算网格作业调度模型的研究．计算机研究与发展，2004-08，Vol．41，No．8，p．22-24，27
57 Buyya R, Murshed M, Abramson D. A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Applications on Global Grids [A]. Proceedings of the 2002 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA02)[C], 2002, pp. 113-120