Scheduling of Real-Time Networks with a Column Generation Approach

Althaus, Ernst and Hoffmann, Sebastian and Kupilas, Joschka and Thaden, Eike
IAENG Transactions on Engineering Technologies - Special Issue of the World Congress on Engineering and Computer Science (WCECS) 2012
We present an algorithm based on column generation for the real-time scheduling problem of allocating periodic tasks to electronic control units in multiple subsystems connected by a global bus. The allocation has to ensure that tasks can be scheduled, and messages between tasks in different subsystems can be transmitted over the global bus and meet their deadlines. Also tasks and messages occurring in a task chain must be scheduled in a way such that the sequence of execution meets their end-to-end deadline. We show that our approach computes the optimal allocation in our model and due to the column generation approach early provides lower bounds on the optimal value. This book chapter is a revised version of the conference paper of the authors.
01 / 2014
Springer Netherlands
Lecture Notes in Electrical Engineering
Software Platform Embedded Systems 2020_XT
Kim, Haeng Kon and Ao, Sio-Iong and Amouzegar, Mahyar A. and Rieger, Burghard B.