A quality-driven algorithm for task scheduling in grid market

doi:10.7523/j.issn.2095-6134.2011.1.013

Abstract

Abstract:

We propose a quality-driven algorithm for task scheduling in grid market, which is deadline- and budget-constrained and maximizes number of completed tasks (DBCN). This algorithm combines the high throughput advantage of Min-min algorithm and the global optimization advantage of linear programming. Meanwhile the algorithm considers not only all the tasks but also those prior ones. Compared with the Min-min and DBCT classical algorithms, DBCN completes about 10.6% and 22.0% more tasks and about 20% and 40% more prior tasks, respectively.

Key words: grid market, QoS, deadline and budget, scheduling algorithm

CLC Number:

TP393

SONG Hu, YANG Shou-Bao, LIU Xiao-Qian, GUO Liang-Min. A quality-driven algorithm for task scheduling in grid market[J]. , 2011, 28(1): 86-93.

References

[1] Buyya R, Abramson D, Giddy J. Economy driven resource management architecture for computational power Grids //PDPTA ’00: Proceedings of the 7th International Conference on Parallel and Distributed Processing Techniques and Applications. 2000.

[2] Ravi B, Sanjukta D, Robert G, et al. A market design for grid computing
[J]. INFORMS Journal on Computing, Forthcoming, 2007, 20(1):100-111.

[3] Stuer G, Vanmechelen K, Broeckhove J. A commodity market algorithm for pricing substitutable grid resources
[J]. Future Generation Computer Systems, 2007, 23(5):688-701.

[4] Buyya R, Murshe M, Abramson D. A deadline and budget constrained cost-time optimization algorithm for scheduling task farming applications on global grids //ICPDP ’02: The 2002 International Conference on Parallel and Distributed Processing Techniques and Applications. Las Vegas, Nevada, USA, 2002.

[5] Buyya R, Abramson D, Giddy J. Nimrod/G: An architecture for a resource management and scheduling System in a Global Computational Grid //HPC ASIA 2000: 4th International Conference and Exhibition on High Performance Computing in Asia-Pacific Region. Beijing, 2000.

[6] Armstrong R, Hensgen D, Kidd T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions //HCW ’98: the 7th IEEE Heterogeneous Computing Workshop. 1998:79- 87.

[7] Freund R, Gherrity M, Ambrosius S, et al. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet //HCW ’98: the 7th IEEE Heterogeneous Computing Workshop. 1998: 184-199.

[8] Ibarra O, Kim C. Heuristic algorithms for scheduling independent tasks on nonidentical processors
[J]. Journal of the ACM, 1997, 77(2): 280-289.

[9] Buyya R, Giddy J, Abramson D. An evaluation of economy-based resource trading and scheduling on computational power grids for parameter sweep applications //AMS ’00: The Second Workshop on Active Middleware Services, Pittsburgh, USA, 2000.

[10] Garg S, Konugurthi P, Buyya R. A linear programming driven genetic algorithm for meta-scheduling on utility grids //ADCOM’ 08: The 16th International Conference on Advanced Computing and Communications, Chennai, India, 2008: 19-26.

[11] Wang Z, Cao J W. Committee-based evaluation and selection of grid resources for QoS improvement //Grid’ 09: The 10th IEEE/ACM International Conference on Grid Computing. Canada, 2009: 138-144.

[12] Vanmechelen K, Depoorter W, Broeckhove J. Economic grid resource management for CPU Bound Applications with hard deadlines //CCGrid’ 08: The 8th International Conference on Cluster Computing and the Grid. Lyon, France, 2008.

[13] Sundaram V, Chandra A, Weissman J. Exploring the throughput-fairness tradeoff of deadline scheduling in heterogeneous computing environments //ACM SIGMETRICS’ 08: The 2008 International Conference on Measurement and Modeling of Computer Systems. Annapolis, Maryland, USA, 2008.

[14] Buyya R, Murshed M. GridSim: A Toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing
[J]. The Journal of Concurrency and Computation: Practice and Experience, 2002, 14(13): 1175-1220.

[15] Land A, Doig A. An automatic method of solving discrete programming problems
[J]. Econometrica, 1960, 28: 497-520.