Design and Evaluation of a Real-Time Task Scheduler using Tabu Search

Real-time task scheduling problems are generally considered to be NP-hard problems. Therefore it is necessary to apply a heuristic search strategy on these problems. This project focuses on the development of a real-time scheduling algorithm using tabu search. A dynamic real-time task scheduling problem is defined for a single processor. The tasks in the system are sporadic, mutually independent, non-preemptable with firm, arbitrary deadlines. This problem is represented with tabu search. For performance measurements a simulator has been designed and implemented. Simulations have been conducted comparing scheduler based on tabu search to two well known scheduling algorithms, namely: earliest deadline first and highest value first. It was expected that the scheduler based on tabu search would outperform highest-value first and it would miss fewer deadlines than earliest deadline, as soon as earliest deadline starts to miss deadlines. The results of the simulations conducted did not show this results. Nevertheless did the simulation results indicate that tabu search could be a suitable heuristic search strategy for real-time task scheduling problems. This project provides a starting point on which it is possible to continue work on enhancing the tabu search scheduler