Journal
IEEE TRANSACTIONS ON COMPUTERS
Volume 62, Issue 4, Pages 644-661Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TC.2012.21
Keywords
Real-time systems; schedulability analysis; mixed integer linear programming
Funding
- NSERC [RGPIN 418741-12]
- NSFC [61070002]
Ask authors/readers for more resources
In the design of time-critical applications, schedulability analysis is used to define the feasibility region of tasks with deadlines, so that optimization techniques can find the best design solution within the timing constraints. The formulation of the feasibility region based on the response time calculation requires many integer variables and is too complex for solvers. Approximation techniques have been used to define a convex subset of the feasibility region, used in conjunction with a branch and bound approach to compute suboptimal solutions for optimal task period selection, priority assignment, or placement of tasks onto CPUs. In this paper, we provide an improved and simpler real-time schedulability test that allows an exact and efficient definition of the feasibility region in Mixed Integer Linear Programming (MILP) optimization. Our method requires a significantly smaller number of binary variables and is viable for the treatment of industrial-size problem, as shown by the experiments.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available