.png){kind=icon}
.png){kind=icon}
Return
Scheduling multiprocessor tasks with genetic algorithms
.png){kind=icon}
OA
AI
DOI：10.1109/71.790600.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In the multiprocessor scheduling problem, a given program is to be scheduled in a given multiprocessor system such that the program's execution time is minimized. This problem being very hard to solve exactly, many heuristic methods for finding a suboptimal schedule exist. We propose a new combined approach, where a genetic algorithm is improved with the introduction of some knowledge about the scheduling problem represented by the use of a list heuristic in the crossover and mutation genetic operations. This knowledge-augmented genetic approach is empirically compared with a pure genetic algorithm and with a pure list heuristic, both from the literature. Results of the experiments carried out with synthetic instances of the scheduling problem show that our knowledge-augmented algorithm produces much better results in terms of quality of solutions, although being slower in terms of execution time.
Keywords:
multiprocessors
scheduling problems
list heuristics for scheduling problems
genetic algorithms
NP-hard optimization
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W
Organization
No organization information available