RUN enhancement through Bayesian networks

ABSTRACT

This work is inspired by the Reduction to UNiprocessor (RUN) algorithm, wich schedules a set of periodic tasks considering their worst-case execution time (WCET). Even if the tasks are executed in less time than their WCETs, there is no possibility of rearranging the rest of the tasks to use the idle slots made available during execution. Therefore, the resulting problem consists of proposing a strategy to exploit the idle intervals. The difficulty of this problem increases when considering that the tasks that are accommodated first have stochastic execution times and that aperiodic tasks used to occupy the idle slots are composed of jobs that have precedence constraints. Besides, these jobs have stochastic temporal restrictions that must be met. To address this issue, a novel heuristic method based on Bayes networks is proposed. Two main contributions are presented. First is the mapping of the problem into a Bayesian network, and second is a heuristic that helps identify the best job, from the new set of aperiodic tasks, for occupying an idle slot created by RUN during its execution. There are two main goals in this work: to reduce global idle time and to execute any reliable job-shop by its deadline.

KEYWORDS:

• Real-time
• Bayesian networks
• reduction to UNiprocessor

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

J. Angel Hermosillo-Gomez http://orcid.org/0000-0002-2392-9459