Abstract
A resource scheduling algorithm called XMin-min is proposed in this paper. In the XMin-min algorithm, we consider not only the expected execution time of tasks, but also expected communication time when calculating expected completion time. In the paper, the execution cost of tasks and budget of application are selected as QoS and an algorithm XMin-min with QoS is also proposed. An extended high-level timed Petri net (EHLTPN) model suiting scheduling of resource in grid computing is presented in the paper. In the EHLTPN, the firing times assigned to transitions are functions of the tokens of input places. We construct a simple model for the resource scheduling in grid computing using EHLTPN. A definition of Reachable Scheduling Graph (RSG) of EHLTPN to analyze the timing property of the resource scheduling is given in this paper. Two algorithms can be use to settle the “state explosion” problem while constructing RSG of EHLTPN.
This work is support partially by projects of National Preeminent Youth Science Foundation (No. 60125205), National 863 Plan (2002AA4Z3430, 2002AA1Z2102A), Foundation for University Key Teacher by the Ministry of Education, Shanghai Science & Technology Research Plan (02DJ14064, 03JC14071), Open project of Laboratory of Computer Science, ISCAS (SYSKF0304).
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
Buyya, R., Giddy, J., Abramson, D.: An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for parameter Sweep Applications. In: Proceedings of the 2nd Int. Workshop on Active Middleware Services (AMS 2000), Kluwer Academic Press, USA (2000)
Maheswaran, M., Ali, S., et al.: Dynamic Mapping of a Class of Independent Task onto Heterogeneous Computing Systems. In: 8th IEEE Heterogeneous Computing Workshop (HCW 1999), San Juan, Puerto Rico (1999)
He, X.-S., Sun, X.-H., Laszewski, G.V.: A QoS Guided Scheduling Algorithm for Grid Computing. In: Proc. of the Int. Workshop on Grid and Cooperative Computing (GCC 2002), Sanya, China, pp. 745–758 (2002)
Murata, T.: Petri Nets: Properties, Analysis And Applications. Proceeding of IEEE 77(4), 541–580 (1989)
Jensen, K.: Coloured Petri nets: Basic Concepts, Analysis Methods and Practical Use. In: Basic Concepts. Mono-graphs in Theoretical Computer Science, vol. 1, Springer, Heidelberg (1997) (2nd corrected printing)
Zuberek, W.M.: Timed Petri Nets: Definitions, Properties and Applications. Microelectron. Reliab. 31(4), 627–644 (1991)
Prashant Reddy, J., Kumanan, S., Krishnaiah Chetty, O.V.: Application of Petri Nets and a Genetic algorithm to Multi-Mode Multi-Resource Constrained Project Scheduling. AMT 17, 305–314 (2001)
Huang, B., Zhang, B.: A New Scheduling Model Based on Extended Petri Net - TREM Net. In: Proc. of the Int. Conference on Robotics and Automation, San Diego, CA, USA, vol. 1 (ICRA94-1), pp. 495–500 (1994)
Han, Y.-J., Jiang, C.-J.: Extended Colored Time Petri Net -Based Resource Scheduling in Grid Computing. In: Proc. of the Int. Workshop on Grid and Cooperative Computing (GCC 2002), Sanya, China, pp. 7345–353 (2002)
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
Han, Y., Jiang, C., Fu, Y., Luo, X. (2004). Resource Scheduling Algorithms for Grid Computing and Its Modeling and Analysis Using Petri Net. 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_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-24680-0_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21993-4
Online ISBN: 978-3-540-24680-0
eBook Packages: Springer Book Archive