Abstract
Scheduling is one of the core steps to efficiently exploit the capabilities of heterogeneous distributed computing systems and it is also an appealing NPcomplete problem. There is a number of heuristic and meta-heuristic algorithms that were tailored to deal with scheduling of independent jobs. In this paper we investigate the efficiency of differential evolution for the scheduling problem and compare it with existing approaches. The analysis shows that the differential evolution is a promising method that can compete with well-established scheduling algorithms.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ali, S., Braun, T., Siegel, H., Maciejewski, A.: Heterogeneous computing (2002)
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., Freund, R.F.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems (2001)
Tracy, M.M., Braun, T.D., Siegel, H.J.: High-performance mixed-machine heterogeneous computing. In: 6th Euromicro Workshop on Parallel and Distributed Processing, pp. 3–9 (1998)
Fernandez-Baca, D.: Allocating modules to processors in a distributed system. IEEE Trans. Softw. Eng. 15(11), 1427–1436 (1989)
Munir, E.U., Li, J.-Z., Shi, S.-F., Rasool, Q.: Performance analysis of task scheduling heuristics in grid. In: 2007 International Conference on Machine Learning and Cybernetics, vol. 6, pp. 3093–3098 (August 2007)
Izakian, H., Abraham, A., Snasel, V.: Comparison of heuristics for scheduling independent tasks on heterogeneous distributed environments. In: International Joint Conference on Computational Sciences and Optimization, CSO 2009, vol. 1, pp. 8–12 (April 2009)
Ritchie, G., Levine, J.: A hybrid ant algorithm for scheduling independent jobs in heterogeneous computing environments. In: Proceedings of the 23rd Workshop of the UK Planning and Scheduling Special Interest Group (December 2004)
YarKhan, A., Dongarra, J.: Experiments with scheduling using simulated annealing in a grid environment. In: Parashar, M. (ed.) GRID 2002. LNCS, vol. 2536, pp. 232–242. Springer, Heidelberg (2002)
Page, A.J., Naughton, T.J.: Framework for task scheduling in heterogeneous distributed computing using genetic algorithms. Artificial Intelligence Review 24, 137–146 (2004)
Carretero, J., Xhafa, F., Abraham, A.: Genetic algorithm based schedulers for grid computing systems. International Journal of Innovative Computing, Information and Control 3(7) (2007)
Abraham, A., Liu, H., Grosan, C., Xhafa, F.: Nature Inspired Meta-heuristics for Grid Scheduling: Single and Multi-objective Optimization Approaches. Studies in Computational Intelligence, vol. 146, pp. 247–272. Springer, Heidelberg (2008)
Munir, E.U., Li, J., Shi, S., Zou, Z., Rasool, Q.: A performance study of task scheduling heuristics in hc environment. In: An, L.T.H., Bouvry, P., Tao, P.D. (eds.) MCO. Communications in Computer and Information Science, vol. 14, pp. 214–223. Springer, Heidelberg (2008)
Freund, R.F., Gherrity, M., Ambrosius, S., Campbell, M., Halderman, M., Hensgen, D., Keith, E., Kidd, T., Kussow, M., Lima, J.D., Mirabile, F., Moore, L., Rust, B., Siegel, H.J.: Scheduling resources in multi-user, heterogeneous, computing environments with smartnet. In: Heterogeneous Computing Workshop, vol. 0, p. 3 (1998)
Shoukat, M.M., Maheswaran, M., Ali, S., Siegel, H.J., Hensgen, D., Freund, R.F.: Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing 59, 107–131 (1999)
Price, K.V., Storn, R.M., Lampinen, J.A.: Differential Evolution A Practical Approach to Global Optimization. Natural Computing Series. Springer, Berlin (2005)
Jongen, H.T., Meer, K., Triesch, E.: Optimization Theory. Kluwer Academic Publishers, Dordrecht (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Krömer, P., Snášel, V., Platoš, J., Abraham, A., Ezakian, H. (2010). Evolving Schedules of Independent Tasks by Differential Evolution. In: Caballé, S., Xhafa, F., Abraham, A. (eds) Intelligent Networking, Collaborative Systems and Applications. Studies in Computational Intelligence, vol 329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16793-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-16793-5_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16792-8
Online ISBN: 978-3-642-16793-5
eBook Packages: EngineeringEngineering (R0)