Contributions to the multiprocessor scheduling problem

Abstract : The problem of multiprocessor scheduling consists in finding a schedule for a general task graph to be executed on a multiprocessor system so that the schedule length can be minimized. This scheduling problem is known to be NP-hard (i.e. algorithms solving the problem have exponential time complexity), and methods based on heuristic search have been proposed to obtain optimal and suboptimal solutions. Efficient methods based on genetic algorithms have been developed by (just to name a few) Hou, Ansari, Ren, Wu, Yu, Jin, Schiavone, Corrêa, Ferreira, Reybrend, ..., to solve the multiprocessor scheduling problem. In this paper, we propose various algorithmic improvements for the multiprocessor scheduling problem. Simulation results show that our methods produce solutions closer to optimality than \cite{cor,hou} when the number of processors and/or the number of precedence constraints increase.
Type de document :
Communication dans un congrès
Razvan Andonie. Computational Intelligence - CI 2007, Jul 2007, Banff, Canada. ACTA Press, pp.55-60, 2007
Liste complète des métadonnées

https://hal.inria.fr/inria-00193312
Contributeur : Bernard Chauvière <>
Soumis le : lundi 3 décembre 2007 - 13:00:18
Dernière modification le : jeudi 11 janvier 2018 - 06:20:05

Identifiants

  • HAL Id : inria-00193312, version 1

Citation

Bernard Chauvière, Dominique Geniet, René Schott. Contributions to the multiprocessor scheduling problem. Razvan Andonie. Computational Intelligence - CI 2007, Jul 2007, Banff, Canada. ACTA Press, pp.55-60, 2007. 〈inria-00193312〉

Partager

Métriques

Consultations de la notice

231