Email this article Implementation of Multi-objective Evolutionary Algorithm for Task Scheduling in Heterogeneous Distributed Systems
Abstract
This paper presents an effective method for task scheduling in heterogeneous distributed systems. Its objective is to minimize the last task’s finish time and to maximize the system reliability probability. The optimum is carried out through a non-domination sort genetic algorithm. The experimental results based on both randomly generated graphs and the graphs of some real applications showed that, when compared to two well known previous methods, such as heterogeneous earliest finish time (HEFT) algorithm and Critical Path Genetic Algorithm, this algorithm surpasses previous approaches in terms of both last task’s finish time and the system reliability probability.
Keywords
References
[1] H. El-Rewini, T.G. Lewis, Scheduling parallel program tasks onto arbitrary target machines, J. Parallel Distrib. Comput. 9 (2) (1990) 138-153.
http://dx.doi.org/10.1016/0743-7315(90)90042-N
[2] M. Iverson, F. Ozuner, G. Follen, Parallelizing existing applications in a distributed heterogeneous environment, in: Proceedings of Heterogeneous Computing Workshop, 1995, pp. 93-100.
[3] P.Y.R. Ma, E.Y.S. Lee, M. Tsuchiya, A task allocation model for distributed computing systems, IEEE Trans. Comput. 31 (1) (1982) 41-47
http://dx.doi.org/10.1109/TC.1982.1675884
[4] G.Q. Liu, K.L. Poh, M. Xie, Iterative list scheduling for heterogeneous computing, J. Parallel Distrib. Comput. 65 (5) (2005) 654-665
http://dx.doi.org/10.1016/j.jpdc.2005.01.002
[5] H. Topcuoglu, S. Hariri, M.-Y. Wu, Performance-effective and low complexity task scheduling for heterogeneous computing, IEEE Trans. Parallel Distrib. Syst.13 (3) (2002) 260-274.
http://dx.doi.org/10.1109/71.993206
[6] Wu, A.S., H. Yu, S. Jin, K.-C. Lin, and G. Schiavone, 2004. “An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling,” IEEE Trans. Parallel and Distributed Systems, 15: 824-834.
http://dx.doi.org/10.1109/TPDS.2004.38
[7] Kwok, Y. and I. Ahmad, 1999,”Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors,” ACM Computing Survey, 31: 406-471.
http://dx.doi.org/10.1145/344588.344618
[8] Fatma A.Omara,Mona M.Arafa,Genetic algorithms fo task scheduling problem.Journal of Parallel and Distributed Computing,70(2010):13-22
http://dx.doi.org/10.1016/j.jpdc.2009.09.009
[9] Attiya, G., Hamam, Y., 2006. Task allocation for maximizing reliability of distributed systems: a simulated annealing approach. Journal of Parallel and Distributed Computing 66, 1259–1266
http://dx.doi.org/10.1016/j.jpdc.2006.06.006
[10] Shatz, S.M., Wang, J.P., Goto, M., 1992. Task allocation for maximizing reliability of distributed computer systems. IEEE Transactions on Computers 41, 1156–1168.
http://dx.doi.org/10.1109/12.165396
[11] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. On Evolutionary Computation, 2002,6(2):182−197.
http://dx.doi.org/10.1109/4235.996017
[12] A. Dogan, F. Özgüner, Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing, IEEE Trans. Parallel Distrib. Syst. 13 (3) (2002) 308-323
http://dx.doi.org/10.1109/71.993209
[13] Mohammad I. Daoud, Nawwaf Kharma, A high performance algorithm for static task scheduling in heterogeneous distributed computing systems, J.Parallel Distrib. Comp ut. 68 (4) (2008) 399409.
[14] Y. Chung, S. Ranka, Application and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors, in: Proc. Super Computing, 1992, pp. 512-521.
[15] C.M. Woodside, G.G. Monforton, Fast allocation of processes in distributed and parallel systems, IEEE Trans. Parallel Distrib. Syst. 4 (2) (1993) 164174
http://dx.doi.org/10.1109/71.207592
[16] M. Wu, D. Dajski, Hypertool: a programming aid for message passing systems, IEEE Trans. Parallel Distrib. Syst. 1 (3) (1990) 330-343
http://dx.doi.org/10.1109/71.80160
Full Text: PDF