PROYECTO DE INVESTIGACIÓN: “PROBLEMA DE ASIGNACIÓN GENERALIZADA (GAP)”

Universidad de Concepción[pic 1][pic 2]

Facultad de Ingeniería
Departamento de Ingeniería Industrial

Ingeniería Civil Industrial

Optimización II

PROYECTO DE INVESTIGACIÓN:

 “PROBLEMA DE ASIGNACIÓN GENERALIZADA (GAP)”

Integrantes: Yoel Castro

Pablo Figueroa

                 Nicolás Gacitúa

Cristóbal Leiva

Profesora:    Rosa Medina

Concepción, 12 de Noviembre de 2018

Introducción

La investigación de operaciones es una rama de la matemática que se centra en la aplicación de métodos analíticos avanzados con el objetivo de resolver problemas para mejorar u optimizar un sistema complejo, ya sea maximizando beneficios o minimizando costos. Dicho procedimiento permite tomar decisiones teniendo en cuenta la escasez de recursos con un objetivo definido.

Dada la gran relevancia que toma la investigación de operaciones es que decidimos enfocarnos en un problema de la literatura el cual es el “Problema de Asignación Generalizada” el cual está enfocado en minimizar costos tomando en cuenta cierta cantidad de tareas y recursos sujetos a una capacidad. Se sabe que una adecuada asignación de tareas puede representar un ahorro significativo en los gastos de cualquier organización o empresa, pero al mismo tiempo, en la mayoría de los casos prácticos la implementación de este problema tiene un alto costo.

Se resolverán diez instancias de este problema mediante la utilización del Solver de Excel para la obtención de la solución óptima y, posteriormente, usaremos el mismo set de datos para encontrar una solución factible mediante una Metaheurística, que en este caso fue el Tabú Search, esto con el fin de comparar los resultados de ambos métodos, y analizar como varían las soluciones al tener distinta cantidad de variables y parámetros.

Descripción del problema

El Problema de Asignación Generalizada (GAP) es un modelo de programación lineal entera que se utiliza para gestionar la asignación de recursos a tareas con un costo total mínimo; para la realización de las actividades se necesita un determinado recurso, los cuales están disponibles en una cantidad limitada, cada tarea debe ser asignada sólo a un recurso. Este tipo de problema se considera NP-Hard.

Como ejemplo, un recinto hospitalario que requiere realizar de mejor manera la asignación de intervenciones quirúrgicas a quirófanos, aparatos sofisticados de diagnóstico, entre otros; para llevar a cabo estas actividades se necesita un determinado recurso que puede ser personal médico, laboratorios o en general equipos y materiales, que normalmente son recursos limitados.

La principal diferencia con el “Problema de Asignación” es que hay una cierta capacidad de recursos, la cual no puede ser sobrepasada al momento de asignarlos a las tareas, por la misma razón un recurso puede asignarse a más de una tarea, lo cual en el problema de asignación no puede pasar.

La gran finalidad de este método es conseguir la mejor combinación posible para lograr una buena efectividad en las tareas a realizar procurando que los costos sean mínimos.

Metaheuristica

La metaheurística escogida para resolver diferentes instancias del problema fue  la Busqueda Tabu (Tabu Search), la cual admite el concepto de memoria y lo implementa mediante estructuras simples con el objetivo de dirigir la búsqueda teniendo en cuenta la historia de ésta, de forma que los elementos de dicha lista estarán penalizados durante un cierto tiempo. Además, esta lista puede contener soluciones visitadas recientemente, movimientos realizados recientemente o características que tenían las soluciones visitadas.

Pseudocodigo:         

Se establece un tamaño de lista tabú.

Se establece un criterio de término.

i)Se elige una solucion actual Inicial.

ii)Se crea un vecindario con un criterio preestablecido.

iii)La solucion actual se va a la lista tabu.

iv)Se selecciona la mejor solucion dentro del vecinario y que no este en la lista tabu.

v)Esa solucion sera nuestra nueva solucion actual.

vi)Se guarda como mejor solucion en caso de que lo sea.

vii)Repetir según criterio de detencion.

Experimentos

Para realizar las 10 instancias se utilizó un set de datos extraído de la web de la Universidad Brunel de Londres (Brunel University London), cuyo enlace se encuentra en las referencias del trabajo.

Al solo necesitar 10 sets de datos, se escogieron de manera que la cantidad de recursos(m) y tareas(n) no generara una matriz de variables de decisión mayor a 200, ya que para resolverlo se utilizaría el solver de excel el cual no permite que se sobrepase esta cantidad, o sea, que la matriz m×n ≤ 200.

En la tabla siguiente se muestran los valores óptimos de la función objetivo obtenidos mediante Excel, se señalan la cantidad de Recursos(m) y Tareas(n), y el vector de asignación, cada uno de estos valores para su respectivo set de datos.

El vector de asignación se explica de la siguiente manera.

Tomando como ejemplo el segundo vector: V= (4,5,1,2,5,1,2,4,4,3,4,1,5,3,3)

Notamos que el largo de este, depende netamente del valor “n”, y el valor de cada una de sus componentes, de “m”.

Para este caso el recurso 4 se asignaría a la tarea 1, el recurso 5 a la tarea 2, el recurso 1 a la tarea 3, el recurso 2 a la tarea 4, y así sucesivamente, hasta que el recurso 3 se le asigna a la tarea 15.

A continuación se muestra una tabla con los valores obtenidos según Busqueda Tabu*:

*Enlace en referencias

...