Abstract
In this paper we propose a solution of a multiprocessor task scheduling problem with use of a new meta-heuristic inspired by a model of natural evolution called Generalized Extremal Optimization (GEO). It is inspired by a simple co-evolutionary model based on a Bak-Sneppen model. One of advantages of the model is a simple implementation of potential optimization problems and only one free parameter to adjust. The idea of GEO metaheuristic and the way of applying it to the multi-processor scheduling problem are presented in the paper. In this problem the tasks of a program graph are allocated into multiprocessor system graph where the program completion time is minimized. The problem is know to be a NP-complete problem. In this paper we show that GEO is to able to solve this problem with better performance than genetic algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Pardalos, P.M., Romeijn, H.E.: Handbook of Global Optimization, vol. 2. Springer, Heidelberg (2002)
Garey, M.P., Johnson, D.S.: Computers and intractability - a guide to NP-completeness. W.H. Freeman and Company, San Francisco (1979)
Eldred, M.S.: Optimization Strategies for Complex Engineering Applications. San-dia Technical Report SAND98-0340 (1998)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading (1989)
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by Simulated Annealing, vol. 220(4598), pp. 671–680. ACM, New York (1983)
Kennedy, J., Eberhart, R.C.: Particle Swarm Optimization. In: Proc. IEEE International Conference on Neural Networks, pp. 1942–1948 (1995)
Dasgupta, D.: Artificial Immune Systems and Their Applications. Springer, Berlin (1999)
Kwok, Y., Ahmad, I.: Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors. ACM Computing Surveys 31(4), 406–471 (1999)
Seredynski, F., Zomaya, A.Y.: Sequential and Parallel Cellular Automata-Based Scheduling Algorithms. IEEE Trans. Parallel Distrib. Syst. 13(10), 1009–1023 (2002)
Bak, P., Sneppen, K.: Punctuated equilibrium and criticality in a simple model of evolution. Phys. Rev. Lett. 71, 4083–4086 (1993)
Sousa, F.L., Ramos, F.M., Galski, R.L., Muraoka, I.: Generalized Extremal Optimization: A New Meta-heuristic Inspired by a Model of Natural Evolution. Recent Developments in Biologically Inspired Computing, 41–60 (2004)
Bollobas, B.: Random Graphs. Academic Press, New York (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Switalski, P., Seredynski, F. (2008). Generalized Extremal Optimization for Solving Multiprocessor Task Scheduling Problem. In: Li, X., et al. Simulated Evolution and Learning. SEAL 2008. Lecture Notes in Computer Science, vol 5361. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89694-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-89694-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89693-7
Online ISBN: 978-3-540-89694-4
eBook Packages: Computer ScienceComputer Science (R0)