2010 | OriginalPaper | Buchkapitel
Study on GEO Metaheuristic for Solving Multiprocessor Scheduling Problem
verfasst von : Piotr Switalski, Franciszek Seredynski
Erschienen in: Parallel Processing and Applied Mathematics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose a solution of the multiprocessor scheduling problem based on applying a relatively new metaheuristic called Generalized Extremal Optimization (GEO). GEO is inspired by a simple coevolutionary model known as Bak-Sneppen model. The model describes an ecosystem consisting of
N
species. Evolution in this model is driven by a process in which the weakest species in the ecosystem, together with its nearest neighbors is always forced to mutate. This process shows characteristic of a phenomenon called a punctuated equilibrium which is observed in evolutionary biology. We interpret the multiprocessor scheduling problem in terms of the Bak-Sneppen model and apply the GEO algorithm to solve the problem. We compare GEO algorithm with well-known Simulated Annealing (SA) algorithm. Both algorithms have some similarities which are considered in this paper. Experimental results show that GEO despite of its simplicity outperforms SA algorithm in all range of the scheduling instances.