L. Cucu, L. Idoumghar, and R. Schott (France)
Tabu Search Algorithm, Multiprocessor Scheduling Problem.
This paper presents two Tabu Search type algorithms for solving the multiprocessor scheduling problem. This problem consists in finding a schedule for a general task graph to be executed on multiprocessor system so that the schedule length is minimized. The multiprocessor scheduling problem is known to be NP-hard, and to obtain optimal and suboptimal solutions, several heuristic based algorithms have been developed in [1, 2, 4, 6]. Our approaches are validated on 13 instances given by [1]. The numerical results show that our algorithms produce solutions closer to optimality and/or of better quality than the methods presented in [1].
Important Links:
Go Back
