Tabu search type algorithms for the 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 a multiprocessor system so that the schedule length can be 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 randomly generated instances. The numerical results show that our algorithms produce solutions closer to optimality and/or of better quality than the methods presented in [1].