Title: A scatter search algorithm for real-time scheduling with timing, precedence and exclusion constraints

Authors: Adel Bouridah; Habiba Drias; Yacine Laalaoui

Addresses: Mila University Center, Mila, 43000, Algeria ' LRIA Laboratory, Faculty of Computer Science, USTHB University, 16111 El-Alia, Bab-Ezzouar, Algiers, Algeria ' Department of Postgraduate Studies, National Computer Science School, 16000 Oued-Smar, Algiers, Algeria

Abstract: Tasks scheduling is one of the most important challenges in embedded hard-real-time systems. The problem is known to be NP-hard and exhaustive search algorithms have no significant benefit in large-scale context. This paper proposes a scatter search-based approach for mono-processor systems with timing, precedence and exclusion constraints with no pre-emption. An empirical study is undertaken and comparison is done with results of other algorithms.

Keywords: pre-run-time scheduling; metaheuristics; scatter search; real-time scheduling; timing constraints; precedence constraints; exclusion constraints; task scheduling; mono-processor systems; embedded systems.

DOI: 10.1504/IJAOM.2013.053531

International Journal of Advanced Operations Management, 2013 Vol.5 No.2, pp.181 - 197

Published online: 28 Apr 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article