Allocating Hard Real-Time Tasks with Constraint Programming
Pierre-Emmanuel Hladik, Hadrien Cambazard, Narendra Jussien · 2006
In this paper, we present an original approach (CPRTA for ”Constraint Programming for solving Real-Time Allocation”) based on constraint programming to solve an allocation problem of hard real-time tasks. This problem consists in assigning periodic tasks to distributed processors in the context of fixed priority preemptive scheduling. CPRTA is built on dynamic constraint programming together with a learning method to find a feasible processor allocation under constraints. Two new approaches are proposed for solving these kinds of problems which produce in their current version as acceptable performances as classical algorithms do. Some experimental results are given to show it. Moreover, CPRTA exhibits very interesting properties. It is complete — i.e., if a problem has no solution — the algorithm is able to prove it; it is non-parametric — i.e., it does not require specific initializations — thus allowing a large diversity of models to be easily considered. Finally, thanks to its capacity to explain failures, it offers attractive perspectives for guiding the architectural design process.