6533b859fe1ef96bd12b7f60

RESEARCH PRODUCT

A Column Generation Approach to Scheduling of Periodic Tasks

Ernst AlthausRouven NaujoksEike Thaden

subject

On columnJob shop schedulingComputer scienceColumn generationParallel computingSolverInteger linear programming formulationScheduling (computing)

description

We present an algorithm based on column generation for a real time scheduling problem, in which all tasks appear regularly after a given period. Furthermore, the tasks exchange messages, which have to be transferred over a bus, if the tasks involved are executed on different ECUs. Experiments show that for large instances our preliminary implementation is faster than the previous approach based on an integer linear programming formulation using a state-of-the-art solver.

yearjournalcountryeditionlanguage
2011-01-01
https://doi.org/10.1007/978-3-642-20662-7_29