Asignación de Recursos Humanos a Proyecto de Desarrollo de

Software utilizando Recocido Simulado y Algoritmos Genéticos

por

Lucía Isabel Mecott Vázquez

Tesis

Presentada al Programa de Graduados en Electrónica, Computación, Información y

Comunicaciones

como requisito parcial para obtener el grado académico de

Maestro en Ciencias

especialidad en

Sistemas Inteligentes

Instituto Tecnológico y de Estudios Superiores de Monterrey

Campus Monterrey

Diciembre de 2002

A todas las personas que trabajan en la industria de la tecnología de información. Con laesperanza de que existan cada vez más procedimientos y recursos técnicos de que podamos

valemos para que nuestro trabajo sea menos confuso y más ordenado.

Reconocimientos

Quiero expresar mi más sincero agradecimiento a las siguientes personas e instituciones porsu enorme contribución a mi formación profesional y académica.

Al ITESM Campus Monterrey, por otorgarme una beca para financiar mis estudios de maestría.Al Dr. Francisco Cantú, por darme la oportunidad de trabajar en el Centro de Inteligencia

Artificial.Al Dr. Hugo Terashima por guiar el presente trabajo de investigación.Al Dr. Manuel Valenzuela y al Dr. Horacio Martínez, por su contribución como sinodales en

el desarrollo del presente trabajo.

LUCÍA ISABEL MECOTT VÁZQUEZ

Instituto Tecnológico y de Estudios Superiores de MonterreyDiciembre 2002

V

Asignación de Recursos Humanos a Proyecto de Desarrollo de

Software utilizando Recocido Simulado y Algoritmos Genéticos

Lucía Isabel Mecott Vázquez, M.C.Instituto Tecnológico y de Estudios Superiores de Monterrey, 2002

Asesor de la tesis: Dr. Hugo Terashima Marín

En el presente trabajo se estudia el problema de asignación de recursos humanos a proyectosde desarrollo de software, que es un problema de programación de tareas. Los problemas de progra-mación de tareas son problemas combinatorios difíciles de resolver, de hecho una solución exactasólo es alcanzable para un subconjunto pequeño de casos. El uso de heurísticas hace posible generaruna solución que, si bien puede no ser la óptima, sí es una buena aproximación a ésta. Para resol-ver el problema que se plantea en este trabajo de investigación se utilizan técnicas de InteligenciaArtificial que han sido utilizadas anteriormente para resolver otros problemas con característicassimilares al estudiado aquí. En particular se usa recocido simulado y algoritmos genéticos.

Primero se define el problema general, tratando de incluir todas las variables que lo afectan.Después se propone una simplificación del mismo, en dónde sólo se consideran un subconjuntode las variables del problema original. Esta simplificación se hace debido a que la complejidaddel problema excede los alcances del presente trabajo, que sólo pretende dar el primer paso paragenerar una herramienta que pueda sugerir una buena asignación de los ingenieros a los distintosproyectos que se tengan. El modelo toma en cuenta restricciones como que todos los ingenierostengan el conocimiento y el rol que les es requerido, que la carga de trabajo sea uniforme entrelos ingenieros y que un ingeniero no esté asignado a dos proyectos al mismo tiempo. Entre lasrestricciones que se dejan de lado, se explica como algunas de éstas pueden ser incluidas fácilmenteen el modelo propuesto.

Se realizan experimentos tendientes a demostrar que éstos pueden ser útiles para resolver ésteproblema. Se ofrecen resultados para los algoritmos por separado así como comparaciones entreambos. En los experimentos se analiza la optimalidad de la solución que entregan y la velocidadcon la que resuelven el problema. También se verifca el tamaño de problema que cada algoritmoes capaz de resolver. Se explora también el comportamiento de los algoritmos cuando se varian lospesos de las restricciones para darle preferencia a una o más de ellas sobre el resto de las soluciones.

Por último se incluye una restricción más que tiene que ver con que la solución propuesta porel algoritmo no sea muy diferente a la solución actual. Los experimentos realizados son alentadoresrespecto a las soluciones que entregan, sin embargo, se plantea la necesidad de robustecer el modeloy acercar a la herramienta a algo que pueda ser utilizado en la práctica.

índice General

Reconocimientos v

Resumen vi

índice de Tablas ix

índice de Figuras xi

Capítulo 1 Introducción 11.1 Contexto de la Investigación 11.2 Definición del Problema 21.3 Objetivos 41.4 Alcance 4

1.4.1 Hipótesis 41.5 Aporte de la Investigación 51.6 Estructura de la Tesis 6

Capítulo 2 Marco Teórico 82.1 El problema de Asignación de Recursos 8

2.1.1 El Problema de Asignación de Recursos Humanos 92.1.2 Evaluación de la Asignación de Recursos 92.1.3 Solución al Problema de Asignación de Recursos 92.1.4 Problemas Relacionados 122.1.5 Complejidad Computacional 13

2.2 Algoritmos de Búsqueda 142.3 Optimización 15

2.3.1 La Suma Ponderada 152.4 Recocido Simulado 16

2.4.1 Implementación del Algoritmo de Recocido Simulado 172.5 Algoritmos Genéticos 182.6 Resumen 21

Capítulo 3 Problema de Asignación de Recursos Humanos a Proyectos de Des-arrollo de Software 223.1 Definición del Problema 22

vii

3.2 Definición del Problema Particular 253.3 Modelación 26

3.3.1 Restricciones Parciales y Optimalidad de la Solución 273.4 Un Problema Pequeño de Asignación de Recursos 293.5 Extensiones al Modelo 323.6 Implementación del Algoritmo de Recocido Simulado 343.7 Implementación del Algoritmo Genético 353.8 Prototipo 363.9 Resumen 37

Capítulo 4 Experimentación y Resultados 394.1 Definición de los Experimentos 394.2 Parámetros utilizados en los experimentos 414.3 Comparación entre los algoritmos 42

4.3.1 Algoritmo Genético 434.3.2 Recocido Simulado 444.3.3 Análisis Compartativo 46

4.4 Variando la Preferencia de las Restricciones 494.4.1 Recocido Simulado 504.4.2 Algoritmo Genético 57

4.5 Diferencia con Respecto a Solución Inicial 594.6 Discusión de Resultados 614.7 Resumen 63

Capítulo 5 Conclusiones y Trabajo Futuro 645.1 Aportaciones 645.2 Trabajo Futuro 65

Vita 67

Bibliografía 68

viii

índice de Tablas

3.1 Requerimientos incluidos en el modelo 33

4.1 Variables a ser evaluadas en los experimentos 404.2 Primer grupo de experimentos 404.3 Segundo grupo de experimentos 414.4 Tercer grupo de experimentos 414.5 Tamaño de los problemas 424.6 Nivel de restricción de los problemas 424.7 Parámetros del Algoritmo Genético 424.8 Parámetros de Recocido Simulado 434.9 Problemas de 10 requerimientos AG 434.10 Problemas de 20 requerimientos AG 444.11 Problemas de 40 requerimientos AG 444.12 Problemas de 10 requerimientos RS 454.13 Problemas de 20 requerimientos RS 454.14 Problemas de 40 requerimientos RS 454.15 Problemas de 10 requerimientos (incremento de RS con respecto a AG) 464.16 Problemas de 20 requerimientos (incremento de RS con respecto a AG) 474.17 Problemas de 40 requerimientos (incremento de RS con respecto a AG) 474.18 Tiempo de Solución, en minutos, al variar el tamaño del problema 484.19 Prefencia en conocimiento con respecto ninguna preferencia, 10 requerimientos (RS). 504.20 Prefencia en conocimiento y rol con respecto a ninguna preferencia, 10 requerimientos

(RS) 514.21 Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 10

requerimientos (RS) 514.22 Prefencia en conocimiento con respecto a pesos iguales, 20 requerimientos ( R S ) . . . . 524.23 Prefencia en conocimiento y roles con respecto a ninguna preferencia, 20 requeri-

mientos (RS) 524.24 Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 20

requerimientos (RS) 534.25 Prefencia en conocimiento con respecto a pesos iguales, 40 requerimientos ( R S ) . . . . 534.26 Prefencia en conocimiento y roles con respecto a ninguna preferencia, 40 requeri-

mientos (RS) 53

ix

4.27 Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 40requerimientos (RS) 54

4.28 Prefencia en conocimiento con respecto a pesos iguales, 70 requerimientos ( R S ) . . . . 544.29 Prefencia en conocimiento y roles con respecto a ninguna preferencia, 70 requerimien-

tos(RS) 554.30 Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 70

requerimientos (RS) 554.31 Prefencia en conocimiento con respecto a pesos iguales, 140 requerimientos (RS). . . 564.32 Prefencia en conocimiento y roles con respecto a ninguna preferencia, 140 requeri-

mientos (RS) 564.33 Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 140

requerimientos (RS) 564.34 Incremento de prefencia en conocimiento con respecto a pesos iguales para 10 reque-

rimientos (AG) 574.35 Incremento de prefencia en conocimiento con respecto a pesos iguales para 20 reque-

rimientos (AG) 584.36 Incremento de prefencia en conocimiento con respecto a pesos iguales para 40 reque-

rimientos (AG) 584.37 Comparación contra una solución inicial, 10 requerimientos 604.38 Comparación contra una solución inicial, 20 requerimientos 604.39 Comparación contra una solución inicial, 40 requerimientos 61

X

índice de Figuras

2.1 Algoritmo de Recocido Simulado 172.2 Algoritmo Genético Simple 20

3.1 Requerimientos existentes 303.2 Matriz de requerimientos contra conocimientos y requerimientos contra roles 303.3 Matriz de ingenieros contra conocimientos y requerimientos contra roles 313.4 Matriz de conflictos entre requerimientos 323.5 Posible solución al problema 323.6 Cromosoma 363.7 Prototipo 37

4.1 Gráfica de intentos contra mejor encontrado para AG y RS, 20 requerimientos. . . . 484.2 Gráfica de intentos contra mejor encontrado de RS, problema de 20 requerimientos

medianamente restringido, variando la preferencia de las restricciones 574.3 Gráfica de intentos contra mejor encontrado, RS para un problema de 20 requeri-

mientos medianamente restringido, al incluir la restricción de similitud 62

xi

Capítulo 1

Introducción

1.1 Contexto de la Investigación

La industria del Tecnología de Información (Information Technology, IT por sus siglas eninglés), ha crecido con gran rapidez en las últimas décadas. La cantidad y la complejidad de losproyectos de IT aumenta y con ellos también aumenta la cantidad, calidad y nivel de especializaciónde los recursos humanos necesarios para satisfacer los requerimientos de esos proyectos. En un casoideal tendríamos tantos recursos humanos como los proyectos lo requieran y estas personas tendríantodas las características que el proyecto requiere. La realidad no es así, las empresas consultorastienen una cantidad de personas limitada y estas personas no siempre cubren con los requerimientosde los proyectos, o no están disponibles para hacerlo.

Asignar de una manera tal que se consiga satisfacer de la mejor manera posible las necesidadesde todos los proyectos de una empresa no es tarea fácil, sobre todo cuando el número de personasy proyectos es grande. A tal grado se vuelve complicado que la persona o grupos de personasdedicados a administrar los recursos humanos del proyecto dejan de tomar decisiones buenas en elsentido del conjunto de todos los proyectos, para tomar decisiones reactivas que tienen que ver consatisfacer la demanda de un proyecto en particular.

La literatura de Administración de Proyectos normalmente considera la formación del equipode trabajo para un proyecto particular pensando en que los recursos humanos están disponiblesen la empresa o pueden ser contratados y, a lo más, toca el tema de negociar la participación deuna persona en caso de que ésta sea requerida por más de un proyecto. No se conocen estudiosrelacionados a la solución del problema de asignación de las personas sujetas de ser asignadas enproyectos de desarrollo de software al conjunto de todos los proyectos abiertos.

En el presente trabajo se estudia el problema de asignación de recursos humanos a proyectosde desarrollo de software, ubicándolo como un problema de programación de tareas y se trata deresolver con técnicas de Inteligencia Artificial que han sido utilizadas anteriormente para resolverotros problemas con características similares al estudiado aquí. En particular se usa recocidosimulado y algoritmos genéticos.

El problema de asignación de recursos humanos a proyectos de desarrollo de software puedeclasificarse como un problema de programación de tareas y como tal es un problema combinatoriodifícil de resolver. El problema de programación de tareas se ocupa de la asignación de recursoslimitados a tareas a través del tiempo. Es un proceso de toma de decisiones que busca la optimi-zación de uno o más objetivos. Los recursos y las tareas pueden tomar muchas formas [12]. Porejemplo, los recursos pueden ser máquinas en una línea de producción y las tareas los distintos

1

productos que deben ser producidos, o bien, los recursos pueden tomar la forma de camiones y lastareas pueden ser las distintas entregas que esos camiones deben efectuar.

Específicamente este problema puede ser clasificado, como un ETP (Employee TimetablingProblem), estos problemas se caracterizan por buscar una asignación de empleados a turnos. LosETPs pueden ser representados como una red de restricciones (CN Constraint Network) represen-tando los turnos como variables y los empleados como valores que tienen que ser asignados a losturnos. El domino de las variables lo forman la lista de empleados que pueden ser asignados a losturnos que son representados por esos valores [10].

En este caso los turnos pueden ser vistos como las diferentes asignaciones de las personas alos proyectos, es decir los turnos son variables y de mayor extensión en el tiempo. Los ETPs setratado de resolver desde varias perspectivas, usando diferentes heurísticas y algoritmos entre ellasse encuentra la de la modelación del problema como un problema de satisfacción de restricciones.

El problema de asignación de recursos humanos a proyectos de desarrollo de software no esdirectamente mapeable a un ETP aunque es posible encontrar una similitud entre ambos problemassi se considera que los turnos están conformados por el período de tiempo limitado por las fechasde inicio y fin de cada uno de los requerimientos -de recursos humanos- de los proyectos.

El problema fundamental es de tipo NP-completo en casi todas sus variantes, por lo tanto unasolución exacta sólo es alcanzable para un subconjunto pequeño de casos. Sólo el uso de heurísticashace factible el encontrar una solución, pero no garantiza alcanzar la solución óptima.

Se han intentado varias maneras de resolver el problema, entre ellas está el uso de heurísticas,la reducción del problema a uno de coloreo de grafos, recocido simulado, búsqueda tabú, algoritmosgenéticos, sistemas expertos y satisfacción de restricciones [14].

1.2 Definición del ProblemaEn una empresa dedicada al desarrollo de sistemas de información el principal capital es el

humano. De la capacidad y experiencia de los individuos que se asignan a los distintos proyectosde la empresa depende el éxito o fracaso de esos proyectos. Se acostumbra en estas empresas crearel rol de gerente de proyectos quien, entre sus principales tareas, tiene la de asignar de maneraóptima los recursos materiales y humanos a los distintos proyectos para permitir que los objetivosespecíficos de cada proyecto se cumplan.

En una empresa pequeña donde las habilidades, capacidades y experiencia de los individuosson conocidas por todos y el número de proyectos es reducido, la tarea del gerente de proyectoses relativamente sencilla. Tomar la decisión de qué personas integrarán cada proyecto y las fechasde asignación y des-asignación de cada una sólo requiere que el gerente conozca, con cierto detalle,a las personas y proyectos a su cargo y, por supuesto, que tenga cierta experiencia en su rol paratomar decisiones exitosas en la asignación de recursos. Manejar un número grande de proyectos ypersonas, digamos un equipo de trabajo de más de 40 ó 50 personas resulta bastante conflictivoy hacerlo sin apoyo, en el mejor de los casos, provoca que las decisiones tomadas sean de cortoalcance, es decir, se escoge la mejor asignación para un recurso o proyecto en particular y no la queoptimice la posibilidad de éxito en el conjunto de proyectos de la empresa. Ahora, el problema nosólo es interesante desde el punto de vista práctico, sino también teórico. El problema es complejode resolverse, no sólo para el gerente de proyectos, sino que, por ser un problema de asignación de

2

recursos se sabe que es un problema combinatorio difícil de resolver. De ahí radica la importancia degenerar un algoritmo capaz de ofrecer buenas soluciones que sirvan de apoyo al gerente de proyectosen el proceso de asignación de ingenieros a proyectos.

En resumen, el problema consiste en distribuir los recursos humanos disponibles en los pro-yectos abiertos de tal manera que se optimice la posibilidad de éxito en el conjunto de proyectos,al buscar satisfacer el mayor número de restricciones impuestas por cada asignación y restriccionesque tienen que ver con el ambiente en el que se desarrolla la empresa consultora, sus clientes ysus ingenieros. Para resolver este problema se requiere de un apoyo que, basado en la informaciónreferente a los ingenieros y a los requerimientos, automáticamente ofrezca buenas alternativas deasignación al gerente de proyectos.

En general las restricciones que deben ser tomadas en cuenta al resolver este problema sonconsecuencias de necesidades ya sea delcliente, de la empresa consultora, del proyecto particular ode los ingenieros. Estas necesidades pueden ser muy distintas e incluso hasta opuestas.

Se tienen, por ejemplo, que reducir al máximo las variables de tiempo y costo y por otro ladomaximizar la calidad del producto que se entrega. Estas son necesidades del cliente. Por otro ladola empresa consultora usca maximizar sus ganancias, endentar el uso de sus recursos, mantener lafidelidad de sus consultores, entre otras cosas.

Las restricciones impuestas por cada asingación tienen que ver, por ejemplo, con que el in-geniero asignado sea capaz de desempeñarse en el rol para el que fue requerido, por ejemplo, sise requiere un líder de proyecto deberá entonces asignarse un ingeniero que haya liderado algúnproyecto antes. También es necesario que el ingeniero conozca la tecnología con que se estará tra-bajando en el proyecto. Los ingenieros, por su parte querrán darle seguimiento a su plan de carrera,no estar sobrecargados de trabajo y tener derecho a vacaciones en las fechas que cada uno elija.

El problema se plantea y define a detalle en el tercer capítulo. Se presenta el caso general y porello muy complejo y difícil de modelar y resolver. De entre todas las restricciones que presenta elproblema se realiza una selección de las que se consideran más importantes y con éstas se define unasimplificación del este problema, que también se detalla en el tercer capítulo, pero puede resumirsede la siguiente manera:

• Existe un conjunto de personas que trabajan en la empresa consultora. De estas personas seconoce el o los roles que puede jugar y sus conocimientos.

• Para cada proyecto abierto se conoce el conjunto de requerimientos de recursos humanos, esdecir la fecha de asignación y desasignación, conocimiento y rol de cada una de las personasrequeridas en el proyecto.

• La tarea será asignar una persona a cada requerimiento de tal manera que se satisfagan lassiguientes restricciones:

- Cada requerimiento debe tener una y sólo una persona asignada.- Cada requerimiento debe tener una persona asignada que sea capaz de jugar el rol o

roles necesarios para ese requerimiento.— Cada requerimiento debe tener una persona asignada que sea tenga los conocimientos

necesarios para ese requerimiento.

3

— Una persona no debe estar asignada a dos requerimientos en el mismo período de tiempo.— La carga de trabajo entre los ingenieros debe estar balanceada.

1.3 ObjetivosEste trabajo de investigación tiene como principal objetivo desarrollar una prototipo capaz

de proponer asignaciones de recursos humanos a proyectos de desarrollo de software a partir de unconjunto de personas con ciertas características (experiencia, rol, etc.) y un conjunto de proyec-tos con requerimientos específicos de personas en fechas definidas, asegurando que las diferentesrestricciones se satisfagan.

Los objetivos particulares a cumplir en este trabajo de investigación son los siguientes:

• Definir una simplificación del problema de asignación de recursos humanos a proyectos dedesarrollo de software. Se escogen dentre el conjunto de restricciones del modelo general lasque se consideran más relevantes al problema de asignación y con ello se define un problemamás simple que es el que se intenta resolver en el presente trabajo. El problema general esdemasiado complejo para intentar ser resuelto en un trabajo como éste.

• Modelar el problema partiendo de la simplificación hecha.

• Proponer algoritmos eficientes para solucionar instancias del problema propuesto.

• Implementar los algoritmos propuestos.

• Construir un prototipo capaz de encontrar una posible asignación que satisfaga todas o lamayor cantidad de restricciones posibles, es decir que trate de optimizar la solución.

• Probar los algoritmos implementados para diferentes instancias del problema, en particularse busca comparar su desempeño con respecto a la velocidad en encontrar soluciones y a lacalidad de las mismas. Se generan para ello varias instancias del problema variando sólo elnúmero de recursos humanos y proyectos.

1.4 AlcanceEl principal objetivo se centra en la construcción del prototipo de una herramienta capaz de

proponer una asignación de un conjunto de recursos humanos a los proyectos respetando las restric-ciones impuestas por cada requerimiento. Esta distribución se realizará a partir del conocimientodel conjunto de proyectos, recursos humanos y sus atributos. Se generarán estadísticas respecto a lavelocidad del algoritmo, esto último con el fin de realizar un análisis comparativo de los diferentesalgoritmos con respecto a su comportamiento para diferentes instancias del problema.

1.4.1 HipótesisEl problema de asignación de recursos humanos a proyectos de desarrollo de software, de la

manera en que fue simplificado y modelado en el presente trabajo puede resolverse utilizando alguna

4

técnica de inteligencia artificial, en particular los algoritmos de recocido simulado y algoritmosgenéticos.

Durante el desarrollo de la tesis se pretende demostrar el enunciado anterior y contestar lassiguientes preguntas particulares:

1. Partiendo de un modelo propuesto para un caso simple del problema de asignación de recursoshumanos a proyectos de desarrollo de software, ¿es posible modelar también instancias máscomplejas de este problema agregando sólo algunas modificaciones al modelo?, o ¿Al acercareste problema al problema real el modelo se modifica radicalmente?

2. El algoritmo de recocido simulado, ¿Es útil para resolver este problema? ¿Qué tamaño deproblema es posible resolver, con tiempo y recursos limitados?, es decir, ¿Cuántas personasy proyectos es capaz de asignar?

3. El algoritmo genético, ¿Es últil para resolver este problema? ¿Qué tamaño de problema esposible resolver con este algoritmo?

4. ¿Puede decirse que un algoritmo es mejor que otro? ¿En qué casos?

1.5 Aporte de la InvestigaciónPara encontrar soluciones a este problema se construye un prototipo capaz de generar una

buena solución para un problema de asignación de recursos a proyectos de desarrollo de softwarebasado en las restricciones definidas en el presente trabajo.

El prototipo incluye un generador de problemas, que es capaz de generar problemas de diferenetamaño. El tamaño está basado en el número de requerimientos e ingenieros con que se cuenta.También es posible generar problemas más o menos restringidos, es decir dónde cada requerimientoexige más o menos características que el ingeniero deba cumplir.

El problema que se genera automáticamente es un conjunto de matrices que proveen la si-guiente información: el conocimiento(s) y rol(es) que cada uno de los ingenieros puede jugar, elconocimiento(s) y rol(es) de cada requerimiento y los conflictos en tiempo de los requerimientos.El prototipo puede resolver un problema con el algoritmo de recocido simulado, con el algoritmogenético o con ambos.

Se considera como la mayor aportación del presente trabajo la modelación del problema y eldiseño y construcción del algoritmo, capaz de ofrecer soluciones al problema.

Respecto a la modelación, se concluye en el tercer capítulo que el modelo propuesto puedeextenderse fácilmente a un modelo más complejo. Se reconoce sin embargo que variables comocalidad o costo no pueden ser incluidas directamente en el modelo.

En los experimentos realizados se resuelven problemas de distintos tamaños y con distintacantidad de restricciones y se observa el comportamiento de cada algoritmo al resolver estos pro-blemas. Se evalúa la rapidez y calidad de las soluciones entregadas por ambos algoritmos. Tambiénse realizan comparaciones entre los algoritmos.

Se encuentra también el límite de estos algoritmos, es decir, el tamaño máximo de problema quepueden resolver. Se considera que un algoritmo puede resolver un problema si es capaz de hacerlo en

5

algunos minutos, menos de 15, ya que de otra manera no sería una herramienta útil para el gerentede proyectos. Este tamaño es de un poco menos de 300 requerimientos y un número similar deingenieros. Este dato es alentador porque, si bien las empresas consultoras grandes pueden contarcon mayor número de consultores, normalmente estas empresas se distribuyen geográficamente ylas oficinas en cada ciudad con poca frecuencia exceden el número de requerimientos e ingenierosdados.

Por otro lado se verifica el comportamiento de los algoritmos al prefernciar una restricciónsobre otra, esto se hace variando los pesos de cada restricción en la función de aptitud. En generalse obtiene que se obtienen mejores respuestas para la restricción a la que se le da preferencia, peroel número de restricciones no satisfechas totales se incrementa. Al satisfacer más de una restricciónal mismo tiempo no se obtienen respuestas tan alentadoras, pero en general se concluye que lasintonización de los pesos de la función objetiva es trabajo del gerente de proyectos ya que él es elque debe decir cuál es la combinación exacta que puede ayudarle en su situación actual.

Por último se incluye una restricción que tiene que ver con que la solución que ofrezca elalgoritmo sea lo más parecida a la solución actual para que el implementar la nueva solución noimplique grandes cambios en las asignaciones actuales.

En general se concluye que ambos algoritmos son capaces de resolver problemas de éste tipo.El tamaño de problema que pueden resolver está al rededor de los 280 requerimiento y un númerosimilar de ingenieros. El algoritmo de recocido simulado encuentra mejores respuestas conforme elproblema se hace más grande.

1.6 Estructura de la Tesis

A continuación se presenta un resumen de la estructura del presente documento.El problema de asignación de recursos como problema de estudio teórico se trata en el capítulo

dos de antecedentes. Se habla de la complejidad del mismo y se propone resolverlo con algoritmosde búsqueda, específicamente recocido simulado y algoritmos genéticos. En este mismo capítulo seexplican los dos algoritmos utilizados así como algunos detalles de su implementación.

En el capítulo tres se presenta la descripción del problema de asignación de recursos humanosa proyectos de desarrollo de software, se plantea la necesidad de limitarlo y se presenta el problemaparticular que se pretende resolver.

Posteriormente se propone un modelo del problema particular y se sugieren algunas extensionesposibles. También se mencionan algunas variables que no podrían ser incluidas fácilmente en elmodelo. Después se presenta un ejemplo para clarificar el modelo. Por último, en este capítulo, sedan los detalles de la implementación con los dos algoritmos seleccionados. Se trata primeramenteel algoritmo de recocido simulado y la manera en que fue implementado para resolver este problema.Después se propone un algoritmo genético para resolver el problema a partir del mismo modelo.

En el capítulo cuarto se presentan los resultados de los experimentos que se realizan con ambosalgoritmos. Además de presentar comparaciones entre ambos métodos, se estudia el comportamien-to de los algoritmos al variar los pesos de la función objetivo y se incluye una nueva restricción quetiene que ver con proponer una solución parecida a la solución actual. Finalmente, se presentan lasconclusiones y discusión de los resultados obtenidos a partir de la experimentación.

6

En el quinto y último capítulo se presentan las conclusiones generales, el aporte de la investi-gación y el trabajo futuro.

7

Capítulo 2

Marco Teórico

Como se mencionó en el capítulo anterior, el problema tratado en el presente trabajo puedeclasificarse como un problema de asignación de recusros. En este capítulo se detallará el problemateórico de la asignación de recursos, incluyendo una breve historia de las técnicas que han sidoutilizadas al intentar resolverlo. Después se detallan algunas particularidades de los problemas deasignación de recursos humanos. A continuación se explicará como la búsqueda puede ayudar aresolver este problema al tratar de optimizar, mejorando progresivamente la solución conforme serecorre el espacio de búsqueda. Por último se detallan las dos técnicas de búsqueda utilizadas enel presente trabajo, recocido simulado y algoritmos genéticos.

2.1 El problema de Asignación de Recursos

El problema de asignación de recursos ocurre en un sinnúmero de actividades. Básicamentebusca asignar recursos limitados a un conjunto de tareas. Tanto los recursos como las tareas puedentomar muchas formas; los recursos pueden ser máquinas y las tareas productos generados por lasmáquinas. Pero los recursos también pueden tomar la forma de personas y las tareas son losrequerimientos de un proyecto.

La importancia del estudio de los problemas de asignación de recursos radica en que estosproblemas se presentan en cualquier área de la actividad económica. Algunos ejemplos típicosson los sistemas de logística, sistemas de planeación de requerimiento de materiales, estaciones decontrol y despacho, entre otros. Los problemas de asignación de recursos normalmente presentanrestricciones que impiden asignar cualquier recurso a las tareas, estas restricciones pueden ser detiempo, por ejemplo, qué tarea debe terminarse primero, también pudiera tener que ver con quérecurso es mejor para cada tarea, etc.

En resumen, en el proceso de asignación de recursos se hacen decisiones dinámicas acercade la organización, selección y programación de un conjunto de recursos para llevar a cabo lasactividades necesarias para producir, en el tiempo deseado, una o más tareas; satisfaciendo unconjunto de restricciones que tienen que ver tanto con el uso de los recursos como con la secuenciaen que éstos deben utilizarse, y en muchos casos tratando de optimizar ciertos criterios.

Debido al hecho de que existen similitudes entre un conjunto de problemas de la industria alos que englobamos como problemas de asignación de recursos, es de esperarse que los avances quese realicen en este sentido tendrán un impacto en todos los diferentes problemas relacionados conesta área, de ahí la importancia del estudio teórico del problema de asignación de recursos.

Las decisiones típicas de asignación de recursos tienen que ver con, el secuenciamiento, es decir

8

el ordenamiento de las distintas tareas, los tiempos en el que cada tarea se realiza y el ruteo o laasignación de una actividad al subconjunto específico de recursos de entre muchos otros que puedeutilizar.

2.1.1 El Problema de Asignación de Recursos Humanos

El problema general de determinar la mejor manera de empatar al personal disponible con losrequerimientos de personal de una organización es un problema no resuelto que preocupa amplia-mente a muchos administradores e ingenieros industriales. Este problema puede subdividirse entres problemas:

• Planeación de personal. Determina los requerimientos de personal, en número y en perfil,a largo plazo para cumplir con las metas de la organización y asegurar la operación regular.La planeación de personal responde a preguntas como ¿cuántas personas y de qué perfil sedeben contratar en los siguientes 5 años?.

• Programación de personal. Determina los patrones de trabajo que pudieran tomar laforma de turnos para satisfacer las demandas de la organización durante el tiempo.

• Asignación de personal. La asignación de personal involucra la asignación de las personasa las tareas, turnos, máquinas, etc.

La tarea de la asignación de personal es encontrar la manera óptima de asignar los recursosde personal disponibles a las necesidades de trabajo de una organización considerando todas lasrestricciones existentes. La solución requiere que los requerimientos y las personas disponibels seanconocidos [1].

2.1.2 Evaluación de la Asignación de Recursos

Para encontrar una solución en la asignación de recursos es necesario definir lo que hace quecierta asignación de recursos sea mejor que otra, es decir es necesario encontrar un buen objetivopara maximizar o minimizar. Encontrar esta función es difícil debido a que, en la industria,normalmente no se realiza una cuantificación formal de la satisfacción del cliente en cuanto acalidad o prontitud.

El problema de asignación de recursos tiene que ver con tres tipos de objetivos que son muydiferentes y hasta antagónicos en ciertas ocasiones:

• Maximizar la salida respecto a un periodo de tiempo.

• Maximizar la calidad la calidad y prontitud.

• Minimizar los costos.

2.1.3 Solución al Problema de Asignación de Recursos

El problema de asignación de recursos se ha tratado de resolver a lo largo de los años de muchasy muy diversas maneras, se presenta aquí un resumen de las principales aproximaciones, orientadas

9

específicamente a líneas de producción, pero no por eso debe olvidarse que existen muchos otrosambientes donde se presenta el problema de asignación de recursos [11].

• Expertos Humanos. Una solución al problema de asignación de tareas es asignar aingenieros especializados en investigación de operaciones a la operación y administraciónde las líneas de producción, ellos, principalmente usan dos aproximaciones; por intervalo opor despacho. Las soluciones por intervalo implican tomar de punto de partida la fechacomprometida y de ahí parten hacia atrás tratando de administrar de la mejor manera loscuellos de botella.Los métodos de despacho, en cambio, buscan hacia adelante, utilizando heurísticas paraseleccionar por prioridad en los puntos clave de solución, pero estas decisiones están sujetasa numerosas excepciones a juicio del ingeniero.Las principales ventajas de la programación de tareas manual son:

— Combinación rápida y precisa de la experiencia humana y de las prioridades formales— Amplio uso del sentido común cuando es necesario adaptarse a algún quiebre o crisis

Las principales debilidades de la programación de tareas manual son:

— Imposibilidad de probar un número importante de prioridades formales diferentes o hacerestimados precisos de del efecto de las acciones realizadas.

- Imposibilidad de reaccionar ante cambios rápidos.- Imposibilidad de trabajar con sistemas complejos.

• Simulación. A partir de 1950 se empezaron a usar las computadoras para soportar laactividad industrial. Desde entonces, las computadoras se han usado para tratar de resolvero apoyar el proceso de asignación de tareas de distintas maneras.En un principio se trató de representar la estructura de los problemas de asignación detareas en una computadora, de tal manera que, recibiendo los datos de entrada apropiados y,aplicando reglas simples de despacho la computadora pudiera extrapolar una programaciónal futuro para que se conocieran sus efectos antes de ser implementada la asignación. Segeneraron simuladores utilizando las diferentes heurísticas de tal manera que se pudieranhacer comparaciones entre una y otra.Las simulaciones pueden representar sistemas con mucho realismo con un costo computacionalmodesto, además provee una interfaz muy natural con el experto humano. Sin embargo, ladesventaja es que los resultados obtenidos a partir de la simulación distan mucho de seróptimos.

• Aproximaciones Matemáticas. A partir de 1960 se empezaron a usar modelos y procedi-mientos para resolver problemas de asignación de recursos usando programación entera. Laprogramación entera, en teoría, permite formular problemas de asignación de recursos de unamanera tal que permite que éstos sean resueltos de manera exacta.Uno de los métodos más importantes es branch and bound, la idea básica es construir un árbolde búsqueda con todas las posibles combinaciones de asignaciones. Al ir construyendo el árbol

10

se busca detectar cuándo una asignación no guía al óptimo y discriminar toda esa rama loque elimina grandes secciones del árbol de búsqueda y permite acortar el costo computacionalde encontrar una solución.

Debido a la complejidad computacional que resolver este problema representa, se han buscadométodos heurísticos para resolver este problema no de manera exacta, sino aproximada. Unatécnica muy utilizada es la búsqueda en una vecindad [11]. Se inicia con una solución noóptima, encontrada con alguna otra heurística; luego se hacen modificaciones suaves a laasignación y se evalúan todas las asignaciones generadas, se selecciona la mejor y se comienzaotra vez hasta encontrar una solución suficientemente buena (previa definición de los criteriosde aceptación).

• Sistemas Expertos. Un sistema experto es un sistema basado en el conocimiento, el cono-cimiento del sistema experto o base de conocimiento, es una representación del conocimientode un experto en un dominio del conocimieno particular. La codificación del conocimientodebe poder ser entendida por la máquina de inferencia. El sistema experto provee solucionesal usuario a través de la máquina de inferencia que utiliza como fuente de conocimiento a labase de conocimiento y lo procesa para encontrar soluciones [13].

El sistema ISIS [11] fue uno de los primeros grandes prototipos de sistemas de asignaciónde tareas. Usa un método de búsqueda ciega combinado con asignación de intervalos haciaatrás. La función de evaluación está definida por el número de restricciones no satisfechas, aestas restricciones se les asigna un peso de acuerdo a su importancia. PATRIARCH [11] es unprototipo para dos niveles, planeación y asignación de tareas. El nivel alto ocupa dinámicade cuello de botella y el inferior es un sistema experto. Existe un sistema más, construidosobre PATRIARCH que es un sistema experto un poco más sofisticado.

• Redes Neuronales. Las redes neuronales son un desarrollo de la inteligencia artificial quetratan de simular el proceso de aprendizaje del cerebro [11]. Si se considera a la red neuronalcomo una caja negra. Para un conjunto de entradas dado, se provee un conjunto de salidasque son la solución del problema. Es posible implementar la red de tal manera que la saldase una función objetivo que pudiera compararse contra la mejor solución encontrada hastaese momento, las soluciones pueden ser generadas por algún métodocualquiera.

• Otras Aproximaciones. La búsqueda tabú, recocido simulado y algoritmos genéticos,generan una solución utilizando métodos de búsqueda ciega que permiten partir de una solu-ción(es) inicial(es) y de la posibilidad de evaluar cualquier solución y, a partir de ahí, generanpequeñas modificaciones a la solución(es) original(es) tratando de llegar a una mejor evalua-ción. Existen muchos algoritmos relacionados con la identificación y manejo de los cuellos debotella. El método más popular es el llamado OPT [11] que identifica el recurso más utili-zado, a partir de ahí, se determinan prioridades de tal manera que primero se atienda a lastareas que requieran un extenso uso de recursos pero que sólo utilizan una pequeña porcióndel tiempo de aquel recurso más utilizado. Este método tiene la ventaja de que si se resuelvepara uno de los cuellos de botella que se identifiquen el problema se simplifica de manera talque puede ser resuelto fácilmente, sin embargo tiene muchas desventajas corno por ejemplo no

11

es capaz de adaptarse a ambientes con múltiples cuellos de botella o, si ocurre algún cambiorequiere de una reprogramación completa, por mencionar algunos.A pesar de todo esto OPT es utilizado como un estándar de comparación para los sistemasde asignación de recursos.

2.1.4 Problemas Relacionados

A continuación se presenta una breve descripción de algunos problemas de asignación derecursos humanos y la manera en que han sido resueltos.

ProAINUS. NURSE ROSTERING

El sistema ProAINUS [7] fue desarrollado por NEC Computer Systems. Su propósito esgenerar los turnos de las enfermeras de un hospital. Está basado en las herramientas provistaspor ILOG; Optimization Suite, Solver y Scheduler [8]. Las restricciones se reciben a través de unarchivo que contiene:

• Información referente a las enfermeras. Datos concernientes a cada enfermera como su califi-cación, días libres, equipo, días libres acumulados, fechas restringidas, datos de compatibilidadentre miembros de un equipo

• Información general. Información estática como los días de descanso oficial número de díasde trabajo permitidos entre dos días libres, etcétera.

• Información referente al hospital. Número mínimo de enfermeras para formar un equipo,preferencias en la conformación de los equipos, número de enfermeras requeridas por turno

Esta herramienta pretende no sólo satisfacer las restricciones descritas, sino además optimizarla solución para minimizar la desviación de la carga de trabajo de las enfermeras, incrementar laasignación de días libres a las enfermeras con días libres acumulados, etcétera.

El algoritmo utilizado por este sistema carga todas las restricciones, y después recorre elespacio de búsqueda. Primero busca a la enfermera con menor carga de trabajo y le asigna unvalor para el turno. Si es posible, se asignan valores que satisfagan los patrones preferidos y lascombinaciones deseadas. Este proceso de prueba y error se repite hasta que los mejores valoresposibles son asignados a las variables. Una vez terminada la búsqueda se presentan las asignacionesde turno al usuario.

TRAPS

TRAPS [4] es un lenguaje para la distribución de recursos dependientes del tiempo. TRAPS sepresenta como una alternativa a la solución de problemas de programación de tareas dependientesdel tiempo que tradicionalmente se resuelven utilizando complejas redes que muchas veces incluyenrestricciones no binarias. La propuesta de TRAPS es un sistema basado en el conocimiento queincorpora conocimiento humano acerca de detalles específicos del problema y estrategias posibles

12

para la distribución de los recursos en las tareas. Estos sistemas también pueden admitir restric-ciones relajadas de una manera natural y en general tratar varias versiones de un mismo problemacomo lo haría un experto.

TRAPS permite la definición de actividades dependientes del tiempo con orden parcial entreellas. Además, mantiene la disponibilidad de recursos a través del tiempo y permite que un recursosea asignado en un tiempo y se libere después. Algunas de las ventajas de TRAPS sobre loslenguajes de programación lógica de restricciones (CLP - Constraint Logic Programming) son queTRAPS provee un lenguaje de más alto nivel para la especificación del problema. Y provee facilidaden el cambio de estrategias de distribución lo que permite alcanzar una solución cercana a la óptimay de manera eficiente con menor esfuerzo.

Es necesario aclarar que los mismos autores responsables del desarrollo de TRAPS reconocenque existen muchos casos en los que el código generado por TRAPS no es tan eficiente como el deun CLP.

2.1.5 Complejidad Computacional

Los métodos descritos aquí ofrecen soluciones exactas pero sólo para un subconjunto muypequeño de problemas. Los problemas que pueden resolver son los más pequeños en cuanto alnúmero de tareas y recursos. Los problemas grandes se consideran intratables. Estos problemasson clasificados así debido a la explosión combinatoria que se presenta, de hecho el problema genéricode TI tareas en m máquinas (recursos) tiene un número infinito de soluciones posibles ya que lostiempos muertos insertados pueden variar. La mayoría de los problemas de asignación de recursostienen una complejidad similar o mayor. Se sabe que los problemas reales son NP-completos, lo quesignifica que no se ha generado ningún algoritmo que lo resuelva en tiempo polinomial con respectoal tamaño del problema (Garey et al. 1976).

Además de la complejidad computacional, existen otras dos características que hacen que elproblema de asignación de recursos sea difícil de automatizar y de que las técnicas actuales pararesolverlo no garanticen la optimalidad. Estas características son:

• La naturaleza conflictiva de los requerimientos que una buena asignación debe cumplir. Losobjetivos se contraponen en muchos casos y no siempre es claro cómo una decisión puedainfluenciar en el o los objetivos globales.

• La incertidumbre que causa la naturaleza dinámica de la mayoría de los ambientes en dondese dan los problemas de asignación de recursos. Cualquier sistema de asignación de recursosdebe ser capaz dé adaptarse a eventos no previstos, en el peor de los casos el cambio puedeser lo suficientemente fuerte como para tener que iniciar la solución desde un inicio, pero esteproceso es lento lo que no permite una respuesta eficiente al ambiente real, por lo tanto esnecesario encontrar maneras de aprovechar la solución anterior y partir de ahí para buscaruna que se adapte a las nuevas condiciones.

13

2.2 Algoritmos de Búsqueda

La búsqueda es el fundamento de gran parte de la inteligencia computacional. Búsqueda esuna enumeración de un conjunto de soluciones parciales a un problema de tal manera que puedeser probadas para comprobar si son o no verdaderas soluciones al problema. Para poder hacerbúsqeda se requiere de una definición de lo que pudiera ser una solución, un método para generarlas soluciones potenciales y por último una manera de verificar que la solución es correcta o no. Labúsqueda puede tomar muchas formas; muchos problemas pueden ser trans formados al problemade encontrar un camino específico en un grafo. Existen muchos estudios acerca de cómo hacerbúsqueda en grafos y muchas técnicas propuestas para hacerlo, basadas principalemente en elorden en que se recorren los nodos y la manera de desechar ramas no interesantes para acortar labúsqueda.

Cuando el espacio de búsqueda es infinito o cuando es demasiado grande para recorrerlotodo, los métodos de búsqueda que recorren todo el espacio de búsqueda no terminarán en untiempo razonable por lo que es necesario utilizar otros métodos de búsqueda que sean de encontrarsoluciones factibles y tratar de mejorarlas recorriendo sólo una porción del espacio de búsqueda.

Existen tres principales métodos de búsqueda; búsqueda basada en el cálculo, búsqueda ex-haustiva y búsqueda aleatoria [13].

Se le llama función objetivo a la función f ( x ) dónde f(x) es la función que se pretende optimizary x pertenece a un dominio acotado y definido. Se le llama espacio de búsqueda al conjunto detodos los valores que puede tomar x es decir al dominio de f ( x ) . Intento es la evaluación de f ( x )para un valor dado de x [15].

Los métodos basados en el cálculo pueden ser indirectos, en cuyo caso se buscan los extremoslocales resolviendo un conjunto de ecuaciones normalmente no lineales, resultado de igualar elgradiente de la función objetivo a cero. Los métodos directos buscan óptimos locales caminandopor la función en la direccióon que indique el gradiente de la función objetivo, lo que normalmentees llamado búsqueda de alpinista.

Estos métodos tienen la desventaja de buscar óptimos locales y dependen de que la funciónobjetivo sea derivable lo que, en problemas reales rara vez se da. Los problemas de búsqueda sonmuy complejos.

Los métodos enumerativos se basan en que, a partir de un espacio de búsqueda finita o unespacio de búsqueda infinita discretizada, el algoritmo de búsqueda exhaustiva punto a punto evalúala función objetivo hasta recorrer por completo el espacio de búsqueda para finalmente determinarel valor o valores óptimos de la función objetivo. Si bien este método garantiza encontrar el óptimoglobal, existen problemas cuyo espacio de búsqueda es tan grande que estos métodos, simplementeno podrían solucionarlos. En espacios de búsqueda menores éstos métodos son poco eficientes ylentos.

Ahora bien, los algoritmos de búsqueda aleatoria son métodos de búsqueda guidados queutilizan la selección aleatoria de puntos de la función objetivos. Los métodos de búsqueda aleatoriano exigen que la función tenga ninguna característica en particular (continua, derivable, etc)

Más adelante se detallan los dos métodos de búsqueda aleatoria, recocido simulado y algoritmosgenéticos, que serán utilizados en el presente trabajo.

14

2.3 Optimización

Optimización es el proceso de encontrar y comparar soluciones factibles hasta que no puedaencontrarse una mejor solución. Las soluciones se califican en base a uno o más objetivos, quepudieran ser el costo de fabricación de un producto, la cantidad de gases venenosos, eficiencia deun proceso, la confiabilidad de algún producto, entre otros [2].

El hecho de optimizar implica encontrar extremos de la función objetivo que pueden ser losvalores máximos, en cuyo caso la Optimización toma el nombre de maximización; o los valoresmínimos, en caso de que se desee hacer una minimización. Se dice entonces que optimizar esencontrar los parámetros que hacen que se optimice (maximice o minimice) una función dada.

La primera definición de este apartado es un poco rigurosa al decir que Optimización tiene quever con encontrar la mejor solución. Es importante separar el hecho de buscar mejorar con el deencontrar un óptimo. En la realidad no siempre es posible garantizar que un punto es el óptimo,ni tampoco siempre estaremos dispuestos a invertir lo necesario para encontrarlo pero siempre seráindispensable mejorar.

Los métodos de Optimización son de gran importancia en la práctica, particularmente en eldiseño en ingeniería, experimentos científicos y en la toma de decisiones gerenciales.

2.3.1 La Suma Ponderada

Existen una gran diversidad de métodos para optimizar funciones con múltiples objetivos,todavía no existe un método infalible que haya probado su efectividad en cualquier tipo de proble-mas, éste es un problema de investigación aún abierto [2]. El objetivo de el presente trabajo no esexperimentar distintos métodos de Optimización multiobjetivo, que como se dijo, es una rama deinvestigación aún abierta, sino encontrar un método para solucionar el problema de asignación derecursos, por ello se seleccionó aquí un método clásico que si bien no encuentra el conjunto de todoslos óptimos de la función objetivo, sí ofrece buenas soluciones y puede utilizarse más de una vez sise requirieran múltiples soluciones, método de suma ponderada, que se explica a continuación. Elmétodo de suma ponderada, convierte por medio de una suma un conjunto de objetivos en un sóloobjetivo, pre-multiplicando cada objetivo con un peso. Este método es la aproximación más simpley probablemente la más utilizada. La aplicación de este método requiere tomar algunas medidas,que se mencionan a continuación.

• La selección de los pesos. Los pesos no pueden ser arbitrarios sino que deben seleccionarsede acuerdo a la importancia de cada uno de los objetivos en el contexto del problema.

• Orden de magnitud. Otra dificultad de este problema es que los objetivos no siempretienen el mismo orden de magnitud, por ejemplo el precio del producto contra la eficienciade su producción. Los objetivos deben ser convertidos a una orden de magnitud homogéneopara después poder integrarlos a la suma ponderada. Es decir la imagen de cada uno de losobjetivos debe ser escalada linealmente de tal manera que todos los objetivos tengan el mismoorden de magnitud.

• Minimizaciones y maximizaciones. Es necesario homogenizar el tipo de Optimizaciónentre los objetivos. Todos los objetivos ser convertidos a un sólo tipo de Optimización ya sea

15 624368

minimización o maximización.

La suma ponderada puede ser utilizado en combinación con algún método de búsqueda de talmanera que la evaluación de la función objetivo del método de búsqueda se obtenga a partir de laevaluación de la surna ponderada de los objetivos. El algoritmo de búsqueda puede ser utilizadomás de una vez modificando en cada corrida los pesos en la suma con tal de encontrar diferentessoluciones favoreciendo a uno u otro objetivo.

2.4 Recocido Simulado

El algoritmo de Recocido Simulado [9] es una técnica útil en problemas de optimización es-pecíficamente para problemas combinatorios. El algoritmo de Recocido de Simulado está basadoen la analogía con el proceso físico de recocido de sólidos y el problema de resolver problemascombinatorios de gran tamaño. En la física de la materia el recocido denota un proceso físico enel que los sólidos son calentados hasta un valor máximo en el que las partículas de los sólidos seconforman de manera aleatoria en forma de líquido, seguidos por un enfriamiento bajando la tem-peratura de manera muy lenta. Si la temperatura inicial es lo suficientemente alta y el enfriamientose hace suficientemente despacio, las partículas se acomodan de maner tal que alcanzan el equilibriotermodinámico, que es un punto de mínima energía.

Empezando en el máximo valor de temperatura, la fase de enfriamiento del proceso de recocidosimulado puede ser descrita de la siguiente manera: En cada temperatura T. se le permite al sólidoalcanzar un estado de equilibrio térmico, caracterizado por la probabilidad de estar en un estadocon energía E dado por la distribución de Boltzman.

donde Z(T) es un factor de normalización conocido como la función de partición que depende dela temperatura T y de la constante de Boltzman Kp. El término exponencial se conoce como elfactor de Boltzman. Conforme decrece la temperatura, la distribución de Boltzman se concentraen los estados con la mínima energía y, finalmente, cuando la temperatura se acerca a cero, sólo losestados con mínima energía tienen una probabilidad diferente de cero de ocurrir.

La analogía con los problemas combinatorios es como sigue; el estado actual del sistematermodinámico es análogo a la solución actual del problema combinatorio, la ecuación de la energíapara el sistema termodinámico es análogo a la función objetivo y el último estado alcanzado, elde mínima energía es análogo al mínimo global del problema combinatario, la solución óptima.La mayor dificultad en la implementación del algorimto es que no hau una analogía obvia parala temperatura T con respecto a alguno de los parámetros del problema combinatorio. Aún más,el hecho de que el algoritmo quede atrapado en mínimos locales o no, depende de la temperaturainicial que se seleccione y de cuántas iteraciones se den en cada temperatura y del tamaño de losdecrcmentos de temperatura.

16

2.4.1 Implementación del Algoritmo de Recocido SimuladoLa implementación del algoritmo de recocido simulado consiste de una función de costo C

y una solución inicial Z0. La solución debe ser codificada en una cadena de caracteres de talmanera que pueda ser perturbado, es decir que se modifique alguno de los elementos de la misma,es importante hacer notar que la modificación de la cadena de caracteresg debe ser mínima. Debetambién definirse una función de costo que evalué la solución propuesta ya que será la herramientapara comparar dos soluciones y decidir cuál es la mejor, el valor devuelto por esta función parala solución i se llamará Ci. Recocido simulado naturalmente hace minimizaciones pero si lo quese requiere es un maximización habremos de hacer un mapeo lineal de la función de costo de talmanera que recocido simulado siga haciendo minimización y la solución final sea el máximo.

El algoritmo busca mejorar la solución actual perturbando aleatoriamente el estado Z0.

Recocido Simulado

"" venticacTempe

1

ion de lajratura

r

Ciclo Interno de RS

1 .̂ Perturbación

i •

Evaluación

iSelecc

probabi

onden con¡dad PT

Figura 2.1: Algoritmo de Recocido Simulado

El proceso de recocido simulado consta de dos ciclos; el más externo controla el decrecimientode la temperatura. El ciclo interno controla la estabilización en esa temperatura. El ciclo internoconsiste en el siguiente proceso:

• Perturbación. Perturbar aleatoriamente el estado Z¡, para obtener la solución Zj.

• Evaluación. Se decodifica la cadena de caracteres Z.j, y se evalúa con la función de costo paraobtener el valor Cj.

• Selección de solución con probabilidad PT- Se define AC* como la diferencia de la función decosto C de la solución original i con respecto a la función de costo para la solución producto

17

de la perturbación j. AC1 = C3 - C¿ Si AC" < O aceptar el nuevo estado.Si AC > O acopar elnuevo estado con probabilidad:

- ACP(A(7) = e— (2.2)

El criterio de aceptación es implementado al generar un número aleatorio Re[Q, 1] y compararloa P(AC'). Si R < P(A(7) entonces el nuevo estado se acepta.

Para una temperatura dada el ciclo interno debe durar lo suficiente como para que el siste-ma alcance un estado estable, es decir hasta que la distribución de probabilidad se acerque a ladistribución de Boltzman, definida en ( 2.1). El ciclo externo del algoritmo se refiere al programade disminución de la temperatura entre cada uno de los ciclos internos y especifica la ecuación dedecrecimiento de la misma, que en este casdo es se usa un factor de decrémento constante, de talmanera que para calcular la nueva temperatura T se utiliza la siguiente ecuación:

TÍ+I = oTj, (2.3)

donde a = 0.90. La temperatura inicial TQ debe ser lo suficientemente grande para asegurar recorrerel espacio de búsqueda de manera que se pueda ofrecer una buena solución. El algoritmo se terminacuando la función de costo permanece sin cambios por un mínimo de ciclos externos determinados.En resumen, el algoritmo, debe recibir un problema como entrada, generar una solución inicial,proveérsela a recocido simulado para que esta solución sea optimizada y por último reportar esasolución.

2.5 Algoritmos Genéticos

Un algoritmo genético [6] es un algoritmo de búsqueda basado en la mecánica de la selecciónnatural. Como se sabe, el proceso de evolución es muy complejo, a continuación se explica la ideabásica en la que están basados los algoritmos genéticos.

Un individuo, o más exactamente, su fenotipo está formado por un conjunto de característicascontenidas en sus genes, su genotipo, y de un conjunto de características adquiridas posteriormente.Los individuos de una misma especie son similares, pero difieren tanto en su genotipo como en sufenotipo. Los nuevos individuo se producen por cruce, es decir, normalmente dos individuos padresaportan sus características al nuevo individuo. El genotipo del individuo hijo es determinadopor una recombinación de los genes de los padres y probablemente también mutaciones, es decir,cambios aleatorios en algunos genes. En la lucha de la vida los individuos luchan por comida,territorio o pareja. Los individuos más aptos de la población sobreviven y pueden pasar sus genesa su descendencia. Este principio de selección ha permitido un alto nivel de adaptación de lasespecies a su ambiente.

Los algoritmos genéticos fueron desarrollados por John Holland, su estudio tenía dos objetivos,abstraer y explicar rigurosamente el proceso de adaptación en la selección natural y diseñar softwareque retuviera esta idea de la selección natural. El principal objetivo en el estudio de los algoritmosgenéticos es la robustez, entendiendo esta como el balance entre la eficiencia y la eficacia, que enconjunto implican alcanzar el objetivo consmiendo el menor número de recursos y esfuerzo. Nose conocen sistemas más robustos que los biológicos, por lo que podría pensarse que el estudiometiculoso de los sistemas biolgógicos y su posterior aplicación podrían ayudar a aumentar la

18

eficiencia de los sistemas artificiales. De hecho, se ha probado de manera teórica y empírica que losalgoritmos genéticos proveen una búsqueda robusta en espacios de búsqueda complejos [5].

Los algoritmos genéticos son computacionalmente simples y sin embargo son muy poderososademas de que no están limitados por restricciones en el espacio de búsqueda.

Los algoritmos presentan un conjunto de diferencias con respecto a los métodos de búsquedatradicionales.

• Trabajan con una codificación del conjunto de parámetros y no los parámetros.

• Buscan entre una población de puntos y no un sólo punto.

• Utilizan información directamente de la evaluación objetivo y no requieren ninguna otrainformación acerca de la función (derivadas parciales, continuidad, número de dimensiones,etc.)

• Utilizan reglas de transición probabilísticas y no determinísticas.

Como se dijo anteriormente en un algoritmo genético no se trabaja con el conjunto de parámetrosoriginal sino con una codificación de los mismos a los que se les llama individuos y que son un con-junto de caracteres en un alfabeto reducido que representan los parámetros de la función. A esteconjunto de caracteres se les llama también cromosoma porque se asemejan a ellos. El uso de estacodificación tiene las siguientes propiedades:

• Es posible codificar cualquier precisión de los parámetros variando la longitud del conjuntode caracteres o cromosoma.

• La precisión de las variables de decisión puede no ser igual para todas utilizando más o menoscaracteres del cromosoma.

• Las variables de decisión pueden tomar valores positivos y negativos.

• Los límites de las variables de decisión se verifican con la función de mapeo, que traduce elcromosoma (o genotipo) en el valor del parámetro.

El algoritmo genético evoluciona una población de individuos, los cromosomas, aplicandooperadores genéticos como selección, cruce y mutación.

Dado un problema de optimizacion, los individuos corresponden a una codificación de lassoluciones mientras que las poblaciones son conjuntos de soluciones. La aptitud del individuocorresponde a la evaluación de la función objetivo. El operador de cruce combina partes de dosindividuos aptos para formar nuevos. Estas partes del individuo que son recombinadas contribu-yeron a la aptitud de los padres. El operador de mutación altera alguna solución y puede producirgenes o combinaciones de genes que no hayan ocurrido antes en la población. No existe una mane-ra única de implementar un algoritmo genético, pueden usarse diferentes operadores de selección,cruce y mutación, la población puede ser generacional o no generacional, puede haber más de unapoblación, etc. En el presente trabajo se implementará el algoritmo genético simple. El algoritmogenético simple puede resumirse así [2]:

19

Figura 2.2: Algoritmo Genético Simple

1. Generar población inicial. Es la creación de un conjunto de individuos suficientes para crearuna población. Los individuos se crean de manera aleatoria.

2. Seleccionar nueva población

(a) Asignar aptitud a cada uno de los individuos de la población. Este proceso consisteen evaluarlos y después asignarles una aptitud. La evaluación de un cromosoma secalcula en base a la evaluación de la función objetivo para el fenotipo correspondienteal cromosoma evaluado. La aptitud de un individuo implica, reajustar la evaluación deacuerdo a la cantidad de restricciones no satisfechas de la solución propuesta.

(b) Verificar condición de término. Antes de generar una nueva población es necesarioverficar si se han cumplido los criterios para terminar la ejecución del algoritmo. Si nose han cumplido se sigue adelante de otra manera, se reportan los resultado y se terminala ejecución del algoritmo.

(c) Aplicar selección/reproducción. El principal objetivo de el operador de reproducción eshacer duplicados de buenas soluciones y eliminar las malas soluciones en una población,manteniendo el tamaño de la población constante. Esto se consigue a través de lassiguientes tareas:

i. Identificar los elementos que serán parte de la siguiente generación. Los individuos

20

con mejor aptitud tendrán más alta probabilidad de contribuir con descendencia ala siguiente generación

ii. Hacer múltiples copias de las soluciones seleccionadas.iii. Eliminar el resto de las soluciones para darle lugar a las copias de las buenas solu-

ciones.Existen varias maneras de hacer selección. Algunos de los métodos más utilizados sonselección proporcional y selección por ranqueo.

(d) Aplicar cruce. Hasta este momento ningún individuo de la nueva población es mejor quealguno de la población anterior porque sólo tenemos copias de la generación anterior sinninguna variante. El operador de cruce más comunmente utilizado puede describirse así:primero los individuos recién seleccionados son formados en parejas de manera aleatoria,después, cada par de individuos se cruzan de la siguiente manera. Se detrmina un puntok, también de manera aleatoria, que representa una posición en la cadena de caracteres.El individuo A se queda con los primeros k caracteres y toma del individuo B el restode los caracteres. El indviduo B toma del individuo A sus primeros k caracters y sequeda con sus restantes caracteres. Se espera que se pueden encontrar buenos individuosutilizando este operador porque los padres tienen una buena combianación de caracteresya que su aptitud fue buena. El operador de cruce es el principar responsable de labúsqueda en los algoritmos genéticos.

(e) Aplicar mutación. Por último se aplica mutación que es un cambio aleatorio en algúncarácter de un individuo, la mutación no se aplica de manera extensiva de hecho serecomienda usar una mutación por cada 1000 caracteres. El operador de mutación seaplica para conservar la diversidad de una población.

(f) Sino regresar al punto 2, seleccionar una nueva población.

2.6 ResumenEn el presente capítulo se estudiaron las principales características de un problema de asig-

nación de recursos y las particularidades de los problemas de asignación de recursos humanos,incluyendo algunas de las técnicas utilizadas para resolverlo. También se habló de algunos proble-mas específicos de asignación de recursos humanos y la manera en que fueron resueltos. Después sesugiere a la búsqueda como una técnica para resolver este problema y se explican los fundamentosde la optimización. Por útlimo, se plantean las técnicas de recocido simulado y algoritmos genéticoscomo herramientas útiles en la solución del problema de asginación de recursos humanos.

21

Capítulo 3

Problema de Asignación de Recursos Humanos a Proyectos deDesarrollo de Software

En el presente capítulo se describe el problema de asignación de recursos humanos a problemasde desarrollo de software, después se presenta una simplificación del problema general que es elproblema que se pretende resolver en el presente trabajo. Una vez definido el problema se modelade tal manera que pueda ser resuelto por los algoritmos propuesto y se presenta un ejemplo conel fin de clarificar lo explicado. Se plantean además posibles extensiones al modelo, basados en elproblema general.

Por último se explican los detalles de la implementación de las dos técnicas de búsquedautililzados para resolver el problema; recocido simulado y algoritmos genéticos.

3.1 Definición del ProblemaEn una empresa dedicada al desarrollo de sistemas de información el principal capital es el

humano. De la capacidad y experiencia de los individuos que se asignan a los distintos proyectosde la empresa depende el éxito o fracaso de esos proyectos. Se acostumbra, en estas empresas crearel rol de gerente de proyectos, quien entre sus principales tareas tiene la de asignar de maneraóptima los recursos materiales y humanos a los distintos proyectos para permitir que los objetivosespecíficos de cada proyecto se cumplan. Para el caso de una empresa pequeña donde las habilidades,capacidades y experiencia de los individuos son conocidas por todos y, además, el número deproyectos es reducido, la tarea del gerente de proyectos es relativamente sencilla. Tornar la decisiónde qué personas integrarán cada proyecto y las fechas de asignación y des-asignación de cada unasólo requiere que el gerente conozca, con cierto detalle, a las personas y proyectos a su cargo y, porsupuesto, que tenga cierta experiencia en su rol para tomar decisiones exitosas en la asignación derecursos. Manejar un número grande de proyectos y personas resulta bastante conflictivo y hacerlosin apoyo, en el mejor de los casos, provoca que las decisiones tomadas sean de corto alcance,es decir, la mejor asignación para un recurso o proyecto en particular y no la que optimice laposibilidad de éxito en el conjunto de proyectos de la empresa.

Para resolver este problema se requiere de un apoyo que automáticamente analice la infor-mación del los proyectos y los recursos y ofrezca buenas alternativas de asignación al gerente deproyectos.

A continuación se presenta una descripción que pretende ser detallada de las variables a lasque normalmente se les presta atención en el proceso de asignación de los recursos humanos a los

22

diferentes proyectos.El conjunto de variables que se describo a continuación no es el problema que se pretende

resolver en el presente trabajo, sino una simplificación del mismo. Se describe el problema para darun panorama general del problema y ubicar al problema que se pretende resolver en el problemageneral.

Las variables se presentan divididas en tres grupos, las variables que interesan al cliente, lasque leinteresan a la empresa consultora y las que interesan al consultor.

• Necesidades del cliente. Normalmente el cliente pedirá para su producto los más altosestándares de calidad en un tiempo muy limitado de desarrollo y exigirá un buen precio, pero,por su naturaleza estas tres variables se contraponen y, por lo tanto, es necesario que el clienteordene estas tres variables por prioridad, es decir, que defina que variables está dispuesto asacrificar en beneficio de la variable restante y en qué proporción.

— Reducir Costos. El cliente de un proyecto de desarrollo de software siempre querrá pagarel menor costo posible.

- Tiempo limitado de desarrollo. El cliente siempre tendrá una fecha de terminación. Porlo tanto el tiempo de desarrollo es limitado.

- Calidad. La calidad del producto final también se define desde un inicio y es el estándarrequerido por el cliente.

• Necesidades de la empresa consultora. La empresa consultora tiene como principalesobjetivos los siguientes:

- Maximizar ganancias. El desarrollo de sistemas será el negocio del consultor, así que suobjetivo deberá ser siempre obtener buenas ganancias. Para ello, cada proyecto debe serlo más rentable posible (rentabilidad del proyecto)

— Preferenciar proyectos importantes. En estricta teoría todos los proyectos son igualmenteimportantes, pero en la realidad existen factores que hacen que la empresa consultoraprefiera asegurar el éxito de un proyecto sobre otro. A continuación se mencionan algunasde las variables involucradas en esta decisión.

* Tamaño. Un proyecto grande necesariamente es más importante para la empresaconsultora que uno más pequeño. Por la utilidad obtenida, por el impacto que haceen oí cliente y en el mercado en general, y por el riesgo que conlleva.

* Nivel de Riesgo. La empresa consultora se preocupará por no tener ningún pro-yecto en números rojos, o en el que el cliente quede poco satisfecho. Por ejemplo,un proyecto en el que la empresa consultora esté en riesgo de ser demandada porsu cliente, será más importante que un proyecto grande que no ha tenido grandescomplicaciones. Por lo tanto, procurará reforzar aquellos proyectos con mayor riesgode caer en esta situación.

* Importancia. Existen proyectos estratégicos para la empresa consultora debido asu alcance, son aquellos proyectos que los posicionen con el cliente o en el mercadoen general. En estos proyecto la empresa estará dispuesta aún a invertir, o a realizar

23

algún otro tipo de sacrificio, ya que los beneficios a largo plazo de que el proyectoresulte exitoso, son aún más importantes que la utilidad que pueda obtenerse delproyecto.

- Eficientar el uso de los recursos. Se requiere una carga de trabajo balanceada entre losingenieros de la firma.

- Mantener a sus consultores. El recurso más importante de la empresa consultora es elcapital humano, es decir, los consultores, así que será muy importante que las personassean fieles a la firma, y la empresa tratará de propiciar esta fidelidad.

Necesidades del proyecto. Para que un proyecto sea exitoso es necesario que un sinnúmerode variables se conjunten, en este documento sólo trataremos aquellas que tengan que ver conla asignación de recursos al proyecto.Durante el arranque de un proyecto es necesario definir los requerimientos del proyecto, esdecir, número y perfil de las personas que trabajarán en el proyecto, fecha de asignación ydes-asignación de cada una, fechas de vacaciones, cursos durante el curso del proyecto, encaso de que esto se dé.Las variables (de asignación de recursos) que permiten el éxito de un proyecto son:

— Asignación y des-asignación de los recursos en las fechas programadas para el proyecto.- Asignación de personas que cubran con el perfil requerido por el proyecto. El perfil de

un recurso humano asignado a proyecto tiene las siguientes dimensiones:* El rol que se requiere que la persona desempeñe tiene que ver con su formación,

experiencia e intereses.* Conocimiento Técnico. Es necesario que las personas asignadas a un proyecto conoz-

can a un cierto nivel (dependiendo de su rol) la plataforma en la cual desarrollaránel proyecto (base de datos, redes, arquitectura, un cierto tipo de tecnología -clienteservidor, web, mainframe, etc.)

* Conocimiento Aplicativo. En las fases de definición del proyecto, los analistas desistemas deben tener un mínimo de conocimiento respecto al proceso que buscanautomatizar con el sistema. El cliente se siente mucho más seguro y los resultadosdel análisis son más aterrizados si se cuenta con personas, dentro del equipo detrabajo, que conozcan el problema.

* Experiencia. La experiencia tiene que ver con la cantidad de tiempo que la personaha realizado el tipo de actividades que realizará en el proyecto. Esta experiencia serelaciona directamente con la soltura con la que una persona realiza su actividad,además de con el nivel de responsabilidad que puede asignársele.

* Habilidades. Ciertas habilidades son requeridas en las diferentes personas que seasignan a un proyecto, por ejemplo, alguien a cargo de un equipo de trabajo tendráque tener características de líder, una persona que tenga actividades de diseño debeser proactiva, etc.

Necesidades del consultor. Como se mencionó anteriormente, la empresa consultora debeponer mucha atención en sus consultores, por dos razones principalmente. Para que las

24

personas sigan creciendo, y la empresa junto con ellos y para que los consultores permanezcanfieles a la firma. Otra vez, no se mencionan aquí todas las variables relacionadas con esteproblema, pero si aquellas que tienen que ver con la asignación de los recursos al proyecto.

— Seguimiento del plan de carrera. El consultor junto con su firma diseñan un plan decarrera para él. Darle seguimiento a lo largo del tiempo implica asignar a este recursoactividades que le permitan crecer en el sentido que su plan de carrera indica, estoincide directamente en las cinco variables relacionadas con el perfil, que se listaron enel apartado anterior. Además, toda o la mayoría de la capacitación que el consultorrecibirá tendrá que relacionarse directamente con su plan de carrera.

— Vacaciones. El consultor tiene derecho a vacaciones, es decir que no siempre podráestar asignado a un proyecto. El periodo de vacaciones, preferente será escogido por elconsultor.

3.2 Definición del Problema Particular

El problema descrito tiene una complejidad tal que excede el alcance del presente trabajo. Sepropone aquí una simplificación de este problema, que básicamente consiste en sólo contemplar unsubconjunto de las restricciones iniciales. El objetivo que se prentende alcanzar consiste en ofrecerun punto de partida, a través de la solución del problema simplificado. Sin embargo, para poderaplicar este algoritmo al uso en la industria de la IT sería primero necesario ampliar el modelopara cubrir todas las restricciones de la sección anterior. En este mismo capítulo, en la sección de"Extensiones al Modelo" se sugiere la manera de incluir algunas de las restricciones que el problemaparticular no contempla.

Una vez presentada la simplificacón al problema, se presenta una modelación del problemasimplificado, que es la que se intentará resolver utilizando algoritmos genéticos y recocido simulado.

A partir de este momento se describen ya no el problema sino la simplificación propuesta aquí.El problema puede definirse de la siguiente manera: Existe un conjunto de personas que

trabajan en la empresa consultora. De estas personas se conoce:

• El o los roles que puede jugar.

• Los conocimientos relevantes a la empresa con los que la persona cuente.

Para cada proyecto abierto se conoce el conjunto de requerimientos de recursos humanos, decada uno de estos requerimientos se sabe:

• El conocimiento o conocimientos requerido

• El rol o roles que se cubrirán

• Si el requerimiento se traslapa o no en el tiempo con alguno de los demás requerimientos deese y otro proyectos.

Se pretende con esta información realizar la tarea de asignar a cada uno de los requerimientos unapersona de tal manera que:

25

• Todos los requerimientos estén cubiertos.

• Ningún requerimiento este cubierto por más de una persona.

Las restricciones descritas anteriormente son forzosas o duras, es decir ninguna posible asig-nación puede considerarse como solución a menos que se cumplan las primeras dos restricciones.

Ahora, se pretende preferir algunas soluciones sobre otras basados en los siguientes criterios(restriccinoes suaves):

• Se busca que un ingeniero no esté asignado a dos o más requerimientos en el mismo periodode tiempo.

• Se pretende que todos los requerimientos reciban un asignación dónde el rol o roles requeridoscoincidan con el de la persona asignada.

• La persona asignada a un requerimiento deben tener los conocimientos requeridos.

• Se debe buscar un balanceo de carga de trabajo entre los ingenieros, es decir que la desviaciónestándar de la carga por ingeniero (número de requerimientos asignados en un periodo detiempo) sea mínima.

3.3 ModelaciónEl problema de asignación de recursos humanos a proyectos de desarrollo de software presenta

un conjunto de restricciones que deben ser cubiertas para ser una solución aceptable. Se presentana continuación las principales características que definen el problema; las variables, su dominio ylas restricciones.

Las variables. Como se sabe, el problema consiste en asignarle a cada uno de los requeri-mientos un ingeniero que cumpla con las especificaciones del requerimiento y que no esté asignadoa otro proyecto que entre en conflicto con el primero. Por último se requiere que la carga de trabajoentre los ingenieros esté balanceada.

Si se define un arreglo de asignación A con tantos renglones como requerimientos existan, detal manera que /![,-] = j significa que alrequerimiento i se le asigna el ingeniero j. Asignarle un valora cada una de las celdas implica una posible solución al problema, por lo tanto la única variable eneste problema es el arreglo de asignación.

El dominio. El domino entonces, son los valores que puede tomar el arreglo de asignación esdecir los ingenieros disponibles.

Las restricciones. Existe un conjunto de ingenieros disponibles para satisfacer los requeri-mientos generados por los diferentes proyectos. Cada uno de estos ingenieros tiene la capacidad,de acuerdo a su experiencia, de jugar un conjunto de roles. Además, cada ingeniero conoce una omás tecnologías de desarrollo. Se tienen, además, un conjunto de requerimientos de los distintosproyectos , cada uno de estos requerimientos implica la asignación de una persona al proyecto quegeneró el requerimiento. El requerimiento tiene asociado uno o más de los roles y uno o más de losconocimientos, es decir se trata de que el ingeniero que se asigne a ese requerimiento tenga el rol yconocimiento requeridos.

26

El objetivo es encontrar un arreglo A tal que exista uno y sólo un ingeniero asignado a cadarequerimiento. Con r requerimientos y e ingenieros, para toda ¿, AÍ = x, donde a;e[l,e]

Sujeto a las siguientes restricciones:

• Cada requerimiento debe tener uno y sólo un ingeniero asignado (R[0])

• Por cada asignación, el ingeniero debe tener el conocimiento requerido (R[l]).

• Por cada asignación, el ingeniero debe poder jugar el rol requerido (R[2j).

• Los requerimientos a los que está asignado un mismo ingeniero no deben tener conflictos entresí (R[3]).

• Los ingenieros deben tener una carga de trabajo balanceada (R[4j).

3.3.1 Restricciones Parciales y Optimalidad de la Solución

Debido a las múltiples restricciones que este problema puede tener, se pretende encontrarsoluciones que cumplan la mayor cantidad de restricciones posibles, es decir, admitir como solucionesaceptables aquellas que violen un subconjunto de restricciones, se sigue la estrategia de ignorarrestricciones impuestas [3]. Debe, por lo tanto, establecerse un criterio de comparación entre lasdistintas soluciones que permita al algoritmo preferir una solución sobre otra y así trate de optimizarla solución encontrada.

Para lograr lo anterior, se define una función objetivo que califique la solución respecto alnúmero y tipo de restricciones no cumplidas. Existirán algunas restricciones más importantes queotras y algunas restricciones que necesariamente deban ser respetadas para considerar a esa solucióncomo una solución factible. La importancia de la satisfacción de estas restricciones se implementaráutilizando pesos para las restricciones, en el entendido de que el valor de estos pesos tendrá que serrefinado una vez implementado el algoritmo.

Entre las diferentes restricciones se pretenderá que siempre se cumpla la restricción de quetodos los requerimientos estén cubiertos y que cada requerimiento este cubierto por sólo un ingeniero

Las restricciones que en algún caso pudieran no cumplirse se listan en orden de importancia,primero las que se desea que se cumplan siempre y luego las que pueden no ser satisfechas enalgunos casos:

• Por cada asignación, el ingeniero debe tener el conocimiento requerido (R[l])

• Por cada asignación, el ingeniero debe poder jugar el rol requerido (R[2j)

• Los requerimientos a los que está asignado un mismo ingeniero no deben tener conflictos entresí (R[3j)

• Los ingenieros deben tener una carga de trabajo balanceada (R[4j)

La función objetivo deberá sujetarse a la siguiente forma:

f ( x ) = w0 • R[Q] + wi • R[l] + w2 • R[2] + w3 • R[3] + w4 • R[4] (3.1)

27

El primer requerimiento es el más importante, por eso el valor del peso WQ deberá ser muchomayor que el resto de los pesos en cualquier impelentación.

Para evaluar los términos R[0]...R[4] es necesario contar el número de restricciones no satis-fechas para cada tipo de restricción, a continuación se presenta la manera en que se calcula cadauna de ellas.

• R[0], cada requerimiento debe tener uno y sólo un ingeniero asignado. Para evaluar el númerode restricciones no satisfechas de este tipo de restricción es necesario contar el número derequerimientos que tienen cero ingenieros asignados y sumarlo al número de requerimientosque tienen más de un ingeniero asignado, el total es el término R[0] en la función objetivo(ecuación 3.1).

• R[l], por cada asignación el ingeniero debe tener el conocimiento requerido. Para evaluar estetérmino, es necesario, para cada requerimiento, verificar qué ingeniero está asignado al mismoy después verificar que el ingeniero cumpla con cada uno de los conocimientos requeridos, si nolo hace para uno o más conocimientos, estos se contabilizan. Después se repite el proceso parael siguiente requerimiento y se agregan los conocimientos no cumplidos y así sucesivamentehasta terminar con la evaluación de todos los requerimientos.

• R[2], por cada asignación el ingeniero debe tener el rol requerido. Otra vez es necesario irevaluando requerimiento por requerimiento para encontrar cuántas restricciones de rol no secumplen y sumarizar todas. Con esto se logra encontrar el valor del término R[2].

• R[3], los requerimientos a los que está asignado un ingeniero no deben tener conflictos entresí. Para evaluar este término es necesario encontrar el conjunto de requerimientos que repitanel ingeniero asignado, por ejemplo, si el requerimiento O, el 2 y el 7 tienen todos asignadosal mismo ingeniero, es necesario separar ese grupo para su evaluación. Se encuentran todoslos grupos de ingenieros con ingeniero igual. Por cada grupo encontrado se evalúa cuántosrequerimientos de esos se traslapan en el tiempo, se evalúa el siguiente grupo de requeri-mientos y se agrega a la suma el número de requerimientos que se traslapen en el tiempo yasí sucesivamente hasta terminar con todos los grupos de requerimientos. El número totalencontrado es la evaluación del término R[3].

• R[4] Los ingenieros deben tener una carga de trabajo balanceada. Para calcular esta restric-ción es necesario obtener la carga de trabajo ideal (cti) que es el número de requerimientosque cada ingeniero debiera atender y se calcula:

requerimientos .cu = - . (•J-¿)ingenieros

Una vez obtenida la carga de trabajo ideal, se obtiene la carga de trabajo real para cadaingeniero (cír¿), que es igual al número de requerimientos que cada ingeniero tiene. Ladesviación estándar con respecto a la carga de trabajo ideal es:

-ctn)'2 (3.3)i

El término R[4] es igual a a.

28

(3.3)

• R[5] La solución ofrecida por el algoritmo debe ser parecida a una solución inicial. Estarestricción no se ha mencionado hasta este momento pero se propone como una restricciónadicional en el capítulo 4. Básicamente implica que la solución ofrecida se parezca lo másposible a la manera en que están asignados los ingenieros actualmente para que no sea tandifícil implementar la solución. Se calcula de la siguiente manera; se incluye la diferencia entrela solución actual y la propuesta por el algoritmo como una restricción, es decir que se cuentael número de diferencias (en pares de requerimiento-ingeniero) de una solución con respectoa la situación actual y se trata de minimizar este número como al resto de las restricciones.

Para implementar la optimizacíón en la búsqueda de una solución que cumpla sólo parcialmentelas restricciones, es necesario evaluar la función objetivo y comparar esta evaluación con el óptimoglobal y en caso de ser mejor la evaluación global guardar la solución.

Como se pretende encontrar una solución que probablemente no cumplirá con todas las restric-ciones será necesario implementar una estrategia de búsqueda que permita contabilizar el númerode restricciones no satisfechas hasta ese momento y poderlo comparar contra las demás soluciones,este contador deberá considerar los pesos de las restricciones, es decir será una evaluación parcialde la función objetivo.

3.4 Un Problema Pequeño de Asignación de RecursosA continuación se define un problema de asignación de recursos humanos a proyectos de

desarrollo de software con el fin de explicar de manera explícita la modelación del problema asícomo la implementación de los algoritmos, y las soluciones que éstos arrojan. El problema es cortopara no distraer la atención del tema principal pero eso no quiere decir que los algoritmos esténpensados para problemas de semejante dimensión. Este ejemplo contiene datos ficticios pero quepermiten imaginar un problema real.

En una empresa de tecnología de software existen cuatro proyectos para cuatro empresasdiferentes: Química del Norte, Periódico el Centro, Grupo Delta y Tacos de don Pepe.

En la figura 3.1 se muestran cada uno de los once requerimientos de los proyectos abiertos,se etiquetan del O al 10. Cada uno de los requerimientos tiene necesidades de conocimiento, queen este caso pueden ser sólo conocimiento de base de datos , columna BD, y/o conocimiento detecnología web, columna Web. También se muestra el rol o roles que cada requerimiento exige,que en este ejemplo puede ser rol de desarrollador, columna Ds, rol de administrador de proyectos,columna Ap y/o rol de analista, columna An. Por último se muestra el periodo de tiempo en elque se pide al ingeniero, el inicio del periodo se muestra en la columna Ini y el fin del periodo enla columna Fin.

Como puede verse en la tabla, el proyecto con Química del Norte requiere de 3 ingenieros conconocimientos de bases de datos, que sean capaces de desarrollar aplicaciones (requerimientos 0,1,2)y uno de ellos, además debe conocer tecnología web y ser también administrador de proyectos(requerimiento 2). Uno de los ingenieros sólo se requiere por tres meses (de enero a marzo) y eladministrador y el otro desarrollador se requieren seis meses (de enero a junio).

Por otro lado, el periódico el Centro requiere dos desarrolladores web de abril a julio (re-querimientos 3 y 4) y un administrador de proyectos (requerimiento 5 ) en el rnisnio periodo de

29

Con. Rol Duración

I Química del NorteI Química del NorteI Química del NorteI Periódico el SurI Periódico el SurI Periódico el SurI Grupo DeltaI Grupo Delta] Grupo Delta| Grupo DeltaI Tacos de Don Pepe

si no nosi no nosi si nosi no nosi no nono si nosi no nosi no nosi no nosi no sisi no no

Ene MarEne JunEne JunAbr JulAbr JulAbr JulJul AgoJul AgoJul AgoJul AgoAbr May

Figura 3.1: Requerimientos existentes.

tiempo.El Grupo Delta estará requiriendo para julio y agosto a cuatro desabolladores de base de

datos (requerimientos 6,7,8 y 9) y uno de ellos deberá realizar, además labores de análisis (reque-rimiento 9).

Por último, los Tacos de Don Pepe sólo requieren a un desarrollador que sepa de base de datosy tecnología web (requerimiento 10) para hacer los meses de abril y mayo.

Esta información se representa usando la matriz de reqerimientos contra roles y requerimientoscontra conocimientos, dónde un 1 indica que se requiere el rol/conocimiento y un O que no. Lasmatrices se presentan en la figura 3.2.

Figura 3.2: Matriz de requerimientos contra conocimientos y requerimientos contra roles.

30

La empresa cuenta actualmente con los siguientes ingenieros:

• Alex es un administrador de proyectos que conoce de tecnología web, base de datos y puederealizar labores de análisis y desarrollo (Ingeniero 0).

• Beto es un desarrollador de web y base de datos (Ingeniero 1).

• Carlos también hace desarollos web y de base de datos (Ingeniero 2).

• Diana es analista y hace desarrollos de base de datos (Ingeniero 3).

• Elsa es una desarrolladora de base de datos (Ingeniero 4).

• Felipe es un desarrollador de aplicaciones web (Ingeniero 5).

• Gaby es un administrador de proyecto (Ingeniero 6).

• Hilda es una analista (Ingeniero 7).

La información de los ingenieros se resume en las matrices de ingenieros contra conocimientosy de ingenieros contra roles, otra vez un uno significa que el ingeniero posee el requerimiento/rol yun cero que no. Las matrices del ingeniero se presentan en la fiugra 3.3.

o 1

Figura 3.3: Matriz de ingenieros contra conocimientos y requerimientos contra roles

Por último, la matriz de conflictos entre requerimientos, indica si dos proyectos se traslapanen el tiempo (un uno en la intersección entre ambos requerimientos y un cero si no). Esta matrizse presenta en la figura 3.4.

En resumen se tienen once requerimientos y seis ingenieros para satisfacerlos. El gerente deproyectos necesita decidir cómo distribuir a sus ingenieros para satisfacer las necesidades de susclientes. Una posible solución, no necesariamente óptima se muestra en la figura 3.5

Esta solución implica, por ejemplo, que Alex cubre el requerimiento 0. Lo que implica que elclliente estrá muy contento ya que Alex cubre todos lo conocimientos y roles que le son exigidosy su otra asingación, el requerimiento 6 no se traslapa en el tiempo con su primer requerimiento.

31

Requerimientos

Figura 3.4: Matriz de conflictos entre requerimientos

I O Alex3 Diana1 Beto

8 11 5 Felipe| I I 5 Felipe

I 4 ElsaI 11 O Alex

2 Car/os6 Gaby4 Osa7 Hilda

Figura 3.5: Posible solución al problema.

Por otro lado, Beto cubre el requerimiento 2, que exige que el ingeniero sea un administrador deproyectos y además un desarrollador que conozca de BD y Web, pero Beto no es un administradorde proyectos, por lo que se estaría violando una restrcción. En general se busca que la soluciónofrecida viole el menor número de restricciones posible.

3.5 Extensiones al ModeloSi bien se decidió modelar sólo una parte del problema debido a su extensiónn y complejidad, es

interesarte plantearnos si es posible partir del modelo aquí presentado para extenderlo a cubrir másrestricciones o aún todas las presentadas aquí. En este análisis se pasarán por alto los requerimientosdel cliente debido a que no inciden por lo menos de manera directa en la asignación de los recursosy porque el problema está planteado desde el punto de vista de la empresa consultora. Ahora, notodos los requerimientos restantes están incluidos en el modelo. Se presenta como resumen tablaque indica cuáles requerimientos están ya modelados y cuáles no.

Requerimiento por requerimiento iremos comentando cómo podría incluirse en el modelo si es

32

Figura 3.4: Matriz de conflictos entre requerimientos

Tabla 3.1: Requerimientos incluidos en el modelo.

Tipo deRequerimiento

EmpresaEmpresaEmpresaEmpresaProyectoProyectoProyectoProyectoProyectoConsultorConsultor

Requerimiento

Maximizar utilidadPreferenciar la importancia del proyectoEndentar uso de recursosMantener a consultoresAsignación oportunaConocimientos técnicos cubiertosConocimientos aplicativos cubiertosExperienciaHabilidadesDesarrollo profesionalVacaciones

Modelado

nonosinosisisínononono

que ésto es posible y finalmente se concluirá si el modelo planteado puede extenderse fácilmentepara acercarse al problema general. Es importane destacar que estas sugerencias no forman partede los experimentos que se presentan en el siguiente capítulo por lo que no se puede decir nadarespecto a la efectividad de las mismas. Se presentan sólo "como una posibilidad que debe serexplorada más profundamente.

Respecto al requerimiento de maximización de la utilidad, para incluirla al modelo sería ne-cesario incluir información económica de los proyectos, que no tienen una relación directa con elmodelo por lo que esta variable no podría ser incluida de manera natural al modelo.

Respecto a la preferencia de un proyecto sobre otro, esto se podría implementar fácilmentecon una matriz de proyectos en dónde se incluyera el peso del proyecto, que será mayor mientrasmayor importancia tenga, este peso sería calculado en base a las variables presentadas anteriormente(tamaño, importancia estratégica y nivel de riesgo). El cálculo del peso tendría que ser definido porel gerente de proyectos. Ahora respecto a su implementación, todas las restricciones que tenganque ver con un proyecto, o con el requerimiento de un proyecto tendrían que ser afectadas con estepeso, por ejemplo si dos roles no se satisfacen para el requerimiento A, que es poco imortante y dosroles no se satisfacen para el requerimiento 5, la contribución del requerimiento A a la función deaptitud sería menor que la del requerimiento B.

La siguiente variable es la fidelidad del consultor, esta variable pudiera ser una consecuenciade las variables que tienen que ver con el consultor así que se deja de lado y se analizan despuéslas variables del consultor.

La experiencia del consultor no se modela aquí pero puede ser tratada exactamente igual quelos roles y los conocimientos, con una matriz que determine el nivel de experiencia de cada consultor.Ahora, si lo que se quiere medir es la experiencia del consultor en un tópico particular, entoncessería necesario declarar niveles para cada uno de los conocimientos y/o roles. Por ejemplo, si serequiere un analista muy experimentado y se tiene para asignar a ese requerimiento un analistaprincipiante se contará como una violación a la restricción pero de menor nivel que si asignamos aalguien que ni siquiera es analista. Otra vez el gerente de proyectos tendría que asignar pesos a los

33

conocimientos y/o roles de acuerdo al nivel de experiencia.Las habilidades sí podrían tratarse como ahora se tratan los conocimientos y roles de un

consultor, serían un sumando más en la función de aptitud.Respecto al seguimiento al plan de carrera, este requerimiento puede implementarse a través

de una matriz que indique que tipo de requerimientos sí cumplan con el plan de carrera de cadaconsultor y cuáles no. El conteo de los requerimientos que no cumplan con el plan de carreradel consultor conformaría otro sumando de la función de aptitud. Por último, para modelar elcumplimiento de las vacaciones del consultor también podría utilizarse una matriz que indiquecuáles requerimientos interferirían en tiempo con las vacaciones del consultor y si éste resulta estarasignado a uno de esos requerimientos se contabilizaría como una violación a una restricción. Comose puede ver aquí la gran mayoría de las variables de este problema tienen que ver directamentecon las asignaciones pueden ser incluidas sin modificar fuertemente el modelo inicial, básicamentelo que se hace es extenderlo. Ahora las restricciones que no tienen que ver directamente con lasasignaciones no pueden ser incluidas al modelo propuesto aquí por lo menos no de una maneranatural.

3.6 Implementación del Algoritmo de Recocido SimuladoPara utilizar Recocido Simulado se debe definir lo siguiente:

• El problema y su solución. El problema que se tratará de resolver será el de la asignaciónde recursos (ingenieros) a los requerimientos de un conjunto de proyectos. La solución aeste problema es una instanciación del arreglo de asignación A (el arreglo de asignación tienerequerimientos como renglones cuyos valores son los ingenieros asignados a ese requerimiento).Por ejemplo:

<

¿ ¿ = [ l 5 3 2 5 0 2 4 0 1 2 ] T (3.4)

En el problema descrito en la sección anterior, si el gerente de proyectos decide optar por estaasignación, el primer requerimiento, es decir el desarrollador para Química del Norte estaríacubierto por Beto, Carlos estaría asignado a los proyectos de Periódico del Centro, GrupoDelta y Tacos de Don Pepe y así sucesivamente.

• La definición de vecindad. Una perturbación del arreglo A será una modificación en unoy solamente un renglón de ésta, lo que implica que uno de los requerimientos cambiará elingeniero que lo cubre. El renglón, o requerimiento, será seleccionado aleatoriamente, asícomo su nuevo valor, cumpliendo sólo con que será un ingeniero válido. Por ejemplo, unaperturbación válida a la matriz anterior es:

4 = [ 1 5 3 2 5 0 2 4 0 3 2 ]T (3.5)

Lo que implica que el analista y desarrollador de base de datos para Grupo Delta ya no seráBeto, sino Diana.

34

• Una función de costo, ya definida (ecuación 3.1). En la que debe removerse el terminoR[Q] ya que la implementación asegura que siempre habrá un sólo ingeniero asignado a cadarequerimiento. En el ejemplo el valor de la función objetivo se calcularía de la siguientemanera:Para calcular la primera restricción, si el ingeniero tiene el o los coocimientos requeridos,existen un sólo requerimientos que no se cumple, al estar Elsa que no sabe de base de datosasignada al requerimiento 1, de Química del Norte. Respecto a los roles, Beto no es unadministrador de proyectos y está asignado al requerimiento O, y para cubrir el requerimientodel analista en Grupo Delta se usa a Beto también, que tampoco es un analista.Por lo tanto son dos los roles que no se cubren utilizando esta asignación. Respecto a losconflictos en los proyectos, Carlos está asignado a los proyectos de periódico del Centro yTacos de Don Pepe que se traslapan en el tiempo, y una vez que termina el proyecto conTacos de Don Pepe el requerimiento atendido por Carlos se traslapa con el de Grupo Delta.Elsa está asignada a los proyectos de Química del Norte y Periódico del Centro que tambiénse traslapan en el tiempo. En resumen son cuatro los requerimientos en conflicto.Por último, respecto a la uniformidad en la carga de trabajo, se espera que con once reque-rimientos y seis ingenieros cada ingeniero este asignado en promedio a 1.83 requerimientos.La desviación estándar para la asignación propuesta es de 1.68. Por lo tanto, el cálculo de lafunción objetivo queda como sigue:

f(x) = tu0 • O + wi • 1 + u>2 • 2 + K>3 • 4 + u>4 • 1.68 (3.6)

• Un control del decrecimiento de la temperatura, que se define a continuación. Entre cadacadena de Markov o ciclo interno de recocido simulado la temperatura disminuye 20% hastauna condición de paro que tiene que ver con el máximo número de cadenas sin que la soluciónmejore y que será especificado en cada experimento.

3.7 Implementación del Algoritmo GenéticoTambién se implemento un algoritmo genético, para resolver el problema planteado en este

trabajo. Los aspectos más importantes de la implementación de este algoritmo se presentan en estasección.

• Función Objetivo. Se utilizan un simulador y un evaluador para medir' la aptitud de losindividuos. El simulador consiste en el arreglo de requerimientos que contiene la informaciónreferente a qué ingeniero satisface qué requerimiento. En nuestro problema una instanciacióndel arreglo de asignación puede ser:

v 4 ¿ = [ l 5 3 2 5 0 2 4 0 1 2 ]T (3.7)

El evaluador, a partir de la matriz de asignación y de las matrices de restricciones (conoci-mientos, roles y conflicitos) evalúa la solución utilizando la misma función objetivo que se havenido usando definida en la ecuación 3.1.

35

Representación Respecto a la representación, el cromosoma binario representa los ocho in-genieros (10.. 17) que están asignados a cada uno de los requerimientos que forman parte delproblema.En nuestro ejemplo, tenemos once requerimientos y ocho ingenieros. Para representar alos ingenieros sólo es necesario utilizar tres bits, pero necesitamos representar qué ingenieroestará asignado a cada uno de los once requerimientos (RO..R10) por lo tanto necesitamos3*11 =33 bits en los cromosomas de este problema. En un problema diferente, con máso menos requerimientos y/o ingenieros será necesario recalcular el tamaño del cromosoma.En la figura 3.6 se presenta un cromosoma que puede representa la solución del arreglo deasignación AÍ-

R1(I5) R2(I3) R3(I2) R4 (15) R5(IO) R6 (12) R7(1) R8(IO) R9(I1) R10(IO)

pTo 1|1 O 1|0 1 1|0 1 0|1 O 1|0 O 0|0 1 0|1 O 0|0 O 0|0 O 1|0 1 0|

Figura 3.6: Cromosoma

Es importante notar que si el número de ingenieros es una potencia de dos no es necesariohacer ningú tipo de reinterpretación en el cromosoma, todas las posibles soluciones generadasdespués de selección, cruce y mutación son válidas.

• Método de selección. Respecto al método de selección se usa selección por torneo.

• Cruce. El cruce es de un punto, la probabilidad de cruce se presenta para cada experimen-to, así como la probabilidad de mutación. El tamaño de la población varia de problema aproblema.

• Oíros parámetros. La probabilidad de mutación y el tamaño de población que se elige en losexperimentos varía de acuerdo al tamaño del problema que se resuelve.

3.8 PrototipoSe implementa uii prototipo de software que se utiliza para probar los algoritmos propuestos.

El prototipo se esquematiza en la figura 3.7. Esta compuesto por un solucionador de problemas deasignación de recursos humanos a proyectos de desarrollo de software. En este programa principalse invoca ya sea al algoritmo genético o a recocido simulado o a ambos un problema para ser resuelton veces.

El problema se crea desde el generador de problemas, que es capaz de generar el problema conmás o menos restrcciones a través de un parámetro que controla la probabilidad de que se generenrestricciones en las matrices de restricciones. El problema generado consiste, básicamente, en unconjunto de matrices, la de los conocimientos del ingeniero, los roles del ingeniero, los conocimientosdel los requerimientos, los roles de los requerimientos y los conflictos entre proyectos, además seincluye la posibilidad de generar una solución inicial.

36

generador deproblemas

env a elprob

pide solucionar nveces y regrese el

solucionador de problemasde asignación de recursoshumanos a proyectos de

desarrollo de sw.

pide g aficarel pro nedio

d(evalué :iones

promedio de las ncorridas

envía el cromosoma y solicita suaptitud

envía el esta ío ysolicita su ap itud

pide solucionar nveces y regrese elpromedio de las n

corridas

solí :itaevalúa ion del

arree lo deasigr ación

Figura 3.7: Prototipo

El algoritmo genético toma el problema y cada vez que genera un nuevo individuo pide alsimulador que lo evalúe. El simulador recibe, tanto el problema, es decir, las matrices de restric-ciones, como el cromosoma. El simulador convierte el cromosoma en un arreglo de asignación quees pasado al evaluador junto con el problema para que se le asigne a ese arreglo de asignación unaptitud, dados los pesos de la función objetiva que se tratan como constantes.

Recocido simulado trabaja de manera similar. Recibe el problema y, cada vez que genera unnuevo estado pide al simulador convierta ese estado en un arreglo de asignación que junto con lasrestricciones son entregadas al evaluador para que evalúe la función objetivo para ese estado.

El problema se corre en los algoritmos tantas veces como se haya pedido y se genera el promediode las n coridas.

Por último el promedio de las corridas se regresa al solucionador y éste, si así se requiere le pideal graficador que genere la o las gráficas (número de intentos, contra evaluación) correspondientes.

3.9 ResumenEn este capítulo se revisó a detalle el problema de la asignación de recursos humanos a proyec-

tos de desarrollo de software. Además se propuso una simplificación del problema que es el que setratará de resolver a lo largo del presente trabajo. También se presenta su modelación, de la cuál

37

parten los detalles de la implemntación de algoritmos genéticos y recocido simulado, estos detallestambién se presentaron en el presente capítulo.

Además se plantean posibles extensiones al modelo propuesto inicialmentc, basados en elplanteamiento inicial del problema. Se puede conlcuir que el modelo es extensible naturalmentesiempre y cuando las extensiones que se presenten tengan que ver directamente con la asignación.Se requiere de un estudio más profundo poder realizar un modelo que contemple variables comocostos, calidad, utilidad, etcétera.

38

Capítulo 4

Experimentación y Resultados

En este capítulo se reportan los experimentos realizados con el fin de responder las preguntasplanteadas en la hipótesis, éstas mismas preguntas son las que determinan el tipo y cantidad deexperimentos que se realizan. Se presentan los resultados de estos experimentos así como el análisisde los resultados obtenidos.

4.1 Definición de los ExperimentosUna vez definido el problema particular, como se ha hecho en el capítulo anterior, se proponen

ahora un conjunto de experimentos con los cuales se pretenden contestar algunas de las preguntasplanteadas en el primer capítulo que básicamente tienen que ver con si los algoritmos propuestosson adecuados para resolver instancias del problema, y qué tamaño de problema pueden resolver.

Las preguntas que se pretenden responder a partir de los experimentos que se presentan en elpresente capítulo parten de la hipótesis, definida en el capítulo uno y son:

1. El algoritmo de recocido simulado, ¿Es útil para resolver este problema? ¿Qué tamaño deproblema es posible resolver, con tiempo y recursos limitados?, es decir, ¿Cuántas personasy proyectos es capaz de asignar?

2. El algoritmo genético, ¿Es últil para resolver este problema? ¿Qué tamaño de problema esposible resolver con este algoritmo?

3. ¿Puede decirse que un algoritmo es mejor que otro? ¿En qué casos?

Es necesario medir qué tan rápido es un algoritmo para resolver un problema, esto se hace atra\'és del número de evaluaciones de la función objetivo que el algoritmo tenga que realizar paraencontrar una solución. Respecto a la optimalidad de la solución, se usa la función de aptitud y laprecisión de la solución se mide con el conteo de las restricciones no satisfechas, por cada tipo derestricción. Por último, para medir el tamaño del problema se utiliza el número de requerimientos.En la tabla 4.1 se resumen las variables que serán monitoreadas y evaluadas en la ejecución de losexperimentos de acuerdo a los objetivos mencionados, mencionados.

Para medir estas variables y contestar con ello las preguntas se realizan dos tipos de experi-mentos. El primer conjunto de experimentos consiste en presentar a cada uno de los algoritmos elmismo problema y comparar la respuesta que arrojan así como el número de intentos necesariospara lograrlo.

39

Tabla 4.1: Variables a ser evaluadas en los experimentos.

¿Qué se quiere medir?Velocidad de ejecuciónOptimalidad de la soluciónPrecisión de la soluciónTamaño de problema

¿Con qué se va a medir?Número de evaluacionesPunción objetivoNúmero de restricciones no satissfechasCantidad de requerimientos

De este primer grupo de experimentos se hacen 90 problemas distribuidos de la siguientemanera; 30 problemas pequeños, 30 problemas medianos y 30 más para problemas grandes.

En el primer grupo de experimentos, de cada conjunto de 30 problemas se hacen 10 conproblemas muy restringidos, 10 con problemas medianamente restringidos y 10 con problemas pocorestringidos, como puede verse en la tabla 4.2. Cada problema que se presenta a los algoritmoses resuelto 10 veces por cada algoritmo. Se utiliza el promedio de las 10 soluciones como base delanálisis de las soluciones. A continuación se presenta la tabla 4.2 que sumariza el primer conjuntode 90 experimentos.

Tabla 4.2: Primer grupo de experimentos.

Poco restringidoMedianamente restringidoAltamente restringido

ProblemaPequeño

101010

ProblemaMediano

101010

ProblemaGrande

101010

El segundo grupo de experimentos consiste en verificar que se pueden obtener respuestas queden preferencia a uno o más de las restricciones impuestas. Por ejemplo que traten de asegurar quetodos los ingenieros tengan los conocimientos para los que fueron requeridos. Para este grupo deexperimientos se correrán y analizarán separadamente los dos algoritmos, con el fin de no complicardemasiado el análsis.

Para cada uno de los algoritmos se resuelven 90 problemas también, utilizando los mismostipos de experimentos que en el apartado anterior, aunque esta vez cada problema es resuelto tresveces, una de la manera original, otra vez preferenciando la satisfacción de la restricción que tieneque ver con que el ingeniero tenga el conocimiento requerido y por último se resuelve una terceravez preferenciando tanto la restricción del conocimiento como la del rol. Se analiza si las solucionesefectivamente preferencian la o las restricciones que se indican y cómo se ve afectada la aptitud ylas demás restricciones. En la tabla 4.3 se presenta el conjunto de experimentos que se realizan enla segunda parte y que tienen que ver con la variación de los pesos de la función objetivo.

Por último se realiza un tercer grupo de experimentos en el que se le agrega a la función objetivouna restricción más, esta restricción tiene que ver con que la solución generada por el algoritmo separezca lo más posible a la solución inicial. Se realizan 90 problemas utilizando recocido simulado,de éstos 90 problemas 30 son problemas pequeños, 30 medianos y 30 grandes. Cada grupo de 30

40

Tabla 4.3: Segundo grupo de experimentos.

Poco restringidoMedianamente restringidoAltamente restringido

ProblemaPequeño

3*103*103*10

ProblemaMediano

3*103*103*10

ProblemaGrande

3*103*103*10

problemas está dividido en 10 medianmente restringidos, 10 altamente restringidos y 10 pobrementerestringido. Cada problema se resuelve veinte veces, diez con los pesos de todas las restriccionesiguales a 1.0 y diez con el peso de la nueva restricción igual a 10.0 y el resto de los pesos igualesa 1.0. Se utiliza como base del análisis el promedio de diez evaluaciones. La tabla 4.4 resume eltercer grupo de experimentos.

Tabla 4.4: Tercer grupo de experimentos.

Poco restringidoMedianamente restringidoAltamente restringido

ProblemaPequeño

2*102*102*10

ProblemaMediano

2*102*102*10

ProblemaGrande

2*102*102*10

4.2 Parámetros utilizados en los experimentos

En esta sección se reportan los parámetros que son utilizados para realizar los experimentosque se reportan en esta sección.

Respecto al tamaño de los problemas, éste se define con pase en las siguientes consideraciones,puede ser resuelto fácilmente de manera manual por un experto, en nuestro caso el gerente deproyectos, un problema donde haya involucrados unos 8 ingenieros y 10 requerimientos podría serresuelto por un experto. Un problema mediano se considera aquel que pudiera ser resuelto demanera manual, pero no necesariamente de manera óptima, dado la complejidad del mismo. Unproblema del doble del tamaño, digamos 16 ingenieros y 20 requerimientos, ya no puede ser resueltotan fácilmente por un gerente de proyectos. Seguramente perderá de vista el problema general ytratará de resolver los problemas específicos, es decir las asignaciones próximas y las asignacionesurgentes. Por último, un problema grande se define como un problema del doble del tamaño deuno mediano, 40 requerimientos, 32 ingenieros. El tamaño de los problemas se resume en la tabla4.5.

En la realidad existen empresas consultoras con mayor número de consultores, pero en generalestas firmas se distribuyen en oficinas que se encuentran en puntos geográficos distantes por loque una oficina particular debe satisfacer los requerimientos del mercado con los consultores quetiene disponibles en ese punto geográfico. Se considera entonces que 40 ingenieros es un tamaño de

41

Tabla 4.5: Tamaño de los problemas.

Número de requerimientos

ProblemaPequeño

10

ProblemaMediano

20

ProblemaGrande

40

problema que ocurre frecuentemente en la industria y que no es posible resolver manualmente, porlo menos de manera óptima.

Se generan problemas más o menos restringidos para saber cómo se comportan los algoritmosen cada caso. Se definen tres niveles de problemas, alta, mediana y pobremente restringidos. Seconsidera un problema muy restringido cuando la probabilidad de que un requerimiento tengaalguna restricción es de 0.6, medianamente restringido cuando esta probabilidad es de 0.4 y pocorestringido cuando esta probabilidad disminuye a 0.1. En la tabla 4.6 se resumen este tipo deproblemas.

Tabla 4.6: Nivel de restricción de los problemas.

Probabilidad de tener restricción

PobrementeRestringido

0.6

MedianamenteRestringido

0.4

AltamenteRestringido

0.1

Los resultados obtenidos se ejecutan con los algoritmos descritos en el capítulo anterior perorequirieron de cierta sintonización. Los parámetros del algoritmo genético se presentan en la tabla4.7 y los de recocido simulado en la tabla 4.8. Estos parámetros fueron encontrados de manerapuramente experimental, se buscó aquellos valores para los que cada algoritmo encontraba unamejor solución y con esos se realizaron los experimentos.

Tabla 4.7: Parámetros del Algoritmo Genético.

Tamaño de la poblaciónLímite de generacionesProbabilidad de cruceProbabilidad de mutación

602000.9

(longitudcromosoma) ~ l

Respecto al cálculo de cada una de las restricciones, se detalla en el capítulo tres la manerade calcular cada uno de los tipos de restricciones.

4.3 Comparación entre los algoritmos

Como se dijo anteriormente el primer conjunto de experimentos consiste de 90 problemasdivididos en tres grupos.

42

Tabla 4.8: Parámetros de Recocido Simulado.

Razón de decremento de temperaturaLongitud de la cadenaMáximo número de cadenas sin mejoraMínimo número de intentosMáximo número de intentos

0.83001050200

El primer grupo de 30 problemas consiste en problemas de 10 requerimientos, 8 ingenieros,6 roles y 6 conocimientos diferentes. Cada algoritmo resuelve 10 veces el mismo problema y seobtiene el promedio de las 10 ejecuciones.

De este grupo de 30, se resuelven 10 problemas altamente restringidos, 10 medianamenterestringidos y 10 más, pobremente restringidos.

La probabilidad de mutación usada para problemas de 10 requerimientos fue de 0.033.A continuación se presentan los resultados de cada uno de los algoritmos por separado, después

se hace un análisis comparativo entre los dos.

4.3.1 Algoritmo Genético

En la tabla 4.9 se presentan los resultados de correr el algortimo genético para problemas de10 requerimientos y ocho ingenieros, en promedio la aptitud mejora conforme menos restringido esel problema. La restricción que menos se viola tiene que ver con que no hay ingenieros asignadosa proyectos que se traslapan en el tiempo, las restricciones que más se violan tienen que ver conque los ingenieros tengan el conocimiento y puedan jugar el rol que se les pide. Se recuerda que enestos experimentos no se hace preferencia por satisfacer ninguna de las restricciones.

Tabla 4.9: Problemas de 10 requerimientos AG.

aptitudintentosconocimientorolconflictoscarga de trabajo

Pobrementerestringido

9.28120004.13.90

1.28

Medianamenterestringido

18.35120008.327.320.262.45

Altamenterestringido

19.33120007.738.680.542.38

En problemas de 20 requerimientos, el algoritmo genético encuentra soluciones con menosrestricciones violadas para los problemas menos restringidos. En este caso el tipo de restricción quemás se viola tiene que ver con que el ingeniero tenga el conocimiento requerido, seguido por queconozca el rol. Solamente en problemas altamente restringidos existen 1 ingeniero, en promedio,que está asignado a dos proyectos al mismo tiempo. Estos resultados se muestran en la tabla 4.10

43

Tabla 4.10: Problemas de 20 requerimientos AG.

aptitudintentosconocimientorolconflictoscarga de trabajo

Pobrementerestringido

13.01120005.864.77

02.38

Medianamenterestringido

32.261200015.5112.350.374.03

Altamenterestringido

31.191200014.8311.171.333.86

Por último, se presentan los resultados al resolver con el algoritmo genético problemas de 40requerimientos en la tabla 4.11. Se observa que para el algoritmo genético, se conserva la tendenciade que las soluciones a los problemas menos restringidos violan menos restricciones que el resto delos problemas. También se violan muy pocas restricciones referentes a los conflictos entre proyectos,y otra vez el número de conocimientos y roles que el los ingenieros asignados no conocen son lasdos restricciones que más se violan.

Tabla 4.11: Problemas de 40 requerimientos AG.

aptitudintentosconocimientorolconflictoscarga de trabajo

Pobrementerestringido

20.29120007.678.310.074.24

Medianamenterestringido

60.491200027.0125.581.656.25

Altamenterestringido

59.631200027.3222.573.696.05

4.3.2 Recocido SimuladoAl resolver problemas de 10 requerimientos con recocido simulado se obtienen los resultados

que se muestran en la tabla 4.12. Otra vez se obtienen mejores respuestas para problemas me-dianamente restringidos. La restricción menos violada es la que tiene que ver con conflictos entreproyectos. Cumplir con el conocimiento y el rol siguen siendo las dos restricciones menos respetadas.

En problemas de 20 requerimientos, recocido simulado, en arroja los resultados que se pre-sentan en la tabla 4.13. Las tendencias que se han estado reportando continúan en este tipo deproblemas. Respecto a la uniformidad en la carga de trabajo, se tiene una desviación estándar de3.7 requerimientos en el peor de los casos. El ideal, en este caso, es que cada ingeniero este asignadoa 1.25 requerimientos en promedio.

Para problemas de 40 requerimientos se obtienen los resultados mostrados en la tabla 4.14.Se obtienen mejores resultados para problemas pobremente restringidos, existe un conflicto entre

44

Tabla 4.12: Problemas de 10 requerimientos RS.

aptitudintentosconocimientorolconflictoscarga de trabajo

Pobrementerestringido

9.28121464.093.91

01.28

Medianamenterestringido

18.35124448.227.530.22.4

Altamenterestringido

19.24122467.738.870.362.28

Tabla 4.13: Problemas de 20 requerimientos RS.

aptitudintentosconocimientorolconflictoscarga de trabajo

Pobrementerestringido

12.65128485.924.79

01.94

Medianamenterestringido

30.11329615.0911.090.143.78

Altamenterestringido

28.961324614.0310.80.53.63

requerimientos, en promedio, en el peor de los casos, que es en problemas altamente restringidos,lo cuál es un muy buen resultado. No se obtienen tan buenos resultados en las restricciones deconocimiento y rol sobre todo en problemas alta y medianamente restringidos. Respecto a la cargade trabajo la peor desviación estándar que se obtiene es de 5.8 requerimientos.

Tabla 4.14: Problemas de 40 requerimientos RS.

aptitudintentosconocimientorolconflictoscarga de trabajo

Pobrementerestringido

15.84150105.986.62

03.24

Medianamenterestringido

45.121667019.819.470.225.63

Altamenterestringido

43.471682820.5716.041.035.83

Para los dos algoritmos es posible concluir que se encuentran mucho mejores respuestas enproblemas pobremente restringidos sin importar su tamaño. También se obtienen muy buenasrespuestas con respecto a la restricción de no asignar a un ingeniero a dos proyectos que se traslapenen el tiempo. Por último se puede decir que los tipos de restricciones que más se violaron fueron

45

las de rol y conocimiento.

4.3.3 Análisis CompartativoEn la tabla 4.15 se resume el comportamiento de los algoritmos para resolver este conjunto

de problemas. Se reporta la mejora en cada uno de los aspectos del algoritmo de RS sobre el AG,dónde 1.0 es que los algoritmos se comportan igual en el promedio, un número mayor que 1.0 indicaque RS supera en cantidad a la variable que se mide y un número menor a 1.0 indica que la variablemedida en RS es inferior en cantidad a la misma variable en AG. Se recuerda que como el objetivode este problema minimizar, un número pequeño en la aptitud y en las restricciones individualeses mejor que uno mayor.

Tabla 4.15: Problemas de 10 requerimientos (incremento de RS con respecto a AG).

AptitudIntentosConocimientosRolesConflictosCarga de trabajo

Pobrementerestringido

1.01.011.00.81.01.0

Medianamenterestringido

1.01.040.991.050.970.98

Altamenterestringido

1.01.021.011.020.970.97

Como puede verse en la tabla, en todos los casos los dos algoritmos obtienen aproximadamentelas mismas respuestas, todos los aspectos son aproximadamente iguales a 1.0, o por lo menossoluciones de similar aptitud. Respecto a las restricciones por separado en RS se obtienen mejoresrespuestas con respecto a los conflictos entre proyectos, véase el 0.97 para problemas mediana yaltamente restringidos, pero esto se compensa con el resto de los requerimientos. En general eneste tamaño de problema ambos algoritmos encuentran alguno de los óptimos globales, lo que pudoser comprobado por la facilidad de solucionar este problema de manera manual. Lo restringido delos problema no afecta en que los algoritmos encuentren el óptimo, por lo menos en este tamañode problema.

El segundo grupo de problemas es del doble del tamaño del anterior con 20 requerimientos,16 ingenieros, 6 conocimientos y 6 roles. Se resuelven otra vez 30 problemas variando el númerode restricciones entre ellos. La probabilidad de mutación usada para problemas de veinte requeri-mientos fue de 0.0125. En la tabla 4.16 se reportan los resultados de la misma manera en que sereportó el primer grupo de problemas.

En este grupo de problemas se nota una ligera superioridad de RS con respecto al AG, enla aptitud, se obtienen valores de 0.97, 0.93 y 0.92 para problmas pobre, mediana y altamenterestringidos, respectivamente. Es importante hacer notar que el AG resultó ser muy sensible a laprobabilidad de mutación y en general resultó difícil de sintonizar. Se encontró que la probabilidadde mutación (Pm) con la que el AG se comporta mejor debe ser aproximadamente igual al inverso

46

Tabla 4.16: Problemas de 20 requerimientos (incremento de RS con respecto a AG).

AptitudIntentosConocimientosRolesConflictosCarga de trabajo

Pobrementerestringido

0.971.071.021.020.960.85

Medianamenterestringido

0.931.110.980.900.960.93

Altamenterestringido

0.921.100.930.950.350.94

de la longitud del cromosoma. En este caso sería:1

m (R*E)dónde R es el número de requerimientos, y E el número de bits necesarios para representar elnúmero de ingenieros. Se cree que pudiera conseguirse un mejor rendimiento del AG quizás conreinicialización o una mejor sintonización.

Los resultados del conjunto de 30 problemas de 40 requerimientos con 32 ingenieros, 6 reque-rimientos y seis roles, se presentan en la tabla 4.17.

Nota: La probabilida de mutación en problemas de 40 requerimientos es de 0.00416.

Tabla 4.17: Problemas de 40 requerimientos (incremento de RS con respecto a AG).

AptitudIntentosConocimientosRolesConflictosCarga de trabajo

Pobrementerestringido

0.771.250.780.781.0

0.76

Medianamenterestringido

0.741.390.730.760.320.90

Altamenterestringido

0.721.400.740.710.270.96

En este últmo conjunto de problemas se repite la tendencia del conjunto de problemas anterior.RS se comporta un poco mejor que el AG, ahora con mejores valores en la aptitud que en elexperimento pasado, véase el 0.77, 0.74 y 0.72 en la tabla 4.17. Se puede ver que el AG hacemenos intentos de la función objetivo, se trató de que corriera más tiempo para conseguir mejoresrespuestas, pero este objetivo no se cumplió.

Al granear el comportamiento de los algoritmos (ver figura 4.1). número de evaluacionescontra mejor encontrado, el algoritmo genético encuentra mejores respuestas desde el inicio y elalgoritmo de recocido simulado se tarda un poco más en llegar a la zona de mejores soluciones. Semuestra como ejemplo el promedio de 10 ejecuciones para resolver un problema de 20 ingenieros,como los descritos anteriormente.

47

Figura 4.1: Gráfica de intentos contra mejor encontrado para AG y R.S, 20 requerimientos.

Gomo se puede ver, a través de los experimentos realizados, las calidad de las soluciones enambos algoritmos es similar, también lo es su evaluación restricción por restricción. Las respuestasofrecidas en el algoritmo de recocido simulado son ligeramente mejores sobre todo en los problemasmás grandes.

Se notó que el algoritmo genético, para estos problemas es muy sensible a la mutación, losvalores para la probabilidad de mutación con los que se encontraron mejores respuestas fueronaproximadamente iguales a 1/longitud del cromosoma.

Se reali/aron más experimentos aumentando el número de requerimientos e ingenieros parasaber cómo se comportan los algoritmos al aumentar el tamaño del problema. En la tabla 4.18 semuestran los tiempos de solución para los distintos tamaños de problema probados.

Tabla 4.18: Tiempo de Solución, en minutos, al variar el tamaño del problema

Requerimientos10204070140280550

Ingenieros8163264128256512

Recocido Simulado0.00730.01380.02830.12180.49435.8403

40,4901

Algoritmo Genético0.01650.03660.08510.21330.544614.340145.4416

Los algoritmos en general encuentran respuestas rápidamente, menos de un minuto, hasta un

48

tamaño de 140 ingenieros, después empiezan a tardar mucho más en encontrar repuestas. Quizásen este caso no sea tan importante que el algoritmo se tarde unos minutos en encontrar respuestaspero, seguramente, el gerente de proyectos no querrá esperar más de una hora a que el algoritmole proponga una solución, sobre todo si quiere experimentar varinando los pesos para encontraruna solución, así que, para efectos prácticos los algoritmos pueden resolver problemas de hasta 280ingenieros.

Respecto a la calidad de la solución en general la tendencia se mantiene, RS obtiene respuestasun poco mejores que el AG y esta mejora se va acentuando conforme el problema se hace más grande.

4.4 Variando la Preferencia de las Restricciones

Las soluciones que devuelven los algoritmos y que se expusieron en la sección anterior sonbuenas soluciones con respecto a la función de aptitud, pero, tal vez el gerente de proyectos noconsidere una buena idea dejar de satisfacer los requerimientos del rol o roles que sus ingenierosdeben jugar o que sus ingenieros no conozcan la tecnolgía que el cliente les requiera sin importarlos conflictos entre proyectos que se pudieran generar, por ejemplo. Se proponen en esta secciónproblemas en los que se trata de satisfacer a una o dos restricciones para verificar si es posibleofrecer soluciones más flexibles al gerente de proyectos.

Los experimentos que se realizan consisten en variar el énfasis en las restricciones a travésde los pesos de la función objetivo para favorecer estos dos requerimientos(conocimientos y roles),utilizando el algoritmo de recocido simulado y después el algoritmo genético. Se espera que lasolución que el algoritmo arroje vaya acorde con la o las restricciones que más nos interesa favorecer.

Cada problema es resuelto 3 veces; la primera vez se resuelve utilizando los mismos pesospara cada una de las restricciones, la segunda vez se favorece a la minimización del número deconocimiento que se requieren y por último se favorece tanto a reducir el número de roles como deconocimientos que no se cumplen.

Se considera que una restricción se favorece si el peso de ésta es 10 veces mayor que el pesodel resto. La selección de los pesos se hizo con criterios puramente experimentales.

Entonces, para el primer caso, cuando no se favorece a ninguna restricción los pesos son todosiguales a 1.0.

En el segundo caso, cuando se favorece la restricción de que todos los ingenieros asignadostengan el concocimiento requerido, en la función objetivo 4.2, definida en el capítulo anteriortenemos que, w% = 103 = 104 = 1.0 y w\ = 10.0 y por último en el tercer caso cuando se deseafavorecer al cumplimiento de la restricción del conocimiento y tamién a la restricción del rol, lospesos que se usan son 103 = 1̂ 4 = 1.0. toi = uty = 10.0.

f ( x ) = lüj • R[l] + MÍ • -R[2] +103 • ñ[3] + u/4 • /Z[4] (4-2)

Entonces, cada problema se resuelve tres veces, variando cada vez los pesos de la funciónobjetivo. Como en el apartado anterior cada vez que se resuelve un problema se hace diez veces yse obtiene el promedio de éstas. En este conjunto de problemas se realizan 30 problemas chicos,30 medianos y 30 grandes. De cada conjunto de 30 problemas, 10 son altamente restringidos, 10medianamente restringidos y los 10 restantes pobremente restringidos.

49

En este tipo de experimentos se estudiará por separado el comportamiento de cada algoritmocon el fin de no complicar el análisis. Al final se intenta realizar el mismo experimento con problemasun poco más grande para verificar si los resultados son similares.

Para cada grupo de experimentos se presentan tres tablas con los siguientes resultados; laprimer tabla contiene el incremento para cada una de las variables que resultan de la ejecuciónde problemas en dónde se preferencia a las restricción de conocimiento con respecto a la ejecucióncuando no se tiene preferencia por ninguna restricción. La segunda tabla muestra el incrementopara cada variable de las ejecuciones donde se preferencian las restricciones de rol y conocimientocon respecto a las ejecuciones sin ninguna preferencia.

La tercera tabla contiene el porcentaje de incremento de las variables cuando se ejecutanproblemas preferenciando al conocimiento y rol con respecto a las ejecuciones preferenciando sóloa la restricción del conocimiento.

Es importante hacer notar que los valores de aptitud que se muestra no necesariamente sonlos que fueron utilizados al correr el algoritmo, sino que es el valor de la función objetivo cuandotodos los pesos son iguales a uno, es decir es el conteo de las restricciones no cumplidas.

4.4.1 Recocido SimuladoEmpezando con RS se muestran los resultados en un problema de 10 requerimientos, 8 inge-

nieros, 6 roles y 6 requerimientos en la tabla 4.19 se presenta el incremento en las variables deejecutar problemas preferenciando a la restricción de conocimiento con respecto a las ejecucionessin preferencia por ninguna restricción.

Tabla 4.19: Prefencia en conocimiento con respecto ninguna preferencia, 10 requerimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.11.351.3

Conocimiento

1.030.350.6

Rol

1.121.8

2.57

Conflictos

11

3.13

Cargade Trabajo

1.11.991.33

Como se puede ver en todos los tipos de problemas, al preferenciar una restricción se obtienenpeores respuestas con respecto a la aptitud, véase el 1.1 en problemas pobremene restringidos,que implica que la aptitud es 10% más alta, en problemas medianamente restringidos en 35% másalta y en problmas altamente restringidos 30% mayor. Es decir que en todos los casos se obtieneuna pero solución al preferenciar la restricción de conocimiento sobre le resto de las restricciones.Por lo menos para los problemas mediana y altamente restringidos sí se logra disminuir el númerode requerimientos no satisfechos en cuanto a conocimientos del ingeniero se refiere, que es undecremento del 65% para problemas medianamente restringidos y del 94% para problemas altamenterestringidos. Las demás restricciones se ven afectadas negativamente,sobre todo la que tiene quever con el rol.

Ahora, qué pasa cuando preferenciamos también al requerimiento que tiene que ver con queel ingeniero cubra el rol requerido. En la tabla 4.20 se muestran los resultados.

50

Tabla 4.20: Prefencia en conocimiento y rol con respecto a ninguna preferencia, 10 requerimientos(RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.111.131.25

Conocimiento

1.341.040.92

Rol

1.011.171.09

Conflictos

11

4.35

Cargade Trabajo

1.111.181.57

En este conjunto de problemas se puede ver que si bien se empeora la aptitud, en 10% paraproblemas pobremente restringidos, 13% para problemas medinamente restringidos y 25% para losaltamente restringidos, no siempre se logra una mejora ni en la restricción del conocimiento ni enla del rol.

Por último se presenta una comparación, en la tabla 4.21, de las ejecuciones preferenciandoa roles y conocimientos con respecto a las ejecuciones preferenciando sólo conocimientos.

Tabla 4.21: Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 10 reque-rimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

10.830.96

Conocimiento

1.32.961.53

Rol

0.890.650.42

Conflictos

11

1.39

Cargade Trabajo

10.591.17

En este último grupo de experimentos sí se alcanza a ver una mejora del rol con respecto alresto de los requerimientos, véase el 0.89 en problemas pobremente restringidos que implica unamejora del 11%, o del 35% en problemas medianamente restringidos o del 58% en los altamenterestringidos. Pero el número de restricciones de conocimientos no sólo no permanece constante sinoque aumenta, por otro lado la aptitud empeora de manera sustancial.

Ahora presentamos estos mismos resultados pero para un problema de 20 requerimientos, 16ingenieros, 6 requerimientos y 6 roles. Primero se presenta, en la tabla 4.22, el incremento de cadavariable cuando se preferencia al conocimiento con respecto a ejecutar el problema sin ningunapreferencia.

Al resolver problemas de 20 ingenieros, preferenciando a la restricción del conocimiento seobtienen muy buenas respuestas para esa restricción, el número de restricciones no satisfechas sereduce a la mitad, 48% en pobremente restringidos, 55% en medianamente restringidos y paraproblemas altamente restringidos se reduce mucho más 90%. El impacto en la función objetivo noes tan importante. Las restricciones que más se ve afectadas es la que tiene que ver con el rol.

En esta tabla no se reporta el incremento en conflictos en los primeros dos casos porque nose violó ninguna restricción cuando no se hacía preferencia por ninguna restricción. En problemaspobremente restringidos se violó una restricción en promedio que tenía que ver con conflictos entre

51

Tabla 4.22: Prefencia en conocimiento con respecto a pesos iguales, 20 requerimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.141.271.41

Conocimiento

0.520.450.1

Rol

1.431.862.68

Conflictos

10.76

Cargade Trabajo

1.391.381.38

proyectos y en problemas medianamente restringidos se violó un poco menos de una restricción enpromedio.

En la tabla 4.23 se presenta la comparación entre la ejecución de problemas sin preferenciaalguna y preferenciando tanto a los roles como a los conocimientos requeridos.

Tabla 4.23: Prefencia en conocimiento y roles con respecto a ninguna preferencia, 20 requerimientos(RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.111.161.97

Conocimiento

0.861.020.01

Rol

2.121.050.26

Conflictos

49.34

Cargade Trabajo

1.131.512.06

En problemas de 20 ingenieros se obtiene sólo una respuesta aceptable para problemas alta-mente restringidos, porque se logra decrementar tanto el número de restricciones no satisfechas deconocimiento en 99% y de roles en 74%. Claro que se sacrifica la aptitud total, se obtiene un incre-mento del 97%. En este caso la restricción más afectada es la que tiene que ver con el número deconflictos no satisfechos. Para problemas medianamente restringidos no se logra mejorar el númerode restricciones no satisfechas ni de conocimientos ni de roles, ni tampoco se mejora la aptitud.Respecto a los conflictos, en promedio se violaron 2, no se muestra el incremento porque para lasolución sin preferenca por ninguna restricción no hubo restricciones violadas. Para problemaspobremente restringidos se logra mejorar las restricciones que tienen que ver con el conocimientopero se incrementan las restricciones no satisfechas por el rol, la carga de trabajo también aumentay por supuesto la aptitud.

Por último se presenta, en la tabla 4.24, el incremento en las variables cuando el problema seresuelve preferenciando al conocimiento y rol con respecto a preferenciar al conocimiento. Respectoa los conflictos hubo 1 restricción violada en promedio, pero para pesos iguales no hubo restriccionesvioladas.

Otra vez en los problemas altamente restringidos se logra una mejoría tanto para roles comopara conocimientos, 99% en ambos casos. El incremento más considerable es en el número deconflictos entre proyectos, 470%, la aptitud se incrementa en 39%. En problemas medianamenterestringidos sólo se mejora el rol en 44%, pero se incrementa dramáticamente el conocimiento en224% y el número de conflictos entre proyectos también se incrementa de manera importante, 355%.

52

Tabla 4.24: Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 20 reque-rimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

0.97. 0.91

1.39

Conocimiento

1.642.240.1

Rol

0.780.560.1

Conflictos

1.093.554.71

Cargade Trabajo

0.811.091.49

Sin embargo la aptitud se mejora, 9%. Para problemas pobremente restringidos también se mejorala aptitud y se mejora solamente el rol.

En general, para problemas de veinte ingenieros, al preferenciar los conocimientos, obtene-mos respuestas que efectivamente disminuyen el número de conocimientos no satisfechos, con algúnimpacto negativo en alguna o varias de las demás restricciones. Al tratar de preferenciar dos restric-ciones ya no se obtiene el resultado esperado, es decir un mejor valor para estas dos restricciones.

Ahora se presentan, en la tabla 4.25, los mismos resultados pero para problemas de 40ingenieros.

Tabla 4.25: Prefencia en conocimiento con respecto a pesos iguales, 40 requerimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.11.431.26

Conocimiento

0.730.480.09

Rol

1.592.291.68

Conflictos

1.0

4.36

Cargade Trabajo

1.181.471.27

También en estos problemas se observa que se logra obtener una marcada mejoría en la restric-ción del conocimiento especialmente en los problemas altamente restringidos 91% . La restricciónmas afectada fue la del rol 168% y los conflictos entre proyectos, 436%. Respecto a los problemasmedianamente restringidos, cunando no se hace ninguna preferencia, se cumplieron todas las res-tricciones, cuando se preferencia al conocimiento se violaron en promedio 10 restricciones de estetipo.

Tabla 4.26: Prefencia en conocimiento y roles con respecto a ninguna preferencia, 40 requerimientos(RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.11.161.78

Conocimiento

1.070.850.13

Rol

1.131.110.66

Conflictos

1.0

18.06

Cargade Trabajo

1.111.371.83

53

En este caso, sólo para problemas pobremente restringidos , no se logró ninguna mejora nipara conocimientos ni para roles y sin embargo sí se incrementó la aptitud 10%. En los problemasmedianamente restringidos,se logró solamente un decremento con respecto a los conocimientos 15%y un incremento en roles 11%. El número de conflictos entre proyectos fue en promedio de 7 en estetipo de problemas. Por último, los problemas en los que sí se logró un decremento en ambos gruposde restricciones fue en los altamente restringidos que por otro lado obtuvieron la peor aptitud delgrupo de problemas, que fue 178% la aptitud entregada cuando no se hace ninguna preferencia.

Tabla 4.27: Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 40 reque-rimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

0.990.811.4

Conocimiento

1.451.751.3

Rol

0.710.480.39

Conflictos

1.00.74.15

Cargade Trabajo

0.940.931.44

En esta comparación se puede notar que se obtuvo un decremento en el rol en los tres gruposde problmeas, 29%, 42% y 61% para problemas pobre mediana y altamente restringidos respec-tivamente, se presentó, sin embargo, un incremento en el conocimiento 45%,75% y 30% respecti-vamente. La aptitud para problemas pobre y medianamente restringidos incluso se mejoró, 1% y19% respectivamente.

Ahora, se realizaron experimentos con problemas de mayor tamaño para analizar el compor-tamiento del algoritmo, se presenta a continuación un resumen. Se resolvió también un problemade 70 requerimientos 64 ingenieros, 6 roles y 6 conocimientos. En la tabla 4.28 se presentan losresultados de comparar el comportamiento cuando no se hace ninguna preferencia, contra prefe-renciar a conocimientos. Otra vez, se logra mejorar el número de restricciones no satisfechas en

Tabla 4.28: Prefencia en conocimiento con respecto a pesos iguales, 70 requerimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.11.21.11

Conocimiento

0.780.310.1

Rol

1.631.91.5

Conflictos

8.942.47

Cargade Trabajo

1.141.171.11

cuanto a conocimiento, 22%, 69% y 90% para problemas pobre, mediana y altamente restringidos,respectivamente. Se afecta principalemente a la restricción de conflictos entre proyectos. En losproblemas pobremente restringidos de violan O restricciones de conflictos cuando no se hace ningunapreferencia y 0.1 restricciones preferenciando al conocimiento.

Al preferenciar tanto al conocimiento como a los roles sólo se logra una mejora en ambosaspectos pero sólo para problemas mediana y altamente restringidos, 26% y 22% de mejora enconocimiento y roles, respectivamente para problemas medianamente restringidos. Para problemas

54

altamene restringidos se logra una mejora del 11% y del 54% para concimiento y rol respectiva-manet.En el caso de problemas pobremente restringidos se violan 0.1 restriccinoes de conflictos, enpromedio. Todo esto se resume en la tabla 4.29

Tabla 4.29: Prefencia en conocimiento y roles con respecto a ninguna preferencia,70 requerimien?tos(RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.11.271.52

Conocimiento

1.070.740.09

Rol

1.150.680.46

Conflictos

48.6554.29

Cargade Trabajo

1.111.461.66

Al comparar problemas preferenciando el rol y conocimiento contra preferenciar sólo conoci-miento, vemos que en los tres casos se logra una mejora en cuanto a roles pero sólo en problemasaltamente restringidos se logra una mejora en cuanto al conocimiento 6%, en los otros dos casossólo se logra una mejora en el rol pero a cambio de un incremento en el conocimiento en el casode pobremente restringidos es de 35% y 236% para medianamente restringidos. También se incre-menta el número de restricciones violada que tienen que ver con los conflictos entre proyectos paralos problemas mediana y altamente restringidos. Esto puede verse en la tabla 4.30

Tabla 4.30: Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 70 reque-rimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

0.991.061.36

Conocimiento

1.352.360.94

Rol

0.70.350.31

Conflictos

0.81. 5.39

25.49

Cargade Trabajo

0.971.251.49

Por ultimo se presentan resultados para problemas de 140 requerimientos 128 ingenieros, 6roles y 6 conociminentos. Cuando se preferencia al concocimiento, vemos que otra vez se logra unamejora respecto a la restricción de conocimiento en. los tres casos, 26%,80% y 90% para problemaspobre, mediana y altamente restringidos, respectivamente. Se demerita la restricción de conflictosentre proyectos. En el caso de problemas poco restringidos se viola menos de una restricción deconflictos en promedio. Esto se muestra en la tabla 4.31

Al preferenciar tanto al conocimiento como al rol, se logran mejorar ambas restricciones enlos problemas mediana y altamente restringido, la restricción de conflictos entre proyectos se veafectada de manera drástica, véase el 909% en problemas medianamente restringidos y el 194%en problemas altamente restringidos. Para problemas pobremente restringidos sólo se logra unamejora en conocimiento pero no en los roles y se obtienen, en promedio 2 violaciones a conflictoentre proyectos. Esto se muestra en la tabla 4.32.

Al comparar problemas preferenciando rol y conocimientos contra preferenciar sólo conoci-

55

Tabla 4.31: Prefencia en conocimiento con respecto a pesos iguales, 140 requerimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.121.21.22

Conocimiento

0.640.20.1

Rol

1.791.952.15

Conflictos

24.246.82

Cargade Trabajo

1.131.211.21

Tabla 4.32: Prefencia en conocimiento y roles con respecto a ninguna preferencia, 140 requerimien-tos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.071.121.6

Conocimiento

0.970.710.47

Rol

1.040.980.65

Conflictos

90.9784.47

Cargade Trabajo

1.151.41.94

miento, sólo se logra mejorar el rol pero con un incremento en conocimiento, véase el 150%, 281% y382% en problemas pobre, mediana y altamente restringidos, respectivamente. Lo que se muestraen la tabla 4.33

Tabla 4.33: Prefencia en conocimiento y rol con respecto a preferencia por conocimiento, 140requerimientos (RS).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

0.950.931.31

Conocimiento

1.52.813.82

Rol

0.580

0.3

Conflictos

1.570

12.5

Cargade Trabajo

1.011.151.6

En la figura 4.2 se presenta una gráfica del comportamiento del algoritmo de recocido simu-lado al solucionar un problema medianamente restringido de 20 requerimientos, 16 ingenieros, 6requerimientos y 6 roles. Se presenta el promedio de diez corridas para cuando el problema se solu-ciona sin preferencia por restricción alguna, cuando se preferencia a la restricción del conocimientoy cuando se preferencia tanto al conocimiento como al rol. podemos ver el claro detrimento de laaptitud conforme se van variando los pesos.

En general es posible concluir para este conjunto de experimentos que preferenciar un sólorequerimiento normalmente implica un número de restricciones violadas menor que si no se tuvierapreferencia por requerimiento alguno. Al aumentar a dos el número de restricciones preferenciadassolamente se obtienen decrementos en el número de restricciones violadas en algunos casos y casisiempre son con problemas alta o medianamente restringidos.

56

Figura 4.2: Gráfica cíe intentos contra mejor encontrado de RS. problema de 20 requerimientosmedianamente restringido, variando la preferencia de las restricciones.

4.4.2 Algoritmo Genético

Los mismos experimentos realizados con recocido simulado se realizaron con el algoritimogenético. A continuación se presenta un resumen de los experimentos hechos con el algoritmosgenético. En este apartado no se incluyen los resultados de satisfacer dos roles ya que como sevio en el apartado anterior no se obtienen respuestas alentadoras. Sin embargo, los experimentossí fueron realizados y las respuestas fueron muy similares a las obtenidas con el algoritmo derecocido simulado. Se presentan primero los resultados en un problema de 10 requerimientos, 8ingenieros, 6 roles y 6 requerimientos en la tabla 4.34 se presenta el incremento en las variablesde ejecutar problemasprefereneiando a la restricción de conocimiento con respecto a las ejecucionessin preferencia por ninguna restricción.

Tabla 1.34: Incremento de prefencia en conocimiento con respecto a pesos iguales para 10 requeri-mientos (At í ) .

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.011.161.33

Conocimiento

0.070.550.25

Rol

1.091.822.33

Conflictos

15.3311.17

Cargade Trabajo

1.051.101 .43

En todos los casos se logra un decremento en el conocimiento y un incremento importante; enlas restricciones de rol violadas, véase por ejemplo el 233% en problemas altamente restringidos.

57

El incremento en la aptitud global es mínimo. En el caso de problemas poco restringidos cuandono se hace preferencia a ninguna restricción no ocurren ningún conflicto entre proyectos, cuando sehace preferencia por el conocimiento se viola 0.1 restricciones de concimiento en promedio.

Los resultados de los experimentos de problemas de 20 requerimientos, 16 ingenieros, 6 rolesy 6 conocimientos se presentan en la tabla 4.35.

Tabla 4.35: Incremento de prefencia en conocimiento con respecto a pesos iguales para 20 requeri-mientos (AG).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.051.191.19

Conocimiento

0.640.490.4

Rol

1.482.011.75

Conflictos

7.71

Cargade Trabajo

1.091.271.27

En problemas de 20 requerimientos, al preferenciar el requerimiento de conocimiento, se ob-tiene una mejor respuesta en esta restricción, 26%, 41% y 60% para problemas pobre, medianay altamente restringidos, respectivamente. Se obtiene también, un leve decremento en la aptitudglobal, véase el 105%, para problemas pobremente restringidos y 119% para los dos restantes. Paraproblemas pobremente restringidos no se viola ninguna restricción de conflictos, al hacer preferenciapor la restricción de conocimiento se viola, en promedio. 0.08 restricciones de conflicto.

Por último se presentan los experimentos con problemas de 40 ingenieros, 32 ingenieros. 6roles y 6 requerimientos, en la tabla 4.36.

Tabla 4.36: Incremento de prefencia en conocimiento con respecto a pesos iguales para 40 requeri-mientos (AG).

pobremente restringidomedianamente restringidoaltamente restringido

Aptitud

1.041.161.26

Conocimiento

0.640.440.21

Rol

1.351.641.82

Conflictos

2013.415.74

Cargade Trabajo

1.111.241.24

En los problemas de 40 requerimientos se logra una mejoría sólo en problemas medianamenterestringidos, de 54% en la restricción de conocimiento. En los restantes problemas no se logramejorar en ésta restricción.

Utilizando el algoritmo genético para preferenciar el requerimiento de conocimiento se obtie-nen soluciones que violan, menos restricciones de conocimiento, con respecto a las soluciones queentrega el mismo algoritmo sin preferenciar ninguna restricción. Los resultados de preferenciar aconocimientos y roles a la vez no se presentan aquí pero, en general puede decirse que no se obitenenrespuestas que disminuyan en todos los casos el número de restricciones violadas para esos tipos derestricción

En general, para el tipo de problemas que se presentan en los experimentos anteriores, satisfacer

58

a una restricción aumentando su peso con respecto al resto de las restricciones ayuda a disminuir elnúmero de las restricciones que se violan para el tipo de restricción escogida. Al aumentar el númerode restricciones que se pefiere satisfacer el resultado no siempre disminuye las restricciones violadaspara los tipos de restricciones escogido, es decir que sólo se puede preferenciar una restricción a lavez.

4.5 Diferencia con Respecto a Solución Inicial

Las soluciones que ofrece el algoritmo tratan de optimizar los criterios definidos en el tercercapítulo y que tienen que ver con encontrar la mejor asignación de ingenieros a proyectos de talmanera que, en conjunto, los proyectos sean exitosos.

Sin embargo, implementar la solución que ofrezca el algoritmo pudiera ser muy complicadodada la asignación actual, por ejemplo, en un problema de 20 ingenieros, la solución óptima pudieraimplicar cambiar a -digamos 18 ingenieros de un proyecto a otro, lo que pudiera resultar quizásmucho más costoso, en términos de rendimiento de los proyectos que dejar a los ingenieros tal ycomo están.

De lo expuesto anteriormente se ve la necesidad de incluir de alguna manera la asignaciónactual en el modelo. Existe más de una manera de implementar esto en el modelo, una muysencilla es incluyendo la diferencia entre la solución actual y la propuesta por el algoritmo comouna restricción, es decir que se cuenta el número de diferencias (en pares de pequerimiento-ingeniero)de una solución con respecto a la situación actual y se trata de minimizar este número como alresto de las restricciones.

A continuación se presentan los experimentos hechos al implementar esta nueva restricción enel algoritmo de recocido simulado. Se realizan 90 experimentos, cada uno de estos experimentosimplica resolver un problema de asignación de ingenieros a proyectos donde ya existe una solucióninicial, el problema se resuelve dos veces, la primera incluyendo la nueva restricción de similitud,que en realidad se resuelve 10 veces y se obtiene el promedio de estas corridas. La segunda se pre-ferenciando a esta nueva restricción, aunque también se corre diez veces y se obitiene un promedio.

Los noventa experimentos pueden ser clasificados como sigue, 30 experimentos de 10 requeri-mientos, 30 de 20 requerimentos y 30 más de 40 requerimientos. Por cada grupo de 30 experimentosse realizan 10 altamente restringidos, 10 medianamente restringidos y los últimos 10 son pobrementerestringidos.

Se reporta en cada grupo de treinta, los resultados respecto al incremento en aptitud de lassoluciones ofrecidas por el algoritmo con respecto a una solución inicial, en la columna aptitudpesos iguales. En este caso, valores menores a 1.0 implica una mejora del algoritmo con respecto ala solución inicial.

Se presenta también la porción de la solución que es igual a la solución inicial, en la colum-na similitud pesos iguales, dónde un 1.0 implica que son exactamente iguales y un 0.0 que soncompletamente diferentes.

Se reportan los mismos resultados pero ahora cuando se resuelve el problema prefrenciando larestricción de similitud, columnas Aptitud pref. similitud y Similitud pref. similitud.

Experimentalmente se escoge el peso para la restricción de similitud cuando se le da preferenciaa ésta, se escoge un balanceo entre tener una solución aproximada a la inicial y mejorar la aptitud

59

de la solución inicial. El peso encontrado' es 5. Es importante recalcar que la comparación conrespecto a la aptitud no es muy representativa debido a que la solución inicial no es una solución realsino que se genera aleatoriamente, sin embargo sí es importante analizar el par aptitud similitudcon solución inicial como una referencia.

Primero se presentan, en la tabla 4.37, los resultados para problemas de 10 requerimientos, 8ingenieros, 6 roles y 6 conocimientos distintos.

Tabla 4.37: Comparación contra una solución inicial, 10 requerimientos.

altamentemedianamentepobremente

Aptitudpesos iguales

0.550.380.73

Similitudpesos iguales

0.410.150.75

Aptitudpref. similitud

1.051.031.07

Similitudpref. similitud

0.940.910.97

Como puede verse en la tabla, cuando se resuelve el problema incluyendo esta nueva restricciónla aptitud se mejora sustancialmente, 45%, 62% y 27% para problemas alta, mediana y pobrementerestringidos, respectivamente. En el caso de los problemas medianamente restringidos, como sedijo, la aptitud se mejora hasta en un 62% pero comparten tan solo 15% de la solución inicial(ver columna similitud pesos iguales para problemas pobremente restringidos) que es, aproxima-damente, 1.5 requerimientos, en promedio, del total de 10 requirimientos. Si se le da preferenciaa el requerimiento de similitud no se logra mejorar la aptitud pero se logra una solución casi igual(95%) a la inicial. Para los problemas pobremente restringidos se logra una mejora promedio enla aptitud de aproximadamente 27% y la solución es en un 75% similiar a la solución anterior. Eneste caso tampoco se logra mejorar la aptitud pero sí se obtiene una solución muy parecida a lainicial.

Por último para problemas altamente restringidos se encontró que la aptitud se mejora en un75% de la solución inicial y comparte un 41% de la solución incial. Tampoco en este último casose logra mejorar la solución, y la solución ofrecida es muy parecida a la anterior.

Al preferenciar el requerimiento de similitud obtenemos soluciones más parecidas a la inicialpero no siempre es posible mejorar la aptitud.

En la tabla 4.38 se presentan los resultados de los experimentos con la nueva restricción desimilitud para problemas de 20 requerimientos, 16. ingenieros, 6 roles y 6 requerimientos.

Tabla 4.38: Comparación contra una solución inicial, 20 requerimientos.

altamentemedianamente >pobremente

. Aptitudpesos iguales

0.50.430.53

Similitudpesos iguales

0.250.280.63

Aptitudpref. similitud

1.050.931.05

Similitudpref. similitud

0.920.870.96

Para problemas altamente restringidos la aptitud se mejora en un 50% pero la solución sólo

60

se parece en un 25% de los requerimientos a la solución inicial. Al darle preferencia a la similitudde las soluciones se obtiene una solución muy similiar a la inicial pero la aptitud no se mejora.

Para problemas medianamente restringidos se obtiene también una solución mucho mejor a lainicial pero que no es muy parecida a la solución incial, al preferenciar esta restricción sí se lograuna leve mejora en la aptitud (7%) y la solución es muy similar a la inicial, en promedio, 17.4requerimientos, de 20, tienen asignado el mismo ingeniero.

En problemas pobremente restringidos se obtiene una fuerte mejora en la aptitud y la soluciónes parecida a la inicial 12.6 requerimientos de 20 tienen igual asignación. Al preferenciar la similitudentre soluciones no se obtiene una mejora en la aptitud.

Por último se muestra, en la tabla 4.39, el resultado de los experimentos de problemas de 40requerimientos, 36 ingenieros, 6 requerimientos y 6 roles.

Tabla 4.39: Comparación contra una solución inicial, 40 requerimientos.

altamentemedianamentepobremente

Aptitudpesos iguales

0.280.250.49

Similitudpesos iguales

0.140.110.53

Aptitudpref. similitud

0.840.91.04

Similitudpref. similitud

0.80.830.94

En problemas de 40 requerimientos se logra mejorar sustancialmente la aptitud pero con muypoco parecido con la solución inicial cuando se incluye la restricción de similitud, el mejor de loscasos son los problemas pobremente restringidos donde aproximadamente la mitad de la soluciónse parece a la solución inicial. Al preferenciar el requerimiento de similitud con la solución inicialsólo se logra mejorar la aptitud en problemas alta y medianamente restringidos y la solución esmuy parecida a la anterior, entre 32 y 34 requerimientos, de 40, son iguales a la solución inicial.

En la la figura 4.3 se muestra la gráfica que del comportamiento del algoritmo de recocidosimulado al solucionar problemas de 20 requerimientos, medianamente restringidos. Cuando no setoma en cuenta se encuentra mejor solución, la siguiente curva ya tiene incluida la restricción deque la solución se parezca a una solución inicial pero los pesos de todas las restricciones son iguales,por último la curva que tiene una peor aptitud es cuando se le da preferencia a la restricción desimilitud.

Si bien en la mayoría de los experimentos no se logró una mejora substancial con respecto a lasolución inicial cuando se trataba de ofrecer una solución similar a la inicial, este dato no puede serconcluyente ya que depende en gran medida de la solución inicial. Por otro lado, es razonable queel gerente de proyectos pueda sintonizar el peso de la restricción de similitud en cada caso hasta encontrar el balance que mejor convenga a su situación actual.

4.6 Discusión de ResultadosRespecto al desempeño de los algoritmos al resolver este tipo de problemas, se probaron

básciamente tres aspectos, la comparación de desempeño entre recocido simulado y el algoritmo

61

Figura 4.3: Gráfica ció intentos contra mejor encontrado. RS para un problema de 20 requerimientosmedianamente restringido, al incluir la restricción de similitud.

genético, la respuesta do los algoritmos auto la preforencia a una o dos restricciones y por últimoel comportamiento del algoritmo al incluir la restricción de similitud entre una solución inicial.

En la comparación del desempeño de los dos algoritmos, cada algoritmo resuelven un totalde 90 de tres tamaños diferentes y con diferente cantidad de restricciones. Se encuentra que re-cocido simulado encuentra respuestas ligeramente superiores al algoritmo genético. El algoritmogenético resulta ser muy sensible a la probabilidad de mutación; experimentalmente se determinaque el algoritmo genético se comporta mejor con valore aproximadamente iguales a I/longitud delcromosoma.

Al gralicar el comportamiento de ambos algoritmos, número de evaluaciones de la función obje-tivo, contra mejor enconttrado, se determina que el algoritmo genético encuentra mejores respuestasdesde el inicio y recocido simulado tarda un poco más en acercarse a las mejores respuestas.

Eu el apartado de comparación de algoritmos también se hicieron experimentos para encontrarel tamaño de problema que los algoritmos son capaces de resolver, se resolvieron problemas dehasta 550 requerimientos. Se determina que el algoritmo puede resolver un problema si le tomasólo algunos minutos en resolverlo ya que, de otra manera, no sería una herramienta útil para elgerente de proyectos. Así que problemas que sean resueltos por el algoritmos en más de 15 minutosse considera que son problemas que no se pueden resolver.

Los experimentos arrojan que los algoritmos son capaces de resolver problemas de aproxima-damente 250 requerimientos y un número un poco menor de ingenieros. Esta es una respuestaalentadora ya que aunque una consultora muy grande tenga muchos más ingenieros, normalmenteestará dividida en oficinas distribuidas geográficamente y las asignaciones a los diferentes proyectosnormalmente se hace con gente de ra.stz.

62

El siguiente grupo de experimentos consiste en variar los pesos de las restricciones con el finde darle preferencia al cumplimiento de algún tipo de restricción con respecto a los demás tipos.

Se resuelven 150 problemas con el algoritmo de recocido simulado, de diferente tamaño yvariando también la cantidad de restricciones en el problema. Se resuelven primero los problemaspreferenciando a la restricción del conocimiento, en la mayoría de los casos esto redunda en un fuertedecremento de las restricciones de conocimiento no cumplidas y un leve incremento del número totalde restricciones no cumplidas.

Los mismos problemas resuelven pero ahora preferenciando tanto a la restricción de conoci-miento como a la del rol. Los resultados en este caso no siempre se logra un decremento en ambasrestricciones y cuando se logra casi siempre es con problemas alta o medianamente restringidos.

Al usar el algoritmo genético, se resuelve ya sólo para preferenciar una restricción, y en todoslos casos se obtienen respuestas que violan muchas menos restricciones de conocimiento y dónde laaptitud global no se incrementa gravemente.

En general podemos decir que el algoritmo entrega buenas respuestas al preferenciar unarestricción, específicamente la de conocimiento, pero al preferenciar dos requerimientos, la respuestano siempe es la esperada.

Ahora, esto no quiere decire que el algoritmo no deba utilizarse para satisfacer mas de unarestricción. El gerente de proyectos debería sintonizar el algoritmo, variando los pesos, hastaencontrar la solución que a él más le convenga.

Por último se agrega una restricción más en la función de aptitud; la similitud con una solucióninicial, en caso de que la solución ofrecida por el algoritmo sea muy diferente a la actual lo queimplique que al gerente de proyectos no le convenga implementarla. Se realizan experimentos quemuestran cómo se deteriora la aptitud de la solución al tratar de hacerla semejante a una solucióninicial, aquí es también conveniente que el gerente de proyectos elija el peso que deba darle a estanueva restricción, es decir, cuántas restricciones de otros tipos está dispuesto a romper con tal deque la nueva solución se parezca a la anterior.

El algoritmo que se propone es sólo una herramienta capaz de encontrar buenas solucionesdado un conjunto de restricciones y un peso para las mismas, la persona que pudiera utilizar laherramienta deberá ajustar los pesos con tal de obtener una buena respuesta dadas su necesidadesespecíficas.

4.7 ResumenEn este capítulo se hicieron los experimentos necesarios para contestar las preguntas de la

hipótesis, particularmente se compararon los dos algoritmos propuestos en cuanto a la calidad de lasolución y la rapidez con que cada uno ofrece la solución. Por otro lado se probó como respondían losalgoritmos a la preferencia de una o más restricciones sobre el resto de las restricciones. Por últimose incluye una nueva restricción, que la solución propuesta se parezca a una solución preexistente.

63

Capítulo 5

Conclusiones y Trabajo Futuro

En este capítulo se resume tanto el problema como la manera en que se resolvió. Se resaltanlas aportaciones hechas y se resumen también las conclusiones de los experimentos y las posiblesampliaciones y mejoras que pueden hacerse a partir de este trabajo.

5.1 Aportaciones

En el presente trabajo se pretende explorar la posibilidad de resolver de manera automática elproblema de asignación de recursos humanos a proyectos de desarrollo de software. La motiviaciónprincipal es que en la industria de IT normalmente se toman las decisiones de asignación de recursoscon base en el proyecto en el que se busca asignar al ingeniero, pero se pierde de vista el panoramaglobal de las demás asignaciones al resto de los proyectos, esto ocurre sobre todo cuando el tamañode los requerimientos y los ingenieros crece y el gerente de proyectos ya no puede administrareficientemente las asignaciones en los proyectos.

Se describe entonces el problema a detalle, tratando de abarcar las variables más importantesque tienen que ver con la asignación. El problema se ve desde tres puntos de vista diferentes, elingeniero, el cliente y la empresa consultora.

Después se simplifica la realidad en un modelo que básicamente toma las variables más im-portantes para la empresa consultora quién es la que en la realidad realiza la asignación.

La más importante aportación del presente trabajo básicamente consiste en encontrar paracada uno de los requerimientos un ingeniero que cumpla con las especificaciones de el o los roles quedeba cumplir, el o los conocimientos que dea dominar y que no este asignado a otro proyecto queentre en conflicto con el primero. También se requiere que la carga de trabajo entre los ingenieroseste balanceada.

El modelo se implementa de tal manera que siempre se asegure que haya uno y sólo un ingenieroasignado a cada requerimiento. Por último se diseña una función de aptitud que sumariza lasrestricciones descritas; el propósito es sugerir una asignación que encuentre un aptitud mínima, esdecir que trate de minimizar el número de restricciones no satisfechas..

Este es el modelo con el que se realizan la mayor parte de los experimentos, pero al finalse incluye una restricción de similitud. El algoritmo entrega buenas soluciones, que minimizan elnúmero de restricciones no satisfechas pero ¿qué pasa si esa solución es muy diferente a asignaciónreal?, probablemente el gerente de proyectos no estará dispuesto a cambiar a un gran número desus ingenieros, ya que esto puede resultar más costoso que tener una mala asignación. Así que se

64

propone inlcuir en el modelo una nueva restricción que implique ofrecer soluciones al gerente deproyectos parecidas a su solución actual.

Ahora, el modelo propuesto, incluso con la extensión de similitud con la solución real, nocontempla todas las variables del problema, sin embargo en el tercer capítulo se analiza la maneraen que el modelo puede ser extendido. Las restricciones que sí pueden ser incluidas fácilmente: lapreferencia por la importancia del proycecto (tamaño, importancia estratégica y nivel de riesgo),elnivel de experiencia del consultor, sus habilidades, su desarrollo profesional y vacaciones.

Las restricciones que no pueden ser incluidas de manera natural en el modelo son la maximi-zación de la utilidad ya que ésta depende de variables no incluidas en el modelo, la ñdelidad delconsultor a la firma no puede incluirse directamente, pero se considera que parte de la fidelidad delconsultor depende de que sus vacaciones sean respetadas y que su desarrollo profesional sea tomadoen cuenta.

En general es posible decir que el modelo puede crecer fácilmente para incluir las variables quetienen que ver con los intereses del ingeniero, experiencia y habilidades y con la importancia de unproyecto sobre otro. Sin embargo, hay otras restricciones que tienen que ver con la utilidad de losproyectos que no pueden incluir fácilmente en el proyecto pero que sí inciden en la asignación deun proyecto.

Respecto a los algoritmos utilizados, es posible decir que tanto el algoritmo genético como elalgoritmo de recocido simulado son capaces de resolver el problema y obtener buenas soluciones.

También se encontró que es posible modificar el peso de una restricción para obtener menosrestricciones violadas en ese tipo de restricción. Al preferenciar más de una restricción no siemprese obtienen respuestas que reduzan las restricciones violadas de los dos tipos de restricciones.

Se obtuvo un tamaño máximo de problema que los algoritmos pueden resolver. Se consideracomo límite que al algoritmo le tome menos de quince minutos resolver. Esto dado que el gerenede proyectos, para encontrar una solución, seguramente querrá probar el algoritmo más de una vezvariando los pesos de las restricciones por lo que un tiempo mayor a 15 minutos por corrida no seconsidera práctico.

Por último se plantea la necesidad de tratar que la solución ofrecida por el algoritmo seaparecida a una solución incial para que el gerente de proyectos pueda implementarla sin necesidadde mover a todos o la mayoría de los ingenieros.

5.2 Trabajo FuturoEn este trabajo se esboza el problema de asignación de recursos humanos a proyectos de

desarrollo de software pero no se da una conclusión contundente ni al problema que se proponecomo simplificación ni mucho menos al problema general. A continuación se listan algunas de laslíneas por las que se puede seguir trabajando en este problema:

• El presente trabajo es sólo el inicio para implementar una herramienta que sea capaz deayudar al gerente de proyecto a encontrar buenas asignaciones.

• Para poder ser implementada es necesario primero incluir las restricciones que fueron dadaspor alto en el presente trabajo y que se mencionan en el capítulo tres, sería también necesarioprobar qué pasa cuando al aumentar el número de restricciones en la función de aptitud se

65

trata de variar el peso de las mismas, muy probablemente se vuelva más difícil de controlarla respuesta que el algoritmo entrega.

• Existe otro conjunto de restricciones que no sólo no fueron incluidas al modelo sino quetampoco se dijo cómo habría que agregarlas, sería también necesario incluirlas directa oindirectamente en el modelo.

• En el presente trabajo se incluye una restricción que tiene que ver con que la solución separezca a una solución inicial. Quizás esta nueva restricción pudiera implementarse de unamanera más sofisticada, tomando en cuenta, por ejemplo, el avance del proyecto, ya que si elproyecto va muy avanzado costará mucho trabajo que otra persona retome el trabajo.

• Respecto al algoritmo, éste sólo genera respuestas dado un generador de problemas, el si-guiente paso sería utilizarlo en un caso real, para ello sería necesario una intcrfaz que pudieraconvertir el concimiento de la empresa consultora en datos útiles para el algoritmo y de igualmanera reportar la solución de tal manera que sea fácilmente manejable por el gerente deproyectos.

• Pudieran sugerirse nuevos algoritmos para resolver el problema, por ejemplo, pudiera resol-verse como un problema de satisfacción de restricciones.

• Es necesario tomar en cuenta que en la mayoría de las empresas consultoras no se tiene unconocimiento preciso de las características de sus ingenieros ni de los requerimientos que esnecesario satisfacer. Sin embargo existe una tendencia por generar ese concimiento y que ésteeste actualizado y sea preciso.

66

Bibliografía

[1] Busby Robert Burguesa, William. Handbook of Industrial Engineering. John Wiley &Sons,Jnstitue of Industrial Engineers, 1992.

[2] Kalyanmoy Deb. Multi-Objective Optimization using Evolutionar¡ Algorithms. John Wiley &Sons.

[3] Richard Freuder, Eugene & Wallace. Partial constraint satisfaction. Artificial Intelligence,(58):21-70, 1992.

[4] Amnon Meisels Gadi Solotorevsky Michael Elhadad Yossi Cohén Gabriel Trzewik. Ehud Gudes.TRAPS - a time dependent resource allocation language. pages 1-54, 1994.

[5] D.E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. AddisonWesley, Reading, MA, 1989.

[6] John Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press,Ann Arbor, 1975.

[7] Inc. ILOG. Manpower White Paper. ILOG, Inc.

[8] Inc ILOG. ILOG Optimization Suite. ILOG, Inc, www.ilog.com, 1998.

[9] S. Kirkpatrick, C.D Gelatt, and M.P. Vecchi. Optimization by simulated annealing. Science,220(4598):671-680, 1983.

[10] Amnon Meisels. Experiments on networks of employee timetabling problems. pages 1-14.

[11] T. Morton and! D. Pentico. Heuristic Scheduling Systems with Applications to ProductionSystems and Project Management. Wiley-Interscience, 1993.

[12] M. Pinedo. Scheduling: Theory, Algorithms, and Systems. Prentice Hall, 1995.t

[13] David & Mackworth Alan & Goebel Randy Poole. Computational Intelligence a Logical Ap-proach. Oxford University Press, 1998.

[14] Andrea Schaerf. A survey on automated timetabling. pages 1-33.

[15] M. Valenzuela. Mutación y selección. Manuscrito sin publicar, 1999.

68