Pre-run-time scheduling in real-time systems: Current researches and Artificial Intelligence perspectives

摘要

This paper presents the taxonomy of real-time systems with special emphasize on pre-run-time scheduling problem. Firstly, we present real-time systems, real-time tasks, timing, precedence and exclusion constraints. Then, we describe the problem of pre-run-time scheduling of tasks under constraints. After that, we present the most existing efficient techniques to deal with the latter problem. We summarize the discussion of existing techniques and possible research perspectives after surveying the Artificial Intelligence's point of view about the problem of pre-run-time scheduling of real-time tasks. The Artificial Intelligence survey includes Constraint Satisfaction Problems class since pre-run-time scheduling belongs to the latter class. The Artificial Intelligence survey includes also Path-finding Problems from which intelligent algorithms could be observed such as Learning-Real-Time-A_*(LRTA_*) thanks to its important properties (optimality, linear space complexity and determinism). The development of an algorithm like LRTA_* to solve Constraints Satisfaction Problems and particularly the pre-run-time scheduling of real-time tasks problem is one clear research direction to deal with large-scale real-time systems. The overall objective of this paper is to show what are the perspectives to Artificial Intelligence literature that could be beneficial firstly to Artificial Intelligence community itself and secondly to real-time systems community.