Personnel assignment problems through the multidimensional assignment problem

Abstract

El problema de asignación de personal aparece en diversas industrias. La asignación eficiente de personal a trabajos, proyectos, herramientas, horarios, entre otros, tiene un impacto directo en términos monetarios para el negocio. El problema de asignación multidimensional (PAM) es la extensión natural del problema de asignación y puede ser utilizado en aplicaciones donde se requiere la asignación de personal. El caso más estudiado de PAM es el problema de asignación en tres dimensiones, sin embargo en años recientes han sido propuestas algunas heurísticas de búsqueda local y algoritmos meméticos para el caso general. En este trabajo de tesis se realiza un estudio profundo de PAM comenzando con un resumen del estado del arte de algoritmos, heurísticas y metaheurísticas para su resolución. Se describen algunos algoritmos y se propone uno nuevo que resuelve instancias de tamaño medio para PAM. Se propone la generalización de las conocidas heurísticas de variación de dimensión como una búsqueda local generalizada que proporciona un nuevo estado del arte de búsquedas locales para PAM. Adicionalmente, se propone un algoritmo memético con una estructura sencilla pero efectiva y que es competitivo con el mejor algoritmo memético conocido para PAM. Finalmente, se presenta un caso particular de problema de asignación de personal: el Problema de Asignación de Horarios (PAH). El PAH considera la asignación de personal a uno, dos o más conjuntos de objetos, por ejemplo puede ser requerida la asignación de profesores a cursos a periodos de tiempo a salones, para determinados grupos de estudiantes. Primero, se presenta el PAH así como una breve descripción de su estado del arte. Luego, se propone una nueva forma de modelar este problema a través de la resolución de PAM y se aplica sobre el PAH en la Universidad Autónoma Metropolitana, unidad Azcapotzalco (UAM-A). Se describen las consideraciones particulares del PAH en la UAM-A y proponemos una nueva solución para éste. Nuestra solución se basa en la resolución de múltiples PA3 a través de los algoritmos y heurísticas propuestos.

Personnel assignment problems appear in several industries. The e cient assignment of personnel to jobs, projects, tools, time slots, etcetera, has a direct impact in terms monetary for the business. The Multidimensional Assignment Problem (MAP) is a natural extension of the well-known assignment problem and can be used on applications where the assignment of personnel is required. The most studied case of the MAP is the three dimensional assignment problem, though in recent years some local search heuristics and memetic algorithms have been proposed for the general case. Let X1; : : : ;Xs be a collection of s 3 disjoint sets, consider all combinations that belong to the Cartesian product X = X1 Xs such that each vector x 2 X, where x = (x1; : : : ; xs) with xi 2 Xi 8 1 i s, has associated a weight w(x). A feasible assignment is a collection A = (x1; : : : ; xn) of n vectors if xi k 6= xj k for each i 6= j and 1 k s. The weight of an assignment A is given by w(A) = Pn i=1 w(xi). A MAP in s dimensions is denoted as sAP. The objective of sAP is to nd an assignment of minimal weight. In this thesis we make an in depth study of MAP beginning with the state-ofthe- art algorithms, heuristics, and metaheuristics for solving it. We describe some algorithms and we propose a new one for solving optimally medium size instances of MAP. We propose the generalization of the called dimensionwise variation heuristics for MAP and a new generalized local search heuristic that provides new state-of-theart local searches for MAP. We also propose a new simple memetic algorithm that is competitive against the state-of-the-art memetic algorithm for MAP. In the last part of this thesis, we study a particular case of personnel assignment problem: the School Timetabling Problem (STP). The STP considers the assignment of personnel to other two or more sets, for example the assignment of professors to courses to time slots to rooms can be required. First, we provide a brief description of the state-of-the-art for STP. Then, we introduce a new approach for modeling this problem through the resolution of several MAP and we apply our solution on a real life case of study: STP at the Universidad Autonoma Metropolitana campus Azcapotzalco (UAM-A). We provide the particular aspects for STP at UAM-A and we provide a new solution for this problem. Our approach is based on solving several 3AP considering the introduced model and our proposed techniques.