Comparación experimental entre algoritmos distribuidos simulando asesores humanos y una extensión del algoritmo de Kuhn-Munkres para el problema de asignación de marineros (SAP)

Variantes del problema de asignación lineal (LAP) y variantes del algoritmo Kuhn-Munkres (KM), un algoritmo que soluciona el LAP también conocido como El Método Húngaro, han sido aplicados en el proceso de asignación de personal enlistado en la marina con el fin de solucionar el problema mejor conocido como el Problema de Asignación de Marineros (SAP). El SAP es un problema de optimización multi-objetivo que puede ser reducido mediante el uso vectores de peso en múltiples LAPs. Este estudio se concentra en la comparación de las soluciones obtenidas por KM cuando es aplicado a LAPs que son versiones ponderadas de instancias del SAP y las soluciones obtenidas por la simulación de asesores humanos que actualmente realizan este proceso de asignación manualmente. Dos modelos de comportamiento de los asesores humanos: el voraz en-línea y el aleatorio en-línea, son estudiados. El objetivo es evaluar cual enfoque es mejor alternativa para encontrar soluciones competitivas para el SAP. / Abstract. Variations of the Linear Assignment Problem (LAP) and variations of the Kuhn-Munkres (KM) algorithm, a solving algorithm for the LAP also known as The Hungarian method, have been applied to the navy enlisted personnel assignment process in order to solve a problem better known as the Sailor Assignment Problem (SAP). The SAP is a multi-objective optimization problem that can be reduced through the use of weight-vectors into multiple LAPs. This study focuses on the comparison of the solutions obtained by KM when it is applied to LAPs that are weighted versions of instances of SAP and the solutions obtained by simulating human detailers that currently do this assignment process manually. Two models of behavior of the human detailers: the greedy on-line and the random on-line, are studied here. The goal is to evaluate which approach is a better alternative to find competitive solutions for SAP.

• Autores: Burbano Portilla, Jesús Alfredo
• Fecha de publicación: 2010
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/70522
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/70522; http://bdigital.unal.edu.co/2702/
• Palabra clave: 51 Matemáticas / Mathematics; 62 Ingeniería y operaciones afines / Engineering; Kuhn-Munkres; Algoritmos aleatorizados; Optimización multi-objetivo; Asignación de marineros; Randomized algorithms; Multi-objective optimization; Sailor assignment
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional