Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados

5 Equation Chapter 1 Section 1 Trabajo Fin de Grado Ingeniería de las Tecnologías Industriales Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados Autor: María Eugenia Fernández Ramírez Tutor: Víctor Fernández-Viagas Escudero Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2023 iii Trabajo Fin de Grado Ingeniería de las Tecnologías Industriales Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados Autor: María Eugenia Fernández Ramírez Tutor: Víctor Fernández-Viagas Escudero Profesor titular Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2023 v Trabajo Fin de Grado: Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados Autor: María Eugenia Fernández Ramírez Tutor: Víctor Fernández-Viagas Escudero El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2023 El Secretario del Tribunal vii Agradecimientos A mi familia, a Ramón y a Eu.. ix Resumen El objetivo de este trabajo es abordar tanto la programación como la planificación de un hospital de referencia real, con el fin de minimizar una función objetivo. Esta función representa el retraso total en la atención de los pacientes con respecto a unos tiempos máximos de respuesta. Mediante la minimización de la función objetivo, se minimiza el retraso promedio de la atención hospitalaria y se promueve, en consecuencia, un aumento de la calidad de vida de la población. Para programar la producción, es decir, establecer las fechas en las que cada paciente será atendido, los cirujanos que lo harán, y las consultas y quirófanos en que se realizará la consulta o intervención, se propone un Algoritmo Genético que, dados unos datos del problema, proporciona una secuencia de intervenciones satisfactoria. Para planificar la producción, concretamente, hallar una adecuada distribución de quirófanos y consultas entre las unidades hospitalarias, se propone un Algoritmo Extendido, que realiza una búsqueda similar a la del algoritmo de mejora local. ÍNDICE DE FIGURAS Figura 1-1. Diagrama de Gantt de la producción de un sistema híbrido (Framinan et al., 2014). 3 Figura 1-2. Diagrama de Gantt de la producción de un sistema híbrido con dos tipos de máquinas. 4 Figura 3-1. Esquema del funcionamiento de la decodificación de la solución. 13 Figura 4-1. Exploración y explotación del espacio de búsqueda de una metaheurística. 21 Figura 4-2. Escapada de un óptimo local mediante una metaheurística. 21 Figura 4-3. Carácter iterativo del Algoritmo Genético. 22 Figura 4-4. A la izquierda, población inicial de un problema cuya solución es una cadena de 7 celdas azules o naranjas. A la derecha, población inicial de un problema cuya solución es una cadena de 7 caracteres que contienen los números del 1 al 7. 22 Figura 4-5. Ejemplo de las reglas de despacho EDD y SPT. 23 Figura 4-6. Ejemplo de vecinos por Intercambio Adyacente, Intercambio General e Inserción. 24 Figura 4-7. Ejemplo de la selección por torneo determinista de un padre en un problema de minimización. 25 Figura 4-8. Ejemplo de la selección por torneo probabilístico de un padre en un problema de minimización. 26 Figura 4-9. Ejemplo de selección por ruleta en un problema de maximización. 27 Figura 4-10. Ejemplo de selección por ruleta en un problema de minimización. 28 Figura 4-11. Arriba, ejemplo del operador de cruce monopunto. Abajo, ejemplo del operador de cruce multipunto. 29 Figura 4-12. Ejemplo inválido del operador de cruce monopunto. 29 Figura 4-13. Ejemplo del operador de cruce para representación de orden. 30 Figura 4-14. Ejemplo del operador de cruce para representación de orden con dos puntos de cruce. 30 Figura 4-15. A la izquierda, ejemplo de mutación por intercambio de pares. A la derecha, ejemplo de mutación por inserción. 31 Figura 6-1. Esquema del funcionamiento del Algoritmo Genético. 35 Figura 6-2. Ejemplo de solución inicial. 41 Figura 7-1. Primera parte de la Hoja de Pacientes de una instancia en formato .xlsx. 51 Figura 7-2. Segunda parte de la Hoja de Pacientes de una instancia en formato .xlsx. 52 Figura 7-3. Hoja de Cirujanos de una instancia en formato .xlsx. 52 Figura 7-4. Hoja de Datos de una instancia en formato .xlsx. 52 Figura 7-5. Excel con los resultados obtenidos. 54 xvii 1 1 INTRODUCCIÓN ste trabajo afronta un problema vigente en el entorno sanitario y lo aborda como si se tratara de un problema de organización de la producción. De entrada, podría no verse claramente la relación existente entre un sistema de producción y un hospital. En este capítulo, se expondrán las similitudes que hacen comparables a ambos sistemas, para posteriormente aplicar fundamentadamente la teoría de los sistemas de producción al hospital. 1.1 Organización de la producción Se entiende por organización de la producción el proceso de toma de decisiones destinadas a garantizar la distribución de productos con máxima calidad, mínimo coste, y mínimo tiempo de elaboración (en inglés, lead time) (Framinan et al., 2014). Dichas decisiones se clasifican en tres grupos según el impacto que tendrán en la empresa y el período de tiempo durante el cual se aplicarán. - Decisiones estratégicas o de planificación: aquellas que sirven para establecer la capacidad de producción y de distribución de los recursos (Framinan et al., 2014). Estas decisiones, tomadas generalmente por los altos directivos de la empresa, tienen un enorme impacto en la misma, y solo pueden ser revisadas en un horizonte temporal de años, debido a su gran envergadura. La selección de productos a fabricar y de proveedores, y la localización y el diseño de la planta son algunas decisiones estratégicas. - Decisiones tácticas: aquellas que sirven para repartir eficientemente los recursos limitados a medio plazo. La información clave para tomar estas decisiones puede estimarse gracias a los datos históricos y a la propia experiencia. El impacto de las decisiones tácticas sobre la empresa es medio, menor que el de las decisiones estratégicas y mayor que el de las operativas, y el horizonte temporal en el que pueden revisarse es de meses. Algunas decisiones tácticas son la elección de contratos con los proveedores, la mano de obra requerida y la distribución en planta (Morera et al., 2012). - Decisiones operacionales: aquellas que sirven para repartir eficientemente los recursos limitados a corto plazo. Al igual que en el caso de las decisiones tácticas, la información utilizada para poder tomar estas decisiones se estima a partir de los datos históricos y de la experiencia. Sin embargo, es evidente que la calidad de la estimación disminuye con el nivel de detalle (Framinan et al., 2014). Por ejemplo, la estimación de las ventas anuales de un cierto modelo de coche será más acertada que la estimación de las ventas semanales de dicho modelo. Por consiguiente, la toma de decisiones tácticas podrá fundamentarse en la información estimada con mayor confianza que la toma de decisiones operacionales, ya que estas últimas programan la producción en el corto plazo. Las decisiones operativas tienen menor impacto que las estratégicas y las tácticas, y pueden ser revisadas en un horizonte temporal de días. Algunos ejemplos pueden ser la asignación de trabajos a los recursos disponibles y el inventario. Se ha hecho referencia en el primer párrafo a la persecución de la máxima calidad, el mínimo coste y el mínimo tiempo de elaboración. Efectivamente, el decisor racional identifica y enumera las alternativas E Introducción 2 posibles, analiza las consecuencias derivadas de cada una, y valora y compara dichas consecuencias (Morera et al., 2012), para elegir finalmente la alternativa óptima. Sin embargo, a la hora de gestionar la producción, es en muchos casos más eficiente aceptar una solución sencillamente satisfactoria, en lugar de perseguir aquella óptima. La razón es que la cantidad de alternativas es tan vasta, que hallar la óptima significaría invertir un tiempo desproporcionado para obtener un resultado con una mejora del objetivo poco significativa. En el presente trabajo se presentará un método para abordar la toma de decisiones operacionales y tácticas de un hospital. Para comenzar, es necesario evidenciar las similitudes del hospital, y en general del entorno sanitario, con los sistemas productivos. 1.2 Los sistemas productivos y el entorno sanitario Un sistema productivo es una estructura organizativa cuyo principal objetivo es la creación de valor. Para conseguirlo, necesita utilizar y combinar una serie de factores productivos que dan lugar a los productos necesarios para alcanzar el objetivo propuesto. En el sistema sanitario, la creación de valor se traduce en una mejora de la salud de la población o un aumento de la calidad de vida del paciente (Gorgemans & Urbina, 2017). En un sistema productivo, entran los trabajos (en inglés, jobs) en forma de producto inicial y, tras ser sometidos a un proceso de transformación llevado a cabo por las máquinas (en inglés, machines), salen del sistema en forma de producto final. Más concretamente, en un entorno híbrido, que es el que más se asemeja al sistema de un hospital, cada trabajo debe pasar por un número de etapas o fases, y en cada una de ellas hay un número de máquinas que realizan la transformación. En el sistema sanitario, los trabajos se identifican con los pacientes, que entran al sistema en forma de pacientes enfermos y salen de él como pacientes sanos. Las fases del entorno híbrido son las etapas por las que debe pasar el paciente en el proceso médico-quirúrgico: la consulta inicial, la intervención quirúrgica y la consulta postoperatoria. Las máquinas que intervienen en cada etapa para llevar a cabo el proceso de recuperación del paciente se identifican con los recursos necesarios para tratar al enfermo. Es evidente que entre estos recursos se encuentran los médicos y cirujanos, pero también las consultas y los quirófanos en los que se debe atender al paciente. Los sistemas de producción se caracterizan también por la necesidad de planificación y programación. La programación de la producción implica la toma de decisiones operacionales con el objetivo de establecer en el corto plazo cuándo debe comenzar cada máquina a procesar cada trabajo (Pérez et al., 2018). La información cuantitativa proporcionada por un programa de la producción puede ser representada de manera gráfica, a través de un Diagrama de Gantt. De este modo, se facilita la visualización de la secuenciación, simultaneidad y relaciones de duración entre trabajos, así como el equilibrio presente en la utilización de los recursos. En la Figura 1-1 se puede ver un Diagrama de Gantt, que es resultado de la programación de un entorno híbrido, en el que cada fase está compuesta por máquinas paralelas. En él se especifica en qué momento (eje X) debe cada trabajo empezar a ser tratado por cada máquina (eje Y). 3 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados Figura 1-1. Diagrama de Gantt de la producción de un sistema híbrido (Framinan et al., 2014). Del mismo modo, en el sistema sanitario es necesario programar la atención a los pacientes. La programación en este caso incluye establecer las fechas concretas en que cada paciente será atendido en cada etapa, así como el cirujano que llevará a cabo esta consulta o intervención, y la consulta médica o quirófano en que se realizará. Tanto en un sistema productivo como en el sistema sanitario, la programación debe realizarse con una finalidad, que viene definida por una función objetivo a minimizar o maximizar. Si no existiera una función objetivo, la programación perdería importancia, ya que cualquier secuencia viable de trabajos sería igualmente válida. En un sistema de producción, la función objetivo puede consistir, por ejemplo, en minimizar el tiempo total de flujo de trabajos (en inglés, total flowtime), es decir, el tiempo total que los trabajos están en el sistema, o en minimizar el tiempo máximo de terminación de los trabajos (en inglés, makespan), o sea, el instante en el que termina el último trabajo. En un sistema sanitario, la función objetivo puede ser muy similar. Por ejemplo, minimizar el tiempo total de flujo de trabajos podría ser la función objetivo de un hospital cuya máxima fuera que cada paciente estuviera el menor tiempo posible enfermo. En cambio, minimizar el tiempo máximo de terminación de los trabajos podría ser la función objetivo de un hospital cuya finalidad es terminar de atender a los pacientes lo antes posible para poder dedicar el resto del tiempo a otros asuntos. En cualquier caso, la función objetivo debe estar definida para poder realizar una programación con el propósito de minimizarla (o maximizarla si fuera el caso). También la planificación de un sistema de producción debe realizarse con el objetivo de optimizar el valor de la función objetivo. La planificación, a diferencia de la programación, consiste en la toma de decisiones tácticas y estratégicas a largo plazo para definir los recursos necesarios y la capacidad de producción. Si bien se entiende fácilmente que estrategias como invertir en maquinaria especializada pueden mejorar funciones objetivo relacionadas con los tiempos de producción, otras decisiones pueden ser más complicadas de tomar. Por ejemplo, en un entorno híbrido en el que el número total de máquinas paralelas que puede haber en cada fase se conoce, y cada trabajo solo puede ser tratado por máquinas de un tipo concreto, es necesario decidir cuántas máquinas de cada tipo debe haber en cada fase. Esta decisión se toma al planificar la producción, y no al programarla, ya que es inalterable en el medio o largo plazo. Para decidir esta cuestión, se utiliza de nuevo la función objetivo, y se toma como mejor decisión aquella que la optimice. En la Figura 1-2 puede verse un ejemplo de la programación de la producción realizada una vez tomadas las decisiones tácticas y estratégicas que comprenden la planificación. Introducción 4 Figura 1-2. Diagrama de Gantt de la producción de un sistema híbrido con dos tipos de máquinas. En el sistema sanitario también hay que planificar la atención a los pacientes en el largo plazo. Más allá de establecer una fecha, un médico y una consulta o quirófano para el enfermo, hay que tomar decisiones tácticas y estratégicas de carácter mucho más permanente. Por ejemplo, en línea con el ejemplo anterior de planificación de la producción, el hospital cuenta con un número de consultas y quirófanos concretos, y corresponde a la planificación asignar cada uno de ellos a las distintas unidades hospitalarias. Una distribución de quirófanos y consultas será mejor que otra si ofrece un mejor resultado de la función objetivo. En conclusión, la necesidad común de programación y planificación para optimizar una función objetivo, la identificación de trabajos como pacientes y la equiparación de máquinas con cirujanos, consultas y quirófanos, permite tratar al sistema sanitario como un sistema de producción. 5 2 PRESENTACIÓN DEL PROBLEMA l presente trabajo trata un problema actual de un hospital de referencia real cuyo nombre no se especifica por cuestiones de confidencialidad. El objetivo de este proyecto es presentar una metodología para facilitar la toma de decisiones operacionales y tácticas. Concretamente, se propondrán una serie de Algoritmos Genéticos que permitan secuenciar satisfactoriamente las intervenciones de una lista de espera (decisión operacional), así como un Algoritmo Extendido para encontrar una distribución aceptable de consultas y quirófanos a cada una de las unidades médicas del hospital (decisión táctica). Aplicando estos algoritmos en la toma de decisiones del hospital, se puede acabar con los desequilibrios en la adjudicación de recursos a las distintas unidades, con el fin de conseguir una mejor atención a todos los pacientes. Esta mejora en la atención se verá reflejada en la minimización de una función objetivo concreta, que se presentará posteriormente. 2.1 Descripción del entorno Cada día, el hospital en cuestión atiende a pacientes con afecciones y síntomas muy diversos. Como la mayoría de los hospitales, posee distintas unidades, entendidas como secciones hospitalarias donde se concentran aparatos y personal especializados para el tratamiento de enfermos con dolencias de carácter similar. Por ejemplo, el hospital tiene una unidad de pediatría, una de cardiología, una de dermatología, etc., donde se trata a los pacientes que lo necesitan. Cuando un paciente que afirma necesitar un médico entra al sistema del hospital, se le asigna una unidad responsable y se incorpora a una lista de espera que le conducirá a una sucesión de tres etapas: consulta PAE, intervención quirúrgica y consulta postoperatoria. - Consulta PAE (Primera Atención Especializada): se trata de una consulta inicial realizada por un cirujano de la unidad para evaluar al paciente y confirmar la necesidad de intervención quirúrgica. Existe un tiempo máximo de respuesta genérico, desde la entrada al sistema hasta la ejecución del PAE, que no se debe superar. A lo largo del trabajo, se hará referencia a esta etapa como PAE. - Intervención quirúrgica: llevada a cabo en un quirófano por un cirujano responsable y un cirujano asistente de la unidad. Existe un tiempo máximo de respuesta genérico entre el PAE y la intervención quirúrgica que no se debe superar. En posteriores alusiones a esta etapa, se utilizará el término OR, debido a la necesidad de llevar a cabo esta fase en un quirófano, que en inglés es operating room. - Consulta postoperatoria: se trata de una consulta final en la que un cirujano de la unidad revisa el resultado de la intervención y comprueba que no hay imprevistos. Una vez finalizada esta consulta, el paciente está curado y abandona el sistema del hospital. Existe un tiempo máximo de respuesta genérico entre la intervención y el POST que no se debe superar. Para hacer referencia a esta etapa, se utilizará el término POST. Por otro lado, pueden entrar al sistema pacientes que solo requieren una consulta genérica, es decir, una E Presentación del Problema 6 consulta única que no va seguida de intervención quirúrgica. La programación y planificación de estas consultas queda fuera del alcance de este trabajo, sin embargo, es esencial tenerlas en cuenta, ya que afectan a la disponibilidad de los cirujanos. Para modelar las consecuencias de esta faceta del hospital, se reducirá la disponibilidad de los cirujanos. 2.2 Objetivo del problema El objetivo de este trabajo es minimizar el retraso total (en inglés, total tardiness) del problema, que es la suma de los días de demora de todas las etapas de cada intervención en el horizonte de planificación. La minimización de los días totales de retraso se traduce en la minimización de la media aritmética de los retrasos. Los días de demora se calculan a partir del tiempo máximo de respuesta de cada una de las etapas. Es importante recalcar que este dato no es una fecha de entrega, sino un intervalo de tiempo entre una etapa y la precedente que no se debe superar. Es decir, si el tiempo máximo de respuesta del OR es de 10 días, y el PAE se realizó en el día 4, el OR no debería realizarse después del día 14. A partir del día 15, el retraso de esa intervención y de esa etapa se hace positivo e incrementa con cada día que pase. En el subcapítulo 3.2. Cálculo de la función objetivo, se presentará el cálculo matemático de la función objetivo, para el que hay que tener en cuenta factores como la etapa en la que la intervención entra al sistema y el horizonte de planificación. Como idea principal, el retraso de la etapa i de la intervención j es simplemente el número de días que dicha etapa se ha retrasado con respecto a su tiempo máximo de respuesta. Una vez se haya definido claramente la función objetivo, esta se tratará de minimizar mediante la aplicación de algoritmos a la programación y la planificación del sistema. 2.3 Restricciones del problema Hay algunas consideraciones genéricas que se han asumido a la hora de elaborar el modelo del hospital, para la correspondencia correcta de este con la realidad. Son las siguientes: - Todo paciente tiene que pasar por el proceso médico-quirúrgico PAE-OR-POST. - El tiempo de respuesta del PAE se inicia cuando el paciente entra al sistema. - El tiempo de respuesta del OR se inicia en el instante de finalización del PAE. - El tiempo de respuesta del POST se inicia en el instante de finalización del OR. - Existen consultas genéricas a las que cada cirujano debe dedicar parte de su disponibilidad. - Todas las consultas PAE tienen la misma duración y el mismo tiempo máximo de respuesta genérico. - Todas las consultas POST tienen la misma duración y el mismo tiempo máximo de respuesta genérico. - Todos los pacientes deben esperar el mismo tiempo mínimo genérico requerido entre la consulta PAE y la intervención OR. - Todos los pacientes deben esperar el mismo tiempo mínimo genérico requerido entre la intervención OR y la consulta POST. - No hay condicionante para decidir qué cirujano realizará las consultas PAE y POST. - El OR lo realizan un cirujano responsable y un cirujano asistente que poseen el nivel de habilidad requerido. - Cada cirujano puede estar asignado en un día a consultas o a quirófanos, pero no a ambos. - Cuando un cirujano está asignado a consultas, puede realizar tanto consultas PAE como POST. - Cada cirujano pertenece a una unidad. 7 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados - Cada intervención está asignada a una unidad, y solo pueden ser realizada por un cirujano de esta. - Cada consulta y cada quirófano pertenece a una unidad, y en ellos solo se pueden realizar consultas e intervenciones de esta. 2.4 Datos del problema Los datos del problema son toda aquella información que el hospital posee y que es necesaria para que el modelo funcione. Para analizarlos, a continuación se distingue entre los recursos y los trabajos. 2.4.1 Recursos Los recursos son los medios disponibles para resolver una necesidad. En este problema, los recursos de los que se dispone para llevar a cabo las tres etapas (PAE, OR y POST) son los cirujanos, las consultas y los quirófanos. Los dos últimos son los que pueden asignarse a una unidad u otra para minimizar la función objetivo. Cada cirujano pertenece a una unidad, por lo que solo podrá participar en el PAE, OR y POST de pacientes de esta. Es decir, un cirujano de la unidad de traumatología no puede atender a un paciente que ingresa en la unidad de oncología. Por otro lado, los cirujanos tienen un nivel de habilidad que les permite realizar unas intervenciones quirúrgicas u otras. Además, cada cirujano posee un calendario de disponibilidad diaria en el horizonte de planificación. Por otro lado, existe un número determinado de consultas y quirófanos, 𝑛𝑢𝑚_𝑐𝑜𝑛𝑠 y 𝑛𝑢𝑚_𝑞𝑢𝑖𝑟, cada uno de los cuales pertenece a una unidad médica y posee una disponibilidad diaria en el horizonte de planificación. Por tanto, los datos de entrada de los recursos son: Cirujano: - Identificador. - Unidad a la que pertenece. - Nivel de habilidad que posee. - Disponibilidad diaria en el horizonte de planificación. Consulta: - Identificador. - Unidad a la que pertenece. - Disponibilidad diaria en el horizonte de planificación. Quirófano: - Identificador. - Unidad a la que pertenece. - Disponibilidad diaria en el horizonte de planificación. 2.4.2 Trabajos Los trabajos son aquellos productos que van a pasar por el proceso de producción. Entendiendo el proceso de producción como la secuencia médico-quirúrgica PAE-OR-POST, los trabajos son los pacientes. Puesto que a cada paciente se le asocia una intervención, se hablará a partir de ahora de intervenciones en lugar de pacientes. Por ejemplo, el paciente número 1 tiene asociada la intervención número 1, pero en este trabajo se hará referencia únicamente a las intervenciones. Las intervenciones se asignan a una unidad. Para cada intervención, es necesario conocer en qué etapa se encuentra al momento de realizar la planificación. Algunas intervenciones entran a la primera etapa, PAE, pero 3 Decodificación de la Solución 14 3.1.1 Etapa PAE En primer lugar, 𝑢𝑑𝑗=𝑢𝑛𝑖𝑑𝑎𝑑 y 𝑥=0. En el caso de que la intervención entre a PAE, se elige el primer día a partir de 𝑥 en el que alguna de las consultas asignadas a la unidad en cuestión tiene disponibilidad suficiente para albergar el PAE, que tiene una duración definida. Es decir, el primer día en el que se cumple que: 𝑢𝑑𝑐𝑜𝑛𝑠=𝑢𝑛𝑖𝑑𝑎𝑑 𝑦 𝑑𝑖𝑠𝑝𝑐𝑜𝑛𝑠,𝑑≥𝑑𝑢𝑟_𝑝𝑎𝑒 ∀𝑐𝑜𝑛𝑠 Cuando esto se cumple, 𝑑𝑖𝑎=𝑑 y 𝑐𝑜𝑛𝑠𝑢𝑙𝑡𝑎=𝑐𝑜𝑛𝑠 Una vez elegido el día 𝑑𝑖𝑎 y la consulta 𝑐𝑜𝑛𝑠𝑢𝑙𝑡𝑎, se comprueba cuáles de los cirujanos asignados a esa unidad están disponibles ese día. La disponibilidad implica que el cirujano no esté asignado a quirófanos en esa jornada (es decir, que esté asignado a consultas o que todavía no haya sido asignado a nada) y que tenga tiempo suficiente para realizar el PAE. 𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎⊂𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 {𝑢𝑑𝑐𝑖𝑟𝑢𝑗=𝑢𝑛𝑖𝑑𝑎𝑑 𝑐𝑖𝑟𝑢𝑗_𝑞𝑢𝑖𝑟𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎⊄𝑐𝑖𝑟𝑢𝑗 𝑑𝑖𝑠𝑝𝑐𝑖𝑟𝑢𝑗,𝑑𝑖𝑎≥𝑑𝑢𝑟_𝑝𝑎𝑒 ∀𝑐𝑖𝑟𝑢𝑗 De entre los cirujanos disponibles, se selecciona a aquellos que están asignados a consultas y se elige al que posee menor habilidad. 𝑐𝑖𝑟𝑢𝑎𝑛𝑜_𝑒𝑙𝑒𝑔𝑖𝑑𝑜=𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗≤ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗′ ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑐𝑜𝑛𝑠𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , 𝑐𝑖𝑟𝑢𝑗′≠𝑐𝑖𝑟𝑢𝑗 Si no hubiera cirujanos asignados a consultas de entre los disponibles, se selecciona al cirujano de menor habilidad y se le asigna a consultas. 𝑐𝑖𝑟𝑢𝑎𝑛𝑜=𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗≤ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗′ ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , 𝑐𝑖𝑟𝑢𝑗′≠𝑐𝑖𝑟𝑢𝑗 𝐴ñ𝑎𝑑𝑖𝑟 𝑐𝑖𝑟𝑢𝑗 𝑎 𝑐𝑖𝑟𝑢𝑗_𝑐𝑜𝑛𝑠𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 Si no hubiera cirujanos disponibles en absoluto, es necesario buscar el siguiente día en el que hay consultas disponibles. Es decir, se vuelve al primer paso con 𝑥=𝑑𝑖𝑎+1, siempre y cuando 𝑥<𝐻. Una vez elegidos la consulta y el cirujano, se reduce la disponibilidad de ambos, y se establece el día elegido como el tiempo de finalización de la etapa PAE de la intervención. 𝑑𝑖𝑠𝑝_𝑐𝑜𝑛𝑠𝑐𝑜𝑛𝑠𝑢𝑙𝑡𝑎,𝑑𝑖𝑎=𝑑𝑖𝑠𝑝_𝑐𝑜𝑛𝑠𝑐𝑜𝑛𝑠𝑢𝑙𝑡𝑎,𝑑𝑖𝑎−𝑑𝑢𝑟_𝑝𝑎𝑒 𝑑𝑖𝑠𝑝_𝑐𝑖𝑟𝑢𝑗𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜,𝑑𝑖𝑎=𝑑𝑖𝑠𝑝_𝑐𝑖𝑟𝑢𝑗𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜,𝑑𝑖𝑎−𝑑𝑢𝑟_𝑝𝑎𝑒 𝑐𝑡0,𝑗=𝑑𝑖𝑎 A continuación, se envía la intervención a la siguiente etapa, el OR. Si no se pudiera realizar el PAE ningún día del horizonte de planificación, se devuelve ‘No time’ para la etapa actual PAE y para las siguientes (OR y POST). 𝑐𝑡0,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′ 15 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados 𝑐𝑡1,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′ 𝑐𝑡2,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′ 3.1.2 Etapa OR En primer lugar, 𝑢𝑑𝑗=𝑢𝑛𝑖𝑑𝑎𝑑. Si la intervención entra a OR, hay que tener en cuenta el tiempo mínimo requerido entre la consulta PAE y la intervención quirúrgica, durante el cual no se puede realizar la intervención. 𝑥=𝑡_𝑝_𝑜_𝑟𝑒𝑙𝑗 Se elige, a partir de la conclusión de este tiempo 𝑥, el primer día en el que alguno de los quirófanos asignados a la unidad en cuestión tiene disponibilidad suficiente para albergar el OR, que tiene una duración definida. Es decir, el primer día en el que se cumple que: 𝑢𝑑𝑞𝑢𝑖𝑟=𝑢𝑛𝑖𝑑𝑎𝑑 𝑦 𝑑𝑖𝑠𝑝𝑞𝑢𝑖𝑟,𝑑≥𝑑𝑢𝑟_𝑜𝑟𝑗 ∀𝑞𝑢𝑖𝑟 Cuando esto se cumple, 𝑑𝑖𝑎=𝑑 y 𝑞𝑢𝑖𝑟𝑜𝑓𝑎𝑛𝑜=𝑞𝑢𝑖𝑟 Una vez elegido el día 𝑑𝑖𝑎 y el quirófano 𝑞𝑢𝑖𝑟𝑜𝑓𝑎𝑛𝑜, se comprueba cuáles de los cirujanos asignados a esa unidad están disponibles ese día para ser asistentes en la intervención quirúrgica. Estos son los cirujanos que, teniendo un nivel de habilidad suficiente para ser asistentes en la intervención, no están asignados a consultas durante el día elegido y tienen suficiente tiempo para realizar el OR. 𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎⊂𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 { 𝑢𝑑𝑐𝑖𝑟𝑢𝑗=𝑢𝑛𝑖𝑑𝑎𝑑 𝑐𝑖𝑟𝑢𝑗_𝑐𝑜𝑛𝑠𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎⊄𝑐𝑖𝑟𝑢𝑗 ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗≥ℎ𝑎𝑏_𝑎𝑠𝑖𝑠𝑡𝑗 𝑑𝑖𝑠𝑝𝑐𝑖𝑟𝑢𝑗,𝑑𝑖𝑎≥𝑑𝑢𝑟_𝑜𝑟 ∀𝑐𝑖𝑟𝑢𝑗 De entre ellos, se selecciona como cirujano asistente al que menor habilidad tiene. 𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑎𝑠𝑖𝑠𝑡𝑒𝑛𝑡𝑒=𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗≤ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗′ ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , 𝑐𝑖𝑟𝑢𝑗′≠𝑐𝑖𝑟𝑢𝑗 Para elegir al cirujano responsable de la intervención, se parte de la lista de cirujanos disponibles para ser asistentes, eliminando de la misma al cirujano asistente y a aquellos cirujanos que no tienen habilidad suficiente para ser responsables. 𝐸𝑙𝑖𝑚𝑖𝑛𝑎𝑟 𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑎𝑠𝑖𝑠𝑡𝑒𝑛𝑡𝑒 𝑑𝑒 𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 𝐸𝑙𝑖𝑚𝑖𝑛𝑎𝑟 𝑐𝑖𝑟𝑢𝑗 𝑑𝑒 𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 𝑠𝑖 ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗<ℎ𝑎𝑏_𝑟𝑒𝑠𝑝𝑗 De la lista resultante, se comprueba si hay cirujanos asignados a quirófanos, en cuyo caso se selecciona a aquel con menor habilidad. 𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑎𝑏𝑙𝑒 =𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗≤ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗′ ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑞𝑢𝑖𝑟𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , 𝑐𝑖𝑟𝑢𝑗′≠𝑐𝑖𝑟𝑢𝑗 Si no hubiera cirujanos asignados a quirófanos, se selecciona al cirujano de menor habilidad y se le asigna a quirófanos durante ese día. También se asigna a quirófanos al cirujanos asistente si no lo estaba ya. 3 Decodificación de la Solución 16 𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑎𝑏𝑙𝑒 =𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗≤ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗′ ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , 𝑐𝑖𝑟𝑢𝑗′≠𝑐𝑖𝑟𝑢𝑗 𝐴ñ𝑎𝑑𝑖𝑟 𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑎𝑏𝑙𝑒 𝑎 𝑐𝑖𝑟𝑢𝑗_𝑞𝑢𝑖𝑟𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 𝐴ñ𝑎𝑑𝑖𝑟 𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑎𝑠𝑖𝑠𝑡𝑒𝑛𝑡𝑒 𝑎 𝑐𝑖𝑟𝑢𝑗_𝑞𝑢𝑖𝑟𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 𝑠𝑖 𝑐𝑖𝑟𝑢𝑗_𝑞𝑢𝑖𝑟𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎⊄𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑎𝑠𝑖𝑠𝑡𝑒𝑛𝑡𝑒 Si no hubiera cirujanos disponibles, se busca el siguiente día en el que hay quirófanos disponibles. Es decir, se vuelve al primer paso con 𝑥=𝑑𝑖𝑎+1, siempre y cuando 𝑥<𝐻. Una vez elegidos el quirófano y los dos cirujanos, se reduce su disponibilidad y se establece el día elegido como el tiempo de finalización de la etapa OR de la intervención. 𝑑𝑖𝑠𝑝_𝑞𝑢𝑖𝑟𝑞𝑢𝑖𝑟𝑜𝑓𝑎𝑛𝑜,𝑑𝑖𝑎=𝑑𝑖𝑠𝑝_𝑞𝑢𝑖𝑟𝑞𝑢𝑖𝑟𝑜𝑓𝑎𝑛𝑜,𝑑𝑖𝑎−𝑑𝑢𝑟_𝑜𝑟𝑗 𝑑𝑖𝑠𝑝_𝑐𝑖𝑟𝑢𝑗𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑎𝑠𝑖𝑠𝑡𝑒𝑛𝑡𝑒,𝑑𝑖𝑎=𝑑𝑖𝑠𝑝_𝑐𝑖𝑟𝑢𝑗𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑎𝑠𝑖𝑠𝑡𝑒𝑛𝑡𝑒,𝑑𝑖𝑎−𝑑𝑢𝑟_𝑜𝑟𝑗 𝑑𝑖𝑠𝑝_𝑐𝑖𝑟𝑢𝑗𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑎𝑏𝑙𝑒,𝑑𝑖𝑎=𝑑𝑖𝑠𝑝_𝑐𝑖𝑟𝑢𝑗𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜_𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑎𝑏𝑙𝑒,𝑑𝑖𝑎−𝑑𝑢𝑟_𝑜𝑟𝑗 𝑐𝑡1,𝑗=𝑑𝑖𝑎 A continuación, se envía a la siguiente etapa, el POST. Si no fuera posible realizar el OR ningún día del horizonte de planificación, se devuelve ‘No time’ para dicha etapa y para la siguiente (POST). 𝑐𝑡1,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′ 𝑐𝑡2,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′ 3.1.3 Etapa POST En primer lugar, 𝑢𝑑𝑗=𝑢𝑛𝑖𝑑𝑎𝑑. Si la intervención entra en POST, hay que tener en cuenta el tiempo mínimo requerido entre la intervención quirúrgica y la consulta POST, durante el cual no se puede realizar la consulta. 𝑥=𝑡_𝑜_𝑝_𝑟𝑒𝑙𝑗 Se elige, a partir de la conclusión de este tiempo 𝑥, el primer día en el que alguna de las consultas asignadas a la unidad en cuestión tiene disponibilidad suficiente para albergar el POST. 𝑢𝑑𝑐𝑜𝑛𝑠=𝑢𝑛𝑖𝑑𝑎𝑑 𝑦 𝑑𝑖𝑠𝑝𝑐𝑜𝑛𝑠,𝑑≥𝑑𝑢𝑟_𝑜𝑟 ∀𝑐𝑜𝑛𝑠 Cuando esto se cumple, 𝑑𝑖𝑎=𝑑 y 𝑐𝑜𝑛𝑠𝑢𝑙𝑡𝑎=𝑐𝑜𝑛𝑠 Una vez elegido el día 𝑑𝑖𝑎 y la consulta 𝑐𝑜𝑛𝑠𝑢𝑙𝑡𝑎, se comprueba cuáles de los cirujanos asignados a esa unidad están disponibles ese día. La disponibilidad implica que el cirujano no esté asignado a quirófanos en esa jornada (es decir, que esté asignado a consultas o que todavía no haya sido asignado a nada) y que tenga tiempo suficiente para realizar el POST. 17 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados 𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎⊂𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 {𝑢𝑑𝑐𝑖𝑟𝑢𝑗=𝑢𝑛𝑖𝑑𝑎𝑑 𝑐𝑖𝑟𝑢𝑗_𝑞𝑢𝑖𝑟𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎⊄𝑐𝑖𝑟𝑢𝑗 𝑑𝑖𝑠𝑝𝑐𝑖𝑟𝑢𝑗,𝑑𝑖𝑎≥𝑑𝑢𝑟_𝑝𝑜𝑠𝑡 ∀𝑐𝑖𝑟𝑢𝑗 De entre los cirujanos disponibles, se selecciona a aquellos que están asignados a consultas y se elige al que posee menor habilidad. 𝑐𝑖𝑟𝑢𝑎𝑛𝑜_𝑒𝑙𝑒𝑔𝑖𝑑𝑜=𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗≤ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗′ ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑐𝑜𝑛𝑠𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , 𝑐𝑖𝑟𝑢𝑗′≠𝑐𝑖𝑟𝑢𝑗 Si no hubiera cirujanos asignados a consultas de entre los disponibles, se selecciona al cirujano de menor habilidad y se le asigna a consultas. 𝑐𝑖𝑟𝑢𝑎𝑛𝑜=𝑐𝑖𝑟𝑢𝑗 𝑠𝑖 ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗≤ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗′ ∀𝑐𝑖𝑟𝑢𝑗,𝑐𝑖𝑟𝑢𝑗′⊂𝑐𝑖𝑟𝑢𝑗_𝑑𝑖𝑠𝑝𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 , 𝑐𝑖𝑟𝑢𝑗′≠𝑐𝑖𝑟𝑢𝑗 𝐴ñ𝑎𝑑𝑖𝑟 𝑐𝑖𝑟𝑢𝑗 𝑎 𝑐𝑖𝑟𝑢𝑗_𝑐𝑜𝑛𝑠𝑢𝑛𝑖𝑑𝑎𝑑,𝑑𝑖𝑎 Si no hubiera cirujanos disponibles en absoluto, es necesario buscar el siguiente día en el que hay consultas disponibles. Es decir, se vuelve al primer paso con 𝑥=𝑑𝑖𝑎+1, siempre y cuando 𝑥<𝐻. Una vez elegidos la consulta y el cirujano, se reduce la disponibilidad de ambos, y se establece el día elegido como el tiempo de finalización de la etapa POST de la intervención. 𝑑𝑖𝑠𝑝_𝑐𝑜𝑛𝑠𝑐𝑜𝑛𝑠𝑢𝑙𝑡𝑎,𝑑𝑖𝑎=𝑑𝑖𝑠𝑝_𝑐𝑜𝑛𝑠𝑐𝑜𝑛𝑠𝑢𝑙𝑡𝑎,𝑑𝑖𝑎−𝑑𝑢𝑟_𝑝𝑜𝑠𝑡 𝑑𝑖𝑠𝑝_𝑐𝑖𝑟𝑢𝑗𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜,𝑑𝑖𝑎=𝑑𝑖𝑠𝑝_𝑐𝑖𝑟𝑢𝑗𝑐𝑖𝑟𝑢𝑗𝑎𝑛𝑜,𝑑𝑖𝑎−𝑑𝑢𝑟_𝑝𝑜𝑠𝑡 𝑐𝑡2,𝑗=𝑑𝑖𝑎 Si no se pudiera realizar el POST ningún día, se devuelve ‘No time’ para dicha etapa. 𝑐𝑡2,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′ Por último, es necesario recalcar que, si una intervención tiene como etapa inicial el OR o el POST, las etapas anteriores que no se contemplan en la planificación en cuestión, tienen como tiempo de finalización ‘-’. 𝑐𝑡0,𝑗= ′−′ 𝑠𝑖 𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗=1 𝑐𝑡0,𝑗= 𝑐𝑡1,𝑗= ′−′ 𝑠𝑖 𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗=2 3.2 Cálculo de la función objetivo La función objetivo que se pretende minimizar es el sumatorio del retraso de todas las etapas de todas las intervenciones. Es una función objetivo sencilla, donde la única complejidad reside en la existencia de distintas maneras de calcular los días de retraso, en función del tiempo de finalización y de la etapa inicial de la intervención. Para simplificar la explicación de este cálculo, va a hacerse una pequeña modificación con respecto a la notación anterior. Los tiempos máximos relativos de respuesta se van a recoger en una única variable 𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙𝑖,𝑗 que tiene dos índices, uno para la etapa y otra para la intervención, de forma que: 3 Decodificación de la Solución 18 𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙0,𝑗=𝑡𝑟𝑒𝑠𝑝_𝑝𝑎𝑒_𝑟𝑒𝑙𝑗 𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙1,𝑗=𝑡𝑟𝑒𝑠𝑝_𝑜𝑟_𝑟𝑒𝑙𝑗 𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙2,𝑗=𝑡𝑟𝑒𝑠𝑝_𝑝𝑜𝑠𝑡_𝑟𝑒𝑙𝑗 La función objetivo queda: 𝐹𝑂= ∑∑𝑇𝑖,𝑗 2 𝑖=0 𝐽 𝑗=1 1) 𝑇𝑖,𝑗=𝑚á𝑥 {0,𝑐𝑡𝑖,𝑗− 𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙𝑖,𝑗} 𝑠𝑖 𝑖=𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗 𝑦 𝑐𝑡𝑖,𝑗⊂𝐻 2) 𝑇𝑖,𝑗=𝑚á𝑥 {0,(𝑐𝑡𝑖,𝑗− 𝑐𝑡𝑖−1,𝑗)−𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙𝑖,𝑗} 𝑠𝑖 𝑖≠𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗 𝑦 𝑐𝑡𝑖,𝑗⊂𝐻 3) 𝑇𝑖,𝑗=𝑚á𝑥 {0, 𝐻− 𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙𝑖,𝑗} 𝑠𝑖 𝑖=𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗 𝑦 𝑐𝑡𝑖,𝑗 = ′𝑁𝑜 𝑡𝑖𝑚𝑒′ 4) 𝑇𝑖,𝑗=𝑚á𝑥 {0,( 𝐻−𝑐𝑡𝑖−1,𝑗)− 𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙𝑖,𝑗} 𝑠𝑖 𝑖≠𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗 , 𝑐𝑡𝑖,𝑗 = ′𝑁𝑜 𝑡𝑖𝑚𝑒′ 𝑦 𝑐𝑡𝑖−1,𝑗 ⊂𝐻 5) 𝑇𝑖𝑗=0 𝑠𝑖 𝑐𝑡𝑖𝑗 ,𝑐𝑡𝑖−1 𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′ 𝑜 𝑐𝑡𝑖,𝑗= ′−′ 1) Se calcula el retraso de la etapa inicial de una intervención (𝑖=𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗), sabiendo que el tiempo de finalización de esta etapa de la intervención está dentro del horizonte temporal de planificación (𝑐𝑡𝑖,𝑗⊂𝐻). El retraso es el tiempo de finalización menos el tiempo máximo de respuesta relativo si este resultado es positivo, o cero si el resultado anterior es negativo. Por ejemplo, si una intervención cuya etapa inicial es OR tiene como tiempo máximo de respuesta relativo del OR 10 días, y su tiempo de finalización es el día 13, el retraso de la etapa OR de la intervención es igual a 3 (13−10=3>0). Si en cambio el tiempo de finalización es el día 5, el retraso de la etapa en cuestión es cero (5−10=−5<0). 2) Se calcula el retraso de una etapa distinta a la inicial de la intervención (𝑖≠𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗), sabiendo que tiempo de finalización de esta etapa de la intervención está dentro del horizonte temporal de planificación (𝑐𝑡𝑖,𝑗⊂𝐻). El retraso es la diferencia entre, por un lado, el número de días que han pasado entre la realización de la etapa anterior hasta la realización de la etapa en cuestión, y, por otro lado, el tiempo máximo de respuesta genérico de la etapa en cuestión (que coincide con el genérico). Este es el retraso si el resultado de esa operación es positivo. Si el resultado fuera negativo, el retraso es cero. Por ejemplo, una intervención entra en OR, y se calcula un tiempo de finalización del OR de 3 y un tiempo de finalización del POST de 25. El número de días entre OR y POST es de 22 (25−3=22). 19 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados Sabiendo que el máximo tiempo de respuesta relativo del POST es de 20, el retraso del POST es de 2 (22−20=2). 3) Se calcula el retraso de la etapa inicial de una intervención (𝑖=𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗), sabiendo que el tiempo de finalización de esta etapa de la intervención está fuera del horizonte temporal de planificación (𝑐𝑡𝑖,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′). El retraso es el número de días en el horizonte temporal de planificación menos el tiempo máximo de respuesta relativo de la etapa si el resultado es positivo, y cero si el resultado es negativo. Por ejemplo, si una intervención entra en POST con un tiempo máximo de respuesta relativo de 10, y al planificar los tiempos de finalización se descubre que no da tiempo a realizar el POST en el horizonte temporal de 14 días, se considera que el retraso del POST es igual a 4 (14−10=4>0). En cambio, si el tiempo máximo de respuesta relativo fuera de 20 días, el retraso del POST sería igual a cero (14−20=−6<0). Consiste simplemente en imaginar que 𝑐𝑡𝑖,𝑗=𝐻. 4) Se calcula el retraso de una etapa 𝑖 distinta a la inicial de la intervención (𝑖≠𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗), sabiendo que el tiempo de finalización de la etapa en cuestión está fuera del horizonte temporal de planificación (𝑐𝑡𝑖,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′), y que el tiempo de finalización de la etapa anterior 𝑖−1 está dentro del horizonte temporal de planificación (𝑐𝑡𝑖−1,𝑗⊂𝐻). El retraso es la diferencia entre, por un lado, el número de días desde el tiempo de finalización de la etapa anterior hasta el final del horizonte temporal, y, por otro lado, el tiempo máximo de respuesta relativo de la etapa en cuestión (que coincide con el genérico). Este es el retraso si el resultado de esa operación es positivo. En caso de que sea negativo, el retraso es cero. Por ejemplo, una intervención entra en PAE, y tiene un tiempo de finalización del PAE de 3, y un tiempo de finalización del OR indefinido porque no da tiempo a realizarlo en el horizonte de planificación de 14 días. Si el tiempo máximo de respuesta genérico del OR es de 10, el retraso del OR es 1 ((14−3)−10=1>0). Consiste simplemente en imaginar que 𝑐𝑡𝑖,𝑗=𝐻. 5) Se calcula el retraso de una etapa 𝑖 sabiendo que el tiempo de finalización de la etapa en cuestión está fuera del horizonte temporal de planificación (𝑐𝑡𝑖,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′), y que el tiempo de finalización de la etapa anterior 𝑖−1 también está fuera del horizonte de planificación (𝑐𝑡𝑖−1,𝑗= ′𝑁𝑜 𝑡𝑖𝑚𝑒′). El retraso es cero. Este también es el retraso de las etapas anteriores a la etapa inicial de la intervención (𝑐𝑡𝑖−1,𝑗= ′−′). Por ejemplo, una intervención entra en PAE, y tiene un tiempo de finalización del PAE fuera del horizonte temporal y, evidentemente, un tiempo de finalización del OR y del POST fuera del horizonte temporal también. El retraso del PAE será el correspondiente, y el retraso de la etapa OR y POST será 0. 20 4 METAHEURÍSTICAS Y ALGORITMOS GENÉTICOS ediante la decodificación de la solución, se obtiene el valor de la función objetivo para unos datos del problema y una solución dados, entendiendo como solución la secuencia de intervenciones y la distribución de quirófanos y consultas en las unidades hospitalarias. A continuación, es necesario aplicar un método heurístico para, a partir de unos datos del problema y una distribución de quirófanos y consultas, es decir, una solución inicial, dados, hallar una secuencia de intervenciones satisfactoria. Antes de presentar los métodos heurísticos propuestos, se va a introducir los conceptos de heurística, metaheurística y, más detalladamente, el funcionamiento de un Algoritmo Genético. 4.1 Métodos heurísticos o aproximados Se considera heurístico a un procedimiento para el que se tiene un alto grado de confianza en que encuentre soluciones de alta calidad con un coste computacional razonable (Melián et al., 2003). A diferencia de los métodos exactos, mediante los cuales se obtienen resultados óptimos, los heurísticos aportan soluciones satisfactorias. Los algoritmos heurísticos o aproximados ofrecen buenas soluciones en un tiempo razonable a problemas de difícil solución, que suelen requerir agrupamientos, ordenaciones o asignaciones de un conjunto discreto de objetos que satisfagan ciertas restricciones (Herrera, 2017). Para estos problemas de gran complejidad computacional, denominados Problemas NP (De Antonio Suárez, 2013), los algoritmos exactos, como el Branch and Bound, la programación matemática, la programación dinámica o los algoritmos constructivos exactos (Pérez et al., 2018), son ineficientes o imposibles de aplicar. Entre los métodos heurísticos o aproximados más frecuentemente utilizados, se encuentran las heurísticas constructivas, las heurísticas de búsqueda o mejora local y las metaheurísticas. Estas últimas han sido utilizadas en el presente trabajo, pero a continuación se expondrá brevemente las principales características de las otras dos heurísticas. Las heurísticas constructivas, como su propio nombre indica, construyen una solución en un número finito de pasos, añadiendo trabajos sin secuenciar en secuencias parciales (Pérez et al., 2022). Son métodos deterministas que se basan en la mejor elección en cada iteración (De Antonio Suárez, 2013). Por otro lado, las heurísticas de búsqueda o mejora local comienzan con una solución del problema y la mejoran progresivamente, de modo que, en cada paso, se realiza un movimiento de una solución a otra mejor (De Antonio Suárez, 2013). Por último, las metaheurísticas son algoritmos aproximados de propósito general, con frecuencia de carácter iterativo, que guían una heurística subordinada mediante un balance adecuado entre la exploración (búsqueda en el espacio actual) y explotación (búsqueda en regiones distantes del espacio) (Herrera, 2017). Estos algoritmos tienen gran éxito en la práctica, en aquellas situaciones en las que no se requiere una solución óptima, sino que basta con una de buena calidad. M 21 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados Figura 4-1. Exploración y explotación del espacio de búsqueda de una metaheurística. Algunas metaheurísticas ampliamente difundidas son el método de búsqueda descendente simple, el Recocido Simulado (en inglés, Simulated Annealing), la Búsqueda Iterada Codiciosa (en inglés, Iterated Greedy) y el Algoritmo Genético (Pérez et al., 2022). Este último ha sido el elegido para llevar a cabo el presente trabajo. A continuación, se presenta el concepto de Algoritmo Genético y sus principales características. 4.2 Algoritmos Evolutivos y Algoritmos Genéticos Los Algoritmos Genéticos son un tipo de Algoritmo Evolutivo muy popular. Los Algoritmos Evolutivos son una técnica de resolución de problemas de búsqueda y optimización inspirada en la teoría de la evolución de las especies y la selección natural (Araujo & Cervigón, 2009). Estos algoritmos combinan la búsqueda aleatoria (contribuyendo a la exploración) con la búsqueda dirigida según la selección de los individuos más adaptados (contribuyendo a la explotación). La búsqueda aleatoria característica de los Algoritmos Evolutivos los hace capaces de escapar de óptimos locales, a diferencia de lo que sucede en el clásico método de escalada. Aplicando esta observación a la Figura 4-2, y considerando que la función objetivo es de maximización, si se parte del punto p y se realiza una técnica de escalada, solo se podrá llegar al punto a, y se dará esta solución por buena. Una vez alcanzado el punto a, es imposible escapar de dicho máximo local. En cambio, si se utiliza un Algoritmo Evolutivo, la búsqueda aleatoria puede conducir a otro punto q que, mediante la búsqueda dirigida por selección, lleve al b. Figura 4-2. Escapada de un óptimo local mediante una metaheurística. Los Algoritmos Evolutivos se basan en las premisas del modelo de evolución natural propuesto por Charles Darwin en 1859. Según la teoría de Darwin, la evolución de las especies se debe al principio de selección Metaheurísticas y Algoritmos Genéticos 22 natural, que favorece la supervivencia y multiplicación de aquellas especies que están mejor adaptadas a las condiciones de su entorno. Además, Darwin señaló como fundamental para la evolución el papel de las mutaciones, o pequeñas variaciones entre padres e hijos (Araujo & Cervigón, 2009). Como ya se ha comentado, el Algoritmo Genético es uno de los Algoritmos Evolutivos más conocidos y utilizados. A continuación, se exponen las claves para comprender su metodología y funcionamiento. Figura 4-3. Carácter iterativo del Algoritmo Genético. 4.2.1 Población inicial La población inicial consiste en un conjunto de individuos que son candidatos a ser solución del problema. Es necesario definir previamente la representación de los individuos, ya que, dependiendo del problema y de la solución buscada, los individuos pueden representarse como cadenas binarias, enteras o de número reales. Figura 4-4. A la izquierda, población inicial de un problema cuya solución es una cadena de 7 celdas azules o naranjas. A la derecha, población inicial de un problema cuya solución es una cadena de 7 caracteres que contienen los números del 1 al 7. 23 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados El tamaño de la población inicial debe ser lo suficientemente grande para proporcionar un rango de exploración adecuado, y lo suficientemente pequeño para no entorpecer el algoritmo provocando tiempos de ejecución demasiado extensos. La mejor manera de encontrar el tamaño adecuado para un problema concreto es ejecutar el algoritmo y, tras valorar la relación entre los resultados obtenidos y los tiempos empleados, decidir aumentar o reducir el tamaño de la población inicial, hasta llegar a uno apropiado. En general, la población no debe ser demasiado numerosa. Poblaciones iniciales con cientos de individuos quedan absolutamente descartadas. Los individuos de la población inicial pueden generarse de diversas maneras: de forma aleatoria, mediante reglas de despacho, con heurísticas constructivas o haciendo uso de las vecindades (Pérez et al., 2022). Puesto que las reglas de despacho y las vecindades no han sido explicadas anteriormente, y han intervenido en el Algoritmo Genético desarrollado en el presente trabajo, se explican a continuación. Las reglas de despacho son reglas que permiten clasificar y ordenar los trabajos de diferente forma, teniendo en cuenta la prioridad establecida (Sipper & Bulfin, 1998). Algunas reglas de despacho muy típicas son la “Regla de la Fecha de Entrega más Temprana” o EDD (en inglés, Earliest Due Date), por la que los trabajos se ordenan de menor a mayor fecha de entrega, la “Regla del Tiempo de Proceso más Corto” o SPT (en inglés, Shortest Processing Time), por la que los trabajos se ordenan de menor a mayor tiempo de proceso, la “Regla de Primeras Entradas, Primeras Salidas” o FIFO (en inglés, First In, First Out), por la que los trabajos se ordenan según el orden de llegada, y muchas otras más. Figura 4-5. Ejemplo de las reglas de despacho EDD y SPT. Por otro lado, se entiende como vecindad de una solución inicial al conjunto de todas las posibles soluciones que se pueden alcanzar mediante un pequeño movimiento local en la misma (Pérez et al., 2022). Los vecinos de una solución inicial pueden obtenerse mediante el Intercambio Adyacente (en inglés, Adjacent Swap), el Intercambio General (en inglés, General Swap) o la Inserción (en inglés, Insertion). El Intercambio Adyacente consiste en el intercambio entre posiciones adyacentes, y da lugar a 𝐽−1 vecinos (siendo 𝐽 el número de trabajos de la solución). El Intercambio General consiste en el intercambio entre dos posiciones, para todas las parejas de posiciones posibles, y da lugar a J×(J−1)÷2 vecinos. La Inserción consiste en el desplazamiento de cada trabajo a todas las posiciones, y da lugar a (J−1)2 vecinos. Metaheurísticas y Algoritmos Genéticos 30 Figura 4-13. Ejemplo del operador de cruce para representación de orden. Este operador también puede diseñarse con más de un punto de cruce, pero es necesario estar alerta, ya que aumenta la probabilidad de obtener descendientes iguales a los padres, y quizá no sea este el objetivo perseguido. El funcionamiento es el mismo que en el caso de un solo punto de cruce, pero en lugar de una sola parte copiada de padre a hijo, habrá dos partes: una antes del primer punto de cruce y otra después del segundo punto. En la Figura 4-13 puede verse un ejemplo. Precisamente, se puede observar que el Descendiente 1 obtenido es igual al Padre 1. Figura 4-14. Ejemplo del operador de cruce para representación de orden con dos puntos de cruce. 31 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados 4.2.5 Mutación El operador de mutación crea un nuevo individuo realizando algún tipo de alteración, usualmente pequeña, en otro individuo (Araujo & Cervigón, 2009). Este operador permite alcanzar cualquier parte del espacio de búsqueda, contribuyendo a mantener la diversidad de la población. Se aplica sobre los descendientes obtenidos tras la fase de cruce, incluidos aquellos que coinciden con los padres porque el operador de cruce no actuó (Universidad de Granada, 2013). Habitualmente, la tasa de mutación es bastante pequeña comparada con la tasa de cruce. Sin embargo, se puede innovar en este sentido introduciendo una tasa de mutación variable, que comienza siendo alta para ampliar la búsqueda en las generaciones iniciales, y se reduce a medida que avanza la evolución (Araujo & Cervigón, 2009). Existen diversos operadores de mutación. Entre los más comunes se encuentra el operador de intercambio de pares, por el que se seleccionan aleatoriamente dos posiciones de la cadena del individuo y se intercambian los trabajos que las ocupan. Otro operador de mutación habitualmente utilizado es el de inserción, que consiste en seleccionar aleatoriamente un trabajo e insertarlo en una posición elegida también aleatoriamente (Pérez et al., 2022). Figura 4-15. A la izquierda, ejemplo de mutación por intercambio de pares. A la derecha, ejemplo de mutación por inserción. 4.2.6 Proceso de reemplazo En los Algoritmos Genéticos, el tamaño de la población suele mantenerse constante. Por esta razón, es lógico pensar que, para que los nuevos descendientes pasen a formar parte de la población, deben reemplazar a otros individuos de generaciones anteriores. En cuanto a este proceso de reemplazo, los Algoritmos Genéticos pueden clasificarse en generacionales o con estado estacionario. Los Algoritmos Genéticos generacionales son aquellos en los que la población se renueva completamente de una generación a otra (Araujo & Cervigón, 2009). Esto quiere decir que los descendientes de una generación reemplazan por completo a sus predecesores. Para mantener el tamaño de la población constante, el número de descendientes debe ser en este caso igual al número total de individuos de la generación anterior. Por otro lado, los Algoritmos Genéticos con estado estacionario son aquellos en los que los descendientes solo reemplazan a algunos individuos de la población anterior, por lo que se conserva parte de la población de generación en generación (Araujo & Cervigón, 2009). En este caso, que es el que concierne a este trabajo, el proceso de reemplazo cuenta con más variables que en el caso generacional, ya que debe decidirse qué individuos predecesores serán los reemplazados. Para tomar esta decisión, se puede optar entre: 1. Reemplazo de los padres: los descendientes sustituyen a sus padres (Araujo & Cervigón, 2009). 2. Reemplazo aleatorio: los individuos de la población anterior que serán reemplazados se eligen aleatoriamente (Araujo & Cervigón, 2009). Metaheurísticas y Algoritmos Genéticos 32 3. Reemplazo de los individuos peor adaptados: los individuos que serán reemplazados se eligen aleatoriamente de entre los que tienen peor fitness (Araujo & Cervigón, 2009). 4. Reemplazo de los individuos de adaptación similar: cada descendiente reemplaza a un individuo de la población anterior que tiene un fitness similar al suyo (Araujo & Cervigón, 2009). Para el presente trabajo se utilizará el método 3 de reemplazo de los individuos con peor fitness. Posteriormente se explicará con más detalle el mecanismo utilizado. 4.2.7 Criterios de terminación Por último, es necesario concretar las condiciones en las que el algoritmo deja de evolucionar, es decir, los requisitos ante los cuales se deja de seleccionar a los padres y de generar a los descendientes, y la población deja de desarrollarse. Es en este punto cuando se presenta la mejor solución encontrada hasta entonces: el individuo con mejor fitness. Existen distintos criterios que pueden poner fin al algoritmo, y pueden usarse por separado o combinados. Según Araujo y Cervigón (2009), Michalewicz contempla las siguientes opciones: 1. Alcanzar un número máximo de generaciones. 2. Alcanzar un número máximo de llamadas al cálculo del fitness. 3. Llegar a una situación con escasas posibilidades de que se produzcan cambios significativos en la generación siguiente. Los valores concretos de los dos primeros criterios dependen de la complejidad de cada problema, por lo que no tiene sentido dar estimaciones generalizadas. Por otro lado, la materialización del tercer criterio puede basarse en el número de genes que han convergido a un mismo valor, o en el número de generaciones seguidas cuyo mejor fitness o fitness medio no mejora (o no mejora lo suficiente) (Araujo & Cervigón, 2009). 33 5 REGLAS DE DESPACHO ELABORADAS ntes de describir los Algoritmos Genéticos desarrollados, se van a presentar las cinco reglas de despacho utilizadas en algunos de ellos como parte de la población inicial. Estas reglas se han elaborado siguiendo el criterio personal del autor, en base al modelo elaborado. Posteriormente, en el capítulo 7 Resultados computacionales, se probarán con algunas instancias para comparar sus resultados. 5.1 Regla de Despacho 1 Consiste en ordenar las intervenciones de menor a mayor tiempo máximo de respuesta relativo de la etapa en la que entran (PAE, OR o POST). 5.2 Regla de Despacho 2 Se seleccionan las intervenciones que entran en la etapa POST y se ordenan de menor a mayor tiempo máximo de respuesta relativo. Después, se ordena el resto de las intervenciones de menor a mayor tiempo máximo de respuesta relativo de la etapa en la que entran (PAE o OR). 5.3 Regla de Despacho 3 Las intervenciones se ordenan según su etapa inicial: primero las que entran en POST, luego en OR y por último PAE. Cada grupo de intervenciones se ordena de menor a mayor 𝑝𝑜𝑠𝑗, que se define de la siguiente manera: 𝑝𝑜𝑠𝑗=𝑑𝑖𝑎𝑠𝑗+2∗𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙𝑖,𝑗 donde 𝑡𝑟𝑒𝑠𝑝_𝑟𝑒𝑙𝑖,𝑗 es el tiempo máximo de respuesta relativo de la intervención 𝑗 en su etapa inicial 𝑖, según la notación especificada en el apartado 3.2 Cálculo de la función objetivo y 𝑑𝑖𝑎𝑠𝑗 se calcula de forma distinta según cuál sea la etapa inicial: - Si la etapa inicial de la intervención es PAE, (𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗=0), 𝑑𝑖𝑎𝑠𝑗 es el número de días, desde el primer día en que se puede realizar la intervención quirúrgica respetando los tiempos mínimos entre PAE y OR y suponiendo que el PAE se realiza el primer día, hasta el último del horizonte de planificación, que hay cirujanos de la unidad adecuada con tiempo disponible para realizar la intervención quirúrgica. - Si la etapa inicial de la intervención es OR, 𝑑𝑖𝑎𝑠𝑗 es el número de días, desde el primer día en que se puede realizar la operación respetando los tiempos mínimos entre PAE y OR, hasta el último día del horizonte de planificación, que hay cirujanos de la unidad adecuada con tiempo disponible para A Reglas de Despacho Elaboradas 34 realizar la intervención quirúrgica. - Si la etapa inicial es POST, 𝑑𝑖𝑎𝑠𝑗 es el número de días que hay desde que se puede realizar el POST respetando los tiempos mínimos entre OR y POST y el último día del horizonte de planificación. 5.4 Regla de Despacho 4 De nuevo, se da prioridad a las intervenciones que entran en POST, y se ordenan de menor a mayor tiempo máximo de respuesta relativo. A continuación, se ordena las intervenciones que entran en OR. Se calcula la diferencia entre la habilidad requerida por el cirujano responsable de la intervención y el tiempo máximo de respuesta. Esta diferencia es mayor cuando aumenta la habilidad requerida y cuando disminuye el tiempo máximo de respuesta relativo, por lo que la lógica dicta que las intervenciones deben ordenarse de mayor a menor. Por último, las intervenciones que entran en PAE se ordenan de menor a mayor tiempo máximo de respuesta relativo. 5.5 Regla de Despacho 5 Se ordenan en primer lugar las intervenciones que entran en POST, luego las que entran en OR y por último las que entran en PAE. Cada grupo se ordena de menor a mayor tiempo máximo de respuesta relativo. 35 6 ALGORITMOS PROPUESTOS continuación, se van a presentar los Algoritmos Genéticos desarrollados en este trabajo. Como ya se ha dicho anteriormente, el objetivo de la aplicación de estos algoritmos es la obtención de una secuencia de intervenciones satisfactoria para un problema concreto, formado por unos datos específicos y una distribución de quirófanos y consultas entre las distintas unidades hospitalarias. A esta distribución se le denomina solución inicial, pues es necesario conocerla antes de poder hallar una secuencia de intervenciones adecuada. Figura 6-1. Esquema del funcionamiento del Algoritmo Genético. Finalmente, una vez explicadas las características de los Algoritmos Genéticos elaborados, se presentará un algoritmo extendido para hallar una satisfactoria distribución de los quirófanos y las consultas, es decir, una solución inicial aceptable. 6.1 Algoritmo Genético 1 o AG1 6.1.1 Población inicial del AG1 El Algoritmo Genético 1 tiene una población inicial compuesta por 15 individuos. Dicho tamaño se mantendrá constante a lo largo de las iteraciones. De los 15 individuos, diez son secuencias generadas aleatoriamente y los otros cinco proceden de la aplicación de las Reglas de Despacho 1, 2, 3, 4 y 5. 6.1.2 Estrategia de selección del AG1 Los dos padres son seleccionados mediante dos torneos deterministas. En cada torneo hay dos concursantes, y A 6 Algoritmos Propuestos 36 resultará ganador el mejor de ellos, es decir, el que tenga mejor fitness, convirtiéndose de este modo en uno de los padres. 6.1.3 Cruce del AG1 La tasa de cruce es 0.9, por lo que hay un 90% de probabilidad de que tenga lugar. En caso de que así sea, se genera un solo hijo mediante el operador de cruce para representación de orden. Concretamente, el hijo copia la primera mitad del Padre 1, y ordena el resto de sus componentes según el orden del Padre 2. Si no tiene lugar el cruce, el hijo es, aleatoriamente, una copia del Padre 1 o del Padre 2. 6.1.4 Mutación del AG1 La tasa de mutación es variable. Comienza siendo 1, es decir, hay un 100% de probabilidad de mutación, y en cada mutación que se realiza disminuye en 0.01 hasta alcanzar el valor de 0.5. A partir de ese valor, la tasa de mutación permanece constante. La mutación se realiza con un 100% de probabilidad si el Padre 1 y el Padre 2 son iguales. La mutación consiste en el intercambio de tres genes (o trabajos, o intervenciones en el caso de este proyecto) seleccionados aleatoriamente. Si no se realiza mutación, el descendiente es el hijo. 6.1.5 Proceso de reemplazo del AG1 El descendiente generado (ya sea mutante o hijo) da un valor de la función objetivo, es decir, su fitness. Este valor se compara con el fitness de toda la población de la anterior generación, individuo a individuo. Para aquellos individuos que tienen un peor fitness, se decide aleatoriamente si será reemplazado por el nuevo descendiente, con una probabilidad del 40% de reemplazo. Si el descendiente es mejor que alguno de los viejos individuos, pero la probabilidad no ha permitido realizar ningún reemplazo, el descendiente reemplaza al individuo con peor fitness de toda la población. 6.1.6 Criterio de terminación del AG1 Hay dos situaciones ante las cuales el Algoritmo Genético deja de iterar. En primer lugar, si se cumplen las 250 iteraciones. En segundo lugar, si se dan 60 iteraciones seguidas en las que no ha habido reemplazo de la población anterior por el descendiente, ya que este último siempre ha sido peor que los individuos de la generación pasada. 6.2 Algoritmo Genético 2 o AG2 6.2.1 Población inicial del AG2 El Algoritmo Genético 2 tiene una población inicial compuesta por 15 individuos. Dicho tamaño se mantendrá constante a lo largo de las iteraciones. De los 15 individuos, uno procede de la Regla de Despacho 5, diez son vecinos por Intercambio General de la Regla de Despacho 5 aleatoriamente generados y cuatro son secuencias generadas aleatoriamente. 6.2.2 Estrategia de selección del AG2 Los dos padres son seleccionados mediante dos torneos probabilísticos, con un umbral de 0.3. En cada torneo hay dos concursantes, de los que resultará ganador, convirtiéndose de este modo en padre, en el 30% de las ocasiones el que tenga peor fitness, y en el otro 70% el que tenga mejor fitness. 6.2.3 Cruce del AG2 La tasa de cruce es 0.9, por lo que hay un 90% de probabilidad de que tenga lugar. En caso de que así sea, se 37 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados genera un solo hijo mediante el operador de cruce para representación de orden. Concretamente, el hijo copia la primera mitad del Padre 1, y ordena el resto de sus componentes según el orden del Padre 2. Si no tiene lugar el cruce, el hijo es, aleatoriamente, una copia del Padre 1 o del Padre 2. 6.2.4 Mutación del AG2 La tasa de mutación es variable. Comienza siendo 1, es decir, hay un 100% de probabilidad de mutación, y en cada mutación que se realiza disminuye en 0.01 hasta alcanzar el valor de 0.5. A partir de ese valor, la tasa de mutación permanece constante. La mutación se realiza con un 100% de probabilidad si el Padre 1 y el Padre 2 son iguales. La mutación consiste en el intercambio de tres genes (o trabajos, o intervenciones en el caso de este proyecto) seleccionados aleatoriamente. Si no se realiza mutación, el descendiente es el hijo. 6.2.5 Proceso de reemplazo del AG2 El descendiente generado (ya sea mutante o hijo) da un valor de la función objetivo, es decir, su fitness. Este valor se compara con el fitness de toda la población de la anterior generación, individuo a individuo. Para aquellos individuos que tienen fitness peor que el del descendiente y peor que la media de fitness, se decide aleatoriamente si será reemplazado por el nuevo descendiente, con una probabilidad del 60% de reemplazo. Si el descendiente es mejor que alguno de los viejos individuos, pero no se ha realizado ningún cambio, se reemplaza a la mitad de los individuos que tengan peor fitness que el descendiente, concretamente a los que peores valores tengan. 6.2.6 Criterio de terminación del AG2 Hay dos situaciones ante las cuales el Algoritmo Genético deja de iterar. En primer lugar, si se cumplen las 250 iteraciones. En segundo lugar, si se dan 60 iteraciones seguidas en las que no ha habido reemplazo de la población anterior por el descendiente, ya que este último siempre ha sido peor que los individuos de la generación pasada. 6.3 Algoritmo Genético 3 o AG3 6.3.1 Población inicial del AG3 El Algoritmo Genético 3 tiene una población inicial compuesta por 15 individuos. Dicho tamaño se mantendrá constante a lo largo de las iteraciones. De los 15 individuos, cinco proceden de las Reglas de Despacho 1, 2, 3, 4 y 5 y diez son vecinos por Intercambio Adyacente de la Regla de Despacho 2 aleatoriamente generados. 6.3.2 Estrategia de selección del AG3 Los dos padres son seleccionados por el método de la ruleta. A cada individuo se le calcula su probabilidad de ser seleccionado y, posteriormente, se compara un número generado aleatoriamente con las puntuaciones acumuladas de los individuos. De este modo se obtienen sucesivamente los dos padres. 6.3.3 Cruce del AG3 La tasa de cruce es 0.9, por lo que hay un 90% de probabilidad de que tenga lugar. En caso de que así sea, se genera un solo hijo mediante el operador de cruce para representación de orden. Concretamente, el hijo copia la primera mitad del Padre 1, y ordena el resto de sus componentes según el orden del Padre 2. Si no tiene lugar el cruce, el hijo es, aleatoriamente, una copia del Padre 1 o del Padre 2. 6 Algoritmos Propuestos 38 6.3.4 Mutación del AG3 La tasa de mutación es variable. Comienza siendo 1, es decir, hay un 100% de probabilidad de mutación, y en cada mutación que se realiza disminuye en 0.01 hasta alcanzar el valor de 0.5. A partir de ese valor, la tasa de mutación permanece constante. La mutación se realiza con un 100% de probabilidad si el Padre 1 y el Padre 2 son iguales. La mutación consiste en el intercambio de cuatro genes (o trabajos, o intervenciones en el caso de este proyecto) seleccionados aleatoriamente. Si no se realiza mutación, el descendiente es el hijo. 6.3.5 Proceso de reemplazo del AG3 El descendiente generado (ya sea mutante o hijo) da un valor de la función objetivo, es decir, su fitness. Este valor se compara con el fitness de toda la población de la anterior generación, individuo a individuo. Para aquellos individuos que tienen un peor fitness, se decide aleatoriamente si será reemplazado por el nuevo descendiente, con una probabilidad del 60% de reemplazo. Si el descendiente es mejor que alguno de los viejos individuos, pero la probabilidad no ha permitido realizar ningún reemplazo, el descendiente reemplaza al individuo con peor fitness de toda la población. 6.3.6 Criterio de terminación del AG3 Hay dos situaciones ante las cuales el Algoritmo Genético deja de iterar. En primer lugar, si se cumplen las 250 iteraciones. En segundo lugar, si se dan 60 iteraciones seguidas en las que no ha habido reemplazo de la población anterior por el descendiente, ya que este último siempre ha sido peor que los individuos de la generación pasada. 6.4 Algoritmo Genético 4 o AG4 6.4.1 Población inicial del AG4 El Algoritmo Genético 5 tiene una población inicial compuesta por 15 individuos. Dicho tamaño se mantendrá constante a lo largo de las iteraciones. De los 15 individuos, uno procede de la Regla de Despacho 5 y catorce son vecinos por Intercambio General de la Regla de Despacho 5 aleatoriamente generados. 6.4.2 Estrategia de selección del AG4 El Padre 1 es el mejor individuo, es decir, aquel con mejor fitness, y el Padre 2 es un individuo seleccionado aleatoriamente. 6.4.3 Cruce del AG4 La tasa de cruce es 0.9, por lo que hay un 90% de probabilidad de que tenga lugar. En caso de que así sea, se genera un solo hijo mediante el operador de cruce para representación de orden. Concretamente, el hijo copia la primera mitad del Padre 1, y ordena el resto de sus componentes según el orden del Padre 2. Si no tiene lugar el cruce, el hijo es, aleatoriamente, una copia del Padre 1 o del Padre 2. 6.4.4 Mutación del AG4 La tasa de mutación es variable. Comienza siendo 1, es decir, hay un 100% de probabilidad de mutación, y en cada mutación que se realiza disminuye en 0.01 hasta alcanzar el valor de 0.5. A partir de ese valor, la tasa de mutación permanece constante. La mutación se realiza con un 100% de probabilidad si el Padre 1 y el Padre 2 son iguales. La mutación consiste en el intercambio de cuatro genes (o trabajos, o intervenciones en el caso de este 39 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados proyecto) seleccionados aleatoriamente. Si no se realiza mutación, el descendiente es el hijo. 6.4.5 Proceso de reemplazo del AG4 El descendiente generado (ya sea mutante o hijo) da un valor de la función objetivo, es decir, su fitness. Este valor se compara con el fitness de toda la población de la anterior generación, individuo a individuo. Para aquellos individuos que tienen un peor fitness, se decide aleatoriamente si será reemplazado por el nuevo descendiente, con una probabilidad del 40% de reemplazo. Si el descendiente es mejor que alguno de los viejos individuos, pero la probabilidad no ha permitido realizar ningún reemplazo, el descendiente reemplaza al individuo con peor fitness de toda la población. 6.4.6 Criterio de terminación del AG4 Hay dos situaciones ante las cuales el Algoritmo Genético deja de iterar. En primer lugar, si se cumplen las 250 iteraciones. En segundo lugar, si se dan 60 iteraciones seguidas en las que no ha habido reemplazo de la población anterior por el descendiente, ya que este último siempre ha sido peor que los individuos de la generación pasada. 6 Algoritmos Propuestos 46 Por ejemplo, en la instancia 3, la solución inicial considerada la mejor es [[4, 3], [2, 1], [2, 1]], que consigue un valor de la función objetivo en la fase 3 de 1113. En la segunda fase, sin embargo, aparece también la matriz, pero con un valor de la función objetivo de 1122, es decir, el valor de la función objetivo se incrementa en un 0.81%. En la instancia 8 sucede lo mismo. La solución inicial para la cual se consigue el menor valor de la función objetivo es [[3, 2], [3, 2], [2, 1]], con un 609 en la fase 3. En la fase 1 aparece la misma matriz, pero da lugar a un valor de la función objetivo de 613, un 0.66% más. Que existan estas pequeñas variaciones en el resultado de la función objetivo, no significa que el Algoritmo Genético no cumpla debidamente con su función, simplemente evidencia la componente aleatoria que interviene en el algoritmo: con unos mismos datos de entrada, no siempre se llegará a la misma solución, pero sí a resultados del mismo orden de magnitud. Distinto sería si, ante la misma instancia y solución inicial, el AG3 obtuviera resultados muy dispares. Esto sí sería señal de deficiencias en el funcionamiento del algoritmo, pero no ha sido el caso. En la Tabla 6-5 se recogen las instancias en las que ha habido repetición de la mejor solución inicial, y el incremento de la función objetivo que se observa. Tabla 6-5. Incremento del valor de la función objetivo para una misma instancia y solución inicial. Instancia Mejor solución inicial Mejor valor de la función objetivo Peor valor de la función objetivo Incremento 3 [[4, 3], [2, 1], [2, 1]] 1113 1122 0.81% 8 [[3, 2], [3, 2], [2, 1]] 609 613 0.66% 11 [[2, 1], [4, 3], [3, 2], [2, 1], [1, 1]] 1725 1736 0.64% 33 [[4, 2], [3, 1], [1, 2]] 3192 3200 0.25% 35 [[2, 1], [4, 2], [2, 2]] 4097 4097 0.00% Efectivamente, el incremento del valor de la función objetivo es prácticamente despreciable, con una media de 0.47%. Los resultados obtenidos al utilizar una solución inicial adecuada hallada a través del Algoritmo Extendido se compararán, en el capítulo 7.2 Comparación de Algoritmos Genéticos, con los resultados obtenidos al utilizar una solución inicial aleatoria cualquiera. 48 7 RESULTADOS COMPUTACIONALES os estudios de simulación basados en un conjunto de instancias de muestra son el método más utilizado para la evaluación del funcionamiento de los algoritmos aproximados. No existe un enfoque universalmente aceptado para llevar a cabo dichos estudios de simulación, pero se pueden sintetizar en dos pasos (Framiñán et al., 2014): 1. Generación del banco de pruebas. Un cierto número de instancias del modelo son, o bien generadas específicamente para el modelo, o bien adaptadas a partir de otras empleadas para otros modelos (Framiñán et al., 2014). Algunos aspectos a tener en cuenta son el tamaño de la instancia, que debe estar en línea con las dimensiones del problema real, y el número de instancias generadas, que debe ser suficiente para proporcionar resultados significativos. 2. Análisis de los algoritmos. Los algoritmos que se desea comparar se ejecutan para cada una de las instancias. A continuación, se utiliza algún parámetro para establecer el desempeño relativo de cada algoritmo en el banco de pruebas (Framiñán et al., 2014). 7.1 Generación del banco de pruebas La función elaborada para generar las instancias se denomina “geninstancia”. Para desarrollar la función, se ha tomado como referencia el procedimiento utilizado por Cañete et al. (2022), adaptándolo a las especificaciones del problema en cuestión. 7.1.1 Parámetros La función “geninstancia” recibe como parámetros de entrada: - 𝑖𝑛𝑠𝑡_𝑖𝑛𝑖𝑐: el número identificativo de la primera instancia que se generará. - 𝑛𝑢𝑚_𝑖𝑛𝑠𝑡: el número de instancias a generar. - 𝑛_𝑢𝑑: el número de unidades hospitalarias en las instancias del conjunto. Ya ha sido definido en el apartado 2.5 Notación. - 𝑛_𝑐𝑜𝑛𝑠: el número de consultas en las instancias del conjunto. Ya ha sido definido en el apartado 2.5 Notación. - 𝑛_𝑞𝑢𝑖𝑟: el número de quirófanos en las instancias del conjunto. Ya ha sido definido en el apartado 2.5 Notación. - 𝑎𝑙𝑓𝑎: factor de control de cobertura de los cirujanos respecto a las consultas y quirófanos disponibles. Se escribe en tanto por uno. - 𝑏𝑒𝑡𝑎: factor de saturación de las consultas y quirófanos con respecto a las intervenciones a realizar. Se escribe en tanto por uno. - 𝐻: número de días en el horizonte de planificación. Ya ha sido definido en el apartado 2.5 Notación. L Resultados Computacionales 48 Los parámetros definidos dentro de la función son: - 𝑙: número de semanas en el horizonte de planificación. Su valor depende de H de la siguiente forma: 𝑙≈𝐻 7 - 𝑑ℎ𝑜𝑟_𝑐𝑜𝑛𝑠: disponibilidad diaria de cada consulta en horas. Se le ha dado un valor de 8 horas/día. - 𝑑ℎ𝑜𝑟_𝑞𝑢𝑖𝑟: disponibilidad diaria de cada quirófano en horas. Se le ha dado un valor de 8 horas/día. - 𝑎: disponibilidad diaria de cada cirujano en horas. Se le ha dado un valor de 8 horas/día. - 𝑑𝑠: disponibilidad semanal de cada cirujano en días. Se le ha dado un valor de 4 días/semana. 7.1.2 Quirófanos y consultas virtuales Para generar una instancia, la función comienza creando una serie de quirófanos y consultas virtuales para cada unidad, de manera aleatoria, de modo que los pacientes que se crearán a continuación obedecerán a la proporción establecida en este momento. En primer lugar, se crean los quirófanos virtuales. Se asigna aleatoriamente un número de quirófanos a cada unidad, comprendido entre 1 y un máximo max_𝑞𝑢𝑖𝑟𝑣𝑖𝑟𝑡: 𝑚𝑎𝑥_𝑞𝑢𝑖𝑟𝑣𝑖𝑟𝑡≈2× 𝑛_𝑞𝑢𝑖𝑟 𝑛_𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 Es decir, el máximo es el doble de lo que a cada unidad le correspondería si el total de los quirófanos se repartiera por igual. Una vez se tienen estos quirófanos virtuales aleatorios, se debe verificar que el total de los quirófanos virtuales coincide con el total real, es decir, 𝑛_𝑞𝑢𝑖𝑟. En caso contrario: - Mientras que el total de quirófanos virtuales sea mayor que 𝑛_𝑞𝑢𝑖𝑟, se selecciona una unidad al azar y se le quita un quirófano virtual (siempre y cuando no tenga un solo quirófano virtual, ya que ninguna unidad puede quedarse con cero quirófanos). - Mientras que el total de quirófanos virtuales sea menor que 𝑛_𝑞𝑢𝑖𝑟, se selecciona una unidad al azar y se le da otro quirófano virtual. Una vez finalizado este proceso, se tienen los quirófanos virtuales definitivos de cada unidad, 𝑞𝑢𝑖𝑟_𝑣𝑖𝑟𝑡𝑢. Para generar las consultas virtuales de cada unidad, 𝑐𝑜𝑛𝑠_𝑣𝑖𝑟𝑡𝑢, se realiza una regla de tres para cada unidad de manera que, si para un total de quirófanos 𝑛_𝑞𝑢𝑖𝑟, la unidad 𝑢 tiene tantos quirófanos virtuales, para un total de consultas 𝑛_𝑐𝑜𝑛𝑠, la unidad 𝑢 tendrá X consultas virtuales. De este modo, se obtienen los quirófanos y consultas virtuales de cada unidad, 𝑞𝑢𝑖𝑟_𝑣𝑖𝑟𝑡𝑢 y 𝑐𝑜𝑛𝑠_𝑣𝑖𝑟𝑡𝑢. A continuación, se comienzan a generar las intervenciones. 7.1.3 Generación de las intervenciones Las intervenciones se generan de una en una, hasta llegar a un número total de intervenciones que se va actualizando progresivamente. Antes de empezar con la primera intervención, se definen los valores que se mantienen constantes para todas ellas: - 𝑑𝑢𝑟_𝑝𝑎𝑒: definido en el apartado 2.5 Notación. Tiene un valor aleatorio entre 0.3 y 0.6 horas. - 𝑑𝑢𝑟_𝑝𝑜𝑠𝑡: definido en el apartado 2.5 Notación. Tiene un valor aleatorio entre 0.3 y 0.6 horas. - 𝑡𝑟𝑒𝑠𝑝_𝑝𝑎𝑒: definido en el apartado 2.5 Notación. Tiene un valor aleatorio entre 28 y 42 días. - 𝑡𝑟𝑒𝑠𝑝_𝑝𝑜𝑠𝑡: definido en el apartado 2.5 Notación. Tiene un valor aleatorio entre 28 y 42 días. 49 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados - 𝑡_𝑝_𝑜: definido en el apartado 2.5 Notación. Tiene un valor aleatorio entre 0 y 5 días. - 𝑡_𝑜_𝑝: definido en el apartado 2.5 Notación. Tiene un valor aleatorio entre 10 y 20 días. A continuación, comienza la generación de intervenciones. Esta parte se realiza unidad por unidad. Comienza a llevarse a cabo con la primera intervención de la primera unidad, cuando el número total de pacientes de esa unidad es 0, y prosigue mientras que el número total de pacientes de la unidad sea menor que 𝑃𝑢: 𝑃𝑢≈(𝑐𝑜𝑛𝑠_𝑣𝑖𝑟𝑡𝑢×𝑑ℎ𝑜𝑟_𝑐𝑜𝑛𝑠+𝑞𝑢𝑖𝑟_𝑣𝑖𝑟𝑡𝑢×𝑑ℎ𝑜𝑟_𝑞𝑢𝑖𝑟)×𝑏𝑒𝑡𝑎×𝐻 𝑑𝑢𝑟𝑚𝑒𝑑𝑖𝑎𝑢 donde 𝑑𝑢𝑟𝑚𝑒𝑑𝑖𝑎𝑢 es la duración media de las etapas iniciales de las intervenciones de la unidad 𝑢 y 𝑃𝑢 se ha definido en el apartado 2.5 Notación. Analizando la expresión anterior, se verifica que 𝑃𝑢 se va actualizando porque 𝑑𝑢𝑟𝑚𝑒𝑑𝑖𝑎𝑢 cambia a medida que se van generando nuevas intervenciones, con distintas duraciones. La expresión no es complicada: el primer paréntesis es la disponibilidad diaria de las consultas y quirófanos de la unidad en horas, y al dividirlo entre la duración media de las intervenciones, se obtiene el número de intervenciones que se pueden realizar en un día. Este número se multiplica por el número de días, 𝐻. Finalmente, 𝑏𝑒𝑡𝑎 representa el factor de saturación de las consultas y quirófanos, y al hacerlo mayor que 1, se obliga al número de pacientes a ser superior al ideal. Este procedimiento se repite para todas las unidades, de modo que se genera el número adecuado de pacientes, según lo establecido por la proporción de quirófanos y consultas virtuales de cada unidad. Una vez establecida la unidad a la que se asigna la intervención, se genera el resto de datos de las intervenciones: - 𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗: definido en el apartado 2.5 Notación. Es un número aleatorio entre 0 y 2. - ℎ𝑎𝑏_𝑟𝑒𝑠𝑝𝑗: definido en el apartado 2.5 Notación. Es un número aleatorio entre 2 y 20. - ℎ𝑎𝑏_𝑎𝑠𝑖𝑠𝑡𝑗: definido en el apartado 2.5 Notación. Es un número aleatorio entre 1 y 20. No puede ser mayor que ℎ𝑎𝑏_𝑟𝑒𝑠𝑝𝑗. - 𝑑𝑢𝑟_𝑜𝑟𝑗: definido en el apartado 2.5 Notación. Es un número pseudoaleatorio con distribución normal de media 𝑚𝑢 y desviación estándar 𝑠𝑖𝑔𝑚𝑎. 𝑚𝑢 es un número aleatorio entre 1 y 4, y 𝑠𝑖𝑔𝑚𝑎 es, aleatoriamente, 0.1×𝑚𝑢,0.2×𝑚𝑢, 0.3×𝑚𝑢, 0.4×𝑚𝑢 o 0.5×𝑚𝑢. No puede ser mayor que 𝑑ℎ𝑜𝑟_𝑞𝑢𝑖𝑟. - 𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗: definido en el apartado 2.5 Notación. Es un número aleatorio entre 40 y 300. - 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗: definido en el apartado 2.5 Notación. - Si la etapa inicial es PAE (𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗=0): ▪ Si 𝑡𝑟𝑒𝑠𝑝_𝑝𝑎𝑒≥35, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 42. ▪ Si 𝑡𝑟𝑒𝑠𝑝_𝑝𝑎𝑒<35, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 35. - Si la etapa inicial es OR (𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗=1): ▪ Si 𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗≥250, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 300. ▪ Si 208≤𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<250, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 250. ▪ Si 173≤𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<208, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 208. Resultados Computacionales 50 ▪ Si 144≤𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<173, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 173. ▪ Si 120≤𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<144, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 144. ▪ Si 100≤𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<120, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 120. ▪ Si 83≤𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<100, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 100. ▪ Si 69≤𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<83, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 83. ▪ Si 58≤𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<69, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 69. ▪ Si 48≤𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<58, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 58. ▪ Si 𝑡𝑟𝑒𝑠𝑝_𝑜𝑟𝑗<48, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 48. - Si la etapa inicial es POST (𝑒𝑡𝑎𝑝𝑎_𝑖𝑛𝑖𝑐𝑗=2): ▪ Si 𝑡𝑟𝑒𝑠𝑝_𝑝𝑜𝑠𝑡≥35, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 42. ▪ Si 𝑡𝑟𝑒𝑠𝑝_𝑝𝑜𝑠𝑡<35, 𝑡𝑖𝑒𝑚𝑝𝑜_𝑎𝑐𝑢𝑚𝑗 es un número aleatorio entre 0 y 35. - 𝑡𝑟𝑒𝑠𝑝_𝑝𝑎𝑒_𝑟𝑒𝑙𝑗: definido en el apartado 2.5 Notación. - 𝑡𝑟𝑒𝑠𝑝_𝑜𝑟_𝑟𝑒𝑙𝑗: definido en el apartado 2.5 Notación. - 𝑡𝑟𝑒𝑠𝑝_𝑝𝑜𝑠𝑡_𝑟𝑒𝑙𝑗: definido en el apartado 2.5 Notación. - 𝑡_𝑝_𝑜_𝑟𝑒𝑙𝑗: definido en el apartado 2.5 Notación. - 𝑡_𝑜_𝑝_𝑟𝑒𝑙𝑗: definido en el apartado 2.5 Notación. Estos últimos cinco tiempos relativos se calculan a partir de los tiempo genéricos y los tiempos acumulados en la lista de espera como se explica al final del apartado 2.5 Notación. Cuando ya están generadas todas las intervenciones de todas las unidades, es momento de generar a los cirujanos que se harán cargo de ellas. 7.1.4 Generación de los cirujanos En primer lugar, se calcula el número total de cirujanos, 𝑆: 𝑆≈(𝑛_𝑐𝑜𝑛𝑠×𝑑ℎ𝑜𝑟_𝑐𝑜𝑛𝑠+𝑛_𝑞𝑢𝑖𝑟×𝑑ℎ𝑜𝑟_𝑞𝑢𝑖𝑟×2)×𝑎𝑙𝑓𝑎×𝐻 𝑑𝑠×𝑙×𝑎 La expresión tiene el siguiente significado: el primer paréntesis representa las horas al día que un cirujano es necesitado en una consulta o quirófano. Las horas de quirófano se multiplican por dos ya que en un quirófano siempre debe haber dos cirujanos: el responsable y el asistente. Sintetizando, el paréntesis podría denominarse “horas de trabajo necesarias al día”. Al multiplicarlo por 𝐻, se obtienen las horas de trabajo necesarias en todo el horizonte de planificación. Por otro lado, el denominador no es más que las horas que un cirujano trabaja en todo el horizonte de planificación, es decir, las horas de trabajo realizadas por cirujano en todo el horizonte de planificación. Numerador entre denominador dan lugar al número de cirujanos necesario para ocupar adecuadamente todas las consultas y quirófanos. Sin embargo, este número se multiplica por 𝑎𝑙𝑓𝑎, que se hace mayor que 1 para garantizar que siempre hay más cirujanos de los que se necesitan. A continuación, se calcula el número de cirujanos necesarios para cada unidad. Para ello, se calcula la duración total de las etapas iniciales de las intervenciones de una unidad concreta, y se dividen entre las horas de trabajo de un cirujano en todo el horizonte de planificación: 𝑛_𝑐𝑖𝑟𝑢𝑗_𝑢𝑛𝑖𝑑𝑎𝑑𝑢=𝑠𝑢𝑚𝑎𝑡𝑖𝑒𝑚𝑝𝑜𝑠𝑢 𝑑𝑠×𝑙×𝑎 51 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados siendo 𝑠𝑢𝑚𝑎𝑡𝑖𝑒𝑚𝑝𝑜𝑠𝑢 la duración total de las etapas iniciales de la unidad 𝑢. Una vez calculado el número de cirujanos por unidad, hay que asegurarse de que el total coincide con 𝑆. De no ser así: - Mientras que ∑𝑛_𝑐𝑖𝑟𝑢𝑗_𝑢𝑛𝑖𝑑𝑎𝑑𝑢 > 𝑆 𝑢, se le quita un cirujano a una unidad aleatoria. - Mientras que ∑𝑛_𝑐𝑖𝑟𝑢𝑗_𝑢𝑛𝑖𝑑𝑎𝑑𝑢 < 𝑆 𝑢, se le suma un cirujano a una unidad aleatoria. Una vez se conoce el número de cirujanos y sus correspondientes unidades, se genera el resto de los datos de cada cirujano: - 𝑑𝑖𝑠𝑝𝑐𝑖𝑟𝑢𝑗: lista con tantos elementos como días tenga el horizonte temporal. Cada elemento puede ser 0 o 𝑎, y representa las horas de trabajo en cada día del horizonte de planificación. Los 0 significan descanso, y 𝑎 las horas de trabajo. Cada siete elementos se repite la secuencia, ya que los días de trabajo son los mismos para todas las semanas del horizonte. Para elaborar esta lista de cada cirujano, se ha utilizado 𝑑𝑠, que es el número de días a la semana que los cirujanos trabajan. - ℎ𝑎𝑏𝑐𝑖𝑟𝑢𝑗: definido en el apartado 2.5 Notación. Es un número aleatorio del 1 al 20. Se procura que haya al menos un cirujano con habilidad suficiente para ser responsable de la intervención con mayor nivel de responsable requerido, y al menos un cirujano, distinto al anterior, con habilidad suficiente para ser asistente de la intervención con mayor nivel de asistente requerido. Todos estos datos se recogen en archivos TXT, que serán utilizados por el modelo, y en archivos XLSX, que muestran la información más visualmente. Figura 7-1. Primera parte de la Hoja de Pacientes de una instancia en formato .xlsx. Resultados Computacionales 52 Figura 7-2. Segunda parte de la Hoja de Pacientes de una instancia en formato .xlsx. Figura 7-3. Hoja de Cirujanos de una instancia en formato .xlsx. 53 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados Figura 7-4. Hoja de Datos de una instancia en formato .xlsx. 7.1.5 Instancias generadas Se han generado 40 instancias con los siguientes parámetros: Tabla 7-1. Instancias generadas. Tipo de instancia Instancias 𝑛_𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑛𝑢𝑚_𝑐𝑜𝑛𝑠 𝑛𝑢𝑚_𝑞𝑢𝑖𝑟 𝑎𝑙𝑓𝑎 𝑏𝑒𝑡𝑎 𝐻 Instancias medianas 1 - 10 3 8 5 1.5 1.25 14 11 - 20 5 12 8 1.5 1.25 14 21 - 30 7 17 10 1.5 1.25 14 Instancias grandes 31 - 35 3 8 5 1.5 1.25 28 35-40 5 12 8 1.5 1.25 28 A través de los distintos parámetros, se han generado instancias considerablemente diversas. Las instancias medianas se caracterizan por poseer un horizonte de planificación de 14 días, es decir, dos semanas. Entre ellas hay instancias mayores, de hasta siete unidades, y más reducidas, con solo tres. Por otro lado, las instancias grandes tienen un horizonte temporal de 28 días, es decir, cuatro semanas. Se ha generado un menor número de estas instancias por el obstáculo que supone para la simulación el aumento del tiempo de ejecución. Sin embargo, las instancias grandes representan una cuarta parte de las instancias totales, por lo que su presencia se considera suficiente. 7.2 Comparación de Algoritmos Genéticos Para comparar los Algoritmos Genéticos elaborados, se han realizado numerosas simulaciones. A cada una de las 40 instancias generadas se le han asignado cuatro soluciones iniciales aleatorias con la función “asigna_mat”. Esto se ha hecho para garantizar que el Algoritmo Genético que resulte elegido habrá sido evaluado ante todo tipo de soluciones iniciales, ya sean buenas o malas. Las 40 instancias multiplicadas por 4 soluciones iniciales cada una, dan lugar a 160 variantes distintas de los problemas, para las que se han ejecutado los Algoritmos Genéticos AG1, AG2, AG3 y AG4. Esto es igual a un total de 640 simulaciones. 7.2.1 Resultados obtenidos Como resultado de las simulaciones, se ha obtenido la mejor secuencia de intervenciones y el mejor valor de la función objetivo que cada algoritmo ha conseguido encontrar. Las secuencias de intervenciones resultantes no se han registrado, ya que son muy extensas, pues el tamaño de las instancias va desde las 1000 intervenciones hasta incluso 5000. Para analizar los resultados obtenidos y determinar cuál es el Algoritmo Genético más fiable, se ha hecho uso del RPD (Relative Percentage Deviation) o Desviación Porcentual Relativa. Esta medida permite calcular el grado, en porcentaje, en que se desvía el valor obtenido por cada algoritmo respecto al mejor valor obtenido por todos ellos. Resultados Computacionales 54 𝑅𝑃𝐷𝑖𝑛𝑠𝑡,𝑚𝑎𝑡𝑑𝑖𝑠𝑡,𝑎𝑔=|𝑜𝑏𝑗𝑖𝑛𝑠𝑡,𝑠𝑜𝑙_𝑖𝑛𝑖𝑐,𝑎𝑔−𝑚𝑖𝑛𝑖𝑛𝑠𝑡,𝑠𝑜𝑙_𝑖𝑛𝑖𝑐| |𝑚𝑖𝑛𝑖𝑛𝑠𝑡,𝑠𝑜𝑙_𝑖𝑛𝑖𝑐|×100, 𝑖𝑛𝑠𝑡=1…40 𝑠𝑜𝑙_𝑖𝑛𝑖𝑐=1…4 𝑎𝑔=1,2,3,4 siendo 𝑖𝑛𝑠𝑡 la instancia; 𝑠𝑜𝑙_𝑖𝑛𝑖𝑐 la solución inicial, es decir, la distribución de los quirófanos y consultas entre las unidades hospitalarias; 𝑎𝑔 el Algoritmo Genético; 𝑜𝑏𝑗𝑖𝑛𝑠𝑡,𝑠𝑜𝑙_𝑖𝑛𝑖𝑐,𝑎𝑔 el valor de la función objetivo al aplicar el Algoritmo Genético 𝑎𝑔 en la instancia 𝑖𝑛𝑠𝑡 con la solución inicial 𝑠𝑜𝑙_𝑖𝑛𝑖𝑐; y 𝑚𝑖𝑛𝑖𝑛𝑠𝑡,𝑠𝑜𝑙_𝑖𝑛𝑖𝑐 el mínimo valor de la función objetivo obtenido al aplicar todos los Algoritmos Genéticos en la instancia 𝑖𝑛𝑠𝑡 con la solución inicia 𝑠𝑜𝑙_𝑖𝑛𝑖𝑐. Una vez calculado el RPD en todos los Algoritmos Genéticos para cada una de las 160 variantes de los problemas (entendidas como conjunto de instancia y solución inicial), se calcula el 𝐴𝑅𝑃𝐷 (Average Relative Percentage Deviation) o Desviación Porcentual Relativa Media de cada Algoritmo Genético. Aquel que presente un 𝐴𝑅𝑃𝐷 menor, es seleccionado como el mejor Algoritmo Genético. 𝐴𝑅𝑃𝐷𝑎𝑔= ∑ ∑ 𝑅𝑃𝐷𝑖𝑛𝑠𝑡,𝑠𝑜𝑙_𝑖𝑛𝑖𝑐,𝑎𝑔𝑠𝑜𝑙_𝑖𝑛𝑖𝑐𝑖𝑛𝑠𝑡 40×4 En la Tabla 7-2 se muestran tanto los resultados de las simulaciones como los 𝑅𝑃𝐷 y 𝐴𝑅𝑃𝐷 calculados. Por falta de espacio, no se han escrito en la tabla las soluciones iniciales, y solo se ha escrito su índice 1, 2, 3 o 4. En el Excel que contiene los resultados, sí están registradas de la siguiente manera: Figura 7-5. Excel con los resultados obtenidos. 55 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados Tabla 7-2. Comparación de los Algoritmos Genéticos. Inst. Sol. Inic. Obj. AG1 Obj. AG2 Obj. AG3 Obj. AG4 Mín. RPD AG1 RPD AG2 RPD AG3 RPD AG4 1 1 1402 1474 1395 1486 1395 0,50% 5,66% 0,00% 6,52% 2 1230 1221 1220 1212 1212 1,49% 0,74% 0,66% 0,00% 3 1462 1592 1441 1592 1441 1,46% 10,48% 0,00% 10,48% 4 1348 1351 1338 1341 1338 0,75% 0,97% 0,00% 0,22% 2 1 1481 1490 1479 1504 1479 0,14% 0,74% 0,00% 1,69% 2 1411 1406 1416 1410 1406 0,36% 0,00% 0,71% 0,28% 3 1506 1500 1516 1505 1500 0,40% 0,00% 1,07% 0,33% 4 1865 1879 1827 1874 1827 2,08% 2,85% 0,00% 2,57% 3 1 1190 1327 1187 1313 1187 0,25% 11,79% 0,00% 10,61% 2 1173 1249 1174 1253 1173 0,00% 6,48% 0,09% 6,82% 3 1449 1698 1442 1934 1442 0,49% 17,75% 0,00% 34,12% 4 1236 1273 1236 1272 1236 0,00% 2,99% 0,00% 2,91% 4 1 746 802 746 810 746 0,00% 7,51% 0,00% 8,58% 2 722 720 721 728 720 0,28% 0,00% 0,14% 1,11% 3 746 766 746 759 746 0,00% 2,68% 0,00% 1,74% 4 793 1024 793 1041 793 0,00% 29,13% 0,00% 31,27% 5 1 1162 1165 1162 1165 1162 0,00% 0,26% 0,00% 0,26% 2 1298 1472 1293 1475 1293 0,39% 13,84% 0,00% 14,08% 3 1197 1197 1198 1198 1197 0,00% 0,00% 0,08% 0,08% 4 1097 1095 1092 1092 1092 0,46% 0,27% 0,00% 0,00% 6 1 977 1509 999 1491 977 0,00% 54,45% 2,25% 52,61% 2 935 1023 932 1025 932 0,32% 9,76% 0,00% 9,98% 3 1087 1724 1082 1727 1082 0,46% 59,33% 0,00% 59,61% 4 1078 1724 1073 1741 1073 0,47% 60,67% 0,00% 62,26% 7 1 946 1028 946 1037 946 0,00% 8,67% 0,00% 9,62% 2 888 1075 892 1054 888 0,00% 21,06% 0,45% 18,69% 3 1019 1245 994 1234 994 2,52% 25,25% 0,00% 24,14% 4 929 939 933 940 929 0,00% 1,08% 0,43% 1,18% 8 1 674 917 674 921 674 0,00% 36,05% 0,00% 36,65% 2 729 977 739 972 729 0,00% 34,02% 1,37% 33,33% 3 737 742 731 718 718 2,65% 3,34% 1,81% 0,00% 4 692 699 697 682 682 1,47% 2,49% 2,20% 0,00% 9 1 1187 1234 1181 1220 1181 0,51% 4,49% 0,00% 3,30% 2 1332 1452 1333 1455 1332 0,00% 9,01% 0,08% 9,23% 3 1367 1398 1376 1419 1367 0,00% 2,27% 0,66% 3,80% 4 1347 1581 1356 1587 1347 0,00% 17,37% 0,67% 17,82% 10 1 1308 1313 1311 1307 1307 0,08% 0,46% 0,31% 0,00% 2 1172 1173 1171 1171 1171 0,09% 0,17% 0,00% 0,00% 3 1163 1162 1161 1162 1161 0,17% 0,09% 0,00% 0,09% 4 1490 1705 1494 1710 1490 0,00% 14,43% 0,27% 14,77% 11 1 2260 2247 2246 2260 2246 0,62% 0,04% 0,00% 0,62% 2 2052 2868 2035 2925 2035 0,84% 40,93% 0,00% 43,73% Resultados Computacionales 62 1 1144 1348.5 17.88% 2 1334 1559.5 16.90% 3 1113 1259 13.12% 4 608 751.5 23.60% 5 861 1186.25 37.76% 6 578 1021.5 76.73% 7 835 941.25 12.72% 8 609 710.25 16.63% 9 1083 1311.5 21.10% 10 1161 1284.25 10.62% 11 1725 2102 21.86% 12 1758 2035.5 15.78% 13 1881 2081.25 10.65% 14 1568 1774.5 13.17% 15 1270 1467.75 15.57% 16 1977 2562.75 29.63% 17 1579 1844.5 16.81% 18 2120 2356.5 11.16% 19 2366 2767.75 16.98% 20 2604 3008 15.51% 21 2792 3248.25 16.34% 22 1483 1735.25 17.01% 23 1617 1976 22.20% 24 2510 2957 17.81% 25 1528 1760.75 15.23% 26 1332 1509.75 13.34% 27 1834 2140.75 16.73% 28 1846 2144.5 16.17% 63 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados 29 3353 3766.75 12.34% 30 1796 1931 7.52% 31 2915 3834.75 31.55% 32 3357 4976.75 48.25% 33 3192 4580 43.48% 34 3989 7082.5 77.55% 35 4097 5987.25 46.14% 36 4632 8119 75.28% 37 7019 9781.5 39.36% 38 3885 6643 70.99% 39 5192 8907.75 71.57% 40 4831 7303.5 51.18% Incremento medio: 28.11% El incremento medio del 28.11% del valor de la función objetivo, pone de manifiesto que, ciertamente, el uso de una buena solución inicial supone una diferencia importante en el resultado obtenido. Se puede observar que las instancias con un mayor incremento porcentual son las que se definieron como grandes (de la 31 a la 40). Estas instancias presentan un incremento medio del valor de la función objetivo del 55.54%, mientras que las instancias medianas (de la 1 a la 30) tienen un incremento medio del 18.92%. Esto se debe a que, como ya se explicó, las instancias medianas tienen un horizonte de planificación de dos semanas, mientras que las instancias grandes tienen uno de cuatro semanas. Por tanto, en este último tipo de instancias, la distribución inadecuada de los quirófanos y las consultas entre las distintas unidades, implica la imposibilidad de hacer frente correctamente a las intervenciones programadas durante cuatro semanas, y el consecuente aumento de la función objetivo durante ese periodo. Esto, por otro lado, significa que la mejoría que supone una solución inicial adecuada, puede verse reflejada en los resultados durante cuatro semanas, de ahí que el incremento del valor de la función objetivo sea mayor que en las instancias medianas. Por tanto, se puede concluir que, si bien la utilización de una solución inicial satisfactoria siempre mejorará visiblemente los resultados, cuanto mayor sea el horizonte de planificación, más evidente será esa mejora, y más necesario será hallar una buena solución inicial. 64 8 CONCLUSIONES l presente trabajo aborda la programación y planificación de un hospital de referencia real, con el fin de minimizar los retrasos totales de la atención a cada uno de los pacientes. De este modo, se garantiza el aumento, no solo de la calidad de vida de cada paciente, que es el objetivo principal, sino también de su grado de satisfacción respecto al cuidado recibido y de la confianza que depositará en el sistema en ocasiones futuras. La programación del hospital en el corto plazo implica establecer las fechas precisas en que cada paciente será atendido en cada etapa, así como el cirujano (o los cirujanos) que llevará a cabo esta consulta o intervención, y la consulta médica o quirófano en que se realizará. Para afrontar la programación de las intervenciones, se han elaborado cuatro metaheurísticas que, a través del característico proceso iterativo, hallan una secuencia de intervenciones que da lugar a un valor de la función objetivo aceptable. Para afrontar la planificación de los recursos del hospital en el medio plazo, se ha elaborado un Algoritmo Extendido que permite hallar una distribución satisfactoria de los quirófanos y las consultas entre las unidades hospitalarias. Este algoritmo parte de una serie de soluciones iniciales aleatorias y, tras analizar los resultados de la función objetivo y elegir la mejor, busca mejorar dicha solución explorando vecindades cercanas en el espacio de soluciones. Este procedimiento, similar al de un algoritmo de búsqueda local, se repite en dos iteraciones. Resulta muy interesante poder aplicar los conocimientos sobre sistemas de producción al entorno sanitario, ya que la salud es primordial y cualquier avance o mejora en su tratamiento supone un enorme progreso para toda la sociedad. E 65 9 LÍNEAS DE FUTURA INVESTIGACIÓN ería muy interesante continuar la investigación sobre la aplicación de la teoría de sistemas productivos en el entorno sanitario, ya que tiene mucho potencial por la semejanza de ambos entornos. En primer lugar, se podrían añadir más restricciones al problema que permitieran equipararlo aún más a la realidad. Por ejemplo, podrían añadirse condicionantes para decidir qué cirujanos realizan las consultas PAE o POST. Por otro lado, podría profundizarse en la programación de la producción teniendo en cuenta, además del proceso médico-quirúrgico PAE-OR-POST, las consultas genéricas. En este proyecto, las consultas genéricas se han tenido en cuenta únicamente a la hora de reducir la disponibilidad de cada cirujano, que en lugar de trabajar cinco días a la semana, se considera que trabajan cuatro. Además, resultaría interesante ampliar la búsqueda de soluciones iniciales. Cambiando los criterios de terminación del Algoritmo Extendido, que actualmente solo itera dos veces, y algunas especificaciones más, podría elaborarse un algoritmo de búsqueda local que hallara soluciones iniciales mejores, y en consecuencia, permitiera mejorar la función objetivo. Por otra parte, para programar las intervenciones se ha utilizado un sistema open-scheduling, según el cual un cirujano asignado a consultas un día, puede atender a muchos pacientes en consultas distintas. Del mismo modo, un cirujano que está asignado a quirófanos un día, puede atender a muchos pacientes en distintos quirófanos. Esta forma de programación puede resultar desorganizada y quizá despertar recelo en los cirujanos, y habría que comprobar si realmente resulta eficiente. Podría elaborarse, sin embargo, un modelo del problema para el cual el cirujano asignado a consultas un día, está asignado a una consulta en concreto. En cuanto a los quirófanos, es más complicado establecer este concepto de permanencia, ya que cada intervención requiere un nivel de habilidad para responsable y asistente distinto, y, por tanto, una pareja de cirujanos distinta. Por último, el modelo que se ha elaborado implica la sucesión directa de PAE, OR y POST de cada intervención de la secuencia. Por esta razón, la mayoría de las reglas de despacho que se han elaborado sitúan antes a las intervenciones que entran en POST, ya que, de lo contrario, estas podrían quedarse sin tiempo (habría tenido lugar antes el PAE, OR y POST de las intervenciones que entran a PAE, y el OR y POST de las intervenciones que entran a OR). Sería interesante elaborar un modelo que programara la etapa inicial de cada intervención primero, y luego siguiera con las etapas posteriores. S 66 REFERENCIAS Araujo, L., & Cervigón, C. (2009). Algoritmos evolutivos: un enfoque práctico. Ra-Ma. Cañete, C., Fernández-Viagas, V. & Molina, J. M. (2022). Métodos iterativos voraces para resolver la planificación integrada de consultas y quirófanos. Escuela Técnica Superior de Ingeniería. Universidad de Sevilla. https://idus.us.es/bitstream/handle/11441/140234/TFG4001_Ca%C3%B1ete%20Yaque.pdf?sequ ence=1 De Antonio Suárez, O. (2013). Una aproximación a la heuristica y metaheuristicas. INGE@UAN, 1(2). http://revistas.uan.edu.co/index.php/ingeuan/article/view/217 Framinan, J. M., Leisten, R., & García, R. R. (2014). Manufacturing scheduling systems: An Integrated View on Models, Methods and Tools. Springer Science & Business Media. Gorgemans, S., & Urbina, O. (2017). Aproximación al proceso productivo del sistema sanitario español. ICADE, 0(99), 69. https://doi.org/10.14422/icade.i99.y2016.003 Herrera, F. (2017). Introducción a los Algoritmos Metaheurísticos. -. https://upcommons.upc.edu/handle/2117/191402 Melián, B., Moreno, J. A., & Moreno, J. M. (2003). Metaheurísticas: una visión global. Inteligencia artificial: Revista Iberoamericana de Inteligencia Artificial, 7(19), 7-28. ISSN: 1137-3601. https://www.redalyc.org/pdf/925/92571901.pdf Morera, C. P., Darós, L. C., Herrera, M., & Maheut, J. (2012). Toma de decisiones en la empresa: proceso y clasificación. http://hdl.handle.net/10251/16502 Pérez, P., Framiñán, J. M., & Fernández-Viagas, V. (2018). Programación de Operaciones. Escuela Técnica Superior de Ingeniería. Universidad de Sevilla. 67 Diseño de la distribución de quirófanos y consultas mediante algoritmos aproximados Pérez, P., Framiñán, J. M., & Navarro, B. (2022). Programación de Operaciones. Escuela Técnica Superior de Ingeniería. Universidad de Sevilla. Sipper, D., & Bulfin, R. L. (1998). Planeación y control de la producción. https://s39fbb900fa1cbc52.jimcontent.com/download/version/1519071965/module/14098469730/ name/1.-Planeacion-y-control-de-la-produccion--Sippper-Bulfin-1-384.pdf Tejeda, A. S., (2011). Mejoras de Lean Manufacturing en los sistemas productivos. Ciencia y Sociedad, 36(2), 276-310. ISSN: 0378-7680. https://www.redalyc.org/articulo.oa?id=87019757005 Universidad de Granada (2013). Bioinformática. Algoritmos Genéticos I. Conceptos Básicos. https://sci2s.ugr.es/sites/default/files/files/Teaching/GraduatesCourses/Bioinformatica/Tema%20 06%20-%20AGs%20I.pdf