Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata
Contributor : Bernard Chauvière Connect in order to contact the contributor
Submitted on : Monday, December 3, 2007 - 1:00:18 PM
Last modification on : Friday, February 4, 2022 - 3:08:50 AM


  • HAL Id : inria-00193312, version 1


Bernard Chauvière, Dominique Geniet, René Schott. Contributions to the multiprocessor scheduling problem. Computational Intelligence - CI 2007, International Association of Science and Technology for Development (IASTED), Jul 2007, Banff, Canada. pp.55-60. ⟨inria-00193312⟩



Record views