Tabu Search Type Algorithms for the Multiprocessor Scheduling Problem | Zendy

Olivier Buffet | Zendy; Liliana Cucu | Zendy; Lhassane Idoumghar | Zendy; René Schott | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Tabu Search Type Algorithms for the Multiprocessor Scheduling Problem

Author(s) -

Olivier Buffet,

Liliana Cucu,

Lhassane Idoumghar,

René Schott

Publication year - 2010

Publication title -

artificial intelligence and applications

Language(s) - English

Resource type - Conference proceedings

ISSN - 2811-0854

DOI - 10.2316/p.2010.674-070

Subject(s) - multiprocessor scheduling , tabu search , computer science , multiprocessing , scheduling (production processes) , parallel computing , schedule , job shop scheduling , mathematical optimization , algorithm , dynamic priority scheduling , rate monotonic scheduling , mathematics , operating system

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].

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research