Efficient Refinery Scheduling Heuristic in Heterogeneous Computing Systems
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.
 Foster and C. Kesselman, “The Grid: Blueprint for a Future Computing Infrastructure,” Morgan Kaufmann Publishers, USA, 1999.
 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.
 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.
 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.
 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.
 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.
 A. Papoulis, “Probability, Random Variables and Stohastic processes,” MCGraw-Hill, New York, NY, 1984.
 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.
 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
 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.
 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