Evaluando algoritmos típicos de optimización combinatoria para resolver problemas de programación basados en tiempo continuo
Autores: Lazarev, Alexander A.; Nekrasov, Ivan; Pravdivets, Nikolay
Idioma: Inglés
Editor: MDPI
Año: 2018
Acceso abierto
Artículo científico
2018
Evaluando algoritmos típicos de optimización combinatoria para resolver problemas de programación basados en tiempo continuo
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Enfoque
Problema de programación de proyectos con recursos limitados
Teoría de optimización combinatoria
Programación continua en el tiempo
Problema de programación lineal
Componente combinatorio
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 35
Citaciones: Sin citaciones
Consideramos un enfoque para formalizar el Problema de Programación de Proyectos con Restricciones de Recursos (RCPSP) en términos de la teoría de optimización combinatoria. La transformación del problema original en un entorno combinatorio se basa en interpretar cada operación como una entidad atómica que tiene una duración definida y debe residir en el eje de tiempo continuo cumpliendo restricciones adicionales. El caso más simple de programación en tiempo continuo asume una correspondencia uno a uno de recursos y operaciones y corresponde al entorno de problemas de programación lineal. Sin embargo, los problemas reales de programación incluyen relaciones de muchos a uno, lo que conduce al componente combinatorio adicional en la formulación debido a la competencia entre operaciones. Investigamos cómo aplicar varios algoritmos típicos para resolver el problema resultante de optimización combinatoria: enumeración que incluye el método de ramificación y acotamiento, algoritmo de gradiente, técnica de búsqueda aleatoria.
Descripción
Consideramos un enfoque para formalizar el Problema de Programación de Proyectos con Restricciones de Recursos (RCPSP) en términos de la teoría de optimización combinatoria. La transformación del problema original en un entorno combinatorio se basa en interpretar cada operación como una entidad atómica que tiene una duración definida y debe residir en el eje de tiempo continuo cumpliendo restricciones adicionales. El caso más simple de programación en tiempo continuo asume una correspondencia uno a uno de recursos y operaciones y corresponde al entorno de problemas de programación lineal. Sin embargo, los problemas reales de programación incluyen relaciones de muchos a uno, lo que conduce al componente combinatorio adicional en la formulación debido a la competencia entre operaciones. Investigamos cómo aplicar varios algoritmos típicos para resolver el problema resultante de optimización combinatoria: enumeración que incluye el método de ramificación y acotamiento, algoritmo de gradiente, técnica de búsqueda aleatoria.