InterRC: An Inter-Resources Collaboration Heuristic for Scheduling Independent Tasks on Heterogeneous Distributed Environments
AbstractThe 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.
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.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.