Resumen de Problemas de secuenciación con fechas de entrega
El objeto de la presente memoria es el estudio de algunos problemas de secuenciación-asignación cuando existen fechas de entrega. La hemos estructurado en tres capítulos. En el primero de ellos se introducen los elementos fundamentales y se exponen las hipótesis que originan el modelo básico de problema de secuenciación-asignación, aportando la posibilidad de existencia de recursos adicionales distintos de las máquinas. El análisis de las situaciones en que algunas de las hipótesis son relajadas nos permite construir un esquema de clasificación que generaliza los hasta ahora desarrollados. Dentro de este capítulo damos una caracterización de las secuencias factibles utilizando el concepto de grafo disyuntivo.El segundo capítulo presenta un compendio de los conceptos y resultados pertenecientes al campo de la Teoría de la Complejidad, que se precisan como bagaje para poder abordar el estudio de la "dificultad" de los problemas de secuenciación-asignación. En el último capítulo primeramente se estudia la inviabilidad del método de enumeración completa, y se desarrolla una formulación por Programación Lineal Entera, analizándose su aplicabilidad. A continuación, dividimos el capítulo en dos apartados atendiendo, en principio, al tipo de criterio (minimización del máximo costo o del costo total). Aunque podemos considerar que la característica fundamental que nos permite hacer la separación es la de la existencia o no de "buenos" algoritmos para la resolución de los problemas. En el primer apartado, una vez expuestos los más potentes resultados conocidos, los puntos de más interés son los relativos al caso de existir tiempos de procesamiento o disponibilidad de recursos variables. En el segundo se establece el carácter fuertemente NP-difícil del problema lo que puede tomarse como una justificación del empleo de técnicas enumerativas. Como principal resultado tenemos un procedimiento de resolución para el caso de recursos variables, que se basa en una formulación por Programación Dinámica que explota la existencia de relaciones de precedencia entre los trabajos, ya sean éstas debidas a las características tecnologías del problema o generadas por condiciones de dominancia. Con nuestro método logramos una disminución de las necesidades de almacenamiento respecto de los procedimientos existentes.De entre las etapas a dar para la resolución de un problema en el campo de la Investigación Operativa, solía relegarse a un segundo plano la de la implementación de los algoritmos, no teniéndose en cuenta la influencia que sobre la efectividad de los mismos tiene la implementación adoptada. En nuestro trabajo hemos intentado expresar los algoritmos de la forma más próxima posible a la utilizada en su implementación en el ordenador, limitándose solo en algunos casos esta cercanía por motivos de inteligibilidad. En el apéndice se introduce y justifica el lenguaje empleado.
