Abstract
Computational grid has a promising future in large-scale computing, because it enables the sharing of widely distributed computing resources. Good managements with excellent scheduling algorithms are in great demand to take full advantage of it. Many scheduling algorithms in grid computing are for independent tasks. However, communications are very common in scientific computing programs. In this paper, we will propose an easy-implemented algorithm to schedule the tasks with some communications. Our algorithm is suitable for a large proportion of scientific computing programs, and is based on Binary Integer Programming. It is able to meet the users’ quality of service (QoS) requirements, and to minimize the combination of costs and time consumed by the users’ programs. We will give an example of scheduling a typical scientific computing task to show the power of our algorithm. In our experiment, the grid resource consists of an SGI Onyx 3900 supercomputer, four SGI Octane workstations, four Intel P4-2.0GHz PCs and four Intel P4-1.8GHz PCs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Foster, I., Kesselman, C. (eds.): The Grid: Blueprint for a Future Computing Infrastructure. Morgan Kaufmann Publishers, USA (1999)
GRAM: Grid Resource Allocation & Management, Argonne National Laboratory, and USC Information Sciences Institute
Youn, C.: Resource Management and Scheduling in Grid (2002)(Concepts and Trends)
Buyya, R., Abramson, D., Giddy, J., Stockinger, H.: Economic Models for Resource Management and Scheduling in Grid Computing, Special Issue on Grid Computing Environments. Journal of Concurrency and Computation: Practice and Experience (CCPE) 14(13-15) (2002)
Dogan, A., Özgüner, F.: Scheduling Independent Tasks with QoS Requirements in Grid Computing with Time-Varying Resource Prices. In: Proceeding of Grid Computing-GRID 2002, pp. 58–69 (2002)
Amoura, K., Bampis, E., Kenyon, C., Manoussakis, Y.: Scheduling Independent Multiprocessor Tasks. Algorithmica 32, 247–261 (2002)
Buyya, R., Murshed, M., Abramson, D.: A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Applications on Global Grids, http://www.cs.mu.oz.au/~raj/ (current September 14, 2003)
Yu, J., Venugopal, S., Buyya, R.: A Market-Oriented Grid Directory Service for Publication and Discovery of Grid Service Providers and their Service, http://www.cs.mu.oz.au/~raj/ (current September 14, 2003)
Iverson, M.A., Özgüner, F., Lee, C.: Potter: Statistical Prediction of Task Execution Times through Analytic Benchmarking for Scheduling in a Heterogeneous Environment. IEEE Trans. Computers 48(12), 1374–1379 (1999)
Reistad, B., Gifford, D.K.: Static Dependent Costs for Estimating Execution Time. In: Proc. of the 1994 ACM Conference on LISP and functional programming, pp. 65–78 (1994)
Hillier, F.S., Lieberman, G.J.: Introduction to Operations Research, 7th edn. McGraw-Hill Higher Education, New York (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feng, H., Song, G., Zheng, Y., Xia, J. (2004). A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Dependent Tasks in Grid Computing. In: Li, M., Sun, XH., Deng, Q., Ni, J. (eds) Grid and Cooperative Computing. GCC 2003. Lecture Notes in Computer Science, vol 3033. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24680-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-24680-0_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21993-4
Online ISBN: 978-3-540-24680-0
eBook Packages: Springer Book Archive