Advances in Operations Research
Volume 2011 (2011), Article ID 561794, 19 pages
Research Article

Optimizing Distributed Real-Time Embedded System Handling Dependence and Several Strict Periodicity Constraints

AOSTE Team, INRIA Rocquencourt, BP 105, 78153 Le Chesnay Cedex, France

Received 16 March 2011; Revised 8 June 2011; Accepted 4 July 2011

Academic Editor: Xiaoqiang Cai

Copyright © 2011 Omar Kermia. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


This paper focuses on real-time nonpreemptive multiprocessor scheduling with precedence and strict periodicity constraints. Since this problem is NP-hard, there exist several approaches to resolve it. In addition, because of periodicity constraints our problem stands for a decision problem which consists in determining if, a solution exists or not. Therefore, the first criterion on which the proposed heuristic is evaluated is its schedulability. Then, the second criterion on which the proposed heuristic is evaluated is its execution time. Hence, we performed a schedulability analysis which leads to a necessary and sufficient schedulability condition for determining whether a task satisfies its precedence and periodicity constraints on a processor where others tasks have already been scheduled. We also present two multiperiodic applications.