B. Chauvire, D. Geniet, and R. Schott (France)
Multiprocessor Scheduling, Non-preemptive tasks, Prece dence Constraints, Genetic Algorithms, Gradient Descent Method, Tabu Search.
The problem of multiprocessor scheduling consists in find ing 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 solu tions. Efficient methods based on genetic algorithms have been developed by (just to name a few) Hou, Ansari, Ren, Wu, Yu, Jin, Schiavone, Corrˆea, 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 optimal ity than [3, 5] when the number of processors and/or the number of precedence constraints increase.
Important Links:
Go Back
