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.
| Departamento de Ingeniería Industrial |
| Facultad de Ciencias Físicas y Matemáticas | Universidad de Chile |
República 701, Santiago, Chile | Teléfono:(562)978-4072 | Fax:(562)978-4011