It is the cache of http://ojs.academypublisher.com/index.php/jait/article/view/5438. It is a snapshot of the page. The current page could have changed in the meantime.
Tip: To quickly find your search term on this page, press Ctrl+F or ⌘-F (Mac) and use the find bar.

Efficient Refinery Scheduling Heuristic in Heterogeneous Computing Systems | Bansal | Journal of Advances in Information Technology
Journal of Advances in Information Technology, Vol 2, No 3 (2011), 159-164, Aug 2011
doi:10.4304/jait.2.3.159-164

Efficient Refinery Scheduling Heuristic in Heterogeneous Computing Systems

Sunita Bansal, Chittaranjan Hota

Abstract


With the emergence of distributed systems, the problem of task scheduling has been arousing attention in recent past. Task scheduling is a NP-complete problem and it is more complicated under the distributed heterogeneous computing environment. To harness the potential of these systems, efficient scheduling algorithms are needed. This paper proposes a new distributed scheduling algorithm for independent tasks to be assigned optimally amongst available machines. The approach works in two phases. In first phase, it assigns a task according to the Min-min heuristic and in second phase, it improves the scheduling by using efficient refinery scheduling heuristic.  The refinery heuristic balances the load across all the machines and reduces the make-span time of jobs. The results obtained using the proposed heuristic improves over the existing approaches. 



Keywords


Scheduling, Heuristics, Load balancing, Grid computing.

References


[1] Foster and C. Kesselman, “The Grid: Blueprint for a Future Computing Infrastructure,” Morgan Kaufmann Publishers, USA, 1999.

[2] Tracy D. Braun, Howard Jay Siegel, and Noah Beck, “A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks on to Heterogeneous Distributed Computing Systems,” Journal of Parallel and Distributed Computing, Vol.61, No.6, June 2001, pp. 810-837.
http://dx.doi.org/10.1006/jpdc.2000.1714

[3] Casanova H., Legrand, A., Zagorodnov, D., and Berman, F. “Heuristics for Scheduling Parameter Sweep Applications in Grid Environment,” Proceeding of 9th Heterogeneous Computing Workshop, Cancun, Mexico, May 2000, pp. 349-363.

[4] Saeed Parsa and Reza Entezari-Maleki, “RASA: A New Grid Task Scheduling Algorithm”, International Journal of Digital Content Technology and its Applications Vol. 3, No. 4, December 2009, pp. 91-99.

[5] Kamalam G. K and MuralibhaskaranV, “A New Heuristic Approach: Min-mean Algorithm for Scheduling Meta-Tasks on Heterogeneous Computing Systems,” International Journal of Computer Science and Network Security, Vol.10, No.1, January 2010, pp. 24-31.

[6] Kadda Beghdad Bey, Farid Benhammadia, Aicha Mokhtarib and Zahia Guessoumc, “Independent Task Scheduling in Heterogeneous Environment via Make-span Refinery Approach,” International Conference on Machine and web Intelligence, Algiers, Algiers, October 2010, pp. 211-217.

[7] A. Papoulis, “Probability, Random Variables and Stohastic processes,” MCGraw-Hill, New York, NY, 1984.

[8] Kim J K, Shivle S, and Siegel H J, “Dynamic Mapping in a Heterogeneous Environment with Tasks having Priorities and Multiple Deadlines,” International Symposium on Parallel and Distributed Processing, Washington, May 2003, pp. 98-110.

[9] He Xiao Shan, Sun Xianhe, “QoS Guided Min-Min Heuristic for Grid Task Scheduling,” Journal of Computer Science and Technology, Vol.18, No.4, 2003, pp. 442-451
http://dx.doi.org/10.1007/BF02948918

[10] Ehsan Ullah Munir, Jian-zhong Li, Sheng-fei Shi1, Zhao-nian Zou and Qaisar Rasool, “A New Heuristic for Task Scheduling in Heterogeneous Computing Environment,” Journal of Zhejiang University Science, Vol.9, No.12, September 2008, pp. 1715-1723.
http://dx.doi.org/10.1631/jzus.A0820007

[11] M. Wu, W. Shu and H. Zhang, “Segmented Min-Min: A Static Mapping Algorithm for Meta-Tasks on Heterogeneous Computing Systems,” Proceedings of the 9th Heterogeneous Computing Workshop, Cancun, Mexico, May 2000, pp. 375-385.


Full Text: PDF


Journal of Advances in Information Technology (JAIT, ISSN 1798-2340)

Copyright @ 2006-2014 by ACADEMY PUBLISHER – All rights reserved.