Cotas Lagrangianas Mejoradas Para El Problema de Asignacion Multiple : Estudio de la estructura de descomposición doble

El problema de asignacin clsico (AP) consiste en asignar un conjunto de tareas quiz trabajos por hacer, a un conjunto de agentes (personas o mquinas que pueden desempear dichas tareas). El problema de asignacin mltiple (MMAP, por sus siglas en ingls de many to many assignment problem) es una generalizacin del AP, este problema a diferencia del AP permite la posibilidad de asignar un agente a varias tareas y varias tareas a un agente respetando las capacidades lmites de ambos conjuntos. Creamos una heurstica que consiste en dos fases: primero construye una relajacin lagrangiana con el objetivo de generar soluciones (esta es mejor que la relajacin clsica lagrangiana y obtiene buenas cotas, as como soluciones factibles en algunos casos), posteriormente aplicamos un algoritmo de factibilizacin "greedy" que obtiene la mejor solucin factible.