Article

A survey of job scheduling in grids

Authors:

Congfeng Jiang,

Yinghui ZhaoAuthors Info & Claims

APWeb/WAIM'07: Proceedings of the joint 9th Asia-Pacific web and 8th international conference on web-age information management conference on Advances in data and web management

Pages 419 - 427

Published: 16 June 2007 Publication History

Abstract

The problem of optimally scheduling tasks onto heterogeneous resources in grids, minimizing the makespan of these tasks, has proved to be NP-complete. There is no best scheduling algorithm for all grid computing systems. An alternative is to select an appropriate scheduling algorithm to use in a given grid environment because of the characteristics of the tasks, machines and network connectivity. In this paper a survey is presented on the problem and the different aspects of job scheduling in grids such as (a) fault-tolerance; (b) security; and (c) simulation of grid job scheduling strategies are discussed. This paper also presents a discussion on the future research topics and the challenges of job scheduling in grids.

References

[1]

Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the grid: Enabling scalable virtual organizations. International Journal of High Performance Computing Applications, 15(3) (2001)200-222.

Digital Library

[2]

Ibarra, O.H., Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. Journal of Association of Computing Machine, 24(2) (1977)280- 289.

Digital Library

[3]

Braun, T.D., Siegel, H.J., Beck, N., Boloni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D., Yao, B.: 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) (2001)810-837.

Digital Library

[4]

Kwok, Y.K., Maciejewski, A.A., Siegel, H.J., Ahmad, I., Ghafoor, A.: A semi-static approach to mapping dynamic iterative tasks onto heterogeneous computing system. Journal of Parallel and Distributed Computing, 66(2006)77-98.

Digital Library

[5]

Dogana, A., Özgüner, F.: Scheduling of a meta-task with QoS requirements in heterogeneous computing systems. Journal of Parallel and Distributed Computing, 66(2) (2006)181-196.

Digital Library

[6]

Song, S., Hwang, K., Kwok, Y.K.: Risk-Resilient Heuristics and Genetic Algorithms for Security-Assured Grid Job scheduling. IEEE Transactions on Computers, 55(6) (2006)703-719.

Digital Library

[7]

Hamscher, V., Schwiegelshohn, U., Streit, A., Yahyapour, R.: Evaluation of job-scheduling strategies for grid computing. In: Proceedings of 1st IEEE/ACM International Workshop on Grid Computing (GRID 2000). LNCS Vol. 1971 (2000)191-202.

Digital Library

[8]

Legrand, A., Quinson, M., Casanova, H., Fujiwara, K.: The SlMGRlD project simulation and deployment of distributed applications. In: Proceedings of 15th IEEE International Symposium on High Performance Distributed Computing (HPDC06) (2006)385-386.

[9]

Fujimoto, N., Hagihara, K.: Near-Optimal Dynamic Task Scheduling of Independent Coarse-Grained Tasks onto a Computational Grid, In: Proceedings of International Conference on Parallel Processing(ICPP2003)(2003)391-398.

[10]

Abawajy, J.H.: Fault-Tolerant Dynamic Job Scheduling Policy. In: M. Hobbs, A. Goscinski, and W. Zhou. (Eds.): Proceedings of ICA3PP'05, LNCS Vol. 3719 (2005)165-173.

Digital Library

[11]

Kaya, K., Aykanat, C.: Iterative-improvement-based heuristics for adaptive scheduling of tasks sharing files on heterogeneous master-slave platforms. IEEE Transactions on Parallel and Distributed Systems, 17(8) (2006)883-896.

Digital Library

[12]

Shivle, S., Siegel, H.J., et al. Static allocation of resources to communicating subtasks in a heterogeneous ad hoc grid environment, Journal of Parallel and Distributed Computing, 66 (2006) 600-611.

Digital Library

[13]

Wolski, R.: Forecasting network performance to support dynamic scheduling using the Network Weather Service. In: Proceedings of the 6th IEEE International Symposium on High Performance Distributed Computing (HPDC97) (1997)316-325.

Digital Library

[14]

Schopf, J.M., D'Arcy, M., Miller, N., et al.: Monitoring and Discovery in a Web Services Framework: Functionality and Performance of the Globus Toolkit's MDS4, Available at http://www-unix.mcs.anl.gov/~schopf/Pubs/mds-sc05.pdf

[15]

Thomas, N.: Modeling job allocation where service duration is unknown. In: Proceedings of 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS'06), 2006.

Digital Library

[16]

Ernemann, C., Hamscher, V., Schwiegelshohn, U., Yahyapour, R., Streit, A.: On advantages of grid computing for parallel job scheduling. In: Proceedings of 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID 2002) (2002)39-46.

Digital Library

[17]

Beaumont, O., Carter, L., Ferrante, J., et al.: Centralized versus distributed schedulers for multiple bag-of-task applications. In: Proceedings of 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS'06), 2006.

Digital Library

[18]

Buyya R., Abramson D., Venugopal S.: The Grid Economy. Proceedings of the IEEE, 93(3) (2005)698-714.

[19]

S. Hwang, C. Kesselman.: A Flexible Framework for Fault Tolerance in the Grid, Journal of Grid Computing, 1(3) (2003)251-272.

[20]

Jones, P.L., Harrison, A.: The application of knowledge-based techniques to the monitoring of computers in a large heterogeneous distributed environment. Knowledge-Based Systems, 19(7) (2006)565-575.

Digital Library

[21]

Thomas, N., Bradley, J.T., Knottenbelt, W.J.: Stochastic analysis of scheduling strategies in a Grid-based resource model. IEE Proceedings: Software, 151(5) (2004)232-239.

[22]

Arenas, A.: State of the art survey on trust and security in Grid computing systems. Technical Report (RAL-TR-2006-008), 2006, CCLRC (ISSN 1358-6254).

[23]

Song, S., Hwang, K.: Trusted grid computing with security assurance and resource optimization. In: Proceedings of ISCA 17th International Conference on Parallel and Distributed Computing Systems (ISCA PDCS04) (2004)110-117.

[24]

Song, S., Hwang, K., Kwok, Y.K.: Trusted grid computing with security binding and trust integration. Journal of Grid Computing, 3(1) (2005)53-73.

[25]

Hwang, K., Kwok, Y.K., Song, S., et al.: GridSec: Trusted grid computing with security binding and self-defense against network worms and DDoS attacks. In: Proceedings of 5th International Conference on Computational Science, LNCS Vol. 3516 (2005)187-195.

Digital Library

[26]

Power, D.J., Politou, E.A., Slaymaker, M.A., et al.: Securing web services for deployment in health grids. Future Generation Computer Systems, 22(2006)547-570.

Digital Library

[27]

Zanikolas, S., Sakellariou, R.: Application-Level Simulation Modeling of Large Grids. In: Proceedings of 5th International Symposium on Cluster Computing and Grid (CCGrid'05) (2005)582-589.

Digital Library

[28]

W. J Bolosky, J.R. Douceur, D. Ely, et al.: Feasibility of a Serverless Distributed File System Deployed on an Existing Set of Desktop PCs. In: 2000 ACM SIGMETRICS, International Conference on Measurement and Modeling of Computer Systems, 28(1) (2000)34-43.

Digital Library

Cited By

Quang BQuang NMedernach EBreton VLong PQuyet TThanh BVan TBui MHong S(2013)Stretch optimization for virtual screening on multi-user pilot-agent platforms on grid/cloudProceedings of the 4th Symposium on Information and Communication Technology10.1145/2542050.2542063(301-310)Online publication date: 5-Dec-2013
https://dl.acm.org/doi/10.1145/2542050.2542063
Bulej LBurea THorký VKeznikl JTůma PCasale GField TAmaral J(2013)Adaptive deployment in ad-hoc systems using emergent component ensemblesProceedings of the 4th ACM/SPEC International Conference on Performance Engineering10.1145/2479871.2479922(343-346)Online publication date: 21-Apr-2013
https://dl.acm.org/doi/10.1145/2479871.2479922
Epimakhov IHameurlain ADillon TMorvan F(2011)Resource scheduling methods for query optimization in data grid systemsProceedings of the 15th international conference on Advances in databases and information systems10.5555/2041746.2041765(185-199)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2041746.2041765
Show More Cited By

Recommendations

An EasyGrid portal for scheduling system-aware applications on computational Grids: Research Articles
Middleware for Grid Computing

One of the objectives of computational Grids is to offer applications the collective computational power of distributed but typically shared heterogeneous resources. Unfortunately, efficiently harnessing the performance potential of such systems (i.e. ...
A PTS-PGATS based approach for data-intensive scheduling in data grids

Grid computing is the combination of computer resources in a loosely coupled, heterogeneous, and geographically dispersed environment. Grid data are the data used in grid computing, which consists of large-scale data-intensive applications, producing ...
Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs

In many manufacturing systems, jobs that are completed early are held as finished-goods inventory until their due-dates, and hence we incur earliness costs. Similarly, jobs that are completed after their due-dates incur penalty. The objective in such ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

APWeb/WAIM'07: Proceedings of the joint 9th Asia-Pacific web and 8th international conference on web-age information management conference on Advances in data and web management

June 2007

895 pages

ISBN:9783540724834

Editors:
Guozhu Dong
Wright State University, Department of Computer Science and Engineering
,
Xuemin Lin
University of New SouthWales & NICTA, Australia
,
Wei Wang
University of New South Wales, School of Computer Science and Engineering, Australia
,
Yun Yang
Swinburne University of Technology, Melbourne, Australia
,
Jeffrey Xu Yu
The Chinese University of Hong Kong, Department of Systems Engineering and Engineering Management, China

Sponsors

Anhui Computer Federation
Anhui University
The University of New South Wales
Anhui Association of Science and Technology
Chinese Univ. of Hong Kong: Chinese University of Hong Kong

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 16 June 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
21
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Quang BQuang NMedernach EBreton VLong PQuyet TThanh BVan TBui MHong S(2013)Stretch optimization for virtual screening on multi-user pilot-agent platforms on grid/cloudProceedings of the 4th Symposium on Information and Communication Technology10.1145/2542050.2542063(301-310)Online publication date: 5-Dec-2013
https://dl.acm.org/doi/10.1145/2542050.2542063
Bulej LBurea THorký VKeznikl JTůma PCasale GField TAmaral J(2013)Adaptive deployment in ad-hoc systems using emergent component ensemblesProceedings of the 4th ACM/SPEC International Conference on Performance Engineering10.1145/2479871.2479922(343-346)Online publication date: 21-Apr-2013
https://dl.acm.org/doi/10.1145/2479871.2479922
Epimakhov IHameurlain ADillon TMorvan F(2011)Resource scheduling methods for query optimization in data grid systemsProceedings of the 15th international conference on Advances in databases and information systems10.5555/2041746.2041765(185-199)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2041746.2041765
Miriam DEaswarakumar K(2010)A novel approach for QoS guided metascheduler for P2P grid systemProceedings of the First international conference on Information computing and applications10.5555/1925974.1925980(33-40)Online publication date: 15-Oct-2010
https://dl.acm.org/doi/10.5555/1925974.1925980
Hsu CChen T(2010)Performance- and economisation-oriented scheduling techniques for managing applications with QoS demands in gridsInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2010.0329965:4(219-226)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1504/IJAHUC.2010.032996
Abawajy J(2009)Adaptive hierarchical scheduling policy for enterprise grid computing systemsJournal of Network and Computer Applications10.1016/j.jnca.2008.04.00932:3(770-779)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1016/j.jnca.2008.04.009

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents