6533b82ffe1ef96bd12963ed

RESEARCH PRODUCT

Scheduling of Real-Time Networks with a Column Generation Approach

Ernst AlthausErnst AlthausSebastian HoffmannEike ThadenJoschka Kupilas

subject

On columnRate-monotonic schedulingJob shop schedulingComputer scienceDistributed computingOptimal allocationColumn generationReal time networksDeadline-monotonic schedulingScheduling (computing)

description

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.

yearjournalcountryeditionlanguage
2013-09-12
https://doi.org/10.1007/978-94-007-6818-5_28