Generating Real-Time Schedules using Constraint Programming

TL;DRAbstract

In real-time systems that contain a large variety of application constraints, such as embedded systems, the most common scheduling approach is to resolve\npotential conflicts off-line by generating a fixed time-table for the execution of the tasks.\nUnfortunately, 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.

Chat with Paper

AI Agents for this Paper