CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

The Performance of Constraint Programming for Off-line-Scheduling of Distributed Real-Time Systems

Cecilia Ekelin (Institutionen för datorteknik) ; Jan Jonsson (Institutionen för datorteknik)
Göteborg : Chalmers University of Technology, 2002.

Many real-time systems are distributed in the sense that they consist of tasks that execute on dierent nodes. As a consequence of the distribution, additional task constraints concerning communication and resource sharing are imposed to the traditional timing constraints. Unfortunately, these constraints increase the computational complexity involved in finding a feasible distributed schedule for the tasks, making an off-line approach to the scheduling problem the only viable alternative. Off-line analysis is also required if the constraints must be guaranteed to always hold and if the distributed schedule should be optimal regarding some objective. State-of-the-art scheduling algorithms for these kind of systems include the application of techniques such as branch-and-bound and simulated annealing. In this paper, we present a scheduling algorithm based on constraint programming which is a technique that originates from the area of artificial intelligence. To demonstrate its usefulness for the scheduling of distributed real-time systems, we compare the performance of our algorithm with previously proposed algorithms through a number of experiments. The results from our evaluation show that the constraint programming approach not only results in faster average runtimes but also produces more and better solutions in terms of optimality.

Denna post skapades 2013-06-11.
CPL Pubid: 178219


Institutioner (Chalmers)

Institutionen för datorteknik (2002-2004)


Data- och informationsvetenskap

Chalmers infrastruktur

Ingår i serie

Technical report - Chalmers University of Technology, Department of Computer Engineering, Göteborg 02-15