Nuevos métodos meta heurísticos para la asignación eficiente, optimizada y robusta de recursos limitados
- Cervantes Posada, Maria Margarita
- Federico Barber Sanchís Doktorvater/Doktormutter
- Antonio Lova Ruiz Doktorvater/Doktormutter
Universität der Verteidigung: Universitat Politècnica de València
Fecha de defensa: 09 von März von 2010
- Joaquín Sicilia Rodríguez Präsident
- Miguel Angel Salido Gregorio Sekretär/in
- María Camino Rodríguez Vela Vocal
- José Ramiro Varela Arias Vocal
- Pilar Tormos Juan Vocal
Art: Dissertation
Zusammenfassung
Los problemas de optimización y satisfacción de restricciones son extraordinariamente complejos y variados, Al mismo tiempo, son problemas de alto interés, tanto en el aspecto científico-técnico como en el aplicado. Por ello, poder disponer de soluciones algorítmicas eficientes y flexibles supone un alto valor añadido en muy diferentes entornos de aplicación. Entre los problemas más típicos se encuentran los problemas de scheduling o asignación temporal de recursos. Esta clase de problemas implica la ejecución de acciones que requieren recursos cuya disponibilidad está limitada y por tanto deben asignarse de modo eficiente Dentro de la amplia variedad de los problemas de scheduling, destaca el problema de programación de proyectos con recursos limitados. Dicho problema considera un conjunto de actividades relacionadas entre sí mediante relaciones de precedencia, un conjunto de recursos con un límite en su disponibilidad y un conjunto de medidas de desempeño. El objetivo es obtener la mejor manera de asignar dichos recursos a las actividades, de tal manera que se optimice la medida de desempeño. Se han publicado muchos y diversos trabajos en relación al problema estándar de programación de proyectos con recursos limitados (RCPSP), el cual incluye un único modo de ejecución de las actividades que le conforman, abordando su solución con métodos exactos y métodos aproximados. En cuanto al problema que considera la posibilidad de que cada actividad se ejecute en uno de varios posibles modos (MRCPSP), su estudio no es tan amplio como el del caso anterior. El objetivo de esta tesis es proponer, diseñar y desarrollar nuevos métodos metaheurísticos para obtener una asignación optimizada de recursos en este complejo problema de scheduling. Para el caso del RCPSP, hemos seguido un proceso de refinamiento para la propuesta de una heurística y un algoritmo genético utilizando de manera selectiva el método de mejora de programaciones factibles FBI. En el caso del MRCPSP, hemos diseñado un método de mejora de programaciones factibles y un método de asignación de modos que genera programaciones factibles en más del 90% de los casos. Estos métodos han sido incorporados en un algoritmo genético, para el cual hemos diseñado una función de evaluación de los individuos que guía adecuadamente la evolución del algoritmo. Uno de los supuestos implícitos en estos dos problemas, es que el entorno de desarrollo del proyecto es determinístico. Ello implica que las duraciones de las actividades durante la ejecución del proyecto se mantienen iguales a las planeadas, que la disponibilidad de los recursos no se ve afectada por eventualidades y por lo tanto la programación puede realizarse sin ningún contratiempo. Sin embargo, es claro que dicho supuesto no se cumple en los proyectos que se ejecutan en el mundo real, por lo que se plantea el problema de la generación de programaciones que sean estables en su ejecución. Para abordar este problema hemos diseñado un algoritmo genético que inserta intervalos de seguridad, y a la vez reserva los recursos necesarios para evitar la propagación de los retrasos primarios a lo largo de la programación. Este algoritmo incorpora una función de evaluación de los individuos que consiste en una medición ex-ante de la robustez de las programaciones generadas. Las programaciones generadas se someten a un proceso de simulación con dos escenarios de variabilidad. Se evalúa la robustez de cada programación con dos medidas que hemos propuesto para este caso. Las propuestas realizadas para esta tipología de problemas se han implementado y sus resultados han sido evaluados mediante la solución de las instancias de las librerías estándar de prueba. La efectividad de estos algoritmos se ha contrastado mediante la comparación con los mejores métodos publicados.