Resumen

Este artículo presenta un enfoque heurístico para resolver el problema de asignación/reasignación de recursos, conocido como problema de la mochila multidimensional de selección múltiple 0/1 (MMKP). Se emplea la matriz de intercepción de las restricciones para encontrar una solución óptima o cercana a óptima del MMKP. Este enfoque heurístico se probó en 33 problemas de referencia tomados de la biblioteca OR de tamaños de hasta 7000, y los resultados se compararon con las soluciones óptimas. Se demostró la complejidad computacional de resolver heurísticamente el MMKP utilizando este enfoque. El rendimiento de nuestra heurística se comparó con los mejores algoritmos heurísticos del estado del arte en cuanto a la calidad de las soluciones encontradas. Los resultados alentadores, especialmente para problemas de prueba de gran tamaño, indican que este enfoque heurístico puede utilizarse con éxito para encontrar buenas soluciones para problemas NP-duros altamente restringidos.

• Materias:Polinomios Modelado matemático Integrales Matrices Derivaciones generalizadas
• Subjects:Polynomials Mathematical modeling Integrals Matrices Generalized derivatives
• Palabras claves:Enfoque; Asignación de recursos; Problema de reasignación; Problema de mochila multidimensional de selección múltiple 0/1; Heurística; Complejidad computacional
• Keywords:Approach; Resource allocation; Reallocation problem; 0/1 multichoice multidimensional knapsack problem; Heuristic; Computational complexity