A Hybrid Differential Evolution Scheduling Algorithm to Heterogeneous Distributed System

Abstract:

This paper presents a differential evolution algorithm with designed greedy heuristic strategy to solve the task scheduling problem. The static task scheduling problem is NP-complete and is a critic issue in parallel and distributed computing environment. A vector consists of a task permutation assigned to each individual in the target population by using DE mutation and crossover operators. A heuristic strategy is used to generate the feasible solutions as there a lot of infeasible solutions in the solution space as the size of the problem increase. And the strategies of the particle swarm algorithm are employed to modify the DE crossover operator for speeding up the search to optimal solution. And then, the individual is replaced with the corresponding target individual if it is global best or local best in terms of fitness. The performance of the algorithm is illustrated by comparing with the existing effectively scheduling algorithms. The performances of the proposed algorithms are tested on the benchmark and compared to the best-known solutions available. The computational results demonstrate that effectively and efficiency of the presented algorithm.

• Periodical: Applied Mechanics and Materials (Volumes 631-632)
• Pages: 271-275
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.631-632.271
• Online since: September 2014
• Authors: Yan Kang*, Zhong Min Wang, Ying Lin, Xiang Yun Guo
• Keywords: Differential Evolution, Distributed System, Genetic Algorithm (GA), Heterogeneous, Scheduling Problem

References

[1] Graham, R.L., L.E. Lawler, J.K. Lenstra and A.H. Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey., Ann. Discrete Math., pp.287-326, (1979).

DOI: 10.1016/s0167-5060(08)70356-x

[2] Chan, J., Lee, C. Y. General multiprocessor task scheduling. Naval Research Logistics, 46, p.57–74, (1999).

DOI: 10.1002/(sici)1520-6750(199902)46:1<57::aid-nav4>3.0.co;2-h

[3] Drozdowski, M. Scheduling multiprocessor tasks-An overview. European Journal of Operational Research, 94, p.215–230, (1996).

DOI: 10.1016/0377-2217(96)00123-3

[4] Topcuoglu, H., Harir S., and Wu M. -Y., Performance effective and low-complexity task scheduling for heterogeneous computing, IEEE Trans. on Parallel and Distributed Systems, vol. 13, p.260–274, Mar. (2002).

DOI: 10.1109/71.993206

[5] EI-Rewini, H. and T.G. Lewis, Scheduling parallel program tasks onto arbitrary target machines. J. Parallel and Distributed Computing, vol. 9, pp.138-153, (1990).

DOI: 10.1016/0743-7315(90)90042-n

[6] Iverson, M., F. Ozguner and G. Follen, Parallelizing existing applications in a distributed heterogeneous environments., Proc. Heterogeneous Computing Workshop, pp: 93-100, (1995).

[7] Cristina Boeres, Jos´e Viterbo Filho and Vinod E. F. Rebello, A cluster-based strategy for scheduling task on heterogeneous processors., Proc. 16th Symp. on Computer Architecture and High Performance Computing (SBAC-PAD), (2004).

DOI: 10.1109/sbac-pad.2004.1

[8] Bajaj, R. and Agrawal, D.P. Improving scheduling of tasks in a heterogeneous environments., IEEE Trans. on Parallel and Distributed Systems, vol. 15, pp.107-118, (2004).

DOI: 10.1109/tpds.2004.1264795

[9] Wang, L., H.J. Siegel, V.P. Rowchoudhry and A.A. Maciejewski, Task matching and scheduling in heterogeneous computing environments using a genetic algorithm-based approach., J. Parallel and Distributed Computing, vol. 47, pp.8-22, (1997).

DOI: 10.1006/jpdc.1997.1392

[10] Sivanandam, S. N., Visalakshi, P., Bhuvaneswari, A. Multiprocessor scheduling using hybrid particle swarm optimization with dynamically varying inertia. International Journal of Computer Science & Applications, 4, p.95–106. (2007).

[11] Storn, R., Price, K.V. Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization 11 p.341–359, (1997).

[12] Mezura-Montes, E., Velázquez-Reyes, J., Coello Coello, C.A. Modified differential evolution for constrained optimization, in: IEEE Congress on Evolutionary Computation, IEEE, p.25–32, (2006).

DOI: 10.1109/cec.2006.1688286