World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A TAXONOMY OF TASK SCHEDULING ALGORITHMS IN THE GRID

    One motivation of Grid computing is to aggregate the power of widely distributed resources, and provide non-trivial services to users. To achieve this goal, efficient task scheduling algorithms are essential. However, scheduling algorithms in the Grid present high diversities that need to be classified. In this paper, with the help of an abstract scheduling architecture, some key features of the task scheduling problem in the Grid are discussed, followed by a taxonomy of the scheduling algorithms. Some typical examples are given in each category to present a picture of the current research and help to find new research problems.

    This research was supported by the Natural Sciences and Engineering Research Council of Canada.

    References

    • A. Abraham, R. Buyya and B. Nath, Nature's Heuristics for Scheduling Jobs on Computational Grids, Proc. 8th IEEE International Conference on Advanced Computing and Communications (2000) pp. 45–52. Google Scholar
    • A. H. Alhusaini, V. K. Prasanna and C. S. Raghavendra, A Unified Resource Scheduling Framework for Heterogeneous Computing Environments, Proc. the 8th Heterogeneous Computing Workshop (HCW) (1999) pp. 156–165. Google Scholar
    • M. Arora, S. K. Das and R. Biswas, A Decentralized Scheduling and Load Balancing Algorithm for Heterogeneous Grid Environments, Proc. International Conference on Parallel Processing (ICPP) (2002) pp. 499–505. Google Scholar
    • M. Baker, R. Buyya and D. Laforenza, J. Software-Practice & Experience 32(15), 1437 (2002). Crossref, ISIGoogle Scholar
    • F.   Berman , chapter in The Grid: Blueprint for a Future Computing Infrastructure , eds. I.   Foster and C.   Kesselman ( Morgan Kaufmann Publishers , 1998 ) . Google Scholar
    • F. Bermanet al., IEEE Trans., on Parallel and Distributed Systems 14(4), 369 (2003). Crossref, ISIGoogle Scholar
    • J. Blytheet al., Task Scheduling Strategies for Workflow-based Applications in Grids, Proc. the 5th IEEE International Symp. on Cluster Computing and the Grid (CCGrid) (2005) pp. 759–767. Google Scholar
    • R. Braunet al., J. Parallel and Distributed Computing 61(6), 810 (2001). Crossref, ISIGoogle Scholar
    • R. Buyya, J. Giddy and D. Abramson, An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications, Proc. the 2nd International Workshop on Active Middleware Services (2000) pp. 221–230. Google Scholar
    • R. Buyya, D. Abramson and S. Venugopal, Proc. the IEEE 93(3), 698 (2005). Crossref, ISIGoogle Scholar
    • H. Casanovaet al., Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, Proc. HCW 2000 (2000) pp. 349–363. Google Scholar
    • C. Cavanaugh et al. , Quality of Service Negotiation for Distributed, Dynamic Real-Time Systems , Proc. the 14th IEEE International Parallel & Distributed Processing Symposium (IPDPS) ( 2000 ) . Google Scholar
    • S. J. Chapinet al., The Legion Resource Management System, Proc. the 5th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP) (1999) pp. 162–178. Google Scholar
    • K. Cooperet al., New Grid Scheduling and Rescheduling Methods in the GrADS Project, Proc. the IPDPS 2004 (2004) pp. 199–206. Google Scholar
    • K. Czajkowskiet al., A Resource Management Architecture for Metacomputing Systems, Proc. JSSPP 1998, LNCS 1459 (1998) pp. 62–82. Google Scholar
    • K. Czajkowskiet al., Grid Information Services for Distributed Resource Sharing, Proc. the 10th IEEE International Symposium on High-Performance Distributed Computing (HPDC) (2001) pp. 181–194. Google Scholar
    • H. Dail, H. Casanova and F. Herman, A Decoupled Scheduling Approach for the GrADS Environment, Proc. the SuperComputing 2002 (2002) pp. 1–14. Google Scholar
    • E. Deelmanet al., J. Grid Computing 1(1), 9 (2003). ISIGoogle Scholar
    • E. Deelmanet al., Pegasus: Mapping Scientific Workflows onto the Grid, Proc. Grid Computing: Second European AcrossGrids Conference (2004) pp. 11–26. Google Scholar
    • F. Desprez and A. Vernois, J. Grid Computing 4(1), 19 (2006). CrossrefGoogle Scholar
    • F. Dong and S. Akl, A Joint Data and Computation Scheduling Algorithm for the Grid, Proc. Euro-Par 2007, LNCS 4681 (2007) pp. 587–597. Google Scholar
    • F.   Dong and S.   Akl , PFAS: A Resource-performance-fluctuation-aware Workflow Scheduling Algorithm for Grid Computing , Proc. HCW 2007 ( 2007 ) . Google Scholar
    • F.   Dong and S.   Akl , A Mobile Agent Based Workflow Rescheduling Approach for the Grid , Proc. the 19th International Conference on Parallel and Distributed Computing and Systems (PDCS) ( 2007 ) . Google Scholar
    • F.   Dong and S.   Akl , Distributed Two-phase Computation-data Combinational Workflow Scheduling Algorithms for the Grid , Proc. ICPP 2007 ( 2007 ) . Google Scholar
    • H.   El-Rewini , T.   Lewis and H.   Ali , Task Scheduling in Parallel and Distributed Systems ( PTR Prentice Hall , 1994 ) . Google Scholar
    • I. Foster, Globus Toolkit Version 4: Software for Service-Oriented Systems, Proc. IFIP International Conference on Network and Parallel Computing, LNCS 3779 (2005) pp. 2–13. Google Scholar
    • J. Gehring and T. Preiss, Scheduling a Metacomputer with Uncooperative Sub-schedulers, Proc. the JSSPP 1999, LNCS 1659 (1999) pp. 179–201. Google Scholar
    • V. Hamscheret al., Evaluation of Job-Scheduling Strategies for Grid Computing, Proc. the 1st IEEE/ACM International Workshop on Grid Computing (Grid), LNCS 1971 (2000) pp. 191–202. Google Scholar
    • X. He, X. Sun and G. Laszewski, J. of Computer Science and Technology 18(4), 442 (2003). Crossref, ISIGoogle Scholar
    • E. Heymannet al., Adaptive Scheduling for Master-Worker Applications on the Computational Grid, Proc. Grid 2000, LNCS 1971 (2000) pp. 214–227. Google Scholar
    • Y. Derbal, J. Grid Computing 4(4), 373 (2006). CrossrefGoogle Scholar
    • T.   Ma and R.   Buyya , Critical-Path and Priority based Algorithms for Scheduling Workflows with Parameter Sweep Tasks on Global Grids , Proc. the 17th International Symposium on Computer Architecture and High Performance Computing ( 2005 ) . Google Scholar
    • J. MacLaren et al. , Towards Service Level Agreement Based Scheduling on the Grid , Proc. the 2nd European Across Grids Conference ( 2004 ) . Google Scholar
    • G. Malewicz, A. Rosenberg and M. Yurkewych, IEEE Trans. Comput. 55(6), 757 (2006). Crossref, ISIGoogle Scholar
    • G. Malewiczet al., J. Grid Computing 5(2), 197 (2007). Crossref, ISIGoogle Scholar
    • G. Mateescu, International J. High Performance Computing Applications 17(3), 209 (2003). Crossref, ISIGoogle Scholar
    • S. McGoughet al., Workflow Enactment in ICENI, Proc. UK e-Science All Hands Meeting (2004) pp. 894–900. Google Scholar
    • S. Park and J. Kim, Chameleon: a Resource Scheduler in a Data Grid Environment, Proc. CCGrid 2003 (2003) pp. 253–260. Google Scholar
    • K. Ranganathan and I. Foster, Identifying Dynamic Replication Strategies for a High Performance Data Grid, Proc. Grid 2001, LNCS 2242 (2001) pp. 75–86. Google Scholar
    • K. Ranganathan and I. Foster, Decoupling Computation and Data Scheduling in Distributed Data-Intensive Applications, Proc. HPDC 2002 (2002) pp. 352–361. Google Scholar
    • H. G. Rotithor, IEE Proc. on Computer and Digital Techniques 141(1), l (1994). Google Scholar
    • F. D. Sacerdotiet al., Wide area cluster monitoring with Ganglia, Proc. IEEE International Conference on Cluster Computing (Cluster) (2003) pp. 289–298. Google Scholar
    • R. Sakellariou and H. Zhao, J. of Scientific Programming 12(4), 253 (2004). Crossref, ISIGoogle Scholar
    • J. Schopf and F. Berman, Stochastic Scheduling, Proc. SuperComputing 1999 (1999) pp. 48–68. Google Scholar
    • J. Schopf, Ten Actions When SuperScheduling, document of Scheduling Working Group, Global Grid Forum, http://www.ggf.Org/documents/GFD.4.pdf, July 2001 . Google Scholar
    • H. Shan et al. , Scheduling in Heterogeneous Grid Environments: The Effects of Data Migration , Proc. 2004 International Conference on Advanced Computing and Communication ( 2004 ) . Google Scholar
    • H. J. Siegel, H. G. Dietz and J. K. Antonio, ACM Computing Surveys 28(1), 237 (1996). Crossref, ISIGoogle Scholar
    • S. Song, Y. Kwok and K. Hwang, Security-Driven Heuristics and A Fast Genetic Algorithm for Trusted Grid Job Scheduling, Proc. IPDPS 2005 (2005) pp. 65–74. Google Scholar
    • A. Suet al., International J. High Performance Computing Applications 13(3), 253 (1999). Crossref, ISIGoogle Scholar
    • J. Subhlok, P. Lieu and B. Lowekamp, Automatic Node Selection for High Performance Applications on Networks, Proc. the 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (1999) pp. 163–172. Google Scholar
    • X. Sun and M. Wu, Grid Harvest Service: A System for Long-term Application-level Task Scheduling, Proc. 17th IPDPS (2003) pp. 25–32. Google Scholar
    • A. Takefusaet al., A Study of Deadline Scheduling for Client-Server Systems on the Computational Grid, Proc. the HPDC 2001 (2001) pp. 406–415. Google Scholar
    • H. Topcuoglu, S. Hariri and M. Y. Wu, IEEE Trans. Parallel and Distributed Systems 13(3), 260 (2002). Crossref, ISIGoogle Scholar
    • M. Wieczorek, R. Prodan and T. Fahringer, ACM SIGMOD Record 34(3), 56 (2005). Crossref, ISIGoogle Scholar
    • R. Wolski, N. T. Spring and J. Hayes, J. Future Generation Computing Systems 15(5-6), 757 (1999). CrossrefGoogle Scholar
    • D.   Wright , Cheap Cycles from the Desktop to the Dedicated Cluster: Combining Opportunistic and Dedicated Scheduling with Condor , Proc. Conference on Linux Clusters: the HPC Revolution ( 2001 ) . Google Scholar
    • M. Wu and X. Sun, A General Self-Adaptive Task Scheduling System for Non-Dedicated Heterogeneous Computing, Proc. Cluster 2003 (2003) pp. 354–361. Google Scholar
    • M. Wu and X. Sun, International J. High Performance Computing and Networking 2(2), 186 (2004). CrossrefGoogle Scholar
    • L. Younget al., Scheduling Architecture and Algorithms within the ICENI Grid Middleware, Proc. UK e-Science All Hands Meeting (2003) pp. 5–12. Google Scholar
    • J.   Yu , R.   Buyya and C. K.   Tham , QoS-based Scheduling of Workflow Applications on Service Grids , Proc. the 1st IEEE International Conference on e-Science and Grid Computing ( 2005 ) . Google Scholar
    • J. Yu and R. Buyya, J. Grid Computing 3(3-4), 171 (2005). Crossref, ISIGoogle Scholar
    • Z.   Yu and W.   Shi , An Adaptive Rescheduling Strategy for Grid Workflow Applications , Proc. IPDPS 2007 ( 2007 ) . Google Scholar
    • http://www.globus.org . Google Scholar
    • http://www.openpbs.org . Google Scholar
    • http://www.cs.wise.edu/condor . Google Scholar