Algoritmos genéticos para programación de proyectos con recursos limitados

  1. Javier Alcaraz Soria
Supervised by:
  1. Concepción Maroto Álvarez Director

Defence university: Universitat Politècnica de València

Year of defence: 2001

Committee:
  1. Rafael Romero Villafranca Chair
  2. Antonio Hervas Jorge Secretary
  3. Eduardo Vicens Salort Committee member
  4. David Alcaide López de Pablo Committee member
  5. María Ángeles Pérez Alarcó Committee member

Type: Thesis

Teseo: 91396 DIALNET

Abstract

El problema de la Programacion de Proyectos con Recursos Limitados ha sido ampliamente estudiado y para resolverlo se han propuesto tanto tecnicas exactas como heuristcas, Las tecnicas exactas no son capaces, en algunos casos, de encontrar la solucion optima, y en otros, los elevados tiempos de calculo requeridos, debido a que se trata de un problema NP-duro, las hace poco utiles. La alternativa la constituyen las tecnicas heuristicas, de las cuales las basadas en reglas de prioridad fueron las primeras en ser aplicadas. Sin embargo, las tecnicas metaheuristicas estan desbancando a las anteriores, debido a los excelentes resultados que estan obteniendo. Entre las tecnicas metaheuristicas mas utilizadas destacan los algoritmos geneticos, tabu-search y simulated anneling. En esta Tesis doctoral se han desarrollado nuevos algoritmos geneticos para resolver el problema, tanto en su version estandar o "unico-modo" como "multi-modo". Se ha diseñado un nuevo tipo de representacion para las soluciones al problema, que incorpora informacion relativa al esquema empleado para secuenciar las actividades: forward o backward. Ademas, se han desarrollado nuevos operadores de cruce y mutacion, capaces de manejar de forma eficiente la informacion almacenada en este nuevo tipo de representacion. Los algoritmos desarrollados han sido comparados con los mejores heuristicos publicados, utilizando para ello la librería estandar de proyectos PSPLIB. El extenso experimento computacional llevado a cabo pone de manifiesto el superior comportamiento de los algoritmos desarrollados.