DII CGO
inicioir al DIIbuscar
fcfm
top
topleft
scheduling on airplanes processors
In the processor of a plane several tasks need processor time periodically. For each task we are given a period, which makes the schedule "rigid": when the first time slot for a task is fixed, then its period defines all future time slots. Then the schedule is determined by choosing an offset for each task, which must avoid all possible future collisions. If the airplane has more than one processor we must also assign tasks to processors. 

In this talk I will present a full study of this problem. I will start describing the  complexity landscape and derive best possible approximation algorithms. The  results are based on properties of the mathematical structure of this type of  schedules, which are also useful for deriving a compact integer programming  formulation. Our formulation allows us to solve real-world instances orders of magnitude faster than previous approaches.


This is joint work with Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, and Andreas Wiese.