Source: http://docplayer.es/499399-Pontificia-universidad-catolica-del-peru-facultad-de-ciencias-e-ingenieria.html
Timestamp: 2016-10-25 01:42:09+00:00

Document:
Belén Río Lucero
1 PONTIFICIA UNIVERSIDAD CATÓLICA DEL PERÚ FACULTAD DE CIENCIAS E INGENIERÍA DISEÑO DE UN ALGORITMO METAHEURÍSTICO GRASP PARA LA MEJORÍA DE UN ALGORITMO MININCREASE APLICADO A LA ASIGNACIÓN EFICIENTE DE INCIDENTES EN UNA MESA DE AYUDA Tesis para optar por el Título de Ingeniero Informático, que presenta el bachiller: Julio César Rodríguez Ramos ASESOR: Ing. Rony Cueva Moscoso Lima, Diciembre del 20142 RESUMEN La mesa de ayuda es un área importante en la resolución de incidentes de tecnologías de información en las empresas, tanto dentro (para la misma empresa y sus empleados) como fuera (para los clientes que la empresa ofrece sus servicios y productos). Sin embargo, la planificación de la resolución de incidentes se hace difícil debido a la imprevisibilidad y espontaneidad de éstos. Dichos incidentes afectan de manera diversa a la continuidad de negocio con consecuencias y tiempo de resolución de diversa magnitud. Asimismo, los técnicos en la mesa de ayuda tienen un tiempo de resolución diverso, con experiencia laboral distinta y son un número finito de personas. Dicho problema se le conoce en problemas de asignación de tareas como asignación estocástica en línea. El algoritmo MinIncrease permite la resolución de problemas de asignación estocásticos en línea. Sin embargo, el problema reside en que los técnicos son personas de diversa experiencia que pueden estar divididos en técnicos con mucha o poca experiencia en el ambiente de una mesa de ayuda. No es preciso que al mejor técnico se le asignen incidentes triviales ni que algún técnico no trabaje hasta que aparezca un incidente de su dificultad apropiada. Es por ello que el algoritmo MinIncrease sólo no basta. El siguiente proyecto presenta el diseño de un algoritmo metaheurístico GRASP para la mejoría de un algoritmo MinIncrease. La combinación de estos algoritmos permitirá que los incidentes, a pesar de que su aparición sea imprevista, puedan asignarse a los técnicos de la mesa de ayuda de manera eficiente.3 4 5 Hey si no puedes hacerlo no lo hagas. Pero si puedes hacerlo hazlo. El único que puede ganar contra ti eres tú mismo. Así que pelea. No importa como resulte, continúa y corre! Despega del pasado y enfrenta el presente! Haz algo, haz memorias. Vence el hoy y apunta hacia el futuro. Dream. Dedicado a todos aquellos que ahora mencionaré6 Agradecimientos: A mis padres, Julio César y Maria Esther. Por todo el amor y cariño que me han dado, por todos los sacrificios que han hecho para que llegue a este punto, por todas las lecciones de vida que me han dado. Es por ustedes que esto ha sido posible. Les estoy infinitamente agradecido. Ésta es una victoria para ustedes también. Papá, Mamá, lo hemos logrado! Y seguro que será una de muchas más victorias de nosotros que vendrán en el futuro. No ha habido mejor fortuna que tenerlos a ustedes. A mis hermanos, Christian y Oscar. Por todo el apoyo y buenos momentos que hemos pasado, por las lecciones de juventud, por todos los consejos que me dieron. Gracias a ustedes es que ahora tengo mi propio camino. Los he visto crecer y ellos me han visto a mí. Ahora los dos toman sus propias decisiones, como yo haré ahora que soy un profesional. Gracias totales! A mis tíos, primos y sobrinos. Todo el cariño y buenos ratos de la familia no se olvida nunca. Gracias por estar durante mis 23 años de vida. Y que sean muchos más. A mis amigos: la 37, los Chichos, los del Bunka, los sobrevivientes de Informática, Rath s Edge, Starwing, Scarlet Library, los del Magic, los Bronies, los del ASD, los de Touhou en Perú, y muchos otros más. Gracias a todos ustedes es que tuve geniales momentos de ocio, diversas lecciones y puntos de vista en la vida, y me permitieron crecer como persona. Todos ustedes han sido parte importante en mi vida. Espero nos veamos pronto! A mis profesores y asesores: Miss Nérida, Carlos Granthon, Tania Peso, Reynaldo de Amore, Rony Cueva, Manuel Tupia. Gracias a ellos es que pude conocer y escoger mi propio camino a seguir. Muchas gracias por todo lo aprendido. Espero algún día transmitir su experiencia a todo el que tenga a mi cuidado. A mis colegas de Interbank, Wolfram y Equifax. Ustedes me han permitido desarrollarme profesionalmente, y me permitieron seguir con mis estudios a la vez que aprendía en el mundo laboral. Gracias por la oportunidad. A muchos personajes ficticios, en los libros, series, animes y videojuegos. Todos los buenos momentos de ocio y alguna que otra moraleja. Es por todos, todos ustedes que me permiten decir éstas palabras: La victoria hoy es mía. Que ustedes también sean victoriosos en lo que se propongan. Y usted también, lector. -Julio Rodríguez7 Tabla de contenido CAPÍTULO PROBLEMÁTICA 1 2 MARCO TEÓRICO MARCO CONCEPTUAL CONCEPTOS RELACIONADOS AL PROBLEMA CONCEPTOS RELACIONADOS A LA PROPUESTA DE SOLUCIÓN OTROS CONCEPTOS 10 3 ESTADO DEL ARTE FORMAS EXACTAS DE RESOLVER EL PROBLEMA PROGRAMACIÓN LINEAL FORMAS APROXIMADAS DE RESOLVER EL PROBLEMA ALGORITMO MININCREASE PRODUCTOS COMERCIALES PARA RESOLVER EL PROBLEMA CA SERVICE DESK MANAGER SUITE R HEAT SERVICE MANAGEMENT MSM V12 MARVAL SERVICE MANAGEMENT OMNITRACKER ITSM V PROACTIVANET V HP SERVICE MANAGER V COMPARACIÓN DE LOS EJEMPLOS POR PINK ELEPHANT PROBLEMAS RELACIONADOS ASIGNACIÓN DE TAREAS ESTOCÁSTICAS ASIGNACIÓN DE TAREAS EN ESTOCÁSTICAS O EN LÍNEA ASIGNACIÓN DE TAREAS EN MÁQUINAS SIN RELACIÓN FLOW SHOP SCHEDULING CONCLUSIONES SOBRE EL ESTADO DEL ARTE 18 CAPÍTULO OBJETIVO GENERAL 18 2 OBJETIVOS ESPECÍFICOS 19 3 RESULTADOS ESPERADOS 19 4 HERRAMIENTAS, MÉTODOS Y PROCEDIMIENTOS MAPEO HERRAMIENTAS ALGORITMO MININCREASE 208 4.2.2 ALGORITMO GRASP PROGRAMACIÓN ORIENTADA A OBJETOS - JAVA SPSS METODOLOGÍAS PSEUDOCÓDIGO PRUEBA DE HIPÓTESIS PRUEBA DE DISTRIBUCIÓN NORMAL PRUEBA DE VARIANZAS HOMOGÉNEAS PRUEBA DE COMPARACIÓN 22 5 ALCANCE LIMITACIONES RIESGOS 23 6 JUSTIFICACIÓN Y VIABILIDAD JUSTIFICATIVA DEL PROYECTO DE TESIS ANÁLISIS DE VIABILIDAD DEL PROYECTO DE TESIS 24 7 PLAN DE ACTIVIDADES 25 CAPÍTULO ESTRUCTURAS DE DATOS INCIDENTE DEFINICIÓN REPRESENTACIÓN EN PSEUDOCÓDIGO TÉCNICO DEFINICIÓN REPRESENTACIÓN EN PSEUDOCÓDIGO LISTA TÉCNICO LISTA INCIDENTES MATRIZ DE TIEMPOS ESPERADOS MATRIZ DE OCURRENCIAS 34 2 BASE DE DATOS TABLA DE CANTIDAD DE TÉCNICOS TABLA DE OCURRENCIAS DE INCIDENTES TABLA TIEMPOS ESPERADOS TABLA DE INCIDENTES TABLA DE CARGA DE INCIDENTES 36 CAPÍTULO 4 379 1 ADAPTACIÓN DEL ALGORITMO MININCREASE AL PROBLEMA: LISTAMININCREASE CALCULOMININCREASE 38 CAPÍTULO ADAPTACIÓN DEL ALGORITMO GRASP AL PROBLEMA: WSEPT PARA EL REORDENAMIENTO DE INCIDENTES ASIGNADOS. 41 CAPÍTULO CÁLCULO DEL ALFA DEL GRASP ÓPTIMO CÁLCULO DE REPETICIONES ÓPTIMAS PARA GRASP 43 CAPÍTULO EXPERIMENTACIÓN NUMÉRICA INTRODUCCIÓN OBJETIVO DISEÑO EJECUCIÓN PRUEBA DE DISTRIBUCIÓN NORMAL PRUEBA F DE FISHER PRUEBA Z 50 CAPÍTULO FUNCIONAMIENTO BÁSICO DEL PROGRAMA 51 2 REPORTES LOG DE ASIGNACIONES RESUMEN DE DESEMPEÑO 54 CAPÍTULO CONCLUSIONES Y RECOMENDACIONES 5510 1.1 CONCLUSIÓN DEL PROYECTO RECOMENDACIONES TRABAJOS FUTUROS 56 REFERENCIAS BIBLIOGRÁFICAS 5711 CAPÍTULO 1 1 Problemática Según ITIL, un área importante de las empresas que venden o utilizan productos o servicios de Tecnologías de Información (en adelante TI), es el área de mesa de ayuda o help desk, debido a que tiene como objetivo ser un punto de contacto único entre los usuarios y los que proveen el servicio (ITIL Foundation 2014). Es por ello que son responsables de proveer soluciones a los incidentes, problemas o preguntas de TI que ocurran a un usuario relacionado con los productos o servicios de la empresa que estén interrumpiendo la continuidad del negocio. Las vías de comunicación más frecuentes a esta área son llamadas telefónicas o por correo electrónico. Interrupción de la continuidad de negocio (incidente TI) Reporte a mesa de ayuda Resolución y recuperación de la continuidad de negocio Categorización, priorización y diagnóstico del incidente Figura 1.1: Ejemplo de flujo de trabajo de una mesa de ayuda contra incidentes. Los usuarios pueden reportar en su servicio de TI problemas que no les permita laborar de manera normal. Mientras no haya sido resuelto, el incidente puede incurrir en perjuicios laborales de niveles variados dependiendo del impacto negativo del incidente. En casos extremos de un impacto negativo severo, puede afectar los procesos críticos del modelo de negocio, incurriendo en pérdidas de recursos monetarios y de tiempo. The Economist reporta que 60% de las organizaciones empresariales tienen un equipo de respuesta a incidentes y un plan de respuesta. Compañías que estén preparadas con un plan de respuesta a incidentes sienten que están preparados o algo preparados en un 94% comparado contra los que no tienen un plan de respuesta con un 38%. Además, reporta que los incidentes más comunes no fueron deliberadamente maliciosos ni deliberados de fuera de la empresa, sino accidentales por acción de empleados (The Economist 2014: 7-8). Según los resultados del ESET Security Report 112 2013, en América Latina, 3 de cada 4 empresas no tienen claramente definido que realizar en casos de incidentes y solo un 26% cuenta con un plan de respuesta. (Diario TI 2014) Entre los planes de respuesta, se encuentra la delegación de incidentes a un equipo técnico especializado en la resolución de incidentes, conocido como Gestión de Incidentes, quienes cubren los fallos, preguntas o consultas hechas por los usuarios (Tupia 2013: 134). Es por ello que es importante que se deleguen y asignen los incidentes de manera apropiada de manera que el impacto negativo se reduzca y se restablezca la función normal del equipo de TI para la continuación del modelo de negocio. A este problema se le conoce como asignación de tareas o task scheduling, la manera más óptima de asignar tareas a máquinas o personas dado ciertas condiciones, restricciones y objetivos a cumplir. Si bien se intenta de varias maneras que las tareas lleguen a un determinado tiempo y se calcula cuando una máquina demora en procesar esta tarea, en el mundo real el escenario ciertamente diferente. Tómese como ejemplo una fábrica en la cual se procesa materia prima: si bien una correcta logística de compras y producción pueden determinar el arribo de la materia prima y calcular el tiempo con que una máquina o máquinas procesan la materia en un intervalo de tiempo; pueden haber imprevistos como un arribo tardío o dentro de un espacio de tiempo, así como las máquinas pueden sufrir imprevistos que puedan ponerla fuera de uso, tales como averías o desgaste. En nuestro caso de estudio tenemos un set de condiciones dadas tomadas de una empresa. En este trabajo simularemos una mesa de ayuda o help desk en una empresa. Dicha mesa de ayuda está conformado por técnicos de niveles de experiencia diversos los cuales tienen como objetivo recibir y solucionar los problemas relacionados a las Tecnologías de Información o TI que ocurran en la empresa, los cuales pueden ocurrir en cualquier momento. Esta situación tiene como objetivo: Asignar los técnicos con suficiente experiencia para resolver un incidente asignado y resolverlo en el menor tiempo posible. Priorizar los incidentes de mayor urgencia; es decir, que tengan un impacto negativo severo en la continuidad del negocio. Minimizar los tiempos muertos de los técnicos. Todos los técnicos deben de tener en lo posible trabajos asignados. Por otro lado, se debe de tener en cuenta las limitaciones del problema en el caso de una mesa de ayuda, en donde es posible que se tenga en consideración diferentes clasificaciones de la severidad de un incidente. También debe de considerarse que puede haber diferentes rangos entre los técnicos, divididos principalmente por sus desempeños y conocimientos y/o divididos por la estructura organizacional que tenga la empresa. Con esto, podemos decir que los problemas que sean clasificados como alta prioridad, requerirán un técnico altamente capacitado, dejando de lado los que tengan menos experiencia. En el presente trabajo de fin de carrera se realizará la aplicación del algoritmo GRASP al algoritmo MinIncrease para la asignación eficiente de incidentes en una mesa de ayuda. 2 Marco teórico En este apartado veremos conceptos que se relacionan con el problema: 213 2.1 Marco conceptual Conceptos relacionados al problema Complejidad Algorítmica Este proyecto posee una complejidad algorítmica alta. Esto es por todas las combinaciones posibles que posee el problema para otorgar un resultado final. Sin embargo, a pesar de las numerosas combinaciones posibles, solo unas cuantas son resultados ideales. La complejidad algorítmica divide estos problemas en dos grupos: Problemas P o Polinomiales: los cuales su tiempo de procesamiento a la solución crece en proporción a los datos insertados. Estos problemas son considerados sencillos y son capaces de otorgar una solución óptima; es decir, la mejor solución posible. Problemas NP o No Polinomiales: los cuales no poseen una solución óptima por no tener un algoritmo polinomial que los resuelva debido a la cuantiosa demanda de cálculo computacional requerido. Sin embargo, se esfuerza por obtener una solución cercano al óptimo o satisfactorio. Además de esto, se consideran como NP-Complete a los problemas con dificultad mayor a las cuales está comprobado de que no existe solución polinómica posible debido a la gran cantidad de datos de entrada. Los NP-Hard o NP-difícil son problemas en donde la complejidad es tan difícil como un NP-Complete y va más allá. Los problemas de optimización como el que se plantea dar una solución con este proyecto se ubican en NP-Hard por su complejidad (Brassar, Bratley 1996). Figura 1.2: Diagrama de Euler para la ubicación de los problemas P, NP, NP-Completo y NP-Hard. 314 Optimización Combinatoria La optimización combinatoria es un tema que reside en las matemáticas y las ciencias de la computación. Este tema habla acerca de encontrar un objeto óptimo de una serie de objetos finitos, hallando un set de soluciones posibles, y tratando de hallar la mejor solución de todas ellas. El objeto que se busca puede ser un número, una lista de números, un gráfico, etc. La complejidad algorítmica de estos algoritmos es de NP a NP-Hard. El reto es desarrollar algoritmos que sean efectivamente o prácticamente mejores que enumerar todas las soluciones posibles (Lee 2004). La instancia de un problema de optimización es la siguiente (Papadimitriou, Steiglitz 1998: 4): Dado un par (F, c), donde F es el set de puntos factibles; c la función costo, el mapeo: El problema es hallar un donde:, para todo Dicho punto f es llamado la solución óptima global en una determinada instancia o también simplemente llamado la solución óptima. La optimización combinatoria abarca un conjunto de problemas clásicos a los temas de inteligencia artificial, algunos ejemplos son: Problema del vendedor viajero cuyo objetivo es ubicar la ruta más corta posible entre la distancia de las ciudades visitándolos todos una sola vez y regresando a su punto de partida. Problema del ruteo un equipo de vehículos que deben entregar paquetes a cierta cantidad de clientes, ubicando las rutas más óptimas. Problema de asignación se tienen un número determinado de agentes y tareas. Se requiere asignar las tareas a los agentes de manera que el costo total de la asignación se minimize. De estos problemas, se pueden desprender varios usos en temas de optimización para las áreas de producción, informática, transporte, etc. En dichos casos, se busca la mejor combinación para el uso de recursos. En su forma más general se puede plantear de esta manera: Optimizar: Sujeto a: Donde: es la función objetivo y representa un valor que debe de ser optimizado (maximizado o minimizado). Tanto y representan a las restricciones del problema y especifican las condiciones de toda solución viable para el mismo (Tupia 2009: 92) Problema de Asignación Generalizada El Problema de Asignación Generalizada o GAP, es uno de los problemas que se apoyan en la Optimización Combinatoria. El GAP consiste en tener un número de 415 agentes (que pueden ser objetos o personas) y un número de tareas. Cada recurso puede ser asignado a una tarea, incurriendo en un costo y ganancia que puede variar dependiendo de la combinación recurso-tarea. Asimismo, cada agentes limitado por una capacidad por ejemplo, un presupuesto- y no puede tomar una tarea que exceda la totalidad de sus recursos. El objetivo es encontrar la lista de asignaciones de "n" trabajos a "m" agentes con el mínimo costo posible, tal que cada trabajo es asignado a un único agente sujeto a sus restricciones de capacidad (Dress, Yinfeng, Binhai 2007). Para este caso de estudio, este problema puede aplicarse al contexto: Los recursos serán el personal que se encuentra en el centro de servicio. La capacidad del personal es la experiencia que tiene dicha persona en algún tema. Las tareas serán los incidentes a resolver que requieren de cierta experiencia para ser resueltas. El coste de la tarea será el tiempo que demora en terminar dicha tarea respecto a la dificultad de dicho problema dependiendo que técnico lo resuelva. Las soluciones algorítmicas para este problema pueden ser exactas o heurísticas. Los algoritmos exactos o exhaustivos permiten dar la respuesta óptima al problema. El problema de las soluciones exactas radica en el costo computacional alto para resolver dicho problema de manera exacta por su búsqueda exhaustiva. Los métodos heurísticos solucionan dicho problema a costo de la solución exacta, pero dando una solución razonable a un costo razonable Asignación de Tareas La asignación de tareas o Scheduling consiste en obtener un plan de ejecución en la cual se asignan tareas a máquinas, con el objetivo de que dicho plan cumpla un objetivo de la manera más efectiva posible. Este objetivo puede ser: cumplir las tareas en el menor tiempo posible, realizar los trabajos más importantes en un intervalo de tiempo, minimizar tardanzas, etc. (Pinedo 2010, 1). Las máquinas pueden representar distintas cosas: máquinas de taller, pistas de aterrizaje en un aeropuerto, personal de construcción, etc. Las tareas pueden tener tiempo de aparición y un tiempo de entrega. Generalmente un problema de asignación de tareas se suele representar por medio de los tres campos de Graham: α β γ En donde: α representa el entorno de las máquinas que se va a trabajar: una máquina, máquinas idénticas en paralelo, máquinas distintas, Flow Shop, etc. β representa las características y restricciones en el problema: tiempos de lanzamiento, pre procesamiento, restricción de elecciones, tiempos de mantenimiento, etc. γ representa el objetivo a alcanzar: minimización del tiempo de finalización del problema (makespan), tardanzas máximas, tiempo total de cumplimiento con peso, etc. 516 Los modelos de planificación suelen ser de dos tipos: Modelos de Planificación Determinísticos: Estos modelos asumen que se tienen un finito número de trabajos que tienen que ser asignados teniendo en cuenta uno o más objetivos a minimizar. En los trabajos, se tiene conocimiento de los tiempos de procesamiento, de los tiempos de arribo y los tiempos de entrega antes del procesamiento. Modelos de Planificación Estocásticos: Similar a la planificación anterior, con la diferencia que es posible que no se tenga conocimiento de los tiempos de procesamiento; es decir, tiene un tiempo de procesamiento variable. Dicho conocimiento del tiempo exacto se tendrá después del procesamiento. Además, puede tener otras dos clasificaciones: Modelos Fuera de Línea: Estas planificaciones contienen todas las tareas a presentarse desde el día cero, o bien se pueden presentar en diferentes días (en un tiempo llamado release date o fecha de lanzamiento), pero se sabe cuándo y cuántas tareas van a llegar, así como datos de peso o prioridad. Modelos en Línea: Estas planificaciones tienen como característica el desconocimiento de la llegada de las tareas y la cantidad de ellas. No se va a saber nada de los datos de la tarea hasta que aparezcan y sean registrados al problema. En el presente proyecto se considerará un modelo de planificación estocástico en línea, puesto que en el escenario escogido de simulación no se tiene conocimiento de cuando aparecerá un incidente a la mesa de ayuda, ni cuando un técnico terminará de solucionar dicho problema Asignación de Tareas: Notación Estocástica La notación para las tareas estocásticas es la siguiente: P ij = el tiempo de procesamiento aleatorio de la tarea j a la máquina i. E[P ij ] = el tiempo esperado de procesamiento de la variable P ij R j = el tiempo aleatorio de aparición de la tarea j. w j = el peso (importancia) de la tarea j Asignación de Tareas: Máquinas en Paralelo sin Relación El α de este problema será Máquinas en Paralelo sin Relaciones o Rm. Este entorno tiene como característica que hay m máquinas con diferentes velocidades de procesamiento. La velocidad de la máquina i para procesar la tarea j se denota por v ij. El tiempo de procesamiento de la tarea j, p ij, es igual a p j /v ij. (Pinedo 2010: 14) Esto se puede simplificar si se tiene que las velocidades de las máquinas no dependen de las tareas (v ij = v i ), llamado Máquinas en Paralelo con Diferentes Velocidades; y aún más si las velocidades de las máquinas son idénticas (v i = 1 y p ij = p j para todo j), pasando a que sea un problema de Máquinas en Paralelo. Para este problema se está considerando Máquinas en Paralelo sin Relaciones, debido a que tendremos trabajos con tiempos variables de procesamiento; y tenemos técnicos que, debido a su experiencia o falta de ella, pueden procesar la tarea más rápida o lenta respectivamente Asignación de Tareas: Restricción en Elección de Máquinas 617 El β de este problema será Restricción en Elección de Máquinas o M j. Esta restricción se encuentra en problemas de Máquinas en Paralelo. Cuando está presente, no todas las m máquinas pueden procesar una tarea j. M j denota el set de máquinas que puede procesar dicha tarea (Pinedo 2010: 17). Esto va a estar presente en nuestro problema de la manera que ciertos incidentes no se le van a asignar a ciertas personas por no tener la suficiente experiencia para resolverlo de una manera rápida (por ejemplo, un técnico junior o practicante no se le van a asignar incidentes de alta urgencia o de alta complejidad) Asignación de Tareas: Tiempo de Cumplimento Total con Pesos El γ de este problema será Tiempo de Cumplimiento Total con Pesos (Σw j C j ). La suma de los tiempos de cumplimiento de las n tareas nos da una indicación del inventario total causado por la asignación. Comúnmente se le conoce como flujo de tiempo con pesos (Pinedo 2010: 19). Esto va para el proyecto en la manera de que el objetivo es la sumatoria de los tiempos de cumplimiento de las tareas con el peso debido a que nos es relevante el peso para la prioridad de las tareas. Es necesario priorizar los trabajos con mayores pesos debido a que tienen un alto nivel de urgencia Conceptos relacionados a la propuesta de solución Tiempo de Procesamiento con Peso Esperado Más Corto Primero - WSEPT Weighted Shortest Expected Processing Time First es un tipo de asignación en situaciones estocásticas. Es una versión estocástica del WSPT o Weighted Shortest Processing Time First que utiliza los tiempos esperados para hacer el cálculo de cuál tarea se asignará primero. Esta asignación es suficiente como política de asignación para máquinas simples. La fórmula de asignación es la siguiente: w j / E[P j ] Esto permite minimizar la suma esperada de los tiempos de cumplimiento con peso, priorizando los trabajos que tengan un peso importante, pero a la vez, considerando el tiempo esperado que se demoran en terminar (Pinedo 2010: 268) Algoritmo MinIncrease El algoritmo MinIncrease es un algoritmo propuesto por Nicole Megow, Marc Uetz y Tjark Vredeveld. Este algoritmo es una política de asignación estocástica y en línea que minimiza el valor esperado del tiempo de cumplimiento con pesos. Este algoritmo se presenta en la siguiente fórmula: Se tiene una tarea j y máquinas i. Se escoge a la máquina i que nos dé el menor valor de la siguiente fórmula: Figura 1.3: Fórmula del Algoritmo Minincrease 718 w j y E[P j ] se refieren al peso y al tiempo esperado de la tarea j respectivamente. H(j) se refiere a un set de tareas que tengan una prioridad mayor o igual a la tarea j. Asimismo, se refiere a L(j) como las tareas que tengan una prioridad menor a j. Esta prioridad se calcula por medio de WSEPT señalado anteriormente. Aquí, se está tomando dos sumatorias: Sumatoria de los tiempos esperados de las tareas ya asignadas a la máquina i que cumplan con el requisito de pertenecer a H(j). Sumatoria de los pesos de las tareas ya asignadas a la máquina i que cumplan con el requisito de pertenecer a L(j). Megow, Uetz y Vredeveld prueban que su algoritmo es una ρ-aproximación (el resultado se aproxima al óptimo), por lo tanto se espera que su desempeño esté garantizado (Megow, Uetz, Vredeveld 2006) Algoritmos Metaheurísticos Los algoritmos metaheurísticos son métodos de solución que guían a un proceso de búsqueda heurístico, el cual su meta es explorar el espacio de búsqueda de manera eficiente para encontrar soluciones óptimas. Usualmente estos algoritmos son aproximados y no determinísticos, y pueden aplicarse a una gama de problemas. Existen diversos algoritmos metaheurísticos que se pueden clasificar de diversas maneras (Blum, Roli 2003: 272). Por ser o no inspirados en la naturaleza. Basado en población o en un solo punto. Objetivo estático o dinámico. Una o varias estructuras de vecindad. Con o sin memoria. Con esto, se permite que un algoritmo heurístico muy general sea optimizado para el contexto del problema, obteniendo un mejor rendimiento Algoritmo GRASP Una de las principales técnicas meta heurísticas es el algoritmo GRASP o Greedy Randomized Adaptative Search Procedure, desarrollada por Thomas Feo y Mauricio Resende en Sus siglas describen lo que el algoritmo realiza: Greedy (Voraz) similar al algoritmo voraz, escoge el mejor candidato más próximo Randomized (Aleatorio) después de tener la lista de candidatos escoge uno de ellos al azar. Adaptative (Adaptativo) por su capacidad de modificarse al contexto del problema Search (Búsqueda) por que realiza una búsqueda dentro de un espacio, realizando la evaluación en los candidatos de ese espacio. 819 Los algoritmos GRASP tienen una ventaja sobre los algoritmos voraces, que en vez de seleccionar solamente el mejor valor de la función objetivo, se amplía o relaja este criterio de tal manera de que en vez de seleccionar un único elemento, se pueda seleccionar un conjunto de elementos candidatos a ser parte del conjunto solución y que cumplen ciertas condiciones, y de estos, se realizará una selección aleatoria de alguno de los elementos. Según Feo y Resende, hay dos fases dentro de cada iteración GRASP: la primera construye inteligentemente una solución inicial vía una función adaptativa aleatoria golosa; la segunda aplica un procedimiento de búsqueda local a la solución construida esperando encontrar una mejora (Feo, Resende 1995: 109). El procedimiento es el siguiente: Se tiene un set de candidatos a ser conjunto solución. Se escoge una lista restringida de candidatos o RCL (Restricted Candidates List), también llamado Paso de Construcción. Se elije un elemento de la RCL. Se inicia un proceso de mejora, que ya sea por medio de repeticiones u optimización, se tiene un resultado mejorado. En caso de que la condición de parada (se llegó al óptimo, o condición de número de iteraciones o tiempo) no esté completa, volver al punto 2. Se muestra la mejor solución. En el paso de construcción, la lista restringida de candidatos es obtenida mediante el mejoramiento del criterio goloso (tomar siempre el próximo mejor), como podemos ver aquí. Sean: El RCL estará definido por: El parámetro se llama parámetro de relajación, y es lo que nos permite construir una lista de soluciones aleatorias. Este parámetro puede modificarse de acuerdo al criterio más adecuado que se requiera. Se observa que: Criterio totalmente goloso. Criterio totalmente aleatorio. Criterio goloso y aleatorio Esto es lo que permite tener un componente adaptativo, puesto que el parámetro puede variar en cada iteración. En el paso de mejora, se toma el resultado entregado en la fase de construcción, y se mejora a través de funciones que permitan mejorar el conjunto solución por medio de un conjunto de vecindad. Este permitirá intercambiar uno a uno los elementos de la solución con aquellos que no pertenecen a la solución. 920 2.1.3 Otros conceptos Gestión de Incidentes Un evento que surge en una infraestructura de TI puede desembocar en un incidente, el cual reduce o interrumpe la calidad del valor del servicio. Los problemas son la causa del incidente, los cuales deben de ser averiguados para la resolución completa. (Tupia 2013: 134) La gestión de incidentes debe de tener una el objetivo de: Restablecer la operación normal del servicio lo más rápido posible ante la ocurrencia de algún incidente. Minimizar el impacto negativo en la operación de negocio y dentro de niveles de calidad y disponibilidad acordados previamente. La gestión de incidentes debe de estar ubicado en un ámbito, que permite registrar directamente los eventos comunicados por los usuarios y por el personal técnico. Los siguientes conceptos deben de ser tomados en cuenta para el manejo de incidentes: Modelo de atención de incidentes: posee pasos predefinidos para escalas de tiempo, listas de actividades, procedimientos de escalamiento y asignación de responsabilidades. Escalas de tiempo: se requiere escalas de tiempo de resolución, notados en los documentos de Acuerdos de Nivel de Servicio (SLA) y Acuerdos de Nivel de Operaciones (OLA). Incidentes graves: que requieren procedimientos particulares por ser de alto impacto negativo a la continuidad del servicio o del negocio. Métricas: para el monitoreo e informe de la eficacia y eficiencia de las acciones correctivas. Las actividades de la gestión de incidentes (según ITIL) son las siguientes: Identificación y Registro de incidentes. Clasificación de los incidentes. Priorización. Diagnóstico (resolución en caso de que sea incidentes menores). Escalado (en caso de que el incidente necesite un nivel superior de asistencia). Investigación (razones del por qué ocurrió el incidente). Resolución y Recuperación. Cierre del Incidente. La tesis no se enfocará a un marco regulatorio de ITIL, ni a cubrir todo el aspecto de la gestión de incidentes, pero sí otorga un en el proceso de asignación en el ámbito de identificación, clasificación y priorización. 1021 3 Estado del arte En este apartado veremos el estado del arte para otorgar la solución del problema de asignación de tareas. 3.1 Formas exactas de resolver el problema Programación Lineal La programación lineal es una técnica de modelado usada en el proceso de toma de decisiones, en donde dado un conjunto de m ecuaciones o inecuaciones lineales, y n número de variables de decisión, se requiere hallar valores no negativos de las variables que satisfagan las restricciones y maximicen o minimicen la función objetivo (Mejía y otros 2012). Gráficamente, se puede representar las restricciones como ecuaciones lineales en un plano. Estas líneas formarán un borde en un polígono en donde se establecerá la región factible que la solución puede tomar, siendo las del más extremo la solución más efectiva posible. La programación lineal es comúnmente utilizada para negocios y economía, pero también puede servir para problemas de ingeniería, como asignaciones. De esta manera, se puede tener una solución exacta al problema de asignación, debido a que puede acoplarse lo que se tiene como incidentes: órdenes de prioridad, objetivos, etc. Sin embargo, la programación lineal tiene limitaciones en cuanto a tiempos de procesamiento y problemas NP, que no poseen representación en polinomios o datos inciertos. Para este caso de estudio, la cantidad de agentes e incidentes, más el factor impredecible de la asignación en línea hace prácticamente imposible resolverlo de manera completamente exacta. 3.2 Formas aproximadas de resolver el problema Algoritmo MinIncrease El algoritmo MinIncrease (Megow, Uetz, Vredeveld 2006) descrito anteriormente responde al problema de asignación de máquinas en paralelo idénticas. Sin embargo, se necesita de consideraciones adicionales en este problema debido a las restricciones de las máquinas (M j ), así como buscar de que todos estén debidamente ocupados. 3.3 Productos comerciales para resolver el problema Se ofrecen una variedad de productos para apoyar en el problema de asignación de tareas en una mesa de ayuda. Estos productos se encargan de apoyar a la gestión de servicios en tecnologías de información o ITSM. Esta lista certificada por ITIL según la página Pink Elephant (Pink Elephant 2014): CA Service Desk Manager Suite r12.9 CA Service Desk Manager Suite es una plataforma de soporte a la mesa de ayuda creada por CA Technologies en donde permite, tanto en versión desktop como móvil, automatización extensiva, Software as a Service, análisis y gráficas con el objetivo 1122 de reducir riesgos y costos; e incrementar la productividad del equipo en la mesa de ayuda. (CA Technologies 2014). Figura Pantalla del programa CA Service Desk Manager Suite HEAT Service Management 2014 HEAT Service Management, creado por FrontRange Solutions USA Inc., es una solución robusta y flexible para la gestión de servicios. Tiene facilidades para requerir, planear, aprobar, cambiar, auditar y controlar los cambios necesarios al servicio. Permite elaborar flujos de trabajo de complejidades variadas (FrontRange Solutions 2014). 1223 Figura 1.5 Pantalla del sistema HEAT Service Management MSM v12 Marval Service Management MSM, desarrollado por Marval Software Ltd. provee soluciones para mesas de ayuda. Es compatible con los marcos ITIL e ISO/IEC Ofrece mejorías de costoeficiencia, acceso rápido a ítems de conocimiento, notificaciones y gráficas en tiempo real (Marval Software 2014). Figura 1.6: Pantalla del sistema Marval Service Management 1324 3.3.4 OMNITRACKER ITSM v5 OMNITRACKER ITSM v5 es un sistema que ofrece soluciones de servicios modelado a ITIL con plantillas de proceso respectivos, incluido la de gestión de incidentes; así como una rápida implementación y escalabilidad garantizada (OMNINET 2014). Figura 1.7 Pantalla del sistema OMNITRACKER ITSM v ProactivaNET v8 ProactivaNET es un sistema de ITSM construido en España. El software incluye los procesos modelados de ITIL de gestión de problemas e incidentes, gestión de problemas y gestión de cambios y entregas. Incluye vista por móvil. Puede integrarse con otros productos de Proactiva NET (Espacio Tecnológico Molinon 2014). 1425 Figura 1.8 Pantalla del sistema ProactivaNET v HP Service Manager v9.30 HP Service Management es el software desarrollado por Hewlett-Packard Development Company. Ofrece varios módulos de servicio para TI, entre ellos un apoyo automatizado para las mesas de ayuda. Puede dar seguimiento a incidentes de TI, apoyo en auto-servicios de TI y otorgar manejo de incidentes y problemas (Hewlett- Packard Development Company 2014). 1526 Figura 1.9 Pantalla del sistema HP Service Manager v Comparación de los ejemplos por Pink Elephant Glosario: Nivel de cumplimiento: o Bronce: demuestra el cumplimiento con el modelo de ITIL con funcionalidad, automatización y documentación. o Plata: Lo mencionado en el nivel bronce y ha sido aplicado siguiendo ITIL en al menos tres clientes. o Oro: Lo mencionado en el nivel plata, y ha presentado evidencia de su funcionamiento por medio de reportes y capturas de pantalla. Procesos: o AVM Gestión de disponibilidad. o CAP Gestión de capacidad. o CHG Gestión de cambios. o EV Gestión de eventos. o FM Gestión de finanzas. o IM Gestión de incidentes. o ITSCM Gestión en la continuidad de servicio de TI. o KM Gestión del conocimiento. o PM Gestión de problemas. o REL Gestión de lanzamiento y aplicación. o RF Cumplimiento de pedidos. o SACM Gestión de activos de servicio y configuración. o SCM Gestión del catálogo de servicios. o SLM Gestión de nivel de servicio. o SPM Gestión de portafolio de servicios. 1627 Sistema Nivel de Cumplimiento Procesos CA Service Desk Bronce AVM, CAP, CHG, EV, FM, Manager Suite r12.9 IM, ITSCM, KM, PM, REL, RF, SACM, SCM, SLM, HEAT Service Management 2014 Bronce SPM CHG, IM, KM, PM, REL, RF, SACM, SCM, SLM, SPM MSM v12 Plata AVM, CAP, CHG, EV, FM, ITSCM, KM, PM, REL, SACM, SPM OMNITRACKER ITSM v5 Plata CHG, EV, IM, KM, PM, RF, SACM, SCM, SLM ProactivaNET v8 Oro CHG, IM, KM, PM, REL, RF, SACM, SCM, SLM, SPM HP Service Manager v9.30 Oro CHG, IM, KM, PM, REL, RF, SACM, SCM, SLM, SPM Figura 1.10 Tabla de comparación de los ejemplos anteriores 3.4 Problemas relacionados Asignación de Tareas Estocásticas Schulz propone algoritmos provee soluciones algorítmicas para asignación estocástica (Schulz 2005). Uetz escribe sobre algoritmos tanto para asignación determinística y estocástica (Uetz 2002) Asignación de Tareas en Estocásticas o en Línea Afrati y otros utilizan esquemas para la solución de minimizar el tiempo de cumplimiento con pesos con tiempos de lanzamiento (Aftati y otros 1999). Anderson y Potts utiliza asignación de tareas para minimizar el tiempo de cumplimientos con pesos en una sola máquina (Anderson y Potts 2004). También lo hacen Fiat y Woeginger para minimizar el objetivo mencionado anteriormente (Fiat y Woeginger 1999). Heydenrich, Muller y Uetz se inspiran en MinIncrease para hacer un mecanismo genérico y descentralizado con una visión miope para otorgar solución a tareas en línea (Heydenrich, Muller y Uetz 2006) Asignación de Tareas en Máquinas sin Relación Schulz y Skutella tienen publicaciones sobre asignación de tareas en máquinas sin relación (Schulz y Skutella 2005) Flow Shop Scheduling 1728 Flow Shop Scheduling contiene un problema en la variante de asignación de tareas en donde hay m máquinas en serie y cada tarea debe de pasar por cada una de estas m máquinas. Se puede generalizar haciendo que haya varias máquinas en cada etapa (Pinedo 2010: 15). Es un tipo de problema diferente a esta situación de la mesa de ayuda, sin embargo puede ser que una mesa de ayuda esté envuelta en varios procedimientos de la gestión de incidentes como análisis del problema, equipos de técnicos para procedimientos de problemas urgentes, etc. Ramirez provee una solución al problema de Flow Shop Scheduling utilizando GRASP con doble relajación; es decir, utilizando dos alfas de relajación para la elección de máquinas y tareas (Ramirez 2006). Bard y Rios proveen un GRASP para la minimización del makespan en un Flow Shop de m máquinas (Bard y Rios 2000). Tupia utiliza GRASP contra un caso de máquinas diferentes y tareas independientes (Tupia, 2004). 3.5 Conclusiones sobre el estado del arte Evaluando los productos comerciales presentados anteriormente, se puede ver que resultan útiles para el seguimiento de errores y su módulo de gestión de incidentes tiene automatizaciones. Se tendría que ver una comparación y simulación de cómo es el algoritmo de asignación contra el propuesto en esta tesis. Algunos servicios utilizan Round Robin como método de asignación. Sin embargo, esta asignación es para máquinas en paralelo (Pinedo 2010: 342) y no para una situación en donde las máquinas varían. Y como se ha optado, Megow, Uetz y Vredeveld optan por crear el algoritmo MinIncrease como una opción para las asignaciones estocásticas y en línea. Según lo leído en las investigaciones, se obtienen soluciones para varias variantes de la asignación de tareas. Las respuestas ciertamente se complican si se pasa a un entorno estocástico y si se pasa a un entorno en línea. El problema radica en la asignación en diferentes velocidades y con restricciones de elección de máquina; es decir, en la notación de Graham Problema-Condiciones- Objetivo sería Rm M j, R j Σw j *C j lo cual no es considerado en el algoritmo que se está basando esta tesis. Para resolverlo, se necesitaría que se consideren las máquinas que puedan resolver las tareas asignadas, así como facilitar la distribución de tareas de manera de que los mejores sean los únicos con tareas para resolver, así como asignar tareas de peso (urgentes) que sean resueltos lo más rápido posible. Es por ello de que a dicho algoritmo se le asignará una metaheurística que permita la elección aleatoria de una lista restringida de candidatos a resolver el problema, a fin de distribuir las tareas de manera distribuida. 1 Objetivo general CAPÍTULO 2 Aplicar el algoritmo GRASP al algoritmo MinIncrease GRASP para obtener una solución eficiente al problema de asignación de incidentes a una mesa de ayuda. 1829 2 Objetivos específicos 1. Definir el algoritmo a usar que permita una asignación de tareas a máquinas en paralelo en un entorno estocástico y en línea. 2. Definir la función de mérito para la evaluación de técnicos e incidentes, utilizado para determinar la asignación entre una lista de candidatos para asignar la tarea a una máquina. 3. Definir los grados de relajación (constantes α) a utilizar en el algoritmo GRASP tanto para el ordenamiento de técnicos como el ordenamiento de incidentes. 4. Implementar las estructuras de datos de soporte para el algoritmo, los incidentes y los técnicos. 5. Desarrollar una experimentación numérica para demostrar la mejora con el algoritmo GRASP con respecto a un algoritmo voraz. 6. Construir el programa simulador de la solución. 3 Resultados esperados Resultado esperado para el objetivo 1: El algoritmo escogido para la asignación de los incidentes a técnicos y adaptado para el problema. Resultado esperado para el objetivo 2: La definición de la función de mérito para escoger al técnico a resolver el incidente. Resultado esperado para el objetivo 3: La definición de los grados de relajación a utilizar en el algoritmo GRASP. Resultado esperado para el objetivo 4: La arquitectura mostrando la construcción de las estructuras de soporte. Resultado esperado para el objetivo 5: El documento de experimentación y comparación numérica evidenciando la superioridad del algoritmo GRASP en la asignación de personal versus un algoritmo voraz. Resultado esperado para el objetivo 6: El programa prototipo de asignación de personal con los algoritmos implementados. 4 Herramientas, métodos y procedimientos 4.1 Mapeo Resultados esperados Herramientas a usarse RE1: El algoritmo escogido para la asignación de los Algoritmo MinIncrease: será utilizado para establecer un método de evaluación de una incidentes a técnicos y tarea a las máquinas adaptado para el problema. RE2: La definición de la Algoritmo GRASP: que especifica una 1930 función de mérito para escoger al técnico a resolver el incidente. RE3: La definición de los grados de relajación a utilizar en el algoritmo GRASP. RE4: La arquitectura mostrando la construcción de las estructuras de soporte. RE5: El documento de experimentación y comparación numérica evidenciando la superioridad del algoritmo GRASP en la asignación de personal versus un algoritmo voraz. RE6: El programa prototipo de asignación de personal con los algoritmos implementados. función de mérito necesario para escoger el técnico de una lista restringida de candidatos. Algoritmo GRASP: que utiliza un grado de relajación correcto para hacer la selección lo suficientemente aleatorio. Pseudocódigo: Utilizado para controlar el proceso de desarrollo del código. Programación Orientada a Objetos - Java, el lenguaje será utilizado para la construcción de código fuente de las estructuras. Prueba de Hipótesis: Utilizada para sostener la hipótesis que un algoritmo es más fuerte que el otro. Prueba de distribución normal: Utilizada para evaluar si ambos algoritmos arrojan datos en una distribución normal. Prueba varianzas homogéneas: Utilizada para comparar varianzas si son o no homogéneas. Prueba de comparación: Utilizada para comparar los valores y validar la superioridad de un algoritmo. SPSS: Programa utilizado para el análisis estadístico. Programación Orientada a Objetos - Java, el lenguaje será utilizado para la construcción de código fuente de todo el programa. 4.2 Herramientas Algoritmo MinIncrease Este algoritmo fue propuesto por Megow, Uetz y Vredeveld para la selección de un técnico a una tarea por medio de una evaluación matemática con respecto a los tiempos de procesamiento y el peso de las tareas. Esta herramienta será utilizada para obtener una lista de cifras respecto de una tarea a todas las máquinas posibles, con la cual se obtendrá en orden las máquinas más ideales a asignar Algoritmo GRASP El algoritmo GRASP, plantea un algoritmo voraz, aleatorio, adaptativo y de búsqueda. Se tiene una ventaja sobre los algoritmos voraces comunes, que en vez de seleccionar solamente el mejor valor de la función objetivo, se relaja el criterio de tal manera que se seleccione un conjunto de elementos que cumplen ciertas condiciones. El algoritmo GRASP, tal como se ha explicado en el marco teórico, establecía que la fórmula de establecer la lista restringida de candidatos tiene un parámetro α, el cual interpreta si la búsqueda tiende más a ser aleatoria o ser voraz. El objetivo será ubicar 2031 el parámetro α entre 0 y 1, el cual nos dé el resultado suficientemente aleatorio que necesitemos Programación Orientada a Objetos - Java La programación orientada a objetos es un paradigma de programación que representa conceptos de datos como objetos que tienen procedimientos asociados llamados métodos. Estos objetos pueden ser agrupados en clases distintas. Este paradigma permite un orden modular del código de programación y puede ser fácilmente modelado. Java es un lenguaje de programación orientada a objetos, desarrollado por James Gosing en Sun Microsystems, ahora parte de Oracle Corporation. Java tiene la ventaja de ser portable y compatible independiente del sistema operativo, ayudado por la Java Virtual Machine. El lenguaje es uno de los más populares en existencia. El código fuente del proyecto será desarrollado utilizando este paradigma de programación con este lenguaje SPSS SPSS es un programa especializado para el análisis estadístico creado por IBM Corporation. Su nombre significa Paquete Estadístico para las Ciencias Sociales. Esta herramienta nos servirá para facilitar los cálculos respectivos en la experimentación numérica. 4.3 Metodologías Pseudocódigo El pseudocódigo es un método de descripción de alto nivel de un código fuente para un programa o un algoritmo. Éste puede ser leído y adaptado a varios lenguajes de programación debido a que sigue una estructura similar estándar. El pseudocódigo será utilizado como una manera preliminar para mostrar el flujo del código del algoritmo y las estructuras de datos Prueba de Hipótesis Es el procedimiento para verificar si una propiedad en una población estadística es compatible con la muestra de la población. Se tiene una hipótesis determinada y una hipótesis alternativa; las cuales final del ejercicio se determinará cuál debe de ser rechazada. Se utilizará para verificar los resultados de la experimentación numérica que certifiquen que el algoritmo apoyado es más rápido Prueba de distribución normal 2132 Las pruebas de distribución normal nos permitirán saber si los datos que hemos generado a través de los dos algoritmos son de distribución normal o no. Estas pruebas consistirán en: Prueba de asimetría y curtosis. Prueba de Kolmogorov-Smirnov. Prueba de Shapiro-Wilk. Prueba de histograma y normal esperada Prueba de varianzas homogéneas La prueba de varianzas homogéneas nos permitirá saber si los datos generados tienen una varianza homogénea o no. Para este caso de estudio utilizaremos la prueba F de Fisher Prueba de comparación La prueba Z permite comparar si dos o más medias muestrales pueden haberse obtenido de poblaciones con la misma media paramétrica respecto de una variable dada o son diferentes. Para esto, los datos requieren que sean de distribución normal y de varianza homogénea. La prueba U de Mann-Whitney permite comparar las medias muestrales en caso de que la distribución no sea normal y la varianza no sea homogénea. Un diseño adecuado permitirá que los datos obtenidos cumplan con las premisas paramétricas y permite la aplicación de pruebas estadísticas para la interpretación de resultados. 5 Alcance El objetivo del proyecto es la asignación de tareas estocásticas en línea a máquinas con diferentes velocidades por medio de dos algoritmos. El tema de mesa de ayuda, usando asignación de técnicos a incidentes será el modelo del programa simulador. El programa no proveerá apoyo a la solución de los incidentes en sí. El programa tampoco hará reasignación de tareas o pre-procesamiento ( preemption en asignación de tareas), ni considerará fechas de entrega o release dates cuando las tareas aparezcan, ya que serán asignadas de inmediato para resolverlas a la brevedad posible. La comparación en la experimentación numérica será contra una posición completamente voraz en la asignación (el primero mejor en la lista de MinIncrease). 5.1 Limitaciones El problema de asignación es un problema de tipo NP-Hard, por lo que no habrá una solución exacta o definitiva. Por la aleatoriedad del algoritmo GRASP y de las 2233 circunstancias del problema, es posible que el resultado no sea el óptimo, pero será uno satisfactorio. La optimización es más visible en casos de mesas de ayuda grandes con flujos de incidentes frecuentes y en una cantidad razonable. La optimización no se percibirá en su totalidad para sets de incidentes que sean pocos o mesas de ayuda de muy pocas personas. 5.2 Riesgos Riesgo identificado Error en la fórmula de cuantificación de las tareas y máquinas en el algoritmo MinIncrease. Error de formulación en la función de mérito en el algoritmo GRASP. Error de selección de grados de relajación en el algoritmo GRASP Error en la generación de tareas para la prueba de asignación. El documento de experimentación numérica demuestra que el algoritmo voraz resulta más eficaz que el algoritmo GRASP con doble relajación. Impacto en el proyecto Mediano - Alto: Es posible que perjudique el desarrollo del proyecto si el error se encuentra en un estado avanzado del proyecto. Mediano - Alto: Es posible que perjudique el desarrollo del proyecto si el error se encuentra en un estado avanzado del proyecto. Alto: Es posible que perjudique el desarrollo del proyecto si el error se encuentra en un estado avanzado del proyecto, o conlleve al fracaso del proyecto si sucede en una presentación final. Mediano: Posibles cálculos no suficientes para la demostración del funcionamiento del algoritmo. Severo: Posible fracaso del proyecto. Medidas correctivas para mitigar Se tiene que realizar pruebas de manera que el algoritmo esté correctamente implementado. Se tienen que realizar formulaciones que estén alineados con la teoría de modelos de asignación, así como los del mismo algoritmo GRASP. La investigación y pruebas sobre la selección del grado de relajación deben de ser exhaustiva a fin de mitigar dicho riesgo. Realizar pruebas a fin de que la lista aleatoria de tareas sea la correcta. Realizar pruebas a revisar si la diferencia es debido a errores de grados de relajación o formulación de la función de mérito. 6 Justificación y viabilidad 6.1 Justificativa del proyecto de tesis Uno de los beneficios significativos es la asignación automática efectiva de recursos. De esta manera, se ahorra tiempo en deliberar quién es el más apropiado para 2334 encargarse de la tarea. En el caso del ejemplo, se delibera quién es el técnico más apropiado para resolver el incidente, a la vez de que los más experimentados están libres para ser asignados donde su experiencia sea la más efectiva, así como estar atento a los diversos incidentes y que el tiempo de respuesta sea dentro de los parámetros establecidos en la prioridad y urgencia del incidente. Para los problemas de asignación de tareas, con esta tesis se ofrece una solución al caso de máquinas en paralelo con diferentes velocidades y restricciones de procesamiento, lo cual el algoritmo MinIncrease no consideraba originalmente, apoyándose con un algoritmo que provea aleatoriedad suficiente. En el ejemplo, el beneficio que trae el proyecto es una mejora a las mesas de ayuda o centros de servicio que restablezcan el valor adicional que otorgan los servicios, así como restablecer la continuidad de negocio si es que el incidente es crítico, otorgando una mayor resilencia a la empresa. 6.2 Análisis de viabilidad del proyecto de tesis Viabilidad técnica: El proyecto se construirá a partir del lenguaje de programación Java, orientado a objetos. Esto es por la facilidad de manejo con los documentos de diseño y por el conocimiento que se tiene del lenguaje. El lenguaje se puede descargar libremente de internet, utilizando como interfaz de desarrollo Netbeans, el cual también se puede descargar libremente. La base de datos que se utilizará para el soporte del sistema de información será MySQL. Esta base de datos puede ser descargado gratis, el cual puede instalar una base de datos localmente en la computadora. En caso de que se requiera una base de datos externa, se tendrá que consultar la viabilidad con el área de redes de la universidad, el cual podrá proveer de una base de datos, con su administrador y contraseña. También se necesita estudiar a profundidad el marco y la teoría de asignación y algoritmo GRASP y MinIncrease. La teoría del algoritmo GRASP y MinIncrease debe de ser aprendida a conciencia para la formulación correcta de las funciones de mérito. Para este proyecto se disponen de recursos bibliográficos como: o Biblioteca de la Facultad de Ciencias e Ingeniería de la Pontificia Universidad Católica del Perú. o Biblioteca de tesis en la Facultad de Ciencias e Ingeniería. o Revistas de investigación online, como por ejemplo AICIT-AISS. Además de contar con el apoyo teórico en las bibliografías, se puede contar con el apoyo del asesor de tesis y profesores con conocimiento en ciencias de la computación para asesorías y consulta de problemas. Viabilidad temporal: Para este proyecto, se dispone de 13 semanas para realizar completamente el proyecto de fin de carrera, con entregables semanales. 2435 Se podrían encontrar dificultades de tiempo con laborales profesionales, por lo que el avance estaría supeditado a las horas de la tarde y noche. Para mayor detalle, revisar el diagrama de Gantt adjunto con el apéndice. Viabilidad económica: El proyecto de fin de carrera es sin fines de lucro y el proyecto no necesita de recursos monetarios para su propósito. Análisis de necesidades: Necesidades Conocimiento Tiempo Monetario Humano Comentario A disposición: Biblioteca de Facultad de Ciencias e Ingeniería Asesorías de profesores relevantes a Ciencias de la Computación Acceso en línea a bases de datos de artículos científicos de AICIT o Mathematics of Operations Research. Se realiza un avance cada siete días (revisar diagrama de Gantt). No es necesario en este proyecto, es un proyecto sin fines de lucro ni busca invertir en un producto. No es necesario en este proyecto, es enteramente un proyecto de una sola persona. No se necesita manejo de personal ni establecer políticas de comunicación. 7 Plan de actividades El plan de actividades se encontrará a continuación en un diagrama de Gantt. 2536 37 27 Mostrar más
UNIVERSIDAD CARLOS III DE MADRID ESCUELA POLITÉCNICA SUPERIOR INGENIERÍA TÉCNICA EN INFORMÁTICA DE GESTIÓN PROYECTO FIN DE CARRERA AUDITORÍA PRÁCTICA DE BASES DE DATOS BAJO INFORMIX Autor: Mª Isabel Romero Más detalles DESARROLLO DE UN APLICATIVO PARA MONITOREO DE RED JOHN ENRIQUE GUAYAZÁN ORTÍZ HENRY ALBERTO MACHADO SÁNCHEZ
DESARROLLO DE UN APLICATIVO PARA MONITOREO DE RED JOHN ENRIQUE GUAYAZÁN ORTÍZ HENRY ALBERTO MACHADO SÁNCHEZ UNIVERSIDAD DE SAN BUENAVENTURA FACULTAD DE INGENIERÍA PROGRAMA DE INGENIERÍA ELECTRÓNICA BOGOTÁ Más detalles Universidad Nacional Autónoma de México. Facultad de Ingeniería
Universidad Nacional Autónoma de México Facultad de Ingeniería Fundamentos de un ERP con administración eficiente y optimización técnica de los recursos. Tesis para obtener el título de: Ingeniero en computación Más detalles UNIVERSIDAD PARA LA COOPERACION INTERNACIONAL (UCI)
UNIVERSIDAD PARA LA COOPERACION INTERNACIONAL (UCI) METODOLOGIA PARA ESTANDARIZAR EL MANEJO DE PROCESOS DE RECURSOS HUMANOS Y ADQUISICIONES EN PROYECTOS DENTRO DE UN SERVICE DESK DE SOPORTE TECNICO SUSTENTANTE: Más detalles Elastix Call Center para supervisores y administradores
Elastix Call Center para supervisores y administradores Juan G. Almeida Cedeño 215 Contenido Agradecimiento...6 Introducción...7 Qué es un Call Center?...7 Importancia de un call center...7 Entrante, saliente Más detalles Grupo B. Sistemas y Tecnologías de la información
Grupo B. Sistemas y Tecnologías de la información Tema 1. Tema 2. Tema 3. Tema 4. Tema 5. Tema 6. Tema 7. Tema 8. Tema 9. Sistemas de Información. Análisis y desarrollo de sistemas de información. Metodologías Más detalles UNIVERSIDAD NACIONAL DE TRUJILLO
UNIVERSIDAD NACIONAL DE TRUJILLO FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS ESCUELA ACADEMICO PROFESIONAL DE INFORMÁTICA DESARROLLO DE UN SISTEMA INTELIGENTE BASADO EN ALGORITMOS GENETICOS PARA INCREMENTAR Más detalles Estudio para la implantación de un ERP en una empresa textil
Estudio para la implantación de un ERP en una empresa textil Memòria del Projecte Fi de Carrera d'enginyeria en Informàtica realitzat per Antonio Aguilar Sánchez i dirigit per Josep Maria Sánchez Castelló Más detalles UN PROCEDIMIENTO OPTIMAL PARA RESOLVER EL MEDIAN SHORTEST PATH PROBLEM
UNIVERSIDAD DEL BÍO-BÍO FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL PROFESOR GUÍA: SR. CARLOS OBREQUE NIÑEZ UN PROCEDIMIENTO OPTIMAL PARA RESOLVER EL MEDIAN SHORTEST PATH PROBLEM TRABAJO Más detalles Ingeniería de Tráfico en Redes MPLS
Ingeniería de Tráfico en Redes MPLS Proyecto Final de Carrera Integrantes: Adrián Delfino, Sebastián Rivero, Marcelo San Martín Tutor: Ing. Pablo Belzarena Instituto de Ingeniería Eléctrica Facultad de Más detalles ANÁLISIS DE LOS SISTEMAS BUSINESS INTELLIGENCE Y SU APLICACIÓN PRÁCTICA EN LOS PROYECTOS SOFTWARE
METODOLOGÍA PARA LA GESTIÓN DE LA SEGURIDAD INFORMÁTICA (Proyecto) Oficina de Seguridad para las Redes Informáticas Página 1 INDICE Sumario... 4 Introducción... 5 Objeto... 6 Objetivos... 6 Alcance... Más detalles FACULTAD DE INFORMATICA Y CIENCIAS APLICADAS CARRERA:TECNICO EN INGENIERIA DE REDES COMPUTACIONALES TEMA: TEMA:
FACULTAD DE INFORMATICA Y CIENCIAS APLICADAS CARRERA:TECNICO EN INGENIERIA DE REDES COMPUTACIONALES TEMA: TEMA: IMPLEMENTACIÓN DE UN PORTAL COLABORATIVO CON TECNOLOGÍA WEB, QUE PERMITA EL ACCESO SEGURO, Más detalles Operación del servicio (SO)
Operación del servicio (SO) Índice Bienvenida Introducción Objetivos Temario Tema 1. Definición de la fase de operación del servicio (SO) Introducción Objetivos Subtema 1. Definición de la fase de operación Más detalles TÉCNICAS Y HERRAMIENTAS PARA EL CONTROL DE PROCESOS Y LA GESTIÓN DE LA CALIDAD, PARA SU USO EN LA AUDITORÍA INTERNA Y EN LA GESTIÓN DE RIESGOS
DOCUMENTO TÉCNICO N 75 Versión 0.1 DOCUMENTO TECNICO N XX Versión 0.1 TÉCNICAS Y HERRAMIENTAS PARA EL CONTROL DE PROCESOS Y LA GESTIÓN DE LA CALIDAD, PARA SU USO EN LA AUDITORÍA INTERNA Y EN LA GESTIÓN Más detalles Trabajo final integrador para la obtención del título. Especialista en Ingeniería en Sistemas de Información
Universidad Tecnológica Nacional Facultad Regional Buenos Aires Dirección de Posgrado Trabajo final integrador para la obtención del título Especialista en Ingeniería en Sistemas de Información "Elementos Más detalles PROTOTIPO DE UN PORTAL DE CONOCIMIENTO; HERRAMIENTA PARA LA GESTIÓN DEL CONOCIMIENTO ORGANIZACIONAL
ESCUELA POLITÉCNICA NACIONAL FACULTAD DE INGENIERÍA DE SISTEMAS ADMINISTRACIÓN DE UN CALL CENTER DE COBRANZA PROYECTO PREVIO A LA OBTENCIÓN DEL TÍTULO DE INGENIERO EN INFORMÁTICA MENCIÓN SOFTWARE IRINA Más detalles Manual: GESTIÓN DE INCIDENTES DE SEGURIDAD INFORMÁTICA
Proyecto AMPARO Manual: GESTIÓN DE INCIDENTES DE SEGURIDAD INFORMÁTICA AMÉRICA LATINA Y CARIBE Página 1 Consideraciones Iniciales El presente manual ha sido desarrollado en el marco de las actividades Más detalles 2. PARTE 1. APROXIMACIÓN TEÓRICA AL PLAN DE MARKETING...
IMPLANTACIÓN SISTEMA DE GESTIÓN TOTAL DE LA CALIDAD EN UNA FÁBRICA DE MOTORES Titulación: Ingeniero en Organización Industrial Alumno/a: MªJosé Egido Montalbán Director/a/s: Angel Rafael Martínez Lorente Más detalles Universidad de San Carlos de Guatemala. Facultad de Ingeniería. Escuela de Ingeniería Industrial
Universidad de San Carlos de Guatemala Facultad de Ingeniería Escuela de Ingeniería Industrial LOGÍSTICA PARA UNA DISTRIBUIDORA DE MATERIALES DE CONSTRUCCIÓN Vivian Adriana Madrid Arriola Asesorado por Más detalles Gestión Analítica de Negocios y herramientas de Business Intelligence BI
33 DERECHOS RESERVADOS ; REGISTRO N 202.466-23 DE marzo 2011 AUTOR: RUBEN ALZOLA HENZI Gestión Analítica de Negocios y herramientas de Business Intelligence BI Fundamentos de las herramientas y tecnologías Más detalles Una Herramienta para la Predicción de Riesgos en Proyectos de Software usando Modelos en Redes Bayesianas
UNIVERSIDAD DE TALCA FACULTAD DE INGENIERIA ESCUELA INGENIERÍA CIVIL EN COMPUTACIÓN Una Herramienta para la Predicción de Riesgos en Proyectos de Software usando Modelos en Redes Bayesianas FRANCISCO GABRIEL Más detalles UNIVERSIDAD POLITÉCNICA SALESIANA SEDE QUITO
UNIVERSIDAD POLITÉCNICA SALESIANA SEDE QUITO CARRERA: PSICOLOGÍA Tesis previa a la obtención del Título de: PSICÓLOGA TEMA: ELABORACIÓN DEL MANUAL DE FUNCIONES, EVALUACIÓN DE DESEMPEÑO, DETECCIÓN DE NECESIDADES Más detalles CAPITULO II DISEÑO (JACQUARD)
MASTER / DEG en Dirección Estratégica del Factor Humano Con mención en Consultoría para el D.O. - 2007 Evaluación del Desempeño Fernando Corral EOI-América / Universidad Peruana de Ciencias Aplicadas (UPC) Más detalles Integración de la Gestión de Clientes en la Plataforma de Negocio de OdPe

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 Resolución 
in fine
in fine