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

Generating Real-Time Schedules using Constraint Programming

Cecilia Ekelin ; Jan Jonsson (Institutionen för data- och informationsteknik, Datorteknik (Chalmers))
ARTES - A Network for Real-Time Research and Graduate Education in Sweden p. 571-587. (2006)

In real-time systems that contain a large variety of application constraints, such as embedded systems, the most common scheduling approach is to resolve potential conflicts off-line by generating a fixed time-table for the execution of the tasks. Unfortunately, the generation of such a schedule is an NP-complete problem which implies that the runtime complexity of an exact scheduling algorithm is exponential in the worst case. Moreover, the amount of different constraints that must be considered makes it hard to devise a reasonably efficient algorithm without sacrificing solution quality or model accuracy. In this work we show how a scheduling algorithm based on constraint programming is able to tackle these difficulties.

Nyckelord: application constraints, constraint programming, real-time scheduling, optimization techniques, complexity reduction

Editor(s): Hans Hansson

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2007-01-26. Senast ändrad 2011-02-17.
CPL Pubid: 25960