Tabu Search Type Algorithms for the Multiprocessor Scheduling Problem

L. Cucu, L. Idoumghar, and R. Schott (France)

Keywords

Tabu Search Algorithm, Multiprocessor Scheduling Problem.

Abstract

This paper presents two Tabu Search type algorithms for solving the multiprocessor scheduling problem. This problem consists in ļ¬nding 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