Configuración de equipos quirúrgicos en el problema de planificación y programación de quirófanos para maximizar el número de pacientes programados

1Equation Chapter 1 Section 1 Trabajo Fin de Grado Ingeniería de Organización Industrial Configuración de equipos quirúrgicos en el problema de planificación y programación de quirófanos para maximizar el número de pacientes programados Autor: Sergio Díaz Arias Tutor: José Manuel Molina Pariente Dpto. Organización Industrial y Gestión de Empresa I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2025 ii iii Trabajo de Fin de Grado Ingeniería de Organización Industrial Configuración de equipos quirúrgicos en el problema de planificación y programación de quirófanos para maximizar el número de pacientes programados Autor: Sergio Díaz Arias Tutor: José Manuel Molina Pariente Profesor Titular de Universidad Dpto. de Organización Industrial y Gestión de Empresa I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2025 iv v Trabajo Fin de Grado: Configuración de equipos quirúrgicos en el problema de planificación y programación de quirófanos para maximizar el número de pacientes programados Autor: Sergio Díaz Arias Tutor: José Manuel Molina Pariente El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2025 El Secretario del Tribunal vi vii A mis padres A mis hermanos viii ix Agradecimientos Con la entrega de este TFG, y después de cuatro años, doy por concluida mi etapa en el Grado de Ingeniería de Organización Industrial. Han sido cuatro años donde he disfrutado, aprendido, sufrido y, sobre todo, he crecido académicamente y como persona. En primer lugar, quería agradecer a mis padres, quienes me apoyaron en todo momento. Agradezco profundamente haber tenido su total confianza en mis decisiones y en mi trabajo. Cuando les plantee la idea de irme a estudiar fuera supongo que no les resultó sencillo, pero aun así me ayudaron a perseguir mis objetivos y me han respaldado durante todo el proceso. Agradecer a sus parejas, mis otros padres, por quererme como un hijo propio y brindarnos un hogar. Quiero agradecer a mis hermanos y pedirles disculpas por todo el tiempo que no pude estar. Los kilómetros pesan, mucho más en fechas señaladas, pero confío que todo el sacrificio merezca la pena y podamos recuperar todo el tiempo perdido en algún momento. Agradecer a mis amigos, a los de aquí y los de allá. A todos los compañeros de clase con los que tantos trabajos he compartido. Me llevo muchas personas maravillosas que, espero, el futuro nos permita reencontrar. Especial mención a Irene, pues sus ánimos y consejos me hacen mejor persona y ha estado a mi lado desde el principio del camino. A todos los profesores con vocación que me han enseñado, especialmente me gustaría agradecer al tutor de este TFG, José Manuel Molina Pariente, quien desde el primer momento aceptó tutorizarme y ha mantenido su compromiso e interés hasta el final. Le agradezco que compartiera conmigo su experiencia, su dedicación y su disponibilidad durante todo el proyecto. Sus consejos me han orientado en todo momento, sintiéndome acompañado y aprendiendo cada día. Este camino no lo podría haber hecho sin el apoyo y la ayuda de mucha gente, por eso quería dedicarles un trocito de este documento a todos ellos. El título llevará mi nombre, pero el mérito es de todos ustedes. Sergio Díaz Arias Sevilla, 2025 xvi xvii ÍNDICE DE ILUSTRACIONES Ilustración 1: Decoding (elaboración propia) 18 Ilustración 2: Pseudocódigo Asignación Random (elaboración propia) 19 Ilustración 3: Pseudocódigo Asignación Common (elaboración propia) 20 Ilustración 4: Pseudocódigo First Fit (elaboración propia) 22 Ilustración 5: Surgical Schedule First Fit 22 Ilustración 6: Pseudocódigo Next Fit (elaboración propia) 23 Ilustración 7: Surgical Schedule Next Fit 23 Ilustración 8: Pseudocódigo Best Fit (elaboración propia) 24 Ilustración 9: Surgical Schedule Best Fit 24 Ilustración 10: Pseudocódigo Worst Fit (elaboración propia) 25 Ilustración 11: Surgical Schedule Worst Fit 25 Ilustración 12: Diagrama de flujo Algoritmo Genético (elaboración propia) 26 Ilustración 13: Ejemplo Roulette Wheel [17]. 28 Ilustración 14: Ejemplo cruce PMX (elaboración propia) 28 Ilustración 15: Ejemplo BlockSwap (elaboración propia) 29 Ilustración 16: Ejemplo Inversión (elaboración propia) 29 Ilustración 17: Ejemplo Inserción (elaboración propia) 30 Ilustración 18: Comparación Modelo de Islas [7] 31 Ilustración 19: Diagrama flujo Modelo de Islas [7] 32 Ilustración 20: Variante Best Teams (elaboración propia) 33 Ilustración 21: Variante Team Change (elaboración propia) 34 Ilustración 22: Variante PopExplode (elaboración propia) 35 Ilustración 23: Funcionamiento Búsqueda Local [21] 36 Ilustración 24: Pseudocódigo Local Search General Swap (elaboración propia) 37 Ilustración 25: Variante Local Search (elaboración propia) 37 Ilustración 26: Variante Simulated Annealing (elaboración propia) 38 Ilustración 27: Pseudocódigo generación cirugías (elaboración propia) 42 Ilustración 28. Pseudocódigo generación cirujanos (elaboración propia) 43 Ilustración 30: Resultados ANOVA 49 Ilustración 31: Diagrama de flujo mejor algoritmo 51 Introducción 12 12 1 INTRODUCCIÓN Desde hace décadas, el sector de salud, más concretamente el ámbito quirúrgico, ha de lidiar con números retos en la planificación y programación de las intervenciones quirúrgicas (cirugías) de los pacientes. Largas listas de espera, escasos recursos, conflictos de horarios y la sobrecarga de trabajo son algunos de los problemas a los que se enfrentan diariamente en los hospitales. Estos desafíos no solo afectan a la eficiencia operativa, sino también a la calidad de la atención al paciente. La creciente demanda de servicios quirúrgicos ha puesto una presión significativa sobre los sistemas hospitalarios y en específico, al servicio quirúrgico. Por ejemplo, en países como Turquía, el número de intervenciones quirúrgicas se ha multiplicado por ocho desde el año 2002, se estima que una de cada seis personas ha sido sometida a una cirugía. Este aumento ha llevado a los hospitales a implementar estrategias más eficientes para reducir los tiempos de espera y los costes asociados [1]. En el ámbito de la gestión quirúrgica, se identifican habitualmente tres niveles de decisión: estratégico, táctico y operativo. Este Trabajo Fin de Grado (en adelante, TFG) se centra en el nivel táctico-operativo, donde se deben decidir, de forma conjunta, tanto la configuración de equipos quirúrgicos como la programación de pacientes en quirófanos y franjas horarias. Tradicionalmente, estos problemas se han abordado de forma aislada, primero se resolvía la asignación de los equipos quirúrgicos y posteriormente la planificación y programación de cirugías. Sin embargo, en este documento se propone un enfoque integrado, donde ambos problemas se combinan en un único marco de optimización, en donde los dos problemas se resuelven en conjunto y de una misma vez. En los últimos tiempos, los investigadores tratan de resolver todo lo relacionado a los problemas de planificación y secuenciación de quirófanos debido a dos grandes razones. Primeramente, porque los quirófanos constituyen una parte fundamental de los hospitales y las cirugías deben ser seguras y eficientes y para ello se necesita una buena coordinación de recursos [2]. En segundo lugar, porque más del 60% de las admisiones hospitalarias están relacionadas al servicio de cirugía, esto representa aproximadamente el 40% de los costos hospitalarios [2]. Un estudio reciente muestra que las cargas de trabajo exigentes y las prioridades conflictivas pueden aumentar el estrés del personal sanitario y afectar negativamente la atención al paciente [3]. Se pretende evitar tiempos de espera prolongados y un uso ineficiente de los recursos [3]. Por ello, es necesario desarrollar modelos de programación quirúrgica que consideren tanto las restricciones de recursos como los tiempos de operación, con el objetivo de asemejarlos con la realidad lo mejor posible. Esta tendencia ha incentivado el desarrollo de modelos que abordan la planificación quirúrgica como un problema complejo, clasificado en la categoría NP-Hard (Non-deterministic Polynomial-time hard). Puesto que estos problemas no pueden resolverse utilizando los métodos exactos, se utilizan métodos heurísticos y metaheurísticos, siendo los algoritmos genéticos uno de los métodos más utilizados [4]. Otro estudio reciente realizado en el Hospital Universitario Virgen del Rocío, en Sevilla, muestra que, mediante la implementación de algoritmos heurísticos adaptados al entorno quirúrgico real, es posible aumentar significativamente la eficiencia operativa. En dicho estudio, se logró programar un total de 2962 cirugías anuales frente a las 2823 realizadas mediante la planificación tradicional, lo que representa un aumento promedio de 2,67 cirugías por semana sin requerir recursos adicionales [5]. Como se ha comentado, este TFG incorpora una componente adicional: la configuración de equipos quirúrgicos. Esto influye de manera directa en la duración de las intervenciones, la calidad de la atención y la seguridad del paciente. La literatura especializada destaca la necesidad de abordar la planificación de quirófanos y la configuración de equipos de manera conjunta para obtener soluciones realistas y de calidad [6]. Por todo ello, se analizarán diferentes estrategias de generación de equipos y de secuenciación y se valorará su eficacia. Los resultados obtenidos, además de validar el enfoque propuesto, servirán para identificar los puntos críticos del proceso y poder trabajar sobre ellos. Pese a la idea inicial de desarrollar un algoritmo genético al uso, en el transcurso de búsqueda de información para acometer este TFG, se ha encontrado un artículo escrito por Mohamed Kurdi [7] que propone un algoritmo genético con Modelo de Islas. Se ha considerado que este algoritmo podría encajar muy bien con el problema que se está resolviendo. Este algoritmo presenta una versión mejorada del tradicional modelo de islas (Island Model Genetic Algorithm, IMGA). A grandes rasgos, es una estrategia de paralelización y diversificación de los 13 algoritmos genéticos, varios algoritmos genéticos trabajando en paralelo para mejorar el rendimiento y la exploración del espacio de soluciones. Es cierto que el artículo [8], aplicó un algoritmo evolutivo basado en Modelo de Islas para optimizar la programación de admisión de pacientes en un hospital, sin embargo, no se ha estudiado previamente cómo es el rendimiento del Modelo de Islas en el problema que se resuelve en este TFG. Por otro lado, existe otro artículo que estudia el problema de programación de aceptación de pedidos en una fábrica, considerando costos de energía dependientes del horario y límites de emisiones de carbono [9], es decir, no solo plantea la resolución del problema, sino que contempla otras variables de este. Ambos estudios concluyen que el Modelo de Islas resulta de gran interés para dichas resoluciones pues los resultados fueron prometedores en calidad y eficiencia. Es todo ello por lo que se quiere comprobar el desempeño, la mejoría o la eficiencia que tiene el algoritmo para la resolución de este problema. Este TFG tiene la intención de aportar un valor añadido a la resolución de este tipo de problema, incluyendo algunas variantes que puedan mejorar la calidad de las soluciones, para que se puedan plantear numerosas líneas de investigación futuras que podrán ampliar el alcance y la aplicabilidad del algoritmo propuesto. 1.1 Objetivos. Este TFG tiene como propósito principal abordar un problema real y de creciente interés en el ámbito sanitario: la optimización de la planificación quirúrgica en hospitales. Para alcanzar el objetivo principal se plantean los siguientes objetivos específicos: • Investigación del problema e identificación de sus elementos y parámetros. Este análisis permite comprender el funcionamiento real del sistema hospitalario, identificar las restricciones operativas y establecer los parámetros que deben incluirse en los algoritmos de optimización. • Implementación de una metodología de resolución aproximada basada en algoritmos genéticos, incluyendo tanto el algoritmo genético base como su extensión en forma de Modelo de Islas, definiendo operadores adecuados de cruce, mutación y selección para el problema en cuestión. o Diseño de un procedimiento de Decoding eficiente. Este es el proceso mediante el cual se transforma una solución codificada en una solución factible para el problema real. En este caso, implica asignar equipos quirúrgicos y programar pacientes respetando todas las restricciones del sistema. • Desarrollo de un generador de instancias. Este permite (bajo unos parámetros) analizar diferentes escenarios hospitalarios y evaluar el comportamiento del algoritmo bajo ciertas condiciones. o Calibración de parámetros clave, tanto en el Decoding como en las diferentes variantes del algoritmo. o Evaluación experimental de las soluciones obtenidas. Comparando la calidad de las soluciones de las distintas variantes propuestas y verificar las diferencias estadísticamente significativa entre ellas. Para ello, se empleará un análisis de la varianza (test ANOVA) El cumplimiento de estos objetivos específicos permitirá el cumplimiento del objetivo general; aportar una solución de calidad al problema de planificación quirúrgica con configuración de equipos, con posibilidad de ser adaptada o extendida a entornos hospitalarios reales. Descripción del problema 14 14 2 DESCRIPCIÓN DEL PROBLEMA 2.1 Formulación general del problema Como se ha comentado anteriormente, la gestión quirúrgica representa uno de los pilares fundamentales en el funcionamiento de los hospitales, no solo por su impacto en la calidad asistencial, sino también por el elevado consumo de recursos humanos, técnicos y económicos que acarrea [2]. En este contexto, la optimización de la planificación y programación quirúrgica resulta clave para mejorar la eficiencia del sistema y reducir tiempos de espera. Sin embargo, esta tarea se ve condicionada por múltiples factores: disponibilidad de quirófanos, compatibilidades entre profesionales, la duración de las cirugías y la necesidad de formar equipos quirúrgicos adecuados. Todo ello conforma un problema altamente complejo desde el punto de vista computacional y organizativo. En un horizonte de planificación, se debe formar previamente un conjunto de equipos compatibles, es decir, que cumplan con las exigencias clínicas y respeten las restricciones operativas, a partir de los profesionales disponibles. Posteriormente asignarlos a los pacientes siguiendo una secuencia determinada. La solución debe respetar un conjunto de restricciones médicas, operativas y de disponibilidad. Se evalúa según el número de pacientes que se logre asignar y la prioridad que tuvieran estos. La prioridad es un parámetro asociado a cada paciente que refleja su importancia relativa, es un peso clínico, asociado a cada intervención quirúrgica. Este problema combina aspectos de team formation, que consiste en la formación de equipos quirúrgicos, advance y allocation scheduling, que se refieren a la asignación de las cirugías a quirófanos y franjas horarias respetando las restricciones y Bin Packing, que busca “encajar” las cirugías en los bloques de tiempo disponibles. Esto lo convierte en un caso de optimización combinatoria no trivial, el problema pertenece a la clase de problemas NP-hard. Esto quiere decir que no existe ningún algoritmo conocido que pueda resolver todos los casos posibles en tiempo polinomial (tiempo razonable) y que la dificultad del problema crece exponencialmente con el tamaño de la instancia de datos. Esta complejidad reside en la necesidad de considerar múltiples variables y restricciones simultáneamente y bajo limitaciones de recursos y disponibilidad. Básicamente, el número de combinaciones posibles es tan elevado que, de probarlas todas, se tardarían varios miles de millones de años [10]. 2.2 Elementos del sistema. Para estructurar correctamente el problema, se han identificado los siguientes elementos: • Días (d). Será el horizonte temporal que se quiera planificar. • Quirófanos (k). Cada quirófano representa un recurso con capacidad horaria limitada. • Niveles (l). Tres niveles: 0, 1 o 2. Cada cirugía y cada doctor tienen asociado uno de ellos. Los niveles van de menor a mayor especialización, siendo un nivel 2 una cirugía compleja o un cirujano experimentado. • Pacientes (i). Cada paciente viene definido por un tiempo quirúrgico estimado (ST) y el cirujano responsable y asistente (responsable y assitant) de su cirugía, que combinados, representan la duración prevista de la intervención (Surgery Time), resultando en una menor duración cuanto mayor habilidad tiene el cirujano asistente. Además, cada uno posee una prioridad (Wi) entre 0 y 100 y requiere un tipo concreto de procedimiento, lo que implica un nivel de habilidad mínima necesaria que satisfacer en su cirugía (s_type). • Cirujanos (j). Cada cirujano posee una cierta habilidad (dr_skill) y se conocen todos sus turnos de trabajo en el horizonte de planificación (dr_sched). Además, se sabe qué pacientes son los propios de cada cirujano, es decir, de que cirugías es el cirujano responsable. 15 Para acotar el problema e intentar hacerlo tratable desde el punto de vista computacional, se han adoptado los siguientes supuestos: • Los quirófanos son homogéneos. Es decir, tienen la misma capacidad y no existen preferencias por paciente o equipo. • Cada cirujano no puede intervenir en más de un quirófano a la misma vez. • Los tiempos de limpieza y preparación entre cirugías vienen incorporados en el propio tiempo de cirugía. Esto permite que, desde que una cirugía termine, se pueda empezar la siguiente. • Se excluyen pacientes de urgencias y posibles cancelaciones de última hora. • Los equipos quirúrgicos serán siempre formados por dos cirujanos. La práctica de operaciones con dos cirujanos ha sido recomendada para mitigar riesgos a la seguridad del paciente [11]. Por ejemplo, recientemente, durante la pandemia de COVID-19, se observó que la colaboración entre dos cirujanos puede mejorar la calidad de la atención y reducir la duración de las intervenciones [12]. Anteriormente, se publicaron estudios que mostraron que las cirugías con dos cirujanos fueron significativamente más cortas y las estancias hospitalarias más breves [11]. • Todos los pacientes están preparados para ser intervenidos en cualquiera de los días del horizonte. 2.3 Restricciones del problema. Para garantizar la viabilidad y coherencia del algoritmo desarrollado, se establecen una serie de restricciones operativas que deben cumplirse en cualquier solución válida. De manera sistemática: • Capacidad diaria de los quirófanos. Cada quirófano está disponible durante 480 minutos diariamente. Por tanto, la suma de los tiempos quirúrgicos asignados a un mismo quirófano en un día no puede superar dicho límite: "La duración total de las cirugías asignadas a un quirófano en un día debe ser menor o igual a su capacidad disponible." • Disponibilidad horaria del personal médico. Al igual que con los quirófanos, cada cirujano tiene asignada una planificación semanal con días y horarios concretos de disponibilidad. Solo puede ser asignado a cirugías en franjas en las que esté presente en el lugar de trabajo: "Las cirugías solo pueden ser asignadas a doctores disponibles en el día que trabaje y dentro del intervalo horario especificado." • No puede haber solapamiento entre cirugías realizadas por un mismo cirujano. Un mismo cirujano no puede participar en más de una cirugía de forma simultánea. Es decir, no puede estar asignado a dos intervenciones que se solapen temporalmente: "Un cirujano no puede estar implicado en dos intervenciones que se realicen simultáneamente." • Nivel mínimo de habilidad requerido. Cada cirugía tiene asociado un nivel de dificultad. El cirujano responsable y el asistente deben tener un nivel de habilidad igual o superior al nivel requerido por la intervención: "El cirujano responsable y el asistente deben cumplir con el nivel de habilidad mínimo exigido por la cirugía correspondiente." Descripción del problema 16 16 • Estructura del equipo quirúrgico. Cada cirugía debe ser realizada por un equipo quirúrgico compuesto por exactamente dos doctores. Uno como responsable y otro como asistente. En consecuencia, un cirujano no podrá ser responsable y asistente de la misma intervención: "Cada intervención debe tener asignado un único responsable y asistente, deben ser personas distintas." • Asignación de cirugías. Una misma cirugía no puede ser programada más de una vez a lo largo del horizonte de planificación y deben realizarse de manera continua: "Cada cirugía se asigna como máximo una vez y debe completarse íntegramente en un único día, dentro de una misma franja y quirófano." • Coordinación de recursos. Una cirugía solo puede programarse si hay disponibilidad simultánea del quirófano, del responsable y del asistente durante todo el tiempo quirúrgico requerido: "La asignación de una cirugía requiere disponibilidad conjunta de los tres recursos implicados: quirófano, responsable y asistente." 2.4 Objetivo del problema. El objetivo principal del problema consiste en maximizar el número de pacientes programados. Cada paciente debe ser asignado a un quirófano, un equipo quirúrgico compatible y una franja horaria, sin que se produzcan solapamientos ni se excedan los límites establecidos. Sin embargo, el objetivo no se limita a asignar el mayor número de pacientes posibles, sino que también busca priorizar aquellas cirugías con mayor relevancia clínica. Esta doble perspectiva permite evaluar la calidad de la planificación desde un enfoque cuantitativo y asistencial al mismo tiempo. 𝑂𝑏𝑗=𝑀𝐴𝑋 ∑𝑤𝑖∗𝑠𝑐ℎ𝑒𝑑𝑖 Siendo w la prioridad y sched una variable binaria que vale 1 si la cirugía pudo ser programada y 0 si no. Comprender la estructura y las restricciones del problema será clave para diseñar algoritmos eficientes que permitan generar soluciones viables y de calidad. A partir de esta descripción, en adelante, se detallará la metodología empleada para abordar el problema. 17 3 METODOLOGÍA DE RESOLUCIÓN Para abordar el problema considerado en la realización del TFG, se ha diseñado una metodología de resolución basada en técnicas metaheurísticas inspiradas en el algoritmo genético. Una metaheurística es un método de optimización diseñado para resolver problemas complejos (tipo NP-hard) que no pueden abordarse eficientemente con algoritmos exactos. Aunque no garantizan encontrar la solución óptima, permiten obtener resultados muy buenos en un tiempo razonable. La flexibilidad y capacidad de adaptación que tienen las metaheurísticas las hacen especialmente útiles en contextos donde existen numerosas restricciones, como en la planificación y programación quirúrgica. El planteamiento adoptado desarrolla un procedimiento de Decoding, que transforma una secuencia de pacientes (lista de espera) en una planificación quirúrgica factible. Este proceso se compone en la generación de equipos quirúrgicos compatibles y la asignación de las cirugías a quirófanos y franjas horarias. Se ha estudiado el algoritmo genético, que tiene como objetivo explorar el espacio de soluciones de forma eficiente. Básicamente, evoluciona iterativamente mediante diferentes operadores. La evaluación de cada solución se realiza a través del Decoding. El objetivo final del proceso evolutivo es maximizar el número total de pacientes programados, teniendo en cuenta la prioridad de cada uno. Como se ha mencionado anteriormente, en este TFG incorpora además un modelo de islas inspirado en el artículo [7]. Se proponen múltiples variantes del algoritmo, así como numerosas estrategias a seguir para que se pueda aportar la mejor metaheurística desarrollada. En los siguientes apartados se detallará cada paso de este TFG y se explicarán cómo funcionan las estrategias, algoritmos y variantes propuestas. Se compararán los resultados obtenidos con el ánimo de encontrar el mejor algoritmo con la mejor combinación de estrategias. 3.1 Decoding El Decoding es una fase fundamental de la metodología de resolución. Es el encargado de representar una solución factible del problema, es decir, una secuencia de los pacientes en lista de espera. A partir de los datos de entrada, es capaz de extraer una asignación válida de pacientes, equipos y tiempos dentro de los quirófanos disponibles. Tal y como se ha ido explicando a lo largo del documento, este problema tiene la peculiaridad de contar con dos etapas; la asignación de equipos y la secuenciación de pacientes. Es por esto mismo que el Decoding debe trabajar también en dos fases. Primeramente, se introduce los datos de la instancia y el Decoding devuelve los equipos quirúrgicos formados, es decir, el cirujano responsable, el asistente y, por ende, el tiempo de cirugía del paciente (responsibles, assistants y Surgery Times). Esos resultados son los datos de entrada a la segunda etapa, en la que se aplica el procedimiento de Bin Packing y devuelve la solución del problema: los pacientes programados (ver Ilustración 1). Cada una de estas etapas se puede realizar haciendo uso de diferentes estrategias de asignación y de secuenciación. A continuación, se detallarán todas las que han sido propuestas. Metodología de resolución 24 24 3.1.2.3 Best Fit (BF) Best Fit consiste en intentar aprovechar al máximo el espacio ya ocupado. Coloca cada cirugía en el quirófano que deje el menor espacio libre posible después de asignarla [14]. Es una estrategia orientada a aprovechar al máximo los recursos, exprimiendo las disponibilidades y capacidades, tanto de los quirófanos como de los cirujanos. Véase las ilustraciones 8 y 9, el pseudocódigo y la representación de la solución respectivamente. Ilustración 8: Pseudocódigo Best Fit (elaboración propia) Ilustración 9: Surgical Schedule Best Fit 25 3.1.2.4 Worst Fit (WF) Esta última estrategia funciona exactamente a la inversa de la anterior. Coloca cada cirugía en el quirófano que deje el mayor espacio libre posible después de asignarla, distribuyendo la carga lo más uniformemente possible [14]. (Ver Ilustración 10 y 11) Ilustración 10: Pseudocódigo Worst Fit (elaboración propia) Ilustración 11: Surgical Schedule Worst Fit Metodología de resolución 26 26 3.2 Algorítmo Genético El algoritmo genético es una metaheurística inspirada en los principios de la evolución natural, propuesta inicialmente por John Holland en los años 70 [15]. Su funcionamiento nace de la idea de que, al igual que en la naturaleza, las soluciones a un problema pueden evolucionar con el tiempo mediante un proceso de selección, cruce y mutación, donde sobrevive el más fuerte y apto [15]. Esta metaheurística se inicia con una población de soluciones del problema, llamadas individuos. Cada individuo de la población representa una secuencia de cirugías y es evaluado mediante una función objetivo, denominada fitness, es un indicador de cuanto de buena es la solución. Con esta evaluación hecha, se seleccionan dos individuos, los padres. Estos padres se cruzarán entre sí, generando una nueva solución que se llamará hijo. Para mantener la diversidad genética y explorar nuevas regiones del espacio de búsqueda, se aplican también pequeñas mutaciones aleatorias sobre los hijos que se han creado. Por último, se valora si el hijo es apto para entrar a la población y poder seguir evolucionando. Todo esto se realiza durante un tiempo determinado, este será la condición de parada del algoritmo. Este párrafo explicativo es solo la idea general del algoritmo, a continuación, se detallará cada paso que sigue, aportando diferentes parámetros propuestos en este TFG. La ilustración 12 muestra el diagrama de flujo explicado. Ilustración 12: Diagrama de flujo Algoritmo Genético (elaboración propia) 27 3.2.1 Inicialización de la población Para empezar con este algoritmo, se precisa de una cierta cantidad de individuos, que constituyen una población. Dentro de esa población se pueden apreciar dos tipos de individuos: Los denominados “superindividuos”, que son soluciones muy buenas del problema e individuos generados de forma completamente aleatoria [16]. En todas las poblaciones creadas en este TFG, las tres soluciones buenas han sido incorporadas haciendo uso de tres reglas de despacho (W, ST, WSPT). En primer lugar, se ha probado secuenciando en orden descendente de prioridad las cirugías (W), siendo las cirugías con mayor peso las primeras en la lista de espera. Otra regla ha sido ordenar de forma ascendiente según su tiempo de intervención (SPT), es decir, las cirugías más cortas irán antes que las más largas. Por último, se ha relacionado estas dos reglas anteriores y se ha implementado la regla WSPT. Esta ordena las cirugías de mayor a menor según el cociente entre su tiempo de cirugía y su peso clínico o prioridad, es decir: 𝑊𝑆𝑃𝑇 𝑣𝑎𝑙𝑢𝑒 =𝑆𝑇𝑖 𝑊𝑖 Las soluciones aleatorias han ido variando para todas las ejecuciones, tanto en forma como en número. Pese a tener segura la incorporación de los tres “superindividuos”, aún no se ha fijado cuántas soluciones aleatorias adicionales se deben incluir, esto lo marcará el tamaño de la población. Es un parámetro fundamental ya que influye directamente en la búsqueda de nuevas soluciones y la mejora intensiva de éstas. Una población demasiado pequeña puede converger prematuramente en óptimos locales por falta de diversidad. En cambio, si la población es excesivamente grande, puede ser ineficiente si se aplica un tiempo de ejecución limitado. Para saber el tamaño que mejor se adapta a este problema, se proponen 3 tamaños: 30, 50 y 100 individuos. 3.2.2 Evaluación del fitness Para cuantificar la calidad de las soluciones se debe calcular o fitness de cada uno de los individuos. En este TFG, el fitness es precisamente el objetivo del problema, esto es debido a la poca capacidad computacional necesaria para calcularlo. Cada individuo representa una secuencia de cirugías y esta es evaluada mediante una de las estrategias de Bin Packing, es decir, de una heurística que aporta el valor de la función objetivo del problema para esa secuencia en concreto. Para saber cuál de las opciones es la mejor, se calibrará el Decoding, obteniéndose la estrategia que mejor se adapte al problema considerado. Tras este proceso, todos y cada uno de los individuos tienen asociado un fitness, es decir, cómo de buena o mala es la solución. 3.2.3 Operador de selección Se trata de un mecanismo por el que se escogen a los individuos de la población que serán "padres" en cada una de las iteraciones. La función principal es dirigir la evolución hacia zonas del espacio de búsqueda prometedoras, haciendo que las soluciones que se combinen puedan generar nuevas soluciones mejores que las existentes. Para ello, se han propuesto dos estrategias de selección: • Selección aleatoria (Random Election). Básicamente selecciona a dos individuos al azar entre toda la población, con independencia de cualquiera de sus atributos. Puede ser útil para mantener la diversidad genética y evitar la convergencia prematura. Aunque de esta forma puede explorar ampliamente el espacio de soluciones, también puede ralentizar el proceso evolutivo pues tiene la libertad de elegir soluciones malas. Metodología de resolución 28 28 • Roulette Wheel. Esta estrategia selecciona individuos con una probabilidad proporcional a su fitness (ver Ilustración 13). Las soluciones buenas tienen más probabilidades de ser elegidas, pero no es imposible seleccionar las de menor calidad. La selección proporcional al fitness tiene el inconveniente de que en las primeras generaciones da demasiada ventaja a los individuos buenos [10]. Ilustración 13: Ejemplo Roulette Wheel [17]. 3.2.4 Operador de cruce Este apartado es sumamente importante ya que combina la información de los dos padres seleccionados y genera una nueva solución, el hijo. El objetivo es heredar de los padres sus características potencialmente beneficiosas. Este operador de cruce debe estar diseñado para poder trabajar con la codificación empleada en este problema, es decir, secuencias sin repeticiones. Es por ello, que se ha utilizado el operador Partially Matched Crossover (PMX) [10]. Sin embargo, esta es una versión simplificada de dicho operador ya que no se realiza el mapeo bidireccional clásico, sino que se rellenan las partes del hijo que faltan en orden. El operador PMX consiste en seleccionar dos puntos de corte aleatorios dentro de los padres, cortando así en tres partes su cadena genética (ver Ilustración 14). A continuación, se intercambian los segmentos y se repara el resto de la secuencia, eliminando cualquier cirugía duplicada y añadiendo las que faltan. Esta estrategia conserva, en parte, el orden y la posición relativa de elementos de los padres [10]. Se ha elegido este operador con intención de preservar las cadenas genéticas útiles y por la compatibilidad que se mantiene, evitando soluciones no factibles. Ilustración 14: Ejemplo cruce PMX (elaboración propia) 29 3.2.5 Operador de mutación Este operador es el responsable de realizar pequeñas modificaciones a los hijos creados. Su objetivo principal es mantener la diversidad genética y evitar la convergencia prematura, debido a que, como ocurre en la naturaleza, se necesitan pequeños cambios en los seres para que estos puedan evolucionar y sobrevivir. Existen numerosos operadores, en este caso, se ha propuesto la estrategia de Block Swap e Inversión, además se ha implementado un tercer operador (Inserción) en ciertas variantes [10]. • Block Swap. Es un operador que trabaja por intercambio de bloques (ver Ilustración 15). Consiste en seleccionar dos bloques dentro de la secuencia del hijo e intercambiarlos, creando un nuevo individuo mutado que conserva gran parte del orden original del hijo, pero con dos secciones intercambiadas. Ilustración 15: Ejemplo BlockSwap (elaboración propia) • Inversión. Este operador funciona introduciendo una modificación estructurada en el hijo (ver Ilustración 16). Básicamente, se trata de darle la vuelta al bloque, pasando las ultimas cirugías del bloque al principio y viceversa. El resto de la secuencia permanece inalterado por lo que se trata de una operación sencilla. Ilustración 16: Ejemplo Inversión (elaboración propia) Metodología de resolución 30 30 • Inserción. Es utilizado de forma habitual en problemas de permutación, consistiendo en extraer un elemento de la secuencia y reinsertarlo otra posición distinta, esto modifica al hijo ligeramente sin alterar su validez (ver Ilustración 17). Sin embargo, este tipo de mutación no se contempla para la calibración pues su incorporación al algoritmo no fue causada por el propio algoritmo genético sino para una de sus variantes. Ilustración 17: Ejemplo Inserción (elaboración propia) En ningún momento se hace referencia a cuanto debe medir el bloque que se mute. Por supuesto, este parámetro es fundamental para realizar una mutación correcta y efectiva. En la bibliografía no existe un consenso sobre el tamaño del bloque óptimo pues cada problema puede aportar diferente calidad de soluciones con el mismo tamaño. Es por todo esto, que se considerará las propuestas por [18] y se estudiará el efecto del 5%, 10% o 15% del tamaño de la secuencia (hijo). 3.2.6 Estrategia de reemplazo Una vez aplicado cruce y la mutación, se obtiene un descendiente; un hijo mutado. Ahora es el momento de ver si este debe entrar en la población. Esta etapa es crucial, pues el desarrollo de las próximas descendencias influye directamente en la capacidad de evitar estancamientos, eliminar individuos malos e incorporar eficazmente a los buenos. La estrategia que se sigue es conocida como Genitor. Es una estrategia muy sencilla. Se basa en que el nuevo individuo reemplaza al peor individuo de la población solo si mejora su valor de fitness. Es decir, si el descendiente generado tiene un fitness mejor que algún individuo de la población, entrará. Se busca al individuo de menor calidad y se elimina, dejando hueco para que el nuevo individuo entre en la población. Se trata de una estrategia de remplazo elitista y continua [19]. 31 3.3 Modelo de Islas (Island Model) Como se ha explicado anteriormente, esta metaheurística divide la población en varias subpoblaciones, denominadas islas, independientes unas de otras [7]. Para poder hacer una comparación justa con el algoritmo genético tradicional, se dividirá el tamaño de población elegido para el algoritmo genético entre el número de islas. Cada isla “vive al margen”, es decir, va ejecutando el algoritmo genético y cada cierto número de iteraciones intercambian información entre ellas mediante un proceso de migración de individuos. La gran novedad que aporta es que, a diferencia del modelo tradicional, este utiliza un tipo de mutación diferente en cada una de las islas (ver Ilustración 18). En la Isla 0 aplica BlockSwap, y en la isla 1 y 2 aplica Inversión e Inserción respectivamente. Esta diversificación de operadores hace que cada subpoblación explore el espacio de soluciones de distinta manera, crea una búsqueda en el espacio de soluciones mucho mayor. La migración se realiza cada 10 iteraciones y su proceso es el siguiente: El mejor individuo de cada isla se selecciona como migrante y reemplaza al peor de la isla siguiente. El pseudocódigo de este algoritmo se presenta en la Ilustración 19. De acuerdo a [7], NIMGA (New Island Model Genetic Algorithm) supera significativamente a las versiones clásicas y a otros algoritmos comparados. Ilustración 18: Comparación Modelo de Islas [7] Metodología de resolución 32 32 Ilustración 19: Diagrama flujo Modelo de Islas [7] 3.4 Variantes del Algoritmo En los apartados anteriores se ha explicado detenidamente las metaheurísticas ya existentes e implantadas. Sin embargo, el objetivo de este TFG es poder aportar un valor añadido a la resolución de este tipo de problema. El algoritmo genético y el Modelo de Islas en sí han sido estudiados y se ha concluido con su buen rendimiento, aun así, puede que, con algunas nuevas modificaciones o variantes, y para este tipo de problema, ofrezca soluciones de mejor calidad y con una carga computacional menor. Por todo ello, se proponen las siguientes variantes para su correspondiente experimentación. 33 3.4.1 Estrategia Best Teams La estrategia Best Teams realiza una exploración exhaustiva previa con múltiples combinaciones de equipos que podría proporcionar mejores resultados. Básicamente, se trata de probar 100 combinaciones de equipos quirúrgicos; aportados, evidentemente, por la ejecución del Decoding. Se evalúa cada configuración de equipos observando su desempeño en las heurísticas que aportan una solución del problema, es decir, las estrategias de Bin Packing. Se mide cuántas cirugías como máximo se pueden programar con ese equipo quirúrgico. Posteriormente, se escoge la mejor configuración y se guardan sus datos, es decir, se sigue el algoritmo con el 1% mejor de los probados. La elección de 100 combinaciones de equipos quirúrgicos se alinea con recomendaciones de la literatura que sugieren tamaños de muestra entre 50 y 200 para problemas de planificación en modelos de islas y algoritmos genéticos [7]. Esta variante intenta centrar los esfuerzos computacionales en la planificación y secuenciación de las cirugías, dando por hecho que la asignación de equipos quirúrgicos ya es considerablemente buena. Además, ayuda a que las primeras soluciones sean de buena calidad, lo que favorece la rapidez del algoritmo en obtener mejores soluciones. La Ilustración 20 muestra el diagrama de flujo de esta variante. Ilustración 20: Variante Best Teams (elaboración propia) Desarrollo de la programación 40 40 4.2 Estructura del Proyecto Para el funcionamiento y desarrollo de este TFG se ha estructurado en cuatro bloques principales, dicho de otra forma; en cuatro carpetas diferenciadas, con el objetivo de mantener una organización clara y funcional. Esta estructura permite una separación lógica entre el código fuente, los datos experimentales y los archivos de configuración del entorno. La distribución es la siguiente. Por un lado, existen dos carpetas dedicadas al almacenamiento de las instancias o datos de los problemas, todos los archivos en formato .txt (texto). La primera, bajo el nombre “Instances”, contiene todas las instancias utilizadas para la calibración de todos parámetros propuestos en este TFG. En Segundo lugar, en la carpeta “Exp_instances”, se hallan las que se han generado con intención de hacer la experimentación. Es decir, contiene todos los datos de los 180 problemas que se han resuelto con cada una de las variantes propuestas. Por otro lado, una carpeta llamada xlxs, es la encargada de almacenar los archivos del tipo xlsx. A efectos prácticos, son hojas de cálculo que permiten el vaciar y trabajar con los resultados. Cabe resaltar, dentro de esta carpeta, al archivo denominado “conclusions.xlxs”. En dicho archivo, se encuentran las comparaciones y, por tanto, las conclusiones, de todas las partes de este TFG. Ha sido de gran utilidad contar con un único archivo en el que poder visualizar, comparar y concluir basándose en todos los resultados obtenidos en la ejecución del código. En esta carpeta también se encuentran los archivos generados con el software SPSS. En último lugar, y con mayor importancia, se presentan los códigos, todos ellos bajo el formato .py (Python). El código desarrollado en este trabajo se encuentra dividido en varios módulos, cada uno con una función concreta dentro de la ejecución del algoritmo. Esta estructura modular permite trabajar de forma ordenada, facilitando tanto las modificaciones como la detección de errores y la incorporación de nuevas variantes. A continuación, se detallan los principales ficheros que componen el proyecto: • Decoding.py. Agrupa las funciones encargadas de transformar una solución codificada en una solución factible. Se incluyen funciones que se encargan de formar equipos quirúrgicos compatibles, asignar pacientes a quirófanos y comprobar que se respetan todas las restricciones. • GeneticAlgorithm.py. Este archivo contiene la implementación base del algoritmo genético. Aquí se gestiona todo el flujo de ejecución del algoritmo: selección de padres, cruce, mutación, aplicación del criterio de parada y almacenamiento de la mejor solución encontrada. Este archivo contiene todas las combinaciones de los parámetros del algoritmo genético propuesto que se han calibrado. • Types_GA.py: Este archivo se ha creado con la intención de comparar los dos algoritmos bases propuestos en este trabajo; el genético y el Island Model. También se comprueba el impacto de comenzar con una población inicial bastante buena, incorporando la estrategia de Best Teams al comienzo. • Variants.py. Aquí se encuentran implementadas distintas variantes propuestas. Algunas de ellas incorporan modificaciones como reinicios parciales de la población, otras introducen nuevas estrategias de selección o adaptan parámetros durante la ejecución (Simulated Annealing, LocalSearch). Este archivo permite comparar el rendimiento entre las distintas versiones del algoritmo base, este incluido. • Instance_creation.py. Se encarga de la generación automática de instancias de datos. Se generan aleatoriamente listas de cirugías, niveles de habilidad, prioridades, horarios de los cirujanos, etc. Todos los datos generados se almacenan en archivos de texto. • tools.py. Contiene funciones auxiliares utilizadas en diferentes partes del código. Incluye métodos para generar secuencias de pacientes, ordenar elementos según distintos criterios y gestionar listas durante la inicialización y manipulación de la población. Aquí se encuentran también las funciones de visualización del Surgical Schedule, que permite ver el calendario de cirugías y cirujanos asignados. Este módulo centraliza funciones reutilizables que no pertenecen directamente al núcleo del algoritmo. 41 5 GENERACIÓN DE INSTANCIAS Para poder calibrar los parámetros del Decoding y del Algoritmo Genético y realizar la experimentación de las variantes propuestas, se precisa de unos datos de entrada, en definitiva; problemas que resolver. Para generar o crear estos problemas, que a partir de ahora denominaremos instancias, se ha recurrido al artículo “Integrated operating room planning and scheduling problema with assistant surgeon dependent surgery durations” de José Manuel Molina Pariente [5]. El objetivo que se busca en este apartado es generar un conjunto de datos lo suficientemente variado como para evaluar el rendimiento del algoritmo propuesto, asemejándose lo máximo posible a la realidad. Para ello, se ha desarrollado un código en Python que crea automáticamente dichos escenarios quirúrgicos, combinando los factores explicados a continuación. 5.1 Factores para la generación de la batería En base a [6], se han considerado los siguientes factores: • Factor |H|. Días por planificar. Será el horizonte temporal del problema, el número de jornadas que se debe programar y secuenciar. En el documento proponen 1, 2 y 5 días. En este caso, con ánimo de acotar el TFG, se fijará el factor |H| a 5 días. Se ha considerado la programación de una semana sin contar el fin de semana. Cinco días, de lunes a viernes. • Factor |J|. Número de quirófanos disponibles. Este factor marca de cuántos quirófanos se dispone para la programación. En el Trabajo de Molina Pariente se evalúan los valores 3, 5 y 9 quirófanos. Esto permite analizar cómo varía el rendimiento del algoritmo bajo diferentes niveles de capacidad estructural. Al igual que con el anterior factor, y por simplificar, en este TFG solo se han contemplado dos valores: 3 y 9 quirófanos. Todos los quirófanos se suponen con una capacidad diaria de 8 horas, es decir, 480 minutos. • Factor β. Determina cuánto tiempo total de cirugías se genera teniendo en cuenta la capacidad del sistema. Cuanto mayor sea el valor de β, más cirugías se generan, eso produce que la planificación estará más ajustada o sobrecargada. Por el contrario, si se trata de un β pequeño, el sistema tendrá la capacidad suficiente como para satisfacer la demanda de cirugías. Se han probado valores de 0.75, 1.5 y 2.0. • Factor α. Actúa como factor de la capacidad quirúrgica por nivel de cirugía, por lo que está directamente relacionado con el número de cirujanos necesarios. Básicamente, es el factor que marca la disponibilidad total que existe entre los cirujanos teniendo en cuenta las cirugías existentes. Si α=1 se genera exactamente el tiempo necesario para cubrir las cirugías, en cambio, si α=1.5, la capacidad de los cirujanos será un 50% mayor a la necesaria. Citando el artículo referenciado: “Se han probado distintos valores del parámetro α (1.5 y 2.0), y no se han encontrado diferencias estadísticamente significativas entre ellos con un nivel de confianza del 99 %. Por tanto, se ha fijado el valor de α en 1.5 sin pérdida de generalidad” [6]. En este TFG se procede de la misma forma, fijando el factor Alpha a 1.5. |H| |J| β α 5 3, 9 0.75, 1.5, 2 1.5 Tabla 2: Resumen factores de entrada Dado estos factores de entrada, se pueden y se han creado 6 tipos de problemas o escenarios. En términos generales; tantos problemas como combinaciones de factores existan. Generación de instancias 42 42 5.2 Generación datos de cirugías En este apartado se explica cómo se han obtenido todos los datos pertenecientes a las cirugías. En concreto, de qué tipo y con qué prioridad o peso clínico. Los tiempos quirúrgicos (ST) son la duración estimada de cada intervención. Son un elemento clave en la construcción de las instancias y en el propio problema. Siguiendo la bibliografía mencionada, se ha optado por estimar la duración de las cirugías utilizando una distribución log-normal de dos parámetros; µ y cv. Este primero hace referencia al tiempo medio esperado de duración de una intervención, básicamente, el valor base. Por otro lado, el parámetro cv representa la dispersión relativa respecto a la media, es decir, cuánto varían los tiempos quirúrgicos respecto a su valor medio. Para este y en el propio artículo, los valores son: µ= {60, 120, 180, 240} y cv= {0.1, 0.2, 0.3, 0.4, 0.5}. Para cada cirugía en concreto se selecciona un µ y un cv de forma aleatoria entre las opciones disponibles. Tal y como se explicó anteriormente en la asignación de equipos quirúrgicos, los tiempos de cirugías definitivos dependerán de la elección del asistente (de su habilidad), por lo que no se conocen hasta que se realice el proceso de asignación. Con esto claro, se procede a explicar el proceso. En pocas palabras, se van creando cirugías con sus respectivos tiempos hasta que supere capacidad total del problema, que no tiene por qué ser la misma que la del sistema ya que entra en juego el parámetro β, antes mencionado. La capacidad máxima del sistema estará marcada por el número de días y la disponibilidad de todos los quirófanos (480 min c.u.), sin embargo, en este caso, la capacidad será la del sistema multiplicada por el porcentaje de sobrecarga que se quiera contemplar; el parámetro β. 𝐶𝑎𝑝𝑇𝑖𝑚𝑒=480min∗|𝐽|∗|𝐻|∗ 𝛽 Teniendo en cuenta dicha condición, se elige un µ y un cv, se calcula ti0 (tiempo de esa cirugía en concreto) usando la distribución log-normal (se guardará bajo la etiqueta ST), se le asigna el nivel mínimo necesario, la prioridad de la intervención y se actualiza el tiempo total generado. Para asignar el nivel de cirugía se elige aleatoriamente entre los posibles niveles y para asignar la prioridad se elige aleatoriamente entre 0 y 100, siendo 100 la más prioritaria. A modo de resumen y para una mejor comprensión, la Ilustración 27 muestra el pseudocódigo de la generación de las cirugías. Ilustración 27: Pseudocódigo generación cirugías (elaboración propia) 43 5.3 Generación datos de cirujanos Del mismo modo que en el apartado anterior, en este se explicará en conjunto todo lo que se ha programado para la obtención de los datos de los cirujanos. Tal y como se ha hecho hasta ahora, se extraen algunos supuestos propuestos por [6]. En este caso, los cirujanos tendrán una disponibilidad diaria igual a alguna del conjunto {240, 360, 480} minutos y trabajarán entre 3 y 5 días cada uno. Teniendo esto en cuenta, se procede a detallar el proceso en cuestión. Haciendo esta parte de una forma análoga a la creación de cirugías, se deben ir creando cirujanos hasta que se cumpla un criterio de parada. El parámetro β fue esencial para las cirugías, en cambio, para los cirujanos se debe utilizar el parámetro α. Como dicho parámetro estaba fijado a 1.5 (150%) se ha de generar cirujanos hasta que se satisfaga la condición de demanda. En este caso, la demanda o la capacidad será dividida en los niveles requeridos de las cirugías, pues que exista un cirujano con habilidad 0 no es relevante para una cirugía de nivel 3. Por ello, primeramente, se calcula el tiempo total de las cirugías por nivel y se entra en un doble bucle, uno para cada nivel y un while. Si no se ha cumplido la condición del while, se crea un cirujano con ese mismo nivel. Se elige aleatoriamente los días concretos en los que trabaja, además, también se fija aleatoriamente los minutos en los que trabaja cada día (dr_sched). Acto seguido, se elige de forma aleatoria el cirujano responsable dentro de los candidatos a elegir, que serán aquellos que posean un nivel de habilidad igual o superior al requerido por la cirugía y en ningún caso será menor. La Ilustración 28 muestra el pseudocódigo en cuestión. Ilustración 28. Pseudocódigo generación cirujanos (elaboración propia) 5.4 Escritura y lectura de archivo de texto Con todos los datos almacenados, solo falta guardarlos en algún archivo de texto al que posteriormente se pueda recurrir. Para ello, se ha usado la función write_tag, de la librería scheptk [29]. Dicha función fue diseñada para guardar los datos en archivos de texto bajo un formato común basado en etiquetas. Permite almacenar valores de tres tipos: escalares, vectores y matrices, por ejemplo, el número de cirugías, la prioridad de estas y las jornadas de los cirujanos respectivamente. Cada dato se encuentra entre dos corchetes ( [] ), los elementos de cada fila están separados por comas y en el caso de la matriz, cada fila se separa con punto y coma. Este formato permite la lectura posterior de una forma eficiente. Generación de instancias 44 44 Partiendo de la misma librería, scheptk brinda otra función llamada read_tag que funciona de manera contraria a la función write_tag. Esta permite extraer de forma estructurada los datos almacenados previamente en los archivos de texto. Para cargar los datos se ha implementado una clase (DATA), definida en el archivo Decoding.py. Combinando la clase con la función read_tag, permite al código disponer de todos los datos y en todo momento sin riesgo de pérdida o modificación de estos. Además, la clase incorpora comprobaciones de integridad que verifican que los tamaños de vectores y matrices sean coherentes entre sí, lo que ayuda a que no existan problemas incompletos. 5.5 Tiempo de ejecución Haciendo referencia de nuevo al artículo [6], y como en este TFG se precisa de un tiempo de ejecución para el algoritmo, se ha empleado una expresión matemática que relaciona los valores clave de las instancias de datos para aportar un tiempo de ejecución razonable para el algoritmo. 𝑀𝑎𝑥𝑇𝑖𝑚𝑒=(|𝐼|∗|𝐽|∗|𝐻| 2∗)𝑣 (𝑚𝑠) Siendo v un parámetro ajustable, con valores como 25 o 100, de forma que sea un factor multiplicador para definir el tiempo de los experimentos. En este Trabajo, se ha fijado v=25 pues se cuenta con una capacidad computacional ciertamente limitada. A pesar de que el tiempo de ejecución depende de los datos de la instancia, se ha decidido no incluirlo como dato propio dentro del archivo de texto ya que se considera que es un dato necesario para el propio algoritmo y no algo intrínseco del problema. Se calculará en el propio código de ejecución del algoritmo. 5.6 Resumen de instancias de datos Para concluir con este apartado, se muestra una tabla resumen (ver Tabla 3) que permite hacerse una idea general de las dimensiones de los experimentos. Se visualizará cada una de las dimensiones de los diferentes problemas; las seis combinaciones citadas. J beta Cirugías Cirujanos Maxtime (s) Problema 1 3 0.75 32.27 7.3 6.05 Problema 2 3 1.5 58.07 13.03 10.89 Problema 3 3 2 74.87 16.97 14.04 Problema 4 9 0.75 85.5 18.8 48.09 Problema 5 9 1.5 172.43 35.8 97.00 Problema 6 9 2 235.5 46.9 132.47 Tabla 3: Resumen instancias de datos 45 6 CALIBRACIÓN DE PARÁMETROS En el apartado 3, se han explicado todos los parámetros y estrategias, tanto para la parte del Decoding como para el algoritmo y sus variantes. Sin embargo, si se quiere presentar el mejor algoritmo general para resolver este problema, primero habrá que comprobar que elementos de cada bloque se comporta mejor en este contexto. Este apartado es esencial para que la evolución del TFG sea coherente, eficiente y eficaz y que el algoritmo final sea capaz de aportar soluciones suficientemente buenas o al menos, mucho mejores que las que aportaría si no se realizara dicha calibración. Para todas las calibraciones se ha evaluado el rendimiento mediante el cálculo del RPD (Relative Percentage Deviation). Es una métrica que permite comparar calidad relativa de una sola solución respecto al mejor valor conocido. Básicamente, se resuelve la misma instancia mediante todas las combinaciones de parámetros o estrategias que se quiere calibrar. La mejor solución (en el caso de maximizar; la mayor) se toma como BestSol y se calcula el RPD de cada una de las otras soluciones, siendo RPD=0 aquella estrategia o combinación de parámetro mejor para esa instancia. En este caso de maximizar: 𝑅𝑃𝐷𝑖=𝐵𝑒𝑠𝑡𝑆𝑜𝑙−𝑆𝑜𝑙𝑖 𝐵𝑒𝑠𝑡𝑆𝑜𝑙 ∗100 Una vez obtenido el RPD de todos los resultados, se puede concluir cual de todas las estrategias o combinaciones es la mejor, para ello se calcula el ARPD (Average Relative Percentage Deviation). Este valor no será más que la media aritmética de todos los RPD respectivos. Aquella que tenga menor ARPD será la elegida, pues quiere decir que fue la estrategia o combinación de parámetros que mejor resultados dio ejecutando todas las instancias de datos. 𝐴𝑅𝑃𝐷𝑗=∑𝑅𝑃𝐷𝑖 𝑛 𝑖=0𝑛 En este TFG se ha calibrado en tres ocasiones: las estrategias del Decoding, los parámetros del algoritmo genético y la comparación entre es genético y Modelo de Islas. Para todas ellas se ha utilizados las instancias que se encuentran en la carpeta instances. El Decoding ha sido el motivo de la primera calibración realizada. Rescatando la información del apartado 3.1, se sabe que existen cuatro estrategias de Bin Packing y dos de Asignación de equipos quirúrgicos. Además, como las estrategias de Bin Packing dependen en gran parte de las secuencias dadas, se han contemplado tres secuencias a partir de tres reglas de despacho diferentes, las mencionadas anteriormente (W, ST, WSPT). Bin Packing Asignación equipos Secuencia FF, NF, BF, WF Random, Common days W, SPT, WSPT Tabla 4: Combinaciones calibración Decoding Se ha ejecutado todas las combinaciones, para todos tipos de problemas y con quince experimentos de cada uno para reducir variabilidad. En total, sumando todo, se resolverá 2160 veces, pues existen 6 tipos de problemas, con 15 copias y 24 combinaciones. En el anexo están los resultados obtenidos para cada instancia de cada problema. Calibración de parámetros 46 46 Los resultados muestran que la mejor combinación para este problema de asignación y secuenciación es: • Bin Packing - WF • Asignación equipos - Common days • Secuencia - W En segundo lugar, se ha calibrado el algoritmo genético. En el apartado 3.2, se puede encontrar toda la explicación teórica de los parámetros que se van a calibrar. Del mismo modo que como en el Decoding se han ejecutado todas las combinaciones posibles, siendo estas las que salen jugando con todos estos parámetros clave: Tamaño Población Elección de padres Tipo de mutación Tamaño del bloque 30, 50, 100 Random, Roulette Wheel Inversion, BlockSwap 5%, 10%, 15% Tabla 5: Combinaciones calibración Genético Se trata de 36 combinaciones posibles. Sin embargo, ahora no se van a ejecutar 15 instancias de cada tipo de los 6 problemas pues se considera que el propio algoritmo realiza bastantes iteraciones, lo que reduce la variabilidad. Además, haciéndolo con 5 experimentos de cada problema, se obtienen 1080 resultados después de casi 14 horas de procesamiento (ver Anexo). Los resultados muestran que la mejor combinación para este problema de asignación y secuenciación es: • Tamaño Población - 50 • Elección de padres - Random Election • Tipo de mutación - BlockSwap • Tamaño del bloque - 15% Por último, y aún sin haber estado en los planes iniciales del Proyecto, se ha comparado también los rendimientos de las dos opciones de algoritmo planteadas. Sumando a esta calibración la estrategia de inicio Best Teams, para poder visualizar su funcionamiento y posibles mejoras en los algoritmos por partir de una solución buena. Algoritmos Estrategia de inicio Algoritmo Genético, Modelo de Islas Con estrategia BT, Sin estrategia BT Tabla 6: Calibración algoritmos Para ser coherentes, la batería de problema ha sido la misma que para calibrar el algoritmo genético, 5 experimentos por cada tipo de problema y extraídos de la misma carpeta. En el Anexo se encuentran los resultados. 47 Los resultados muestran que la mejor combinación para este problema de asignación y secuenciación es: • Algoritmo - Modelo de Islas • Estrategia de inicio - Con BestTeams Tal y como es el funcionamiento del Modelo de Islas, era esperable que aportase mejores soluciones, pues su capacidad de migración entre los conjuntos del modelo, dotan al algoritmo de una exploración mucho mayor. Contempla muchas más soluciones y las islas se van retroalimentando unas a otras. Experimentación con Variantes 48 48 7 EXPERIMENTACIÓN CON VARIANTES Tras toda esta explicación y métodos propuestos, se debe materializar el objetivo del TFG, demostrar que mecanismo es el mejor para resolver el problema de asignación de equipos quirúrgicos y planificación y programación de cirugías. Cada una de estas variantes se ha diseñado con la intención de abordar distintos aspectos del problema. Algunas intentan realizar una exploración del espacio de soluciones más extensa, mejoran la diversidad poblacional o incluso la aceleran de la convergencia hacia soluciones de alta calidad. A modo de resumen, las variantes a experimentar son las siguientes (ver Tabla 7). Algoritmo Base (G) Variante 1 (TC) Variante 2 (PE) Variante 3 (LS_GS) Variante 4 (SA) Modelo de Islas + Best Teams Algoritmo Base + Team Change Algoritmo Base + PopExplode Algoritmo Base + Local Search Algoritmo Base + Simulated Annealing Tabla 7: Resumen Variantes Para poder comparar los rendimientos se ha hecho un doble proceso conclutorio. En primer lugar y al igual que en la calibración, se han tomado los valores numéricos de las soluciones calculando el ARPD de cada una de las opciones ejecutadas. En este caso se han tomado diferentes instancias de datos, creadas de la misma forma que para la calibración, pero con 30 instancias para cada tipo de problema, pues a partir de n ≈ 30, se puede ajustar a una distribución normal. Es por ello por lo que permite realizar posteriormente un Test ANOVA. Tal y como se había adelantado, el primer análisis comparativo se ha realizado mediante la métrica ARPD, vista en el apartado 6. Esta métrica permite ver la calidad promedio de las soluciones obtenidas por cada variante, relacionándola con la mejor solución encontrada para la misma instancia. Una variante con un ARPD cercano a 0 muestra un comportamiento muy competitivo en relación con las mejores soluciones encontradas. En otras palabras, cuanto más cercano a 0 es su ARPD, más veces ha sido la variante que aporta la mejor solución para la instancia de datos en cuestión. J beta Cirugías Cirujanos Maxtime (s)GSA LS_GS PE TC Problema 1 3 0.75 32.27 7.3 6.05 1,951% 2,056% 1,122% 1,637% 1,345% Problema 2 3 1.5 58.07 13.03 10.89 2,116% 1,752% 1,177% 2,582% 3,547% Problema 3 3 2 74.87 16.97 14.04 0,977% 1,683% 1,087% 2,308% 2,482% Problema 4 9 0.75 85.5 18.8 48.09 1,563% 0,593% 2,681% 2,156% 2,456% Problema 5 9 1.5 172.43 35.8 97.00 0,952% 0,763% 4,705% 1,996% 3,490% Problema 6 9 2 235.5 46.9 132.47 1,041% 0,938% 4,860% 2,659% 3,517% 1,185% 0,765% 4,082% 2,271% 3,155% RDP Medio ARPD Tabla 8: Resumen resultados ARPD 49 Como se puede observar en la Tabla 8, si solo se tuviera en cuenta los problemas con 3 quirófanos, la variante que mejor rendimiento aporta es la LS_GS, pero en problemas de 9 quirófanos no trabaja igual de bien. Es decir, en general y para todos los tipos de problema, la variante que incorpora Simulated Annealing (SA), ha sido la que menor valor ARPD ha mostrado. Sin embargo, este resultado por sí solo no es suficiente para concluir que su rendimiento es el mejor. No se puede justificar que es estadísticamente superior al del resto de variantes pues dicho resultado puede deberse a la variabilidad entre instancias o a fluctuaciones propias de los algoritmos. Por ello, se ha considerado necesario realizar un análisis de varianza (Test ANOVA), para poder determinar si las diferencias observadas entre los promedios de cada variante son significativas desde un punto de vista estadístico. Además, las soluciones que aporta el algoritmo base con respecto a la variante ganadora no se diferencian mucho, motivo de más para realizar esta segunda comparación. Con la intención de analizar si existen diferencias estadísticamente significativas entre las distintas variantes, en concreto, entre la variante del Simulated Annealing y el algoritmo base, se ha realizado un análisis de la varianza. Se ha realizado un test ANOVA de un factor utilizando el software estadístico SPSS, mencionado anteriormente. Este proceso permite comparar simultáneamente las medias de todos los grupos independientes (G, SA, LS, PE y TC), bajo la hipótesis nula de que todas las medias poblacionales son iguales. Ya que se han generado 30 experimentos por cada tipo de problema se puede asumir que los resultados obtenidos siguen una distribución aproximadamente normal, lo cual justifica el uso de esta prueba. Específicamente, se ha aplicado el test Tukey HSD (Honestly Significant Difference), el cual permite identificar específicamente qué pares de variantes difieren entre sí, manteniendo controlada la probabilidad de cometer errores al realizar múltiples comparaciones (tasa de error tipo I). Esta prueba es recomendable cuando las varianzas son homogéneas y el tamaño muestral es equilibrado, condiciones que se cumplen en este caso. Se ha fijado un nivel de confianza del 95% (α = 0,05) para la evaluación. Los resultados obtenidos se muestran a continuación: Ilustración 29: Resultados ANOVA Como se observa, las variantes SA y G se encuentran dentro del mismo subconjunto homogéneo, lo que indica que no existen diferencias significativas entre ellas. Por otro lado, la variante PE aparece en un subconjunto intermedio, lo que sugiere cierta diferencia con respecto a SA y G, aunque no suficientemente fuerte como para constituir un grupo completamente separado. Por último, las variantes LS-GS y TC forman un subconjunto distinto, separado de SA y G, lo que implica que presentan un comportamiento significativamente diferente. Anexo 56 56 write_tag("DR_SKILL", DR_SKILL, "instance_"+str(id_OR)+"_"+str(id_beta)+"_"+str(num_archive)+".txt") write_tag("DR_NAMES", dr_name, "instance_"+str(id_OR)+"_"+str(id_beta)+"_"+str(num_archive)+".txt") write_tag("DR_RES", dr_resp, "instance_"+str(id_OR)+"_"+str(id_beta)+"_"+str(num_archive)+".txt") write_tag("DR_SCHED", dr_schedule, "instance_"+str(id_OR)+"_"+str(id_beta)+"_"+str(num_archive)+".txt") write_tag("ST", ST, "instance_"+str(id_OR)+"_"+str(id_beta)+"_"+str(num_archive)+".txt") write_tag("W", W, "instance_"+str(id_OR)+"_"+str(id_beta)+"_"+str(num_archive)+".txt") return Create_Instances(30) 57 Decoding: import copy from copy import deepcopy import sys import numpy as np from tools import print_tag, read_tag, sorted_index_desc,sorted_index_asc import random from openpyxl import Workbook class DATA(): def __init__(self, filename): # initializing additional data (not basic) self.OR = 0 # starting reading print("----- Reading self data from file " + filename + " -------") # Days self.days = read_tag(filename,"DAYS") # if days = -1 the program cannot continue if(self.days ==-1): print("No days specified. The program cannot continue.") sys.exit() else: print_tag("DAYS", self.days) # Levels self.l = read_tag(filename,"LEVEL") # if level = -1 the program cannot continue if(self.l ==-1): print("No level specified. The program cannot continue.") sys.exit() else: print_tag("LEVEL", self.l) # Surgeries (mandatory data) self.surgeries = read_tag(filename,"SURGERIES") # if surgeries = -1 the program cannot continue if(self.surgeries ==-1): print("No surgeries specified. The program cannot continue.") sys.exit() else: print_tag("SURGERIES", self.surgeries) # Surgery type (a vector, one S_type for surgery). self.s_type = read_tag(filename,"S_TYPE") if(self.s_type ==-1): print("No surgery type specified. The program cannot continue.") sys.exit() else: if(len(self.s_type) != self.surgeries ): print("Number of s_type does not match the number of surgeries. The program cannot continue" ) sys.exit() else: print_tag("S_TYPE", self.s_type) # OR (another mandatory data) self.OR = read_tag(filename, "OR") if(self.OR ==-1): print("No OR specified. The program cannot continue.") sys.exit() else: Anexo 58 58 print_tag("OR", self.OR) # Surgeons (another mandatory data) self.dr = read_tag(filename, "DR") if(self.dr ==-1): print("No surgeons specified. The program cannot continue.") sys.exit() else: print_tag("DR", self.dr) # Surgeon skill (a vector, one dr_skill for surgeon). self.dr_skill = read_tag(filename,"DR_SKILL") if(self.dr_skill ==-1): print("No surgery type specified. The program cannot continue.") sys.exit() else: if(len(self.dr_skill) != self.dr ): print("Number of dr_skill does not match the number of surgeries. The program cannot continue" ) sys.exit() else: print_tag("DR_SKILL", self.dr_skill) # Surgeon responsible (a matrix). self.dr_res = read_tag(filename,"DR_RES") if(self.dr_res ==-1): print("No surgeon skills specified. The program cannot continue.") sys.exit() else: if(len(self.dr_res) != self.surgeries ): print("Number of responsibles does not match the number of surgeries . The program cannot continue" ) sys.exit() else: for i in range(self.surgeries): if(len(self.dr_res[i])!= self.dr): print("Number of responsible surgeon does not match the number of surgeons. The program cannot continue" ) sys.exit() print_tag("DR_RES", self.dr_res) self.dr_sched = read_tag(filename,"DR_SCHED") if(self.dr_sched ==-1): print("No surgeon schedule specified. The program cannot continue.") sys.exit() else: if(len(self.dr_sched) != self.dr ): print("Number of surgeon schedule does not match the number of surgeons . The program cannot continue" ) sys.exit() else: for i in range(self.dr): if(len(self.dr_sched[i])!= self.days): print("Number of surgeon schedule does not match the number of days. The program cannot continue" ) sys.exit() print_tag("DR_SCHED", self.dr_sched) # Surgery times (a vector, one st for surgery). Mandatory self.st = read_tag(filename,"ST") if(self.st ==-1): print("No surgery times specified. The program cannot continue.") sys.exit() else: if(len(self.st) != self.surgeries ): print("Number of surgery times does not match the number of surgeries. The program cannot continue") sys.exit() 59 else: print_tag("ST", self.st) # Weights, if not all are assumed to be 1.0 self.w = read_tag(filename, "W") if(self.w ==-1): self.w = [1.0 for i in range(self.surgeries)] print("No weights specified for the surgeries. All weights set to 1.0.") else: # if the type is an int (single number), it is transformed into a list if( type(self.w) == int): self.w = [self.w] if(len(self.w) != self.surgeries): print("Number of weights given in tag W is different that the number of surgeries. The program cannot continue.") sys.exit() else: print_tag("W", self.w) print("----- end of self data from file " + filename + " -------") def FirstFit(Surgery_Times, responsibles, assistant, self, sequence): # Se recogen las disponibilidades iniciales de OR y dr ava_sched = np.array(self.dr_sched).T ava_dr=copy.deepcopy(ava_sched) ava_OR = np.full((self.days, self.OR), 480) # Se inicializan los parametros a 0 next_ava_dr=[[0 for i in range(self.dr)] for d in range(self.days)] next_ava_OR=[[0 for i in range(self.OR)] for d in range(self.days)] ct_OR = [[0 for _ in range(self.OR)] for _ in range(self.days)] ct = [[[0 for _ in range(self.surgeries)] for _ in range(self.OR)]for d in range(self.days)] # Se inicializa el parametro de cirugías programadas (1 si se programa, 0 ecc) scheduled=[0 for _ in range (self.surgeries)] not_scheduled=[] # Para cada cirugía de la secuencia for i in sequence: assigned = False for d in range(self.days): for k in range(self.OR): # Si el OR está disponible y tiene capacidad ese dia if next_ava_OR[d][k] + Surgery_Times[i] <= 480 and ava_OR[d][k] >= Surgery_Times[i]: resp = responsibles[i] assist = assistant[i] # Si el responsable y asistente están disponibles y tienen capacidad ese dia if (next_ava_dr[d][resp] + Surgery_Times[i] <= ava_sched[d][resp] and next_ava_dr[d][assist] + Surgery_Times[i] <= ava_sched[d][assist] and ava_dr[d][resp] >= Surgery_Times[i] and ava_dr[d][assist] >= Surgery_Times[i]): # Se empieza en el momento que todos los recursos estan disponibles start_time = max(next_ava_OR[d][k], next_ava_dr[d][resp], next_ava_dr[d][assist]) completion_time = start_time + Surgery_Times[i] # se actualizan los parámetros Anexo 60 60 ct[d][k][i] = completion_time ct_OR[d][k] = completion_time ava_OR[d][k] -= Surgery_Times[i] ava_dr[d][resp] -= Surgery_Times[i] ava_dr[d][assist] -= Surgery_Times[i] next_ava_OR[d][k] = completion_time next_ava_dr[d][resp] = completion_time next_ava_dr[d][assist] = completion_time assigned = True # Se recoge cuales estan asignados scheduled[i]=1 break if assigned: break obj=0 # Se calcula la función objetivo for i in range(self.surgeries): obj+=scheduled[i]*self.w[i] # Se recogen los que no fueron asignados if scheduled[i]<1: not_scheduled.append(i) N_schedule=0 # Se calcula la función objetivo for i in range(self.surgeries): if scheduled[i]>=1: N_schedule+=1 P_schedule= (N_schedule/self.surgeries)*100 iddle_time_dr=np.mean(ava_dr) var_iddle_dr=np.std(ava_dr) return ct, obj, not_scheduled, P_schedule, iddle_time_dr, var_iddle_dr def NextFit(Surgery_Times, responsibles, assistant, self, sequence): # Se recogen las disponibilidades iniciales de OR y dr ava_sched = np.array(self.dr_sched).T ava_dr=copy.deepcopy(ava_sched) ava_OR = np.full((self.days, self.OR), 480) # Se inicializan los parametros a 0 next_ava_dr=[[0 for i in range(self.dr)] for d in range(self.days)] next_ava_OR=[[0 for i in range(self.OR)] for d in range(self.days)] ct_OR = [[0 for _ in range(self.OR)] for _ in range(self.days)] ct = [[[0 for _ in range(self.surgeries)] for _ in range(self.OR)]for d in range(self.days)] # Se inicializa el parametro de cirugías programadas (1 si se programa, 0 ecc) scheduled=[0 for _ in range (self.surgeries)] not_scheduled=[] # Variables para Next-Fit last_d = 0 last_OR = 0 # Para cada cirugía de la secuencia for i in sequence: # Inicializamos variables assigned = False d = last_d 61 k = last_OR # Mientras no este asignado, intenta probar con otro OR o día while not assigned: # Si el OR está disponible y tiene capacidad ese dia if next_ava_OR[d][k] + Surgery_Times[i] <= 480 and ava_OR[d][k] >= Surgery_Times[i]: resp = responsibles[i] assist = assistant[i] # Si el responsable y asistente están disponibles y tienen capacidad ese día if (next_ava_dr[d][resp] + Surgery_Times[i] <= ava_sched[d][resp] and next_ava_dr[d][assist] + Surgery_Times[i] <= ava_sched[d][assist] and ava_dr[d][resp] >= Surgery_Times[i] and ava_dr[d][assist] >= Surgery_Times[i]): # Se empieza en el momento que todos los recursos están disponibles start_time = max(next_ava_OR[d][k], next_ava_dr[d][resp], next_ava_dr[d][assist]) completion_time = start_time + Surgery_Times[i] # Se actualizan los parámetros ct[d][k][i] = completion_time ct_OR[d][k] = completion_time ava_OR[d][k] -= Surgery_Times[i] ava_dr[d][resp] -= Surgery_Times[i] ava_dr[d][assist] -= Surgery_Times[i] next_ava_OR[d][k] = completion_time next_ava_dr[d][resp] = completion_time next_ava_dr[d][assist] = completion_time assigned = True # Se recoge cuales estan asignados scheduled[i] = 1 # Se actualizan los parámetros last_d = d last_OR = k break # Si no cabe en el OR actual, pasamos al siguiente OR k += 1 # Si no quedan mas OR, pasamos al siguiente día if k >= self.OR: k = 0 d += 1 if d >= self.days: break obj=0 # Se calcula la función objetivo for i in range(self.surgeries): obj+=scheduled[i]*self.w[i] if scheduled[i]<1: # Se recogen los que no fueron asignados not_scheduled.append(i) N_schedule=0 # Se calcula la función objetivo for i in range(self.surgeries): if scheduled[i]>=1: N_schedule+=1 iddle_time_dr=np.mean(ava_dr) var_iddle_dr=np.std(ava_dr) P_schedule= (N_schedule/self.surgeries)*100 Anexo 62 62 return ct, obj, not_scheduled, P_schedule, iddle_time_dr, var_iddle_dr def BestFit(Surgery_Times, responsibles, assistant, self, sequence): # Se recogen las disponibilidades iniciales de OR y dr ava_sched = np.array(self.dr_sched).T ava_dr=copy.deepcopy(ava_sched) ava_OR = np.full((self.days, self.OR), 480) # Se inicializan los parametros a 0 next_ava_dr=[[0 for i in range(self.dr)] for d in range(self.days)] next_ava_OR=[[0 for i in range(self.OR)] for d in range(self.days)] ct_OR = [[0 for _ in range(self.OR)] for _ in range(self.days)] ct = [[[0 for _ in range(self.surgeries)] for _ in range(self.OR)]for d in range(self.days)] # Se inicializa el parametro de cirugías programadas (1 si se programa, 0 ecc) scheduled=[0 for _ in range (self.surgeries)] not_scheduled=[] # Para cada cirugía de la secuencia for i in sequence: # Variables para el best fit best_d = -1 best_k = -1 min_space_left = float('inf') #número muy grande for d in range(self.days): for k in range(self.OR): # Si el OR está disponible, tiene capacidad y deja el menor espacio ocioso if next_ava_OR[d][k] + Surgery_Times[i] <= 480 and ava_OR[d][k] - Surgery_Times[i] >= 0 and ava_OR[d][k] - Surgery_Times[i] < min_space_left: resp = responsibles[i] assist = assistant[i] # Si el responsable y asistente están disponibles y tienen capacidad ese día if (next_ava_dr[d][resp] + Surgery_Times[i] <= ava_sched[d][resp] and next_ava_dr[d][assist] + Surgery_Times[i] <= ava_sched[d][assist] and ava_dr[d][resp] >= Surgery_Times[i] and ava_dr[d][assist] >= Surgery_Times[i]): # Se guarda el dia y el quirofano que cumple las restricciones y se actualizan parámetros best_d = d best_k = k min_space_left = ava_OR[d][k] - Surgery_Times[i] # Si se encontró el mejor OR con menor espacio sobrante if best_d != -1 and best_k != -1: d= best_d k=best_k # Se empieza en el momento que todos los recursos están disponibles y en el dia y OR elegido start_time = max(next_ava_OR[d][k], next_ava_dr[d][responsibles[i]], next_ava_dr[d][assistant[i]]) completion_time = start_time + Surgery_Times[i] # Se actualizan los parámetros ct[d][k][i] = completion_time ct_OR[d][k] = completion_time ava_OR[d][k] -= Surgery_Times[i] ava_dr[d][responsibles[i]] -= Surgery_Times[i] ava_dr[d][assistant[i]] -= Surgery_Times[i] 63 next_ava_OR[d][k] = completion_time next_ava_dr[d][responsibles[i]] = completion_time next_ava_dr[d][assistant[i]] = completion_time # Se recoge cuales están asignados scheduled[i] = 1 obj=0 #Se calcula la función objetivo for ii in range(self.surgeries): obj+=scheduled[ii]*self.w[ii] #Se recogen los que no fueron asignados if scheduled[ii]<1: not_scheduled.append(ii) N_schedule=0 # Se calcula la función objetivo for i in range(self.surgeries): if scheduled[i]>=1: N_schedule+=1 iddle_time_dr=np.mean(ava_dr) var_iddle_dr=np.std(ava_dr) P_schedule= (N_schedule/self.surgeries)*100 return ct, obj, not_scheduled, P_schedule, iddle_time_dr, var_iddle_dr def WorstFit(Surgery_Times, responsibles, assistant, self, sequence): # Se recogen las disponibilidades iniciales de OR y dr ava_sched = np.array(self.dr_sched).T ava_dr=copy.deepcopy(ava_sched) ava_OR = np.full((self.days, self.OR), 480) # Se inicializan los parametros a 0 next_ava_dr=[[0 for i in range(self.dr)] for d in range(self.days)] next_ava_OR=[[0 for i in range(self.OR)] for d in range(self.days)] ct_OR = [[0 for _ in range(self.OR)] for _ in range(self.days)] ct = [[[0 for _ in range(self.surgeries)] for _ in range(self.OR)]for d in range(self.days)] # Se inicializa el parametro de cirugías programadas (1 si se programa, 0 ecc) scheduled=[0 for _ in range (self.surgeries)] not_scheduled=[] # Para cada cirugía de la secuencia for i in sequence: # Variables para el best fit worst_d = -1 worst_k = -1 max_space_left = -1 #número muy pequeño for d in range(self.days): for k in range(self.OR): # Si el OR está disponible, tiene capacidad y deja el menor espacio ocioso if next_ava_OR[d][k] + Surgery_Times[i] <= 480 and ava_OR[d][k] - Surgery_Times[i] >= 0 and ava_OR[d][k] - Surgery_Times[i] > max_space_left: resp = responsibles[i] assist = assistant[i] # Si el responsable y asistente están disponibles y tienen capacidad ese día if (next_ava_dr[d][resp] + Surgery_Times[i] <= ava_sched[d][resp] and next_ava_dr[d][assist] + Surgery_Times[i] <= ava_sched[d][assist] and ava_dr[d][resp] >= Surgery_Times[i] and ava_dr[d][assist] >= Surgery_Times[i]): Anexo 64 64 # Se guarda el dia y el quirofano que cumple las restricciones y se actualizan parámetros worst_d = d worst_k = k max_space_left = ava_OR[d][k] - Surgery_Times[i] # Si se encontró el mejor OR con menor espacio sobrante if worst_d != -1 and worst_k != -1: d= worst_d k=worst_k # Se empieza en el momento que todos los recursos están disponibles y en el dia y OR elegido start_time = max(next_ava_OR[d][k], next_ava_dr[d][responsibles[i]], next_ava_dr[d][assistant[i]]) completion_time = start_time + Surgery_Times[i] # Se actualizan los parámetros ct[d][k][i] = completion_time ct_OR[d][k] = completion_time ava_OR[d][k] -= Surgery_Times[i] ava_dr[d][responsibles[i]] -= Surgery_Times[i] ava_dr[d][assistant[i]] -= Surgery_Times[i] next_ava_OR[d][k] = completion_time next_ava_dr[d][responsibles[i]] = completion_time next_ava_dr[d][assistant[i]] = completion_time # Se recoge cuales están asignados scheduled[i] = 1 obj=0 #Se calcula la función objetivo for ii in range(self.surgeries): obj+=scheduled[ii]*self.w[ii] #Se recogen los que no fueron asignados if scheduled[ii]<1: not_scheduled.append(ii) N_schedule=0 # Se calcula la función objetivo for i in range(self.surgeries): if scheduled[i]>=1: N_schedule+=1 iddle_time_dr=np.mean(ava_dr) var_iddle_dr=np.std(ava_dr) P_schedule= (N_schedule/self.surgeries)*100 return ct, obj, not_scheduled, P_schedule, iddle_time_dr, var_iddle_dr def Create_team_random(self): # Lista de equipos quirúgicos Surgeon_teams=copy.deepcopy(self.dr_res) # Lista de cirujanos principales responsibles=[0 for _ in range(self.surgeries)] for i in range(self.surgeries): for j in range(self.dr): if Surgeon_teams[i][j]>=1: responsibles[i]=j #matriz tiempo Til = np.zeros((self.surgeries,len(self.l))) 65 # cota superior CS=(sum(self.st[i] for i in range(self.surgeries)))*10 # intervalos de variación variation= [ (0.2, 0.5), # Nivel 0 (-0.1, 0.2), # Nivel 1 (-0.3, -0.1)] # Nivel 2 # Rellenamos matriz de tiempos for i in range(self.surgeries): for l in range (len(self.l)): # Si la habilidad no puede participar, añade cota superior if self.s_type[i]>l: Til[i][l]=CS # Si puede, se generan los tiempos aleatorios segun la variación por nivel else: Til[i][l]=self.st[i]*(1+ random.uniform(*variation[l])) # Rellenamos matriz de niveles candidatos candidates=np.zeros((self.surgeries,len(self.l))) for i in range(self.surgeries): for l in range (len(self.l)): #si mejora el tiempo o la habilidad necesaria es la misma que su nivel es nivel candidato if Til[i][l]<=self.st[i] or self.s_type[i]==l: candidates[i][l]=1 # Elección aleatoria election=[0 for _ in range(self.surgeries)] for i in range(self.surgeries): election[i] = random.choice(np.where(candidates[i] == 1)[0]) # Elegir uno aleatorio # Creamos listas auxiliares surgeons_per_patient=[0 for _ in range(self.surgeries)] patients_per_surgeon=[0 for _ in range(self.dr)] values = [0 for _ in range(len(self.l))] assistant=[0 for _ in range(self.surgeries)] # Calculamos los cirujanos que tiene cada paciente y los pacientes que tiene cada cirujano for i in range(self.surgeries): for j in range(self.dr): if Surgeon_teams[i][j]==1: surgeons_per_patient[i]+=1 patients_per_surgeon[j]+=1 for i in range(self.surgeries): # Si aún no se ha seleccionado un ayudante if surgeons_per_patient[i]<2: # Se calcula el valor minimo de pacientes por cada habilidad for l in range(len(self.l)): values[l] = min((patients_per_surgeon[j] for j in range(self.dr) if self.dr_skill[j] == l)) for j in range(self.dr): # Si no está seleccionado, si su habilidad concuerda con la elegida y es el que menos tiene asignadas if j != responsibles[i] and self.dr_skill[j]==election[i] and patients_per_surgeon[j]<=values[self.dr_skill[j]]: Surgeon_teams[i][j]=1 surgeons_per_patient[i]+=1 patients_per_surgeon[j]+=1 assistant[i]=j break Anexo 72 72 cont+=1 Pi_tesoro,Obj_tesoro=GeneticAlgorithm(instance, MaxTime, Population,e,m,b) ws.append([id_OR,id_beta,num_archive,p,e,m,b,Obj_tesoro]) print("copia",cont) # Guardamos por instancia wb.save(filename) 73 Types of Genetic Algorithm: import numpy as np import random from Decoding import DATA,Create_team_common, WorstFit from tools import sorted_index_desc,sorted_index_asc,random_sequence from GeneticAlgorithm import Population_creation, PMX, BlockSwap, Inversion, RandomElection import copy from copy import deepcopy import time from openpyxl import Workbook def GeneticAlgorithm(instance, MaxTime,s): if s == "OT": # Solo la primera asignación de equipos Surgery_Times, responsibles, assistant = Create_team_common(instance) if s == "BT": # Se coge la mejor asignación de las 100 probadas best_team_obj = -1 for _ in range(100): Surgery_Times_aux, responsibles_aux, assistant_aux = Create_team_common(instance) sequence = sorted_index_desc(instance.w) value = WorstFit(Surgery_Times_aux, responsibles_aux, assistant_aux, instance, sequence)[1] if value > best_team_obj: best_team_obj = value Surgery_Times = Surgery_Times_aux responsibles = responsibles_aux assistant = assistant_aux # Cálculo de fitness Population=Population_creation(50, instance, Surgery_Times) Psize=len(Population) Pi_tesoro=copy.deepcopy(Population[0]) Obj_tesoro=WorstFit(Surgery_Times, responsibles, assistant, instance, Pi_tesoro)[1] fitness_tesoro=Obj_tesoro fitness_values=[0 for _ in range(Psize)] for j in range(Psize): fitness_values[j]=WorstFit(Surgery_Times, responsibles, assistant, instance, Population[j])[1] if fitness_values[j]>fitness_tesoro: Pi_tesoro=copy.deepcopy(Population[j]) fitness_tesoro=fitness_values[j] # Inicio del algoritmo start_time = time.time() while time.time() - start_time < MaxTime: Parent1,Parent2 = RandomElection(Population) # Eleccion Child=PMX(Parent1,Parent2) #Cruce Mutant=BlockSwap(Child,0.15) # Mutacion fitness_m=WorstFit(Surgery_Times, responsibles, assistant, instance, Mutant)[1] worst_index = fitness_values.index(min(fitness_values)) # Estrategia de entrada a poblacion GENITOR (sale el peor) if fitness_m > fitness_values[worst_index]: Population[worst_index] = Mutant fitness_values[worst_index] = fitness_m if fitness_m>fitness_tesoro: Anexo 74 74 Pi_tesoro=copy.deepcopy(Mutant) Obj_tesoro=fitness_m return Pi_tesoro,Obj_tesoro def GeneticAlgorithm_Islands(instance, MaxTime,s): if s == "OT": # Solo la primera asignación de equipos Surgery_Times, responsibles, assistant = Create_team_common(instance) if s == "BT": # Se coge la mejor asignación de las 100 probadas best_team_obj = -1 for _ in range(100): Surgery_Times_aux, responsibles_aux, assistant_aux = Create_team_common(instance) sequence = sorted_index_desc(instance.w) value = WorstFit(Surgery_Times_aux, responsibles_aux, assistant_aux, instance, sequence)[1] if value > best_team_obj: best_team_obj = value Surgery_Times = Surgery_Times_aux responsibles = responsibles_aux assistant = assistant_aux num_islands=3 island_size = 20 # Creacion de islas y sus poblaciones islands = [] fitness_islands = [] pi_tesoros = [] obj_tesoros = [] for _ in range(num_islands): # Se crean las 3 islas island = Population_creation(island_size, instance,Surgery_Times) islands.append(island) fitness = [WorstFit(Surgery_Times, responsibles, assistant, instance, indiv)[1] for indiv in island] fitness_islands.append(fitness) best_idx = np.argmax(fitness) pi_tesoros.append(copy.deepcopy(island[best_idx])) obj_tesoros.append(fitness[best_idx]) start_time = time.time() generation = 0 while time.time() - start_time < MaxTime: generation+=1 for isl in range(num_islands): # Se itera sobre las 3 islas por separado Population=islands[isl] fitness=fitness_islands[isl] Parent1,Parent2 = RandomElection(Population) # Eleccion Child=PMX(Parent1,Parent2) #Cruce # Mutación diferenciada por isla if isl == 0: Mutant = BlockSwap(Child, 0.15) # BlockSwap elif isl == 1: Mutant = Inversion(Child, 0.15) # Inversion else: i, j = sorted(random.sample(range(len(Child)), 2)) # Insertion Mutant = copy.deepcopy(Child) 75 gene = Mutant.pop(i) Mutant.insert(j, gene) fitness_m = WorstFit(Surgery_Times, responsibles, assistant, instance, Mutant)[1] worst_isl = np.argmin(fitness) if fitness_m > fitness[worst_isl]: Population[worst_isl] = Mutant fitness[worst_isl] = fitness_m if fitness_m > obj_tesoros[isl]: pi_tesoros[isl] = copy.deepcopy(Mutant) obj_tesoros[isl] = fitness_m # Migración cada 10 generaciones: el mejor de cada isla reemplaza al peor de la siguiente if generation>= 10: for idx in range(num_islands): next_idx = (idx + 1) % num_islands # la última pasa a la primera best_indiv = pi_tesoros[idx] best_fit = obj_tesoros[idx] worst_next_idx = np.argmin(fitness_islands[next_idx]) islands[next_idx][worst_next_idx] = copy.deepcopy(best_indiv) fitness_islands[next_idx][worst_next_idx] = best_fit # Elegimos el mejor de todas las islas best_idx = np.argmax(obj_tesoros) return pi_tesoros[best_idx],obj_tesoros[best_idx] ############################################################################# # CALIBRATION # ############################################################################# filename = 'types.xlsx' # # Crear archivo y escribir cabecera solo una vez wb = Workbook() ws = wb.active ws.append(['id_OR','beta','num_archive','Start', 'Type','Obj_tesoro']) ORS=[3,9] beta=[0.75,1.5,2] start=['OT','BT'] types=['GA','IM'] for id_OR in ORS: for id_beta in beta: for num_archive in range(5): cont=0 instance=DATA("instances\instance_"+str(id_OR)+"_"+str(id_beta)+"_"+str(num_archiv e)+".txt") MaxTime = ((instance.surgeries * instance.OR * (instance.days / 2)) * 25)/1000 print(MaxTime) for s in start: for t in types: cont+=1 if t=="GA": Pi_tesoro,Obj_tesoro=GeneticAlgorithm(instance, MaxTime, s) Anexo 76 76 if t=="IM": Pi_tesoro,Obj_tesoro=GeneticAlgorithm_Islands(instance, MaxTime, s) ws.append([id_OR,id_beta,num_archive,s,t,Obj_tesoro]) print(cont) # Guardamos por instancia wb.save(filename) 77 Variants: import numpy as np import random from Decoding import DATA,Create_team_common, WorstFit from tools import sorted_index_desc,sorted_index_asc,random_sequence from GeneticAlgorithm import Population_creation, PMX, BlockSwap, Inversion, RandomElection import copy from copy import deepcopy import time from openpyxl import Workbook def LocalSearch_GS_BI(instance, sequence, Surgery_Times, responsibles, assistant, start_time, MaxTime): best_seq = copy.deepcopy(sequence) best_obj = WorstFit(Surgery_Times, responsibles, assistant, instance, best_seq)[1] improved = True while improved and (time.time() - start_time < MaxTime): improved = False # durante 10% del tamaño de la secuencia veces for _ in range(0.1*len(sequence)): i, j = sorted(random.sample(range(len(sequence)), 2)) vecino = copy.deepcopy(best_seq) vecino[i], vecino[j] = vecino[j], vecino[i] obj = WorstFit(Surgery_Times, responsibles, assistant, instance, vecino)[1] if obj > best_obj: best_seq = copy.deepcopy(vecino) best_obj = obj improved = True break # Se acepta el mejor vecino encontrado y se vuelve a comenzar return best_seq, best_obj def GeneticAlgorithm_Islands(instance, MaxTime): # Se coge la mejor asignación de las 100 probadas best_team_obj = -1 for _ in range(100): Surgery_Times_aux, responsibles_aux, assistant_aux = Create_team_common(instance) sequence = sorted_index_desc(instance.w) value = WorstFit(Surgery_Times_aux, responsibles_aux, assistant_aux, instance, sequence)[1] if value > best_team_obj: best_team_obj = value Surgery_Times = Surgery_Times_aux responsibles = responsibles_aux assistant = assistant_aux num_islands=3 island_size = 20 # Creacion de islas y sus poblaciones islands = [] fitness_islands = [] pi_tesoros = [] obj_tesoros = [] for _ in range(num_islands): # Se crean las 3 islas island = Population_creation(island_size, instance,Surgery_Times) Anexo 78 78 islands.append(island) fitness = [WorstFit(Surgery_Times, responsibles, assistant, instance, indiv)[1] for indiv in island] fitness_islands.append(fitness) best_idx = np.argmax(fitness) pi_tesoros.append(copy.deepcopy(island[best_idx])) obj_tesoros.append(fitness[best_idx]) start_time = time.time() generation = 0 while time.time() - start_time < MaxTime: generation+=1 for isl in range(num_islands): # Se itera sobre las 3 islas por separado Population=islands[isl] fitness=fitness_islands[isl] Parent1,Parent2 = RandomElection(Population) # Eleccion Child=PMX(Parent1,Parent2) #Cruce # Mutación diferenciada por isla if isl == 0: Mutant = BlockSwap(Child, 0.15) # BlockSwap elif isl == 1: Mutant = Inversion(Child, 0.15) # Inversion else: i, j = sorted(random.sample(range(len(Child)), 2)) # Insertion Mutant = copy.deepcopy(Child) gene = Mutant.pop(i) Mutant.insert(j, gene) fitness_m = WorstFit(Surgery_Times, responsibles, assistant, instance, Mutant)[1] worst_idx = np.argmin(fitness) if fitness_m > fitness[worst_idx]: Population[worst_idx] = Mutant fitness[worst_idx] = fitness_m if fitness_m > obj_tesoros[isl]: pi_tesoros[isl] = copy.deepcopy(Mutant) obj_tesoros[isl] = fitness_m # Migración cada 10 generaciones: el mejor de cada isla reemplaza al peor de la siguiente if generation>= 10: for idx in range(num_islands): next_idx = (idx + 1) % num_islands # la última pasa a la primera best_indiv = pi_tesoros[idx] best_fit = obj_tesoros[idx] worst_next_idx = np.argmin(fitness_islands[next_idx]) islands[next_idx][worst_next_idx] = copy.deepcopy(best_indiv) fitness_islands[next_idx][worst_next_idx] = best_fit # Elegimos el mejor de todas las islas best_idx = np.argmax(obj_tesoros) return pi_tesoros[best_idx],obj_tesoros[best_idx] def GeneticAlgorithm_Islands_SA(instance, MaxTime): # Se coge la mejor asignación de las 100 probadas best_team_obj = -1 for _ in range(100): Surgery_Times_aux, responsibles_aux, assistant_aux = Create_team_common(instance) 79 sequence = sorted_index_desc(instance.w) value = WorstFit(Surgery_Times_aux, responsibles_aux, assistant_aux, instance, sequence)[1] if value > best_team_obj: best_team_obj = value Surgery_Times = Surgery_Times_aux responsibles = responsibles_aux assistant = assistant_aux num_islands=3 island_size = 20 # Creacion de islas y sus poblaciones islands = [] fitness_islands = [] pi_tesoros = [] obj_tesoros = [] for _ in range(num_islands): # Se crean las 3 islas island = Population_creation(island_size, instance,Surgery_Times) islands.append(island) fitness = [WorstFit(Surgery_Times, responsibles, assistant, instance, indiv)[1] for indiv in island] fitness_islands.append(fitness) best_idx = np.argmax(fitness) pi_tesoros.append(copy.deepcopy(island[best_idx])) obj_tesoros.append(fitness[best_idx]) # parámetros Simulated Annealing T = 100 T_min = 1 alpha = 0.95 start_time = time.time() generation = 0 while time.time() - start_time < MaxTime: generation+=1 for isl in range(num_islands): # Se itera sobre las 3 islas por separado Population=islands[isl] fitness=fitness_islands[isl] Parent1,Parent2 = RandomElection(Population) # Eleccion Child=PMX(Parent1,Parent2) #Cruce # Mutación diferenciada por isla if isl == 0: Mutant = BlockSwap(Child, 0.15) # BlockSwap elif isl == 1: Mutant = Inversion(Child, 0.15) # Inversion else: i, j = sorted(random.sample(range(len(Child)), 2)) # Insertion Mutant = copy.deepcopy(Child) gene = Mutant.pop(i) Mutant.insert(j, gene) fitness_m = WorstFit(Surgery_Times, responsibles, assistant, instance, Mutant)[1] worst_idx = np.argmin(fitness) delta = fitness_m - fitness[worst_idx] # SA criterio de entrada if delta > 0 or random.random() < np.exp(delta / T): Population[worst_idx] = Mutant fitness[worst_idx] = fitness_m if fitness_m > obj_tesoros[isl]: Anexo 80 80 pi_tesoros[isl] = copy.deepcopy(Mutant) obj_tesoros[isl] = fitness_m # Enfriamiento de temperatura T = max(T * alpha, T_min) # Migración cada 10 generaciones: el mejor de cada isla reemplaza al peor de la siguiente if generation>= 10: for idx in range(num_islands): next_idx = (idx + 1) % num_islands # la última pasa a la primera best_indiv = pi_tesoros[idx] best_fit = obj_tesoros[idx] worst_next_idx = np.argmin(fitness_islands[next_idx]) islands[next_idx][worst_next_idx] = copy.deepcopy(best_indiv) fitness_islands[next_idx][worst_next_idx] = best_fit # Elegimos el mejor de todas las islas best_idx = np.argmax(obj_tesoros) return pi_tesoros[best_idx],obj_tesoros[best_idx] def GeneticAlgorithm_Islands_LS(instance, MaxTime): # Se coge la mejor asignación de las 100 probadas best_team_obj = -1 for _ in range(100): Surgery_Times_aux, responsibles_aux, assistant_aux = Create_team_common(instance) sequence = sorted_index_desc(instance.w) value = WorstFit(Surgery_Times_aux, responsibles_aux, assistant_aux, instance, sequence)[1] if value > best_team_obj: best_team_obj = value Surgery_Times = Surgery_Times_aux responsibles = responsibles_aux assistant = assistant_aux num_islands=3 island_size = 20 # Creacion de islas y sus poblaciones islands = [] fitness_islands = [] pi_tesoros = [] obj_tesoros = [] for _ in range(num_islands): # Se crean las 3 islas island = Population_creation(island_size, instance,Surgery_Times) islands.append(island) fitness = [WorstFit(Surgery_Times, responsibles, assistant, instance, indiv)[1] for indiv in island] fitness_islands.append(fitness) best_idx = np.argmax(fitness) pi_tesoros.append(copy.deepcopy(island[best_idx])) obj_tesoros.append(fitness[best_idx]) start_time = time.time() generation = 0 while time.time() - start_time < MaxTime: generation+=1 for isl in range(num_islands): # Se itera sobre las 3 islas por separado Population=islands[isl] fitness=fitness_islands[isl] Parent1,Parent2 = RandomElection(Population) # Eleccion Child=PMX(Parent1,Parent2) #Cruce 81 # Mutación diferenciada por isla if isl == 0: Mutant_aux = BlockSwap(Child, 0.15) # BlockSwap elif isl == 1: Mutant_aux = Inversion(Child, 0.15) # Inversion else: i, j = sorted(random.sample(range(len(Child)), 2)) # Insertion Mutant_aux = copy.deepcopy(Child) gene = Mutant_aux.pop(i) Mutant_aux.insert(j, gene) Mutant, fitness_m = LocalSearch_GS_BI(instance, Mutant_aux, Surgery_Times, responsibles, assistant, start_time, MaxTime) worst_idx = np.argmin(fitness) if fitness_m > fitness[worst_idx]: Population[worst_idx] = Mutant fitness[worst_idx] = fitness_m if fitness_m > obj_tesoros[isl]: pi_tesoros[isl] = copy.deepcopy(Mutant) obj_tesoros[isl] = fitness_m # Migración cada 10 generaciones: el mejor de cada isla reemplaza al peor de la siguiente if generation>= 10: for idx in range(num_islands): next_idx = (idx + 1) % num_islands # la última pasa a la primera best_indiv = pi_tesoros[idx] best_fit = obj_tesoros[idx] worst_next_idx = np.argmin(fitness_islands[next_idx]) islands[next_idx][worst_next_idx] = copy.deepcopy(best_indiv) fitness_islands[next_idx][worst_next_idx] = best_fit # Elegimos el mejor de todas las islas best_idx = np.argmax(obj_tesoros) return pi_tesoros[best_idx],obj_tesoros[best_idx] def GeneticAlgorithm_Islands_Pexplode(instance, MaxTime): # Se coge la mejor asignación de las 100 probadas best_team_obj = -1 for _ in range(100): Surgery_Times_aux, responsibles_aux, assistant_aux = Create_team_common(instance) sequence = sorted_index_desc(instance.w) value = WorstFit(Surgery_Times_aux, responsibles_aux, assistant_aux, instance, sequence)[1] if value > best_team_obj: best_team_obj = value Surgery_Times = Surgery_Times_aux responsibles = responsibles_aux assistant = assistant_aux num_islands=3 island_size = 20 # Creacion de islas y sus poblaciones islands = [] fitness_islands = [] pi_tesoros = [] obj_tesoros = [] Anexo 88 88 def sorted_index_asc(list): return sorted_index(list, False) def sorted_index_desc(list): return sorted_index(list, True) def plot_schedule(ct, Surgery_Times, sequence, responsibles, assistant, instance): fig, ax = plt.subplots(figsize=(12, 6)) days=instance.days OR=instance.OR #Asignar colores aleatorios colors = plt.cm.get_cmap("tab20", len(sequence)) # Dibujar la cuadrícula de quirófanos y días for d in range(days + 1): ax.plot([d, d], [0, OR + 1], "k", linewidth=2.5) # Línea vertical para los días for k in range(OR + 1): ax.plot([0, days], [k, k], "k", linewidth=2.5) # Línea horizontal para los quirófanos # Agregar marcas de referencia en cada día for d in range(days): for t in [120, 240, 360]: ax.text(d + (t / 480), OR + 0.25, f"{t}", ha="center", va="bottom", fontsize=10) # Agregar etiquetas de los días for d in range(days): ax.text(d + 0.5, OR +0.5, f"D{d}", ha="center", va="center", fontsize=12, fontweight="bold") # Agregar etiquetas de los OR for k in range(OR): ax.text(-0.1, k + 0.5, f"OR{k}", ha="center", va="center", fontsize=12, fontweight="bold", rotation=90) # Agregar las cirugías for d in range(days): for k in range(OR): for i, completion_time in enumerate(ct[d][k]): if completion_time > 0: start_time = completion_time - Surgery_Times[i] start_x = d + (start_time / 480) # Escalar el tiempo dentro del día ax.add_patch(plt.Rectangle((start_x, k), Surgery_Times[i] / 480, 1, facecolor=colors(i % 20), edgecolor='black', linewidth=1)) ax.text(start_x + Surgery_Times[i] / 480 / 2, k + 0.5, f"S{i}\nDR{responsibles[i]} / DR{assistant[i]}", color="black", ha="center", va="center", fontsize=10, fontweight="bold") # Embellecer la visualización ax.set_xticks(range(days)) ax.set_xticklabels(["" for _ in range(days)]) ax.set_yticks(range(OR)) ax.set_yticklabels(["" for _ in range(OR)]) ax.set_xlim(0, days) ax.set_ylim(0, OR ) ax.set_title("Calendario") ax.invert_yaxis() plt.show() return 89 def plot_schedule_dr(ct, Surgery_Times, sequence, responsibles, assistant, instance, doctor_id): fig, ax = plt.subplots(figsize=(12, 6)) days = instance.days OR = instance.OR #Asignar colores aleatorios a los doctores colors = plt.cm.get_cmap("tab20", instance.dr) # Dibujar la cuadrícula de quirófanos y días for d in range(days + 1): ax.plot([d, d], [0, OR + 1], "k", linewidth=2.5) for k in range(OR + 1): ax.plot([0, days], [k, k], "k", linewidth=2.5) # Agregar marcas de referencia en cada día for d in range(days): for t in [120, 240, 360]: ax.text(d + (t / 480), OR + 0.25, f"{t}", ha="center", va="bottom", fontsize=10) # Agregar etiquetas de los días for d in range(days): ax.text(d + 0.5, OR + 0.5, f"D{d}", ha="center", va="center", fontsize=12, fontweight="bold") # Agregar etiquetas de los OR for k in range(OR): ax.text(-0.1, k + 0.5, f"OR{k}", ha="center", va="center", fontsize=12, fontweight="bold", rotation=90) # Agregar las cirugías del doctor_id (sea resp o asistente) for d in range(days): for k in range(OR): for i, completion_time in enumerate(ct[d][k]): if completion_time > 0 and (responsibles[i] == doctor_id or assistant[i] == doctor_id): start_time = completion_time - Surgery_Times[i] start_x = d + (start_time / 480) width = Surgery_Times[i] / 480 resp = responsibles[i] assist = assistant[i] if resp == doctor_id: ax.add_patch(plt.Rectangle((start_x, k), width, 0.5, facecolor=colors(resp), edgecolor='black', linewidth=1)) ax.text(start_x + width / 2, k + 0.25, f"DR{resp}", color="black", ha="center", va="center", fontsize=9,fontweight="bold") if assist == doctor_id: ax.add_patch(plt.Rectangle((start_x, k + 0.5), width, 0.5, facecolor=colors(assist), edgecolor='black', linewidth=1)) ax.text(start_x + width / 2, k + 0.75, f"DR{assist}", color="black", ha="center", va="center", fontsize=9,fontweight="bold") # Embellecer la visualización ax.set_xticks(range(days)) ax.set_xticklabels(["" for _ in range(days)]) ax.set_yticks(range(OR)) ax.set_yticklabels(["" for _ in range(OR)]) ax.set_xlim(0, days) ax.set_ylim(0, OR) ax.set_title(f"Calendario - DR{doctor_id}") ax.invert_yaxis() plt.show() return Anexo 90 90 def plot_dr(ct, Surgery_Times, sequence, responsibles, assistant, instance): fig, ax = plt.subplots(figsize=(12, 6)) days = instance.days OR = instance.OR colors = plt.cm.get_cmap("tab20", len(sequence)) for d in range(days + 1): ax.plot([d, d], [0, OR + 1], "k", linewidth=2.5) for k in range(OR + 1): ax.plot([0, days], [k, k], "k", linewidth=2.5) for d in range(days): for t in [120, 240, 360]: ax.text(d + (t / 480), OR + 0.25, f"{t}", ha="center", va="bottom", fontsize=10) for d in range(days): ax.text(d + 0.5, OR + 0.5, f"D{d}", ha="center", va="center", fontsize=12, fontweight="bold") for k in range(OR): ax.text(-0.1, k + 0.5, f"OR{k}", ha="center", va="center", fontsize=12, fontweight="bold", rotation=90) for d in range(days): for k in range(OR): for i, completion_time in enumerate(ct[d][k]): if completion_time > 0: start_time = completion_time - Surgery_Times[i] start_x = d + (start_time / 480) width = Surgery_Times[i] / 480 color = colors(i) resp = responsibles[i] assist = assistant[i] ax.add_patch(plt.Rectangle((start_x, k), width, 0.5, facecolor=color, edgecolor='black', linewidth=1)) ax.add_patch(plt.Rectangle((start_x, k + 0.5), width, 0.5, facecolor=color, edgecolor='black', linewidth=1)) ax.text(start_x + width / 2, k + 0.25, f"DR{resp}", color="black", ha="center", va="center", fontsize=9,fontweight="bold") ax.text(start_x + width / 2, k + 0.75, f"DR{assist}", color="black", ha="center", va="center", fontsize=9,fontweight="bold") ax.set_xticks(range(days)) ax.set_xticklabels(["" for _ in range(days)]) ax.set_yticks(range(OR)) ax.set_yticklabels(["" for _ in range(OR)]) ax.set_xlim(0, days) ax.set_ylim(0, OR) ax.set_title("Calendario") ax.invert_yaxis() plt.show() return # utility function to generate a random sequence of length size def random_sequence(size): sequence = [] for i in range(size): number = random.randint(0, size-1) while( sequence.count(number)!= 0): number = random.randint(0, size-1) sequence.append(number) 91 return sequence def medias(num): ORS=[3,9] beta=[0.75, 1.5, 2] Num_archive=num media_surg=[] media_dr=[] media_Maxtime=[] Ors=[] bet=[] for id_OR in ORS: for id_beta in beta: sum_surgeries_t=0 sum_doctors_t=0 sum_maxtime=0 for num_archive in range(Num_archive): instance=DATA("exp_instances\instance_"+str(id_OR)+"_"+str(id_beta)+"_"+str(num_ar chive)+".txt") sum_surgeries_t+=instance.surgeries sum_doctors_t+=instance.dr sum_maxtime+=((instance.surgeries * instance.OR * (instance.days / 2)) * 25)/1000 Ors.append(id_OR) bet.append(id_beta) media_surg.append(sum_surgeries_t/Num_archive) media_dr.append(sum_doctors_t/Num_archive) media_Maxtime.append(sum_maxtime/Num_archive) return Ors, bet, media_surg, media_surg, media_Maxtime 86 Resultados calibración Decoding: Tabla 9: Resultados calibración Decoding I instances FF NF BF WF FF NF BF WF FF NF BF WF FF NF BF WF FF NF BF WF FF NF BF WF instance_3_0.75_0 0,2119 0,4993 0,2298 0,1543 0,3237 0,6420 0,3237 0,3299 0,6097 0,8265 0,6097 0,4438 0,0754 0,4684 0,0816 0,0000 0,3807 0,4499 0,3807 0,2545 0,3477 0,8306 0,4314 0,2949 instance_3_0.75_1 0,1807 0,5420 0,1730 0,1072 0,2062 0,6103 0,1836 0,2090 0,5012 0,7069 0,4373 0,3988 0,0745 0,4272 0,1000 0,0000 0,1523 0,5627 0,1591 0,1245 0,4243 0,7025 0,5243 0,3705 instance_3_0.75_2 0,2610 0,4148 0,1976 0,2109 0,3486 0,4962 0,3563 0,3417 0,6695 0,9367 0,6695 0,5324 0,1002 0,3640 0,0682 0,0000 0,1809 0,4134 0,3083 0,1761 0,4001 0,8038 0,3827 0,3097 instance_3_0.75_3 0,1751 0,3023 0,1761 0,1761 0,1106 0,2701 0,1106 0,1468 0,3552 0,6703 0,3826 0,2710 0,0000 0,6800 0,0166 0,0000 0,1076 0,1311 0,1076 0,1106 0,1145 0,5499 0,1145 0,1272 instance_3_0.75_4 0,1579 0,4882 0,1579 0,1579 0,3206 0,6461 0,3686 0,2970 0,2612 0,7331 0,2612 0,2522 0,0293 0,4752 0,0391 0,0000 0,1098 0,4394 0,2229 0,1635 0,3141 0,7046 0,3141 0,3141 instance_3_0.75_5 0,2154 0,2708 0,2154 0,1548 0,3002 0,3564 0,3002 0,3564 0,4775 0,8875 0,4775 0,4213 0,0000 0,3279 0,0433 0,0095 0,3088 0,3088 0,3088 0,1860 0,3702 0,7924 0,3685 0,2881 instance_3_0.75_6 0,3908 0,4962 0,3781 0,2778 0,4656 0,5616 0,3976 0,3976 0,3314 0,7468 0,3314 0,3356 0,0731 0,3475 0,0000 0,0229 0,2625 0,4027 0,2549 0,1818 0,4962 0,7171 0,5285 0,5472 instance_3_0.75_7 0,1446 0,3406 0,1222 0,1264 0,2722 0,5233 0,1924 0,2722 0,5027 0,8984 0,5590 0,4422 0,0569 0,2958 0,0000 0,0345 0,1670 0,3200 0,1670 0,1240 0,3122 0,8336 0,4011 0,3382 instance_3_0.75_8 0,0000 0,1417 0,0000 0,0000 0,0209 0,2206 0,0805 0,0805 0,0209 0,5378 0,1739 0,1739 0,0000 0,0564 0,0000 0,0000 0,0000 0,0596 0,0000 0,0258 0,0000 0,2931 0,1401 0,0000 instance_3_0.75_9 0,2147 0,2412 0,2040 0,1966 0,3177 0,5197 0,3177 0,2901 0,4315 0,8672 0,4357 0,4315 0,0287 0,2380 0,0478 0,0000 0,0670 0,0840 0,0670 0,1116 0,4251 0,8395 0,4251 0,2678 instance_3_0.75_10 0,1870 0,3640 0,1893 0,1494 0,3065 0,3609 0,3065 0,2605 0,6352 0,9349 0,6352 0,6352 0,0000 0,2268 0,0015 0,0444 0,1088 0,1602 0,0628 0,1088 0,1372 0,7149 0,2322 0,1372 instance_3_0.75_11 0,1044 0,3408 0,1422 0,0846 0,2012 0,4676 0,2012 0,1845 0,3933 0,8200 0,4311 0,3075 0,0295 0,3299 0,0038 0,0000 0,1441 0,3331 0,1775 0,0884 0,2921 0,6675 0,2742 0,1742 instance_3_0.75_12 0,2161 0,3494 0,1908 0,2169 0,3540 0,5395 0,3540 0,3188 0,5042 0,8084 0,5226 0,4038 0,0874 0,4973 0,0874 0,0000 0,1096 0,3464 0,0751 0,0805 0,4215 0,7517 0,3295 0,4023 instance_3_0.75_13 0,2298 0,6465 0,2908 0,1639 0,3342 0,7049 0,3476 0,2908 0,4322 0,9480 0,4055 0,3674 0,0536 0,6267 0,0696 0,0000 0,0889 0,6722 0,1119 0,1489 0,3048 0,8307 0,4119 0,1591 instance_3_0.75_14 0,1053 0,6952 0,1113 0,1053 0,3151 0,7235 0,2586 0,2731 0,4529 0,5728 0,4786 0,3964 0,0223 0,3861 0,0000 0,0000 0,1584 0,4033 0,1986 0,1515 0,3390 0,9212 0,2748 0,1361 instance_3_1.5_0 0,1278 0,6022 0,1546 0,0816 0,2226 0,7329 0,2193 0,2069 0,5144 0,8730 0,6360 0,4996 0,0936 0,2683 0,1261 0,0000 0,1991 0,6298 0,2135 0,2345 0,4765 0,8751 0,5478 0,4852 instance_3_1.5_1 0,1394 0,7143 0,1789 0,1060 0,1930 0,6390 0,2216 0,1394 0,6269 0,9533 0,6245 0,5890 0,0000 0,4367 0,0395 0,0185 0,2248 0,7518 0,1567 0,1934 0,5560 0,9218 0,5101 0,4831 instance_3_1.5_2 0,1370 0,5758 0,1573 0,1205 0,3217 0,5897 0,2192 0,1201 0,5721 0,8716 0,6089 0,4767 0,0664 0,4005 0,0394 0,0000 0,1836 0,5056 0,1633 0,1156 0,5353 0,9032 0,5755 0,4812 instance_3_1.5_3 0,0736 0,5159 0,1921 0,0284 0,0711 0,5138 0,1171 0,0827 0,4246 0,7929 0,4565 0,4388 0,0642 0,5370 0,0926 0,0000 0,1034 0,4927 0,1210 0,0401 0,2937 0,8919 0,3523 0,3040 instance_3_1.5_4 0,0604 0,3183 0,1031 0,0000 0,1015 0,2369 0,1015 0,1757 0,3876 0,8638 0,3191 0,1136 0,1088 0,3570 0,1088 0,0411 0,1233 0,3554 0,1555 0,0612 0,3280 0,5882 0,3529 0,1571 instance_3_1.5_5 0,1562 0,8312 0,1631 0,0173 0,2226 0,6658 0,2836 0,1830 0,5668 0,9279 0,6427 0,5837 0,0837 0,6535 0,0533 0,0000 0,1213 0,5526 0,1017 0,0748 0,3569 0,8745 0,4275 0,3308 instance_3_1.5_6 0,1076 0,4728 0,1558 0,1194 0,3266 0,5191 0,2689 0,2612 0,4758 0,7388 0,5294 0,5268 0,0492 0,5176 0,0933 0,0000 0,2568 0,5676 0,2296 0,1664 0,4541 0,8112 0,5213 0,3990 instance_3_1.5_7 0,0923 0,4024 0,1462 0,0228 0,1022 0,4986 0,1831 0,1450 0,5862 0,9124 0,6106 0,5603 0,0000 0,5387 0,0428 0,0071 0,0919 0,3411 0,1489 0,0880 0,3430 0,8912 0,3556 0,4479 instance_3_1.5_8 0,1594 0,6834 0,1544 0,1318 0,3009 0,6871 0,3765 0,2134 0,5083 0,8940 0,6060 0,5645 0,0668 0,5392 0,0530 0,0000 0,2332 0,6018 0,2286 0,2092 0,5088 0,9456 0,5276 0,4203 instance_3_1.5_9 0,1391 0,4578 0,1535 0,0469 0,0840 0,4375 0,2082 0,1125 0,5941 0,8895 0,6004 0,4871 0,0465 0,4516 0,1277 0,0000 0,1258 0,5910 0,1633 0,1020 0,6004 0,9406 0,6332 0,5281 instance_3_1.5_10 0,1778 0,6528 0,2407 0,0833 0,2567 0,6365 0,2666 0,1766 0,4277 0,8629 0,4699 0,4898 0,0000 0,4229 0,0478 0,0211 0,1794 0,4799 0,2188 0,1515 0,5695 0,9398 0,5269 0,3093 instance_3_1.5_11 0,0645 0,5121 0,0570 0,0263 0,1428 0,6589 0,1859 0,1686 0,2365 0,8557 0,2365 0,2266 0,0803 0,5196 0,0283 0,0000 0,0654 0,6187 0,0456 0,0878 0,1943 0,8260 0,2315 0,0694 instance_3_1.5_12 0,1716 0,5757 0,2333 0,0333 0,1418 0,5406 0,2517 0,1680 0,4796 0,9124 0,5700 0,4715 0,0202 0,4548 0,0305 0,0000 0,1861 0,3800 0,1861 0,1159 0,4821 0,8639 0,3747 0,2903 instance_3_1.5_13 0,0804 0,4826 0,0914 0,0000 0,1951 0,4706 0,1863 0,0936 0,5991 0,9258 0,5806 0,6605 0,0411 0,5351 0,0525 0,0433 0,2675 0,4146 0,2278 0,1519 0,5272 0,9810 0,4759 0,3837 instance_3_1.5_14 0,0902 0,5707 0,0977 0,0000 0,1020 0,6695 0,1621 0,1195 0,2699 0,8680 0,3336 0,1988 0,1063 0,4980 0,0602 0,0367 0,0801 0,4809 0,0816 0,0246 0,3516 0,8613 0,4379 0,4293 instance_3_2_0 0,1566 0,6462 0,1607 0,1637 0,2043 0,5884 0,2942 0,2409 0,4929 0,9157 0,5444 0,4243 0,0556 0,6663 0,0790 0,0000 0,1506 0,6010 0,1939 0,0787 0,5276 0,9459 0,5045 0,4515 instance_3_2_1 0,1886 0,7466 0,2021 0,1274 0,3438 0,8023 0,3506 0,1886 0,6634 0,9278 0,7024 0,6774 0,1087 0,5137 0,1107 0,0000 0,2169 0,5719 0,2161 0,1601 0,6263 0,9234 0,5835 0,5189 instance_3_2_2 0,1043 0,6178 0,1366 0,0612 0,2340 0,6287 0,2699 0,1132 0,5556 0,9714 0,5537 0,4401 0,0744 0,5862 0,0283 0,0000 0,0955 0,5625 0,1224 0,0856 0,5112 0,9190 0,5309 0,4684 instance_3_2_3 0,0616 0,6771 0,1055 0,0000 0,3471 0,5134 0,2635 0,2484 0,5278 0,8174 0,4817 0,4654 0,1293 0,4620 0,1267 0,0446 0,2181 0,4983 0,2231 0,2144 0,4688 0,8612 0,4529 0,3849 instance_3_2_4 0,1527 0,6381 0,1905 0,0930 0,2850 0,7040 0,3205 0,1963 0,5868 0,9352 0,6289 0,5879 0,0491 0,4963 0,0857 0,0000 0,2703 0,6557 0,2945 0,2381 0,6498 0,9744 0,6176 0,6436 instance_3_2_5 0,0850 0,6804 0,1939 0,0884 0,2985 0,7006 0,2701 0,1816 0,5515 0,9599 0,5733 0,5111 0,1292 0,5221 0,1475 0,0000 0,2138 0,7644 0,2675 0,1930 0,5423 0,9201 0,5992 0,5815 instance_3_2_6 0,1678 0,7489 0,1772 0,0214 0,2167 0,5634 0,2667 0,1018 0,4736 0,9518 0,5467 0,4674 0,0768 0,7366 0,1362 0,0000 0,1540 0,5572 0,1703 0,0279 0,5913 0,9228 0,6051 0,5634 instance_3_2_7 0,0710 0,6756 0,1726 0,0079 0,2035 0,7515 0,2341 0,1669 0,3965 0,9290 0,4683 0,3810 0,0906 0,8017 0,1348 0,0000 0,1545 0,5057 0,1567 0,1643 0,3818 0,8365 0,4347 0,3727 instance_3_2_8 0,1675 0,5114 0,2123 0,0937 0,2024 0,5922 0,1572 0,2384 0,6058 0,9085 0,5878 0,6345 0,1054 0,5580 0,1345 0,0000 0,2142 0,4600 0,2054 0,1558 0,5198 0,9184 0,5456 0,5265 instance_3_2_9 0,1008 0,4934 0,1405 0,0000 0,1742 0,7292 0,2452 0,1292 0,5415 0,8743 0,6107 0,5519 0,0275 0,4963 0,0307 0,0055 0,1997 0,6465 0,1868 0,1706 0,5977 0,9250 0,5415 0,5195 instance_3_2_10 0,1027 0,6453 0,0766 0,0600 0,1885 0,7543 0,2626 0,1468 0,5757 0,9259 0,6251 0,4892 0,0533 0,6474 0,1334 0,0000 0,1490 0,5679 0,1493 0,0988 0,5778 0,9478 0,5905 0,5761 instance_3_2_11 0,0795 0,5422 0,0661 0,0000 0,1376 0,5167 0,1831 0,0661 0,1970 0,8821 0,3162 0,2291 0,0197 0,4837 0,0143 0,0174 0,0567 0,3716 0,0826 0,1130 0,2827 0,8325 0,2519 0,2854 instance_3_2_12 0,0847 0,6077 0,0624 0,0000 0,1455 0,6284 0,2639 0,1574 0,3231 0,9384 0,3450 0,1991 0,1502 0,5509 0,0600 0,0560 0,1117 0,5393 0,1180 0,1335 0,4515 0,9308 0,3692 0,4388 instance_3_2_13 0,0000 0,5841 0,1333 0,0387 0,2639 0,5171 0,2501 0,1444 0,5544 0,9150 0,5095 0,3872 0,0339 0,5637 0,0642 0,0197 0,1703 0,5250 0,1668 0,1285 0,3855 0,8625 0,4625 0,3423 instance_3_2_14 0,1026 0,5601 0,1250 0,0375 0,2290 0,7412 0,3275 0,2684 0,6512 0,9289 0,6627 0,6156 0,0908 0,5062 0,1256 0,0000 0,2673 0,6544 0,2287 0,1554 0,5800 0,9549 0,6131 0,6698 AVERAGE 0,13772 0,530576 0,160286 0,086501 0,232348 0,5749 0,251336 0,200085 0,47878 0,862631 0,506482 0,43915 0,058937 0,47709 0,065921 0,009388 0,165127 0,47404 0,173922 0,132686 0,421568 0,838755 0,437917 0,371744 MIN sequence = WSPT Surgeons teams = random Surgeons teams = random Surgeons teams = random Surgeons teams = common Surgeons teams = common Surgeons teams = common sequence = W sequence = ST sequence = WSPT sequence = W sequence = ST 87 Tabla 10: Resultados calibración Decoding II instances FF NF BF WF FF NF BF WF FF NF BF WF FF NF BF WF FF NF BF WF FF NF BF WF instance_9_0.75_0 0,1676 0,4913 0,2033 0,0604 0,3064 0,6211 0,3284 0,1923 0,6256 0,8939 0,6888 0,5055 0,1064 0,5200 0,1386 0,0000 0,2580 0,4660 0,2273 0,0967 0,5654 0,8314 0,5597 0,4598 instance_9_0.75_1 0,1716 0,6932 0,1983 0,0100 0,3654 0,6449 0,3524 0,2129 0,5734 0,8500 0,5394 0,4177 0,1495 0,6759 0,1811 0,0000 0,2410 0,4768 0,2572 0,0931 0,6174 0,8972 0,6257 0,5993 instance_9_0.75_2 0,1938 0,5696 0,1792 0,0949 0,3288 0,6413 0,3380 0,2002 0,5657 0,9000 0,5760 0,5046 0,1504 0,7533 0,1764 0,0000 0,2391 0,5956 0,2845 0,1644 0,6357 0,9095 0,5872 0,5189 instance_9_0.75_3 0,1965 0,5767 0,1909 0,0000 0,3150 0,6900 0,3590 0,1853 0,6319 0,9130 0,6837 0,4881 0,0571 0,4333 0,0998 0,0271 0,2012 0,6491 0,2349 0,0627 0,5474 0,8964 0,5699 0,3821 instance_9_0.75_4 0,1996 0,6259 0,2921 0,1047 0,2552 0,4832 0,3358 0,2009 0,6835 0,8492 0,6113 0,5117 0,0424 0,3758 0,0600 0,0000 0,2125 0,5134 0,1772 0,0908 0,5673 0,8529 0,6381 0,3961 instance_9_0.75_5 0,1937 0,7396 0,2688 0,0909 0,3432 0,6846 0,3462 0,1824 0,5393 0,8568 0,4694 0,3800 0,0864 0,7007 0,0451 0,0000 0,2753 0,6697 0,2257 0,0912 0,5632 0,8930 0,4774 0,4562 instance_9_0.75_6 0,1989 0,6372 0,2242 0,1425 0,2364 0,7492 0,2508 0,1855 0,4685 0,9202 0,5259 0,3854 0,0749 0,5227 0,0594 0,0000 0,3152 0,6287 0,3185 0,2035 0,3434 0,7331 0,4793 0,2646 instance_9_0.75_7 0,1449 0,5167 0,1487 0,1107 0,2897 0,6265 0,2564 0,2154 0,4778 0,9325 0,4667 0,3957 0,0765 0,6150 0,1620 0,0000 0,0889 0,6167 0,1705 0,0444 0,3568 0,7444 0,3098 0,2462 instance_9_0.75_8 0,1938 0,6540 0,1860 0,1467 0,2537 0,7353 0,2416 0,2465 0,4146 0,8312 0,3782 0,2741 0,0589 0,4462 0,1177 0,0000 0,2179 0,7489 0,1655 0,1717 0,3613 0,7954 0,4407 0,2163 instance_9_0.75_9 0,0665 0,4618 0,0795 0,0116 0,2742 0,6141 0,2346 0,1194 0,5333 0,8435 0,5672 0,3568 0,0228 0,4496 0,0273 0,0000 0,2052 0,5231 0,2139 0,1148 0,5448 0,7857 0,5676 0,4629 instance_9_0.75_10 0,2100 0,5520 0,2252 0,1173 0,2590 0,7330 0,2894 0,1538 0,5279 0,9196 0,5730 0,4296 0,1021 0,3987 0,1204 0,0000 0,2899 0,5817 0,2508 0,1690 0,4371 0,9049 0,4140 0,3399 instance_9_0.75_11 0,1873 0,6817 0,2276 0,0361 0,2962 0,6890 0,3592 0,2259 0,5078 0,9166 0,5518 0,4779 0,1212 0,5112 0,1892 0,0000 0,1464 0,6391 0,2301 0,1571 0,4824 0,8849 0,3863 0,3869 instance_9_0.75_12 0,1619 0,6014 0,1912 0,0487 0,2180 0,6351 0,2498 0,1606 0,5646 0,8712 0,5446 0,3459 0,1538 0,5197 0,1098 0,0000 0,1644 0,5823 0,2477 0,0774 0,4956 0,7767 0,4576 0,2536 instance_9_0.75_13 0,1821 0,5912 0,2693 0,0279 0,3550 0,7769 0,3153 0,2830 0,6622 0,9237 0,7023 0,6267 0,1682 0,6876 0,1251 0,0000 0,2335 0,6566 0,2662 0,1748 0,5666 0,9100 0,5815 0,4169 instance_9_0.75_14 0,0556 0,5493 0,0609 0,0009 0,2332 0,5797 0,3327 0,1042 0,5218 0,8800 0,5429 0,3284 0,0433 0,6178 0,0512 0,0000 0,1961 0,4858 0,1876 0,0571 0,4118 0,8540 0,5095 0,2019 instance_9_1.5_0 0,2030 0,6601 0,1782 0,0000 0,2443 0,7426 0,2165 0,0538 0,5151 0,9020 0,5211 0,4844 0,1561 0,5884 0,1726 0,0268 0,2498 0,6828 0,2156 0,0689 0,5560 0,9176 0,5425 0,5463 instance_9_1.5_1 0,1433 0,5735 0,2003 0,0054 0,3314 0,8015 0,3094 0,1040 0,6305 0,9248 0,5857 0,4302 0,1217 0,6416 0,1766 0,0000 0,2785 0,7154 0,2557 0,0826 0,5105 0,9220 0,6230 0,4804 instance_9_1.5_2 0,2253 0,6897 0,2309 0,1092 0,2814 0,7005 0,2511 0,1174 0,7168 0,9169 0,6660 0,5822 0,1646 0,6280 0,1757 0,0000 0,1836 0,6193 0,2197 0,1417 0,5740 0,9354 0,5244 0,4718 instance_9_1.5_3 0,0745 0,5656 0,1417 0,0142 0,2364 0,8028 0,2326 0,0990 0,3947 0,8480 0,4028 0,2846 0,0817 0,4929 0,0911 0,0000 0,1926 0,6136 0,2510 0,0949 0,3257 0,8530 0,3317 0,2186 instance_9_1.5_4 0,1613 0,6300 0,2137 0,0360 0,3220 0,8318 0,3438 0,1179 0,5028 0,9001 0,5351 0,3304 0,1611 0,5800 0,1409 0,0000 0,2946 0,7738 0,2938 0,1358 0,5513 0,8753 0,5479 0,4701 instance_9_1.5_5 0,1509 0,6771 0,1838 0,0340 0,2447 0,7432 0,2786 0,0945 0,5438 0,9167 0,6159 0,4425 0,1424 0,5640 0,1227 0,0000 0,2548 0,6573 0,2227 0,1495 0,6076 0,9126 0,6326 0,4649 instance_9_1.5_6 0,1597 0,7156 0,1900 0,0258 0,2485 0,7469 0,2726 0,1449 0,5295 0,8730 0,5101 0,4997 0,1678 0,7897 0,1721 0,0000 0,2603 0,7469 0,2865 0,1080 0,5221 0,9300 0,5104 0,4683 instance_9_1.5_7 0,1505 0,7153 0,1729 0,0757 0,3111 0,7370 0,3209 0,2007 0,6321 0,9468 0,5810 0,5596 0,0668 0,5903 0,1614 0,0000 0,2716 0,6272 0,3224 0,1433 0,5843 0,9308 0,6066 0,5672 instance_9_1.5_8 0,1231 0,5666 0,1291 0,0000 0,2522 0,6921 0,2704 0,0713 0,5316 0,8961 0,5323 0,3635 0,1407 0,6235 0,1529 0,0144 0,2750 0,6581 0,2488 0,1052 0,5216 0,8867 0,5280 0,4709 instance_9_1.5_9 0,1520 0,7007 0,2213 0,0465 0,2607 0,6986 0,2871 0,1264 0,5291 0,8608 0,5538 0,4324 0,1312 0,5466 0,1215 0,0000 0,2337 0,6627 0,2412 0,1362 0,5285 0,8605 0,5366 0,4701 instance_9_1.5_10 0,1596 0,7622 0,1874 0,0000 0,2777 0,7403 0,3183 0,1420 0,5101 0,9360 0,5171 0,4080 0,1580 0,7371 0,1269 0,0105 0,1990 0,7236 0,2231 0,1087 0,5003 0,9386 0,5783 0,3781 instance_9_1.5_11 0,1532 0,6225 0,1081 0,0142 0,2312 0,7964 0,3240 0,0947 0,5270 0,9280 0,5748 0,3419 0,0894 0,4965 0,0815 0,0000 0,2473 0,6214 0,2236 0,1717 0,5059 0,8937 0,5436 0,3997 instance_9_1.5_12 0,2080 0,7506 0,1891 0,0522 0,3210 0,6373 0,3316 0,2190 0,6112 0,9282 0,5772 0,5186 0,1479 0,7264 0,0914 0,0000 0,2909 0,6947 0,3074 0,1673 0,4886 0,8727 0,4803 0,4013 instance_9_1.5_13 0,1784 0,5472 0,1827 0,0000 0,3017 0,8098 0,2852 0,1616 0,5173 0,9038 0,5018 0,3501 0,1789 0,6088 0,1225 0,0056 0,2518 0,7470 0,2890 0,1070 0,5264 0,9109 0,4829 0,3858 instance_9_1.5_14 0,1535 0,7431 0,1726 0,0628 0,3259 0,8171 0,3191 0,1207 0,6655 0,9108 0,6470 0,4704 0,1419 0,5608 0,0908 0,0000 0,1805 0,6460 0,2020 0,0524 0,4301 0,9106 0,4283 0,3322 instance_9_2_0 0,2388 0,7410 0,2089 0,0515 0,2928 0,7095 0,2956 0,1435 0,5433 0,9227 0,5300 0,4495 0,1343 0,6135 0,1443 0,0000 0,2200 0,6528 0,2672 0,0648 0,5923 0,9289 0,5458 0,4818 instance_9_2_1 0,1682 0,6929 0,1654 0,0416 0,3272 0,7696 0,2950 0,1650 0,5526 0,9053 0,5768 0,4949 0,1378 0,6754 0,1540 0,0000 0,2943 0,7267 0,2721 0,1547 0,5482 0,9371 0,5246 0,5427 instance_9_2_2 0,2120 0,7249 0,1865 0,0680 0,2895 0,7189 0,2993 0,1745 0,5464 0,9269 0,5419 0,4999 0,1599 0,6906 0,1472 0,0000 0,2009 0,5857 0,2483 0,1570 0,5129 0,9107 0,4990 0,3967 instance_9_2_3 0,2401 0,7429 0,2533 0,0951 0,3004 0,7937 0,3376 0,2101 0,6685 0,9235 0,6304 0,5074 0,1390 0,6627 0,2053 0,0000 0,2874 0,7766 0,3087 0,1249 0,6017 0,9638 0,5867 0,5327 instance_9_2_4 0,1138 0,6743 0,1748 0,0000 0,2377 0,7639 0,2787 0,1245 0,5037 0,8924 0,4484 0,3942 0,1488 0,6009 0,1290 0,0087 0,2524 0,7076 0,2365 0,0982 0,5422 0,8875 0,4942 0,4089 instance_9_2_5 0,1890 0,7759 0,2345 0,0875 0,3000 0,8329 0,2892 0,1916 0,6495 0,9174 0,6746 0,5430 0,0727 0,7237 0,1172 0,0000 0,2695 0,7437 0,2438 0,1652 0,6020 0,9521 0,5751 0,5467 instance_9_2_6 0,1481 0,6450 0,1776 0,0193 0,2795 0,7897 0,2878 0,1541 0,5691 0,9632 0,5616 0,5065 0,1420 0,6443 0,1156 0,0000 0,3076 0,7955 0,3212 0,1156 0,5908 0,9392 0,5639 0,5720 instance_9_2_7 0,1107 0,6547 0,1116 0,0036 0,2197 0,7195 0,2331 0,1215 0,5136 0,9268 0,4769 0,3902 0,1497 0,6258 0,1369 0,0000 0,2548 0,7476 0,2973 0,1247 0,4748 0,9612 0,5159 0,4326 instance_9_2_8 0,1574 0,7118 0,1792 0,0380 0,3224 0,8005 0,3250 0,1767 0,6160 0,9588 0,6324 0,5793 0,1394 0,7083 0,1665 0,0000 0,2758 0,7735 0,2764 0,1599 0,6568 0,9788 0,5705 0,6117 instance_9_2_9 0,1507 0,6527 0,1508 0,0167 0,3121 0,7513 0,2845 0,1415 0,4798 0,9357 0,5311 0,4423 0,1210 0,6357 0,1091 0,0000 0,2253 0,7263 0,2371 0,1084 0,4686 0,9490 0,4336 0,3888 instance_9_2_10 0,1081 0,6700 0,1228 0,0176 0,2688 0,8080 0,2844 0,1274 0,4779 0,8891 0,5271 0,4071 0,1446 0,6563 0,1370 0,0000 0,1663 0,7511 0,2307 0,1069 0,5170 0,8787 0,5284 0,3907 instance_9_2_11 0,1056 0,6874 0,1054 0,0000 0,2106 0,7297 0,2062 0,0727 0,4575 0,9546 0,5008 0,4935 0,1379 0,6819 0,1361 0,0229 0,2049 0,7707 0,2397 0,0423 0,4895 0,9300 0,5058 0,4003 instance_9_2_12 0,1861 0,7216 0,1986 0,0526 0,2463 0,8109 0,3180 0,1436 0,5705 0,9434 0,5560 0,5751 0,1594 0,7117 0,2246 0,0000 0,2266 0,7557 0,2931 0,1590 0,6449 0,9535 0,5626 0,5337 instance_9_2_13 0,1886 0,6899 0,1544 0,0018 0,2784 0,8034 0,3125 0,1767 0,5980 0,9368 0,6096 0,5872 0,1564 0,7754 0,2200 0,0000 0,2344 0,7575 0,3045 0,1259 0,5978 0,9450 0,5904 0,5105 instance_9_2_14 0,1039 0,6792 0,1199 0,0000 0,2207 0,7463 0,2288 0,1127 0,5355 0,9422 0,4972 0,4477 0,1546 0,6926 0,1605 0,0158 0,2020 0,6784 0,2280 0,0945 0,5572 0,9472 0,5476 0,4664 AVERAGE 0,163136 0,651684 0,182018 0,043837 0,280567 0,727766 0,293926 0,154941 0,554153 0,907384 0,556395 0,449885 0,123587 0,611132 0,132606 0,002929 0,234905 0,666061 0,250329 0,118755 0,52502 0,895175 0,523235 0,429852 MIN sequence = W sequence = ST sequence = WSPT sequence = W sequence = ST sequence = WSPT Surgeons teams = random Surgeons teams = random Surgeons teams = random Surgeons teams = common Surgeons teams = common Surgeons teams = common Anexo 88 Resultados calibración Genético: Tabla 11: Resultados calibración Genético I 30 30 30 30 30 30 30 30 30 30 30 30 50 50 50 50 50 50 50 50 50 50 50 50 100 100 100 100 100 100 100 100 100 100 100 100 RW RW RW RW RW RW RE RE RE RE RE RE RW RW RW RW RW RW RE RE RE RE RE RE RW RW RW RW RW RW RE RE RE RE RE RE I I I BS BS BS I I I BS BS BS I I I BS BS BS I I I BS BS BS I I I BS BS BS I I I BS BS BS 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 instance 3 0,8 0 0,0240 0,0240 0,0113 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0226 0,0226 0,0226 0,0093 0,0093 0,0093 0,0093 0,0093 0,0093 0,0093 0,0093 0,0093 0,0033 0,0033 0,0033 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 0,8 1 0,0473 0,0218 0,0218 0,0205 0,0130 0,0130 0,0130 0,0130 0,0130 0,0130 0,0130 0,0130 0,0096 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 0,8 2 0,0192 0,0192 0,0192 0,0172 0,0172 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0172 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 0,8 3 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 0,8 4 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 1,5 0 0,0290 0,0290 0,0187 0,0154 0,0154 0,0154 0,0154 0,0154 0,0154 0,0140 0,0140 0,0140 0,0173 0,0066 0,0055 0,0055 0,0055 0,0055 0,0055 0,0055 0,0000 0,0000 0,0000 0,0000 0,0305 0,0305 0,0257 0,0206 0,0184 0,0184 0,0169 0,0143 0,0206 0,0143 0,0143 0,0143 instance 3 1,5 1 0,0215 0,0149 0,0141 0,0141 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0070 0,0070 0,0102 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 1,5 2 0,0206 0,0206 0,0206 0,0099 0,0099 0,0099 0,0099 0,0099 0,0099 0,0092 0,0082 0,0082 0,0103 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0266 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 instance 3 1,5 3 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 instance 3 1,5 4 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 2 0 0,0662 0,0606 0,0606 0,0521 0,0521 0,0521 0,0505 0,0505 0,0505 0,0443 0,0443 0,0443 0,0173 0,0173 0,0126 0,0126 0,0126 0,0126 0,0126 0,0126 0,0126 0,0063 0,0019 0,0000 0,0477 0,0270 0,0195 0,0195 0,0195 0,0195 0,0195 0,0129 0,0195 0,0066 0,0066 0,0066 instance 3 2 1 0,0466 0,0375 0,0312 0,0247 0,0247 0,0247 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0057 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0419 0,0075 0,0062 0,0062 0,0034 0,0021 0,0021 0,0021 0,0062 0,0021 0,0021 0,0021 instance 3 2 2 0,0581 0,0438 0,0282 0,0267 0,0267 0,0267 0,0261 0,0206 0,0206 0,0206 0,0206 0,0206 0,0279 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0598 0,0296 0,0293 0,0238 0,0244 0,0238 0,0238 0,0226 0,0238 0,0226 0,0226 0,0226 instance 3 2 3 0,0303 0,0267 0,0267 0,0188 0,0188 0,0188 0,0188 0,0155 0,0155 0,0155 0,0155 0,0155 0,0099 0,0003 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0362 0,0270 0,0270 0,0237 0,0230 0,0237 0,0197 0,0197 0,0237 0,0197 0,0197 0,0197 instance 3 2 4 0,0115 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0051 0,0051 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0193 0,0010 0,0010 0,0010 0,0007 0,0007 0,0007 0,0007 0,0010 0,0007 0,0007 0,0007 0,02495 0,020496 0,017454 0,013931 0,013038 0,011889 0,011277 0,01069 0,01069 0,010126 0,009977 0,009977 0,010999 0,004945 0,004198 0,003311 0,003311 0,003311 0,003311 0,003311 0,002943 0,002525 0,002232 0,002106 0,018489 0,01038 0,009453 0,008301 0,007936 0,007854 0,007493 0,006804 0,008301 0,006386 0,006386 0,006386 AVERAGE Pop_size election mutation cluster_size 30 30 30 30 30 30 30 30 30 30 30 30 50 50 50 50 50 50 50 50 50 50 50 50 100 100 100 100 100 100 100 100 100 100 100 100 RW RW RW RW RW RW RE RE RE RE RE RE RW RW RW RW RW RW RE RE RE RE RE RE RW RW RW RW RW RW RE RE RE RE RE RE I I I BS BS BS I I I BS BS BS I I I BS BS BS IIIBS BS BS I I I BS BS BS I I I BS BS BS 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 instance 3 0,8 0 0,0240 0,0240 0,0113 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0226 0,0226 0,0226 0,0093 0,0093 0,0093 0,0093 0,0093 0,0093 0,0093 0,0093 0,0093 0,0033 0,0033 0,0033 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 0,8 1 0,0473 0,0218 0,0218 0,0205 0,0130 0,0130 0,0130 0,0130 0,0130 0,0130 0,0130 0,0130 0,0096 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0021 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 0,8 2 0,0192 0,0192 0,0192 0,0172 0,0172 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0172 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 0,8 3 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 0,8 4 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 1,5 0 0,0290 0,0290 0,0187 0,0154 0,0154 0,0154 0,0154 0,0154 0,0154 0,0140 0,0140 0,0140 0,0173 0,0066 0,0055 0,0055 0,0055 0,0055 0,0055 0,0055 0,0000 0,0000 0,0000 0,0000 0,0305 0,0305 0,0257 0,0206 0,0184 0,0184 0,0169 0,0143 0,0206 0,0143 0,0143 0,0143 instance 3 1,5 1 0,0215 0,0149 0,0141 0,0141 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0070 0,0070 0,0102 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0082 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 1,5 2 0,0206 0,0206 0,0206 0,0099 0,0099 0,0099 0,0099 0,0099 0,0099 0,0092 0,0082 0,0082 0,0103 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0266 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 instance 3 1,5 3 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 0,0120 instance 3 1,5 4 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 3 2 0 0,0662 0,0606 0,0606 0,0521 0,0521 0,0521 0,0505 0,0505 0,0505 0,0443 0,0443 0,0443 0,0173 0,0173 0,0126 0,0126 0,0126 0,0126 0,0126 0,0126 0,0126 0,0063 0,0019 0,0000 0,0477 0,0270 0,0195 0,0195 0,0195 0,0195 0,0195 0,0129 0,0195 0,0066 0,0066 0,0066 instance 3 2 1 0,0466 0,0375 0,0312 0,0247 0,0247 0,0247 0,0177 0,0177 0,0177 0,0177 0,0177 0,0177 0,0057 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0419 0,0075 0,0062 0,0062 0,0034 0,0021 0,0021 0,0021 0,0062 0,0021 0,0021 0,0021 instance 3 2 2 0,0581 0,0438 0,0282 0,0267 0,0267 0,0267 0,0261 0,0206 0,0206 0,0206 0,0206 0,0206 0,0279 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0598 0,0296 0,0293 0,0238 0,0244 0,0238 0,0238 0,0226 0,0238 0,0226 0,0226 0,0226 instance 3 2 3 0,0303 0,0267 0,0267 0,0188 0,0188 0,0188 0,0188 0,0155 0,0155 0,0155 0,0155 0,0155 0,0099 0,0003 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0362 0,0270 0,0270 0,0237 0,0230 0,0237 0,0197 0,0197 0,0237 0,0197 0,0197 0,0197 instance 3 2 4 0,0115 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0095 0,0051 0,0051 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0193 0,0010 0,0010 0,0010 0,0007 0,0007 0,0007 0,0007 0,0010 0,0007 0,0007 0,0007 0,02495 0,020496 0,017454 0,013931 0,013038 0,011889 0,011277 0,01069 0,01069 0,010126 0,009977 0,009977 0,010999 0,004945 0,004198 0,003311 0,003311 0,003311 0,003311 0,003311 0,002943 0,002525 0,002232 0,002106 0,018489 0,01038 0,009453 0,008301 0,007936 0,007854 0,007493 0,006804 0,008301 0,006386 0,006386 0,006386 AVERAGE Pop_size election mutation cluster_size 89 Tabla 12: Resultados calibración Genético II 30 30 30 30 30 30 30 30 30 30 30 30 50 50 50 50 50 50 50 50 50 50 50 50 100 100 100 100 100 100 100 100 100 100 100 100 RW RW RW RW RW RW RE RE RE RE RE RE RW RW RW RW RW RW RE RE RE RE RE RE RW RW RW RW RW RW RE RE RE RE RE RE I I I BS BS BS I I I BS BS BS I I I BS BS BS I I I BS BS BS I I I BS BS BS I I I BS BS BS 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 instance 9 0,8 0 0,0206 0,0206 0,0134 0,0077 0,0009 0,0009 0,0009 0,0009 0,0009 0,0009 0,0009 0,0009 0,0161 0,0161 0,0161 0,0079 0,0079 0,0079 0,0079 0,0061 0,0061 0,0000 0,0061 0,0000 0,0127 0,0127 0,0109 0,0050 0,0050 0,0050 0,0050 0,0050 0,0050 0,0041 0,0041 0,0041 instance 9 0,8 1 0,0269 0,0190 0,0190 0,0183 0,0180 0,0180 0,0180 0,0180 0,0180 0,0068 0,0056 0,0030 0,0140 0,0140 0,0028 0,0008 0,0008 0,0008 0,0008 0,0008 0,0008 0,0008 0,0008 0,0008 0,0223 0,0129 0,0058 0,0053 0,0053 0,0053 0,0028 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 0,8 2 0,0280 0,0280 0,0280 0,0157 0,0157 0,0157 0,0157 0,0157 0,0157 0,0157 0,0157 0,0157 0,0042 0,0042 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0157 0,0147 0,0147 0,0031 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 0,8 3 0,0338 0,0181 0,0181 0,0160 0,0160 0,0160 0,0160 0,0160 0,0160 0,0160 0,0160 0,0160 0,0225 0,0214 0,0057 0,0057 0,0021 0,0021 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0181 0,0181 0,0181 0,0147 0,0147 0,0147 0,0147 0,0147 0,0147 0,0147 0,0147 0,0147 instance 9 0,8 4 0,0273 0,0228 0,0228 0,0122 0,0122 0,0122 0,0122 0,0122 0,0122 0,0122 0,0122 0,0122 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0141 0,0064 0,0064 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 1,5 0 0,0226 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0016 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0157 0,0056 0,0043 0,0015 0,0013 0,0018 0,0018 0,0005 0,0005 0,0000 0,0000 0,0000 instance 9 1,5 1 0,0333 0,0333 0,0333 0,0328 0,0328 0,0328 0,0328 0,0294 0,0294 0,0294 0,0294 0,0294 0,0218 0,0218 0,0211 0,0200 0,0200 0,0200 0,0189 0,0189 0,0189 0,0189 0,0189 0,0189 0,0127 0,0033 0,0005 0,0003 0,0000 0,0003 0,0003 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 1,5 2 0,0379 0,0379 0,0379 0,0379 0,0379 0,0379 0,0379 0,0379 0,0379 0,0343 0,0343 0,0343 0,0292 0,0292 0,0237 0,0199 0,0199 0,0199 0,0199 0,0199 0,0199 0,0199 0,0199 0,0199 0,0083 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 1,5 3 0,0098 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0004 0,0004 0,0004 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 instance 9 1,5 4 0,0133 0,0049 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0085 0,0079 0,0079 0,0079 0,0079 0,0079 0,0079 0,0079 0,0079 0,0093 0,0079 0,0079 0,0062 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 instance 9 2 0 0,0168 0,0168 0,0168 0,0146 0,0146 0,0146 0,0146 0,0146 0,0146 0,0146 0,0146 0,0146 0,0128 0,0128 0,0112 0,0102 0,0102 0,0102 0,0102 0,0060 0,0060 0,0060 0,0060 0,0060 0,0237 0,0063 0,0011 0,0015 0,0008 0,0011 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 2 1 0,0319 0,0319 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0226 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0204 0,0048 0,0039 0,0039 0,0038 0,0038 0,0033 0,0001 0,0001 0,0001 0,0000 0,0000 instance 9 2 2 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0225 0,0225 0,0225 0,0225 0,0222 0,0222 0,0214 0,0198 0,0198 0,0198 0,0198 0,0198 0,0080 0,0011 0,0011 0,0002 0,0008 0,0008 0,0008 0,0002 0,0000 0,0000 0,0000 0,0000 instance 9 2 3 0,0301 0,0301 0,0260 0,0248 0,0248 0,0248 0,0248 0,0248 0,0248 0,0232 0,0232 0,0232 0,0165 0,0165 0,0165 0,0149 0,0149 0,0149 0,0149 0,0149 0,0149 0,0149 0,0149 0,0149 0,0065 0,0034 0,0021 0,0012 0,0003 0,0015 0,0015 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 2 4 0,0222 0,0222 0,0222 0,0219 0,0219 0,0219 0,0155 0,0050 0,0050 0,0028 0,0034 0,0034 0,0215 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0078 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,025014 0,021825 0,020701 0,018324 0,017854 0,017854 0,017427 0,016496 0,016496 0,01527 0,015225 0,015056 0,015917 0,01514 0,012811 0,011598 0,011341 0,011341 0,011079 0,010572 0,010572 0,010262 0,010572 0,010164 0,013174 0,006653 0,005295 0,003156 0,002845 0,002994 0,002714 0,002075 0,002059 0,001966 0,001959 0,001959 Pop_size election mutation cluster_size AVERAGE 30 30 30 30 30 30 30 30 30 30 30 30 50 50 50 50 50 50 50 50 50 50 50 50 100 100 100 100 100 100 100 100 100 100 100 100 RW RW RW RW RW RW RE RE RE RE RE RE RW RW RW RW RW RW RE RE RE RE RE RE RW RW RW RW RW RW RE RE RE RE RE RE I I I BS BS BS I I I BS BS BS I I I BS BS BS IIIBS BS BS I I I BS BS BS I I I BS BS BS 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 0,05 0,1 0,15 instance 9 0,8 0 0,0206 0,0206 0,0134 0,0077 0,0009 0,0009 0,0009 0,0009 0,0009 0,0009 0,0009 0,0009 0,0161 0,0161 0,0161 0,0079 0,0079 0,0079 0,0079 0,0061 0,0061 0,0000 0,0061 0,0000 0,0127 0,0127 0,0109 0,0050 0,0050 0,0050 0,0050 0,0050 0,0050 0,0041 0,0041 0,0041 instance 9 0,8 1 0,0269 0,0190 0,0190 0,0183 0,0180 0,0180 0,0180 0,0180 0,0180 0,0068 0,0056 0,0030 0,0140 0,0140 0,0028 0,0008 0,0008 0,0008 0,0008 0,0008 0,0008 0,0008 0,0008 0,0008 0,0223 0,0129 0,0058 0,0053 0,0053 0,0053 0,0028 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 0,8 2 0,0280 0,0280 0,0280 0,0157 0,0157 0,0157 0,0157 0,0157 0,0157 0,0157 0,0157 0,0157 0,0042 0,0042 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0039 0,0157 0,0147 0,0147 0,0031 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 0,8 3 0,0338 0,0181 0,0181 0,0160 0,0160 0,0160 0,0160 0,0160 0,0160 0,0160 0,0160 0,0160 0,0225 0,0214 0,0057 0,0057 0,0021 0,0021 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0181 0,0181 0,0181 0,0147 0,0147 0,0147 0,0147 0,0147 0,0147 0,0147 0,0147 0,0147 instance 9 0,8 4 0,0273 0,0228 0,0228 0,0122 0,0122 0,0122 0,0122 0,0122 0,0122 0,0122 0,0122 0,0122 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0247 0,0141 0,0064 0,0064 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 1,5 0 0,0226 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0193 0,0016 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0157 0,0056 0,0043 0,0015 0,0013 0,0018 0,0018 0,0005 0,0005 0,0000 0,0000 0,0000 instance 9 1,5 1 0,0333 0,0333 0,0333 0,0328 0,0328 0,0328 0,0328 0,0294 0,0294 0,0294 0,0294 0,0294 0,0218 0,0218 0,0211 0,0200 0,0200 0,0200 0,0189 0,0189 0,0189 0,0189 0,0189 0,0189 0,0127 0,0033 0,0005 0,0003 0,0000 0,0003 0,0003 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 1,5 2 0,0379 0,0379 0,0379 0,0379 0,0379 0,0379 0,0379 0,0379 0,0379 0,0343 0,0343 0,0343 0,0292 0,0292 0,0237 0,0199 0,0199 0,0199 0,0199 0,0199 0,0199 0,0199 0,0199 0,0199 0,0083 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 1,5 3 0,0098 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0017 0,0004 0,0004 0,0004 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 0,0052 instance 9 1,5 4 0,0133 0,0049 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0085 0,0079 0,0079 0,0079 0,0079 0,0079 0,0079 0,0079 0,0079 0,0093 0,0079 0,0079 0,0062 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 0,0054 instance 9 2 0 0,0168 0,0168 0,0168 0,0146 0,0146 0,0146 0,0146 0,0146 0,0146 0,0146 0,0146 0,0146 0,0128 0,0128 0,0112 0,0102 0,0102 0,0102 0,0102 0,0060 0,0060 0,0060 0,0060 0,0060 0,0237 0,0063 0,0011 0,0015 0,0008 0,0011 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 2 1 0,0319 0,0319 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0313 0,0226 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0196 0,0204 0,0048 0,0039 0,0039 0,0038 0,0038 0,0033 0,0001 0,0001 0,0001 0,0000 0,0000 instance 9 2 2 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0207 0,0225 0,0225 0,0225 0,0225 0,0222 0,0222 0,0214 0,0198 0,0198 0,0198 0,0198 0,0198 0,0080 0,0011 0,0011 0,0002 0,0008 0,0008 0,0008 0,0002 0,0000 0,0000 0,0000 0,0000 instance 9 2 3 0,0301 0,0301 0,0260 0,0248 0,0248 0,0248 0,0248 0,0248 0,0248 0,0232 0,0232 0,0232 0,0165 0,0165 0,0165 0,0149 0,0149 0,0149 0,0149 0,0149 0,0149 0,0149 0,0149 0,0149 0,0065 0,0034 0,0021 0,0012 0,0003 0,0015 0,0015 0,0000 0,0000 0,0000 0,0000 0,0000 instance 9 2 4 0,0222 0,0222 0,0222 0,0219 0,0219 0,0219 0,0155 0,0050 0,0050 0,0028 0,0034 0,0034 0,0215 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0161 0,0078 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,025014 0,021825 0,020701 0,018324 0,017854 0,017854 0,017427 0,016496 0,016496 0,01527 0,015225 0,015056 0,015917 0,01514 0,012811 0,011598 0,011341 0,011341 0,011079 0,010572 0,010572 0,010262 0,010572 0,010164 0,013174 0,006653 0,005295 0,003156 0,002845 0,002994 0,002714 0,002075 0,002059 0,001966 0,001959 0,001959 Pop_size election mutation cluster_size AVERAGE Anexo 90 Resultados comparación algoritmos: Tabla 13: Resultados comparación algoritmos OT OT BT BT GA IM GA IM instance 3 0,75 0 0,085305 0,1886675 0,04171856 0 instance 3 0,75 1 0,034513 0,05133736 0 0,02286454 instance 3 0,75 2 0,088794 0,09308022 0 0,03000612 instance 3 0,75 3 0,04093 0,02325581 0,01581395 0 instance 3 0,75 4 0 0 0,01913171 0,00220751 instance 3 1,5 0 0,035622 0,02337662 0,00185529 0 instance 3 1,5 1 0,010705 0 0,01033592 0,00147656 instance 3 1,5 2 0,025382 0,04520167 0,01147427 0 instance 3 1,5 3 0,059487 0,02682737 0,01166407 0 instance 3 1,5 4 0,026561 0,10911701 0,01938263 0 instance 3 2 0 0,025 0,0403125 0 0,015625 instance 3 2 1 0,060728 0,03161857 0,01204517 0 instance 3 2 2 0,046239 0,03131402 0,04067896 0 instance 3 2 3 0,005358 0,03382451 0 0,00200938 instance 3 2 4 0,020155 0,06012765 0 0,00268727 instance 9 0,75 0 0,080623 0,08666357 0 0,00046468 instance 9 0,75 1 0,062712 0,01549637 0,02348668 0 instance 9 0,75 2 0,004338 0 0,02449604 0,01735137 instance 9 0,75 3 0,077362 0,03141225 0 0,00597092 instance 9 0,75 4 0,038817 0,04959951 0 0,00030807 instance 9 1,5 0 0,080244 0,07215725 0,02550386 0 instance 9 1,5 1 0,086855 0,01382965 0,02313558 0 instance 9 1,5 2 0,100352 0 0,00229463 0,02768854 instance 9 1,5 3 0,036507 0 0,00988302 0,00766438 instance 9 1,5 4 0,055148 0,00701307 0 0,00669429 instance 9 2 0 0,025965 0,00209044 0,02596545 0 instance 9 2 1 0,031398 0,02066862 0,01976508 0 instance 9 2 2 0,020334 0,01752951 0,03716256 0 instance 9 2 3 0,06825 0,05742634 0,03908599 0 instance 9 2 4 0,00379 0 0,02481663 0,00317848 0,047622 0,01317307 0,02023433 0,00502508 MIN AVERAGE Start Type 91 Resultados experimentación: Tabla 14: Resultados experimentación GSA LS_GS PE TC instance 3 0,75 0 0,00229 0,02442748 0,00687023 0 0,00381679 instance 3 0,75 1 0,001868 0,001868 0 0,03985056 0,01556663 instance 3 0,75 2 0,011218 0,00694444 0,00694444 0 0,01121795 instance 3 0,75 3 0,010665 0,01505646 0 0,01066499 0,03074028 instance 3 0,75 4 0,034853 0,03485255 0,0357462 0,02680965 0 instance 3 0,75 5 0 0 0,00632022 0 0,00561798 instance 3 0,75 6 0,025489 0,0112626 0,0112626 0 0,01007706 instance 3 0,75 7 0,003313 0,00331309 0 0,02650469 0,00828272 instance 3 0,75 8 0,008796 0 0,00879567 0 0 instance 3 0,75 9 0,020571 0 0,0066357 0,01658925 0,0199071 instance 3 0,75 10 0,019204 0,01028807 0 0,00891632 0,01783265 instance 3 0,75 11 0,002044 0,04291553 0 0,03269755 0,02792916 instance 3 0,75 12 0,013313 0,01280082 0,01280082 0 0,01075269 instance 3 0,75 13 0 0,03712721 0,06208156 0,03104078 0,00121729 instance 3 0,75 14 0 0,01043585 0,01043585 0 0 instance 3 0,75 15 0,029917 0,00441393 0 0,00245218 0,00882786 instance 3 0,75 16 0,038719 0,00744602 0,03127327 0,03127327 0 instance 3 0,75 17 0,027065 0,00624566 0 0,01249133 0,01318529 instance 3 0,75 18 0,021854 0,05275057 0 0,03165034 0,01808591 instance 3 0,75 19 0,048091 0,00353607 0 0,02475248 0,01202263 instance 3 0,75 20 0,021415 0,03634004 0 0,04347826 0,01946788 instance 3 0,75 21 0,054966 0,02935665 0 0,05246721 0,03685197 instance 3 0,75 22 0,008621 0,0393319 0 0,01993534 0,01346983 instance 3 0,75 23 0,084577 0,08159204 0,05671642 0 0,03283582 instance 3 0,75 24 0,010536 0,0105364 0,01245211 0,02011494 0 instance 3 0,75 25 0,010321 0,05103211 0,0315367 0 0,04013761 instance 3 0,75 26 0,016857 0,01685731 0 0,01083685 0,01083685 instance 3 0,75 27 0 0,0420354 0,03687316 0,0140118 0,02654867 instance 3 0,75 28 0,056264 0,024006 0 0,03450863 0,00825206 instance 3 0,75 29 0,002357 0 0 0 0 instance 3 1,5 0 0 0,02237049 0,00745683 0,02040816 0,02708006 instance 3 1,5 1 0 0,01851852 0 0,0141844 0,02600473 instance 3 1,5 2 0,023091 0,0008881 0 0,01776199 0,03596803 instance 3 1,5 3 0,04988 0,07102953 0 0,07382283 0,07023144 instance 3 1,5 4 0,021954 0 0,03627108 0,001909 0,03722558 instance 3 1,5 5 0 0,04206433 0,02509721 0,02474373 0,04100389 instance 3 1,5 6 0,009207 0 0,02481986 0,0236189 0,03522818 instance 3 1,5 7 0,016026 0,00549451 0 0,00595238 0,01236264 instance 3 1,5 8 0,022276 0 0,01884853 0,02193283 0,02398903 instance 3 1,5 9 0,013061 0,01784937 0 0,03831084 0,01959077 instance 3 1,5 10 0,060592 0 0,03416856 0,04191344 0,06560364 instance 3 1,5 11 0,066204 0,01441538 0 0,04431393 0,0565937 instance 3 1,5 12 0 0,00445164 0,02873331 0,00687981 0,01821125 instance 3 1,5 13 0,035793 0 0,04821037 0,00693937 0,02629657 instance 3 1,5 14 0,026848 0 0,02217899 0,04980545 0,05719844 instance 3 1,5 15 0 0,01052285 0,01940151 0,01479776 0,02926669 instance 3 1,5 16 0,050441 0,05296343 0 0,05254309 0,06935687 instance 3 1,5 17 0,003577 0,04813008 0 0,04878049 0,04292683 instance 3 1,5 18 0,016017 0,0043684 0,00509647 0 0,03094285 instance 3 1,5 19 0,045304 0,03670635 0 0,03869048 0,04695767 instance 3 1,5 20 0 0,01657459 0,00103591 0,03314917 0,02486188 instance 3 1,5 21 0 0,01147776 0,03299857 0,04985653 0,0233142 instance 3 1,5 22 0 0,00238436 0,01812113 0,02145923 0,02288984 instance 3 1,5 23 0,001719 0 0,02005731 0,01833811 0,02750716 instance 3 1,5 24 0,017109 0,01497006 0 0,00128315 0,01454234 instance 3 1,5 25 0 0,01694232 0,0104881 0,00161355 0,02299314 instance 3 1,5 26 0,03113 0,01918977 0 0,0217484 0,03752665 instance 3 1,5 27 0,032356 0,01061678 0 0,01263903 0,02831143 instance 3 1,5 28 0,037122 0,05243016 0 0,01033295 0,02908534 instance 3 1,5 29 0,055175 0,03122327 0 0,05688623 0,06116339 Type instance 3 2 0 0,016769 0 0,01872554 0,04639463 0,0410844 instance 3 2 1 0 0,00646204 0,01292407 0,03352181 0,02221325 instance 3 2 2 0 0,01266439 0,00487092 0,01509985 0,01680468 instance 3 2 3 0,042153 0,01025349 0 0,04443179 0,02905155 instance 3 2 4 0 0,00149533 0,02317757 0,02579439 0,01308411 instance 3 2 5 0,00981 0,02373418 0 0,00158228 0,01012658 instance 3 2 6 0,025757 0,00354153 0,00482936 0 0,02221507 instance 3 2 7 0,009401 0,0269508 0 0,00094014 0,03979944 instance 3 2 8 0,000655 0 0,02586771 0,02685003 0,02455796 instance 3 2 9 0 0,04246285 0,03269639 0,03312102 0,03609342 instance 3 2 10 0 0,03993155 0,00998289 0,01169424 0,02196235 instance 3 2 11 0,015546 0 0,01375187 0,01943199 0,03348281 instance 3 2 12 0 0,02877044 0,03270745 0,05057541 0,03452453 instance 3 2 13 0,014261 0,00695652 0 0,0306087 0,01008696 instance 3 2 14 0 0,00216685 0,01056338 0,00189599 0,02031419 instance 3 2 15 0,040015 0,05609574 0 0,03964099 0,04899028 instance 3 2 16 0 0,04075738 0,03145058 0,01732991 0,0304878 instance 3 2 17 0,037373 0 0,028292 0,01571778 0,04191408 instance 3 2 18 0 0,00412159 0,0015456 0,03812468 0 instance 3 2 19 0 0,02610565 0,02395577 0,0230344 0,0230344 instance 3 2 20 0,000316 0,02937461 0 0,02716361 0,02242577 instance 3 2 21 0,0108 0,03531816 0 0,02597782 0,04874489 instance 3 2 22 0,013546 0,00347343 0 0,02014588 0,02744008 instance 3 2 23 00000 instance 3 2 24 0 0,02117061 0,0239726 0,05354919 0,01681196 instance 3 2 25 0,004829 0,00931356 0,00172473 0,03621939 0 instance 3 2 26 0,033996 0,02820976 0,02495479 0 0,03942134 instance 3 2 27 0,01018 0,00928144 0 0,01646707 0,01317365 instance 3 2 28 0,005716 0,03108253 0 0,00643087 0,02893891 instance 3 2 29 0,001922 0,00512656 0 0,03075937 0,02787568 instance 9 0,75 0 0 0,010961 0,02141218 0,01988274 0,01580423 instance 9 0,75 1 0 0,02099533 0,03499222 0,00622084 0,03628823 instance 9 0,75 2 0,031565 0 0,05763952 0,042086 0,04620311 instance 9 0,75 3 0,002014 0,01835273 0,01902417 0 0,00962399 instance 9 0,75 4 0,03501 0 0,01597553 0,02855201 0,03602991 instance 9 0,75 5 0,010476 0 0,02349206 0,03269841 0,01714286 instance 9 0,75 6 0,016173 0 0,02339986 0,01410874 0,01720578 instance 9 0,75 7 00000 instance 9 0,75 8 0 0,01448838 0,00422578 0,0153939 0,01207365 instance 9 0,75 9 0,02009 0,01665345 0,04837431 0 0,03013481 instance 9 0,75 10 0,009104 0 0,01697835 0,01599409 0,00885827 instance 9 0,75 11 0,004203 0,01230862 0,01020715 0 0,01531072 instance 9 0,75 12 0,012408 0 0,01917654 0,01692047 0,01579244 instance 9 0,75 13 0,043035 0 0,04875622 0,05845771 0,02960199 instance 9 0,75 14 0,025007 0 0,0437614 0,01198229 0,02318312 instance 9 0,75 15 0,01846 0 0,01903663 0,01442169 0,03403519 instance 9 0,75 16 0,024203 0 0,04958678 0,03896104 0,03099174 instance 9 0,75 17 0,03311 0 0,02102908 0,0639821 0,0049217 instance 9 0,75 18 0,011789 0,00523972 0 0,03903589 0,02331674 instance 9 0,75 19 0,017774 0,01048951 0 0,04050117 0,01864802 instance 9 0,75 20 0 0,00572012 0,06680286 0,02308478 0,03493361 instance 9 0,75 21 0,026422 0 0,0390941 0,00781882 0,02938798 instance 9 0,75 22 0 0,00399886 0,00428449 0,01199657 0,02227935 instance 9 0,75 23 0,036533 0 0,01609907 0,03931889 0,02569659 instance 9 0,75 24 0 0,00178845 0,01992846 0,03142565 0,02376086 instance 9 0,75 25 0,029889 0 0,03382762 0,04587581 0,02085264 instance 9 0,75 26 0,041182 0,02326664 0,07142857 0 0,05490926 instance 9 0,75 27 0,001263 0 0,03630051 0,02241162 0,0407197 instance 9 0,75 28 0,005379 0 0,00537857 0,0057923 0,0103434 instance 9 0,75 29 0,01372 0,03351327 0,03418803 0 0,04880792 instance 9 1,5 0 0,003142 0,01085249 0,03769813 0 0,00971012 instance 9 1,5 1 0,013371 0 0,03673469 0,01970443 0,00731879 instance 9 1,5 2 0 0,00029913 0,00837571 0,02049058 0,01405923 instance 9 1,5 3 0,013164 0,00014626 0,04738921 0 0,04139242 instance 9 1,5 4 0,036649 0 0,06757199 0,02568717 0,04139398 instance 9 1,5 5 0 0,00453446 0,04610036 0,03461306 0,02252116 instance 9 1,5 6 0,000284 0 0,05467973 0,00610709 0,03351797 instance 9 1,5 7 0 0,03319825 0,0451995 0,03912095 0,05595387 instance 9 1,5 8 0,003985 0 0,04269247 0,02675395 0,04454248 instance 9 1,5 9 0 0,00349701 0,0327845 0,00888824 0,0295789 instance 9 1,5 10 0,031082 0 0,05620915 0,01989833 0,05272331 instance 9 1,5 11 0,021419 0 0,06374194 0,01677419 0,0436129 instance 9 1,5 12 0 0,02198492 0,06708543 0,01432161 0,04082915 instance 9 1,5 13 0,003716 0,00312128 0,02170036 0,00222949 0 instance 9 1,5 14 0 0,00602916 0,03323051 0,00897364 0,03266966 instance 9 1,5 15 0 0,00525855 0,02917241 0,03756104 0,02704395 instance 9 1,5 16 0 0,02781237 0,0567317 0,05008994 0,05327245 instance 9 1,5 17 0,017328 0,0077389 0,03886272 0 0,0282638 instance 9 1,5 18 0,008043 0 0,04368326 0,01594786 0,02399112 instance 9 1,5 19 0,008318 0 0,06792976 0,04544054 0,04004929 instance 9 1,5 20 0,010363 0,00719632 0,04562464 0 0,02677029 instance 9 1,5 21 0,020865 0 0,04520714 0,01390989 0,03054128 instance 9 1,5 22 0,001515 0 0,03272727 0,02151515 0,02151515 instance 9 1,5 23 0,007554 0 0,03640867 0,01547988 0,03343653 instance 9 1,5 24 0,041072 0,02695845 0,04123057 0 0,06359023 instance 9 1,5 25 0,020438 0 0,0501522 0,04841281 0,05160168 instance 9 1,5 26 0,023163 0 0,06993318 0,03801039 0,03830735 instance 9 1,5 27 0 0,01311239 0,06340058 0,02291066 0,05893372 instance 9 1,5 28 0 0,01809097 0,04531358 0,01085458 0,02618884 instance 9 1,5 29 0 0,03921289 0,08398688 0,03522031 0,05375731 instance 9 2 0 0 0,02586207 0,0655426 0,07581136 0,06034483 instance 9 2 1 0 0,00474703 0,03260462 0,00237352 0,02648345 instance 9 2 2 0,000114 0 0,02059627 0,00682749 0,02344106 instance 9 2 3 0 0,00291606 0,03384712 0,00239533 0,02739013 instance 9 2 4 0 0,02151795 0,0381242 0,05473044 0,0126301 instance 9 2 5 0 0,01603994 0,04408328 0,02825579 0,03728489 instance 9 2 6 0,051113 0,01167658 0,05177352 0 0,04758757 instance 9 2 7 0 0,03771949 0,05072621 0,02991546 0,03826144 instance 9 2 8 0,007474 0 0,03642188 0,02159212 0,02218531 instance 9 2 9 0,035631 0 0,04876463 0,0260078 0,02418726 instance 9 2 10 0,017017 0 0,04126349 0,0229118 0,02469136 instance 9 2 11 0,006199 0 0,03984946 0,01295107 0,03021917 instance 9 2 12 0,020217 0 0,02699345 0,01524735 0,02021685 instance 9 2 13 0 0,00861273 0,06028914 0,01640521 0,04162822 instance 9 2 14 0 0,02238523 0,06399393 0,05286455 0,01707348 instance 9 2 15 0,015792 0,00613417 0,04907335 0,00600365 0 instance 9 2 16 0 0,00477612 0,00298507 0,00585075 0,0198209 instance 9 2 17 0,016877 0 0,0557161 0,02658652 0,02982314 instance 9 2 18 0,023686 0 0,05177081 0,030679 0,04680803 instance 9 2 19 0,036086 0 0,07255683 0,05072557 0,06472326 instance 9 2 20 0 0,01614196 0,07006297 0,04876932 0,05861477 instance 9 2 21 0 0,02196889 0,05391284 0,02565016 0,04239401 instance 9 2 22 0,003005 0 0,02323431 0,01837938 0,03525604 instance 9 2 23 0,022563 0 0,07181308 0,04856259 0,05016607 instance 9 2 24 0,008011 0,0088603 0,04296638 0 0,04041753 instance 9 2 25 0 0,04131001 0,08038705 0,04800893 0,06128272 instance 9 2 26 0,019054 0 0,05993691 0,02258675 0,04302839 instance 9 2 27 0 0,01705147 0,05994493 0,02488879 0,03463249 instance 9 2 28 0,029544 0 0,05562608 0,04258511 0,03923832 instance 9 2 29 0 0,0138234 0,05325761 0,03011144 0,03536219 0,011852 0,00764848 0,04082307 0,02270574 0,03154597 MIN AVERAGE