Secuenciación de trabajos en una máquina con una fecha común de entrega

Resumen

Este trabajo presenta metodos exactos y heursticos para resolver el problema de secuenciaci on de trabajos en una maquina con el objetivo de minimizar la penalizacion por retrasos o adelantos. Todos los trabajos tienen la misma fecha de entrega, las penalizaciones por atraso y retraso son distintas entre s y particulares para cada trabajo y no se permite la interrupcion de un trabajo una vez iniciado. Hemos dise~nado dos modelos de programacion cuadratica entera y un modelo auxiliar de programacion entera cuadratica irrestringida. La combinacion de los tres modelos proporciona el optimo en muchos problemas test, incluso de grandes dimensiones. Cuando el tiempo de computacion se restringe, los algoritmos proporcionan buenas soluciones factibles y, en este sentido, el procedimiento puede considerarse como un buen algoritmo heurstico. La calidad de dichas soluciones viene probada por su cercana a una cota inferior y porque en muchas ocasiones mejoran las mejores soluciones conocidas.