Generalized Extremal Optimization for Solving Multiprocessor Task Scheduling Problem
| 详细信息 | 推荐本文 | |
- 作者：Piotr Switalski ; Franciszek Seredynski
- 关键词：multiprocessor task scheduling problem ; Generalized Extremal Optimization ; GEO ; genetic algorithm
- 刊名：Lecture Notes in Computer Science
- 出版时间：2008
- 出版年：2008
- 期刊代码：99_0302-9743
- 类别：cp
- 卷：5361
- 期：1
- 页码：161-169
- 数据来源：sp
摘要
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.