A Hybrid Genetic Scheduling Algorithm to Heterogeneous Distributed System

Yan Kang, Defu Zhang

Department of Computer Science, Xiamen University, Xiamen, Fujian, China.
Department of Software Engineering, Yunnan University, Kunming, Yunnan, China.

DOI: 10.4236/am.2012.37111                

Abstract

In parallel and distributed computing, development of an efficient static task scheduling algorithm for directed acyclic graph (DAG) applications is an important problem. The static task scheduling problem is NP-complete in its general form. The complexity of the problem increases when task scheduling is to be done in a heterogeneous environment, consisting of processors with varying processing capabilities and network links with varying bandwidths. List scheduling algorithms are generally preferred since they generate good quality schedules with less complexity. But these list algorithms leave a lot of room for improvement, especially when these algorithms are used in specialized heterogeneous environments This paper presents an hybrid genetic task scheduling algorithm for the tasks run on the network of heterogeneous systems and represented by Directed Acyclic Graphs (DAGs). First, the algorithm assigns a coupling factor to each task to present the tasks should be scheduled onto the same processor by avoiding the large communication time. Second, the algorithm generate some high quality initial solution by scheduling the tasks which are strongly coupled with each other onto the same processor, and improve the quality of the solution by using coupling initial solutions, random solution, near optimal solutions obtained by the list scheduling algorithm in the crossover and mutation operator. The performance of the algorithm is illustrated by comparing with the existing effectively scheduling algorithms.

Keywords

Scheduling; Genetic Algorithm; Heterogeneous; Distributed System

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. L. Graham, L. E. Lawler, J. K. Lenstra and A. H. Kan, “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey,” Annals of Discrete Mathematics, Vol. 5, 1979, pp. 287-326.
[2]	H. Topcuoglu, S. Harir and M.-Y. Wu, “Performance Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 3, 2002, pp. 260-274. doi:10.1109/71.993206
[3]	H. EI-Rewini and T. G. Lewis, “Scheduling Parallel Program Tasks onto Arbitrary Target Machines,” Journal of Parallel and Distributed Computing, Vol. 9, No. 2, 1990, pp. 138-153. doi:10.1016/0743-7315(90)90042-N
[4]	M. Iverson, F. Ozguner and G. Follen, “Parallelizing Existing Applications in a Distributed Heterogeneous Environments,” Proceedings of the Heterogeneous Computing Workshop, 1995, pp. 93-100.
[5]	H. Topcuoglu, S. Hariri and M. Y. Wu, “Performance Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 3, 2002, pp. 260-274.
[6]	C. Boeres, J. V. Filho and V. E. F. Rebello, “A ClusterBased Strategy for Scheduling Task on Heterogeneous Processors,” Proceedings of the 16th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Brazil, October 2004.
[7]	S. Basker and P. C. SaiRanga, “Scheduling Directed A-Cyclic Task Graphs on Heterogeneous Network of Workstations to Minimize Schedule Length,” Proceedings of the ICPPW, Taiwan, October 2003.
[8]	R. Bajaj and D. P. Agrawal, “Improving Scheduling of Tasks in a Heterogeneous Environments,” IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 2, 2004, pp. 107-118. doi:10.1109/TPDS.2004.1264795
[9]	L. Wang, H. J. Siegel, V. P. Rowchoudhry and A. A. Maciejewski, “Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic Algorithm-Based Approach,” Journal of Parallel and Distributed Computing, Vol. 47, No. 1, 1997, pp. 8-22. doi:10.1006/jpdc.1997.1392
[10]	M. K. Dhodhi, I. Ahmad and A. Yatama, “An Integrated Technique for Task Matching and Scheduling onto Distributed Heterogeneous Computing Systems,” Journal of Parallel and Distributed Computing, Vol. 62, No. 9, 2002, pp. 1338-1361. doi:10.1006/jpdc.2002.1850
[11]	S. C. Kim and S. Lee, “Push-Pull: Guided Search DAG Scheduling for Heterogeneous Clusters,” Proceedings of the International Conference on Parallel Processing, Oslo, June 2005.
[12]	S. W. Annie, H. Yu, S. Jin and K.-C. Lin, “An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling,” IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 9, 2004, pp. 824-834. doi:10.1109/TPDS.2004.38