Multiprocessor scheduling by generalized extremal optimization

We propose a solution of the multiprocessor scheduling problem based on applying a relatively new metaheuristic technique, called Generalized Extremal Optimization (GEO). GEO is inspired by a simple coevolutionary model known as the 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 the characteristics of a phenomenon called 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 show that the proposed optimization technique is simple and yet outperforms genetic algorithm-based and swarm algorithm-based approaches to the multiprocessor scheduling problem.