Edgar Possani

ITAM

¿Ya salgo?, o de cuándo despegar aviones y producir microchips

¿Alguna vez te has preguntado por qué tu avión sale a una hora determinada, y no media hora antes o después?

En esta plática se presentarán algunos problemas de programación de horarios (scheduling) que consisten en determinar qué tareas se realizan antes que otras.

En particular hablaremos sobre el problema de programar los despegues de aeronaves tomando en cuenta las restricciones de seguridad, y las impuestas por el trazo de la pista. Nos interesa maximizar la utilización de la pista respetando las directivas de control aéreo, los tiempos de espera y la equidad entre las aerolíneas.

También presentaremos el problema de programar una máquina de procesamiento por lote, común en la industria de fabricación de microchips, donde varios circuitos se evalúan al mismo tiempo en una misma máquina, y nos interesa minimizar el máximo retraso entre todas las tareas. Se dará una breve introducción a algunas de las técnicas empleadas para resolver estos problemas, en específico el uso y aplicación de métodos de ramificación (tipo beam-search), heurísticas de búsqueda local, y programación dinámica.