InterRC: An Inter-Resources Collaboration Heuristic for Scheduling Independent Tasks on Heterogeneous Distributed Environments

Abdelhamid Khiat; Abdelkamel Tari

doi:10.13164/mendel.2019.1.179

Abdelhamid Khiat Networks and Distributed Systems Division, Research Center on Scientific and Technical Information, Algeria ; Faculty of Exact Sciences, University of Bejaia, Algeria
Abdelkamel Tari Faculty of Exact Sciences, University of Bejaia, Algeria

DOI: https://doi.org/10.13164/mendel.2019.1.179

Keywords: distributed computing, scheduling, makespan, evolutionary algorithms

Abstract

The independent task scheduling problem in distributed computing environments with makespan optimization as an objective is an NP-Hard problem. Consequently, an important number of approaches looking to approximate the optimal makespan in reasonable time have been proposed in the literature. In this paper, a new independent task scheduling heuristic called InterRC is presented. The proposed InterRC solution is an evolutionary approach, which starts with an initial solution, then executes a set of iterations, for the purpose of improving the initial solution and close the optimal makespan as soon as possible. Experiments show that InterRC obtains a better makespan compared to the other efficient algorithms.

References

Ali, S., Siegel, H. J., Maheswaran, M., Hensgen, D., and Ali, S. 2000. Task execution time modeling for heterogeneous computing systems. In Proceedings 9th Heterogeneous Computing Workshop (HCW 2000). Cat. No.PR00556, pp. 185-199. DOI: 10.1109/HCW.2000.843743

Braun, T. D., Siegel, H. J., Beck, N., Boloni, L. L., Maheswaran, M., Reuther, A. I., Robertson, J. P., Theys, M. D., Yao, B., Hensgen, D., and Freund, R. F. 2001. A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems. Journal of Parallel and Distributed Computing 61, 1, pp. 810-837.

Dorigo, M. and Di Caro, G. 1999. Ant colony optimization: a new meta-heuristic. In Proceedings of the 1999 congress on evolutionary computation-CEC99. Cat. No. 99TH8406, IEEE, pp. 1470-1477.

Eshelman, L. J. 1991. The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination. In Foundations of Genetic Algorithms. Vol 1, Elsevier, pp. 265-283. DOI: 10.1016/B978-0-08-050684-5.50020-3

Etminani, K. and Naghibzadeh, M. 2007. A min-min max-min selective algorithm for grid task scheduling. In 2007 3rd IEEE/IFIP International Conference in Central Asia on Internet. IEEE, pp. 1-7.

Gary, M. R. and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman and Company, New York, USA.

Gogos, C., Valouxis, C., Alefragis, P., Goulas, G., Voros, N., and Housos E. 2016. Scheduling independent tasks on heterogeneous processors using heuristics and Column Pricing. Future Generation Computer Systems 60, pp. 48-66.

Golberg, D. E. 1989. Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.

Izakian, H., Abraham, A., and Snasel, V. 2009. Comparison of heuristics for scheduling independent tasks on heterogeneous distributed environments. In 2009 International Joint Conference on Computational Sciences and Optimization. Vol 1, IEEE, pp. 8-12.

Maheswaran, M., Ali, S., Siegel, H. J., Hensgen, D., and Freund, R. F. 1999. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of parallel and distributed computing 59, 2, 107-131.

Nesmachnow, S., Cancela, H., and Alba, E. 2012. A parallel micro evolutionary algorithm for heterogeneous computing and grid scheduling. Applied Soft Computing 12, 2, 626-639.

Pinel, F., Dorronsoro, B., and Bouvry, P. 2010. A new parallel asynchronous cellular genetic algorithm for scheduling in grids. In 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). IEEE, pp. 1-8.

Sadashiv, N. and Kumar, S. M. D. 2011. Cluster, grid and cloud computing: A detailed comparison. In 2011 6th International Conference on Computer Science Education (ICCSE). IEEE, pp. 477-482.

Shi, Y. et al. 2001. Particle swarm optimization: developments, applications and resources. In Proceedings of the 2001 Congress on Evolutionary Computation. Cat. No. 01TH8546, IEEE, Vol 1, pp. 81-86.

Wu, M.-Y. and Shu, W. 2001. A high-performance mapping algorithm for heterogeneous computing systems. In Proceedings 15th International Parallel and Distributed Processing Symposium (IPDPS 2001). IEEE, No. 6964466. DOI: 10.1109/IPDPS.2001.925020

Xhafa, F., Alba, E., Dorronsoro, B., Duran, B., and Abraham, A. 2008. Efficient batch job scheduling in grids using cellular memetic algorithms. In Metaheuristics for Scheduling in Distributed Computing Environments. Springer, 273-299.