Estudio del poliedro del problema de secuenciación de proyectos con limitación de recursos

Resumen

EL PROBLEMA DE SECUENCIACION CON LIMITACION DE RECURSOS QUE ESTUDIAMOS CONSISTE EN LA PLANIFICACION DE UN PROYECTO SIN POSIBILIDAD DE INTERRUPCION DE LAS ACTIVIDADES QUE LO COMPONEN UNA VEZ HAN INICIADO SU EJECUCION, CON LIMITES DE RECURSOS DISPONIBLES CONSTANTES A LO LARGO DE TODO EL PROYECTO, Y EN EL QUE EL OBJETIVO ES MINIMIZAR EL TIEMPO TOTAL DE EJECUCION, LAS DURACIONES DE LAS ACTIVIDADES, LAS RELACIONES DE PROCEDENCIA ENTRE ELLAS Y LOS REQUERIMIENTOS DE RECURSOS PARA SU EJECUCION SE SUPONEN ENTEROS, CONOCIDOS Y CONSTANTES A LO LARGO DE TODO EL TIEMPO EN EL QUE SE REALIZA EL PROYECTO. DADA LA IMPORTANCIA QUE TIENE EN LA COMBINATORIA POLIEDRICA, EL DISPONER DE BUENAS SOLUCIONES INICIALES POSIBLES, EN ESTA TESIS PRESENTAMOS EN PRIMER LUGAR, DOS NUEVAS FAMILIAS DE ALGORITMOS HEURISTICOS PARA LA OBTENCION DE TALES SOLUCIONES. EL DESARROLLO DE ESTOS ALGORITMOS SE BUSCA EN LOS CONCEPTOS DE RAMIFICACION Y ACOTACION SIN RETROCESO PARA UNA DE LAS FAMILIAS Y EN EL DE RESOLUCION DE CONJUNTOS INCOMPATIBLES PARA LA OTRA. ASIMISMO SE HACE UN ESTUDIO COMPARATIVO DE ESTOS ALGORITMOS ENTRE SI Y CON LOS QUE YA EXISTEN EN LA LITERATURA. EN SEGUNDO LUGAR SE PROPONE UNA NUEVA FORMULACION ENTERA PARA EL PROBLEMA DEFINIENDO A PARTIR DE ELLA, EL POLIEDRO ASOCIADO. SE OBTIENE LA DIMENSION DEL POLIEDRO Y SE ESTUDIA A CONTINUACION, CUALES DE LAS DESIGUALDADES QUE APARECEN EN LA FORMULACION INDUCEN FACETAS. A CONTINUACION SE GENERALIZAN LOS TEOREMAS DE LIFTING SIMULTANEO ENUNCIADO POR ZEMEL EN 1978, PARA ADECUARLOS A NUESTRO PROBLEMA, Y SE APLICAN PARA OBTENER NUEVAS DESIGUALDADES VALIDAS Y FACETAS. POR ULTIMO SE EXPONE UN METODO PARA OBTENER COTAS INFERIORES QUE JUNTO CON LAS COTAS SUPERIORES YA OBTENIDAS, PERMITIRA REDUCIR EL NUMERO DE VARIABLES Y LA COMPLEJIDAD DEL PROBLEMA ORIGINAL.