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

https://hal.inria.fr/inria-00193312
Contributor : Bernard Chauvière <>
Submitted on : Monday, December 3, 2007 - 1:00:18 PM
Last modification on : Tuesday, March 30, 2021 - 12:08:01 PM

Identifiers

  • HAL Id : inria-00193312, version 1

Citation

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⟩

Share

Metrics

Record views

280