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 realworld instances orders of magnitude faster than previous approaches.

 Contacto
 Departamento de Ingeniería Industrial   Facultad de Ciencias Físicas y Matemáticas  Universidad de Chile  República 701, Santiago, Chile  Teléfono:(562)9784072  Fax:(562)9784011 