Programación de la producción en entornos sanitarios: resolución mediante algoritmo iterativo con restricción de camas

i Proyecto Fin de Grado Ingeniería de Organización Industrial Programación de la producción en entornos sanitarios: resolución mediante algoritmo iterativo con restricción de camas Autor: José María González Nieto Tutor: Víctor Fernández-Viagas Escudero y Carla Talens Fayos Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 ii iii Proyecto Fin de Grado Ingeniería de Organización Industrial Programación de la producción en entornos sanitarios: resolución mediante algoritmo iterativo con restricción de camas Autor: José María González Nieto Tutores: Víctor Fernández-Viagas Escudero Carla Talens Fayos Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 iv v Trabajo Fin de Grado: Programación de la producción en entornos sanitarios: resolución mediante algoritmo iterativo con restricción de camas Autor: José María González Nieto Tutores: Víctor Fernández-Viagas Escudero y Carla Talens Fayos El tribunal nombrado para juzgar el trabajo arriba indicado, compuesto por los siguientes profesores: Presidente: Vocal/es: Secretario: acuerdan otorgarle la calificación de: El Secretario del Tribunal Fecha: vi vii Agradecimientos Me gustaría empezar por agradecer a mi tutor, Víctor Fernández-Viagas Escudero, todo el tiempo que me ha dedicado durante los últimos meses, su atención y su pronta respuesta a mis dudas. No podría haber pedido un mejor tutor para este trabajo que presento. También agradecer la colaboración de Carla Talens Fayos que ha atendido a las tutorías para ofrecer su visión del trabajo y ayudarme en su realización. Por supuesto, quiero agradecer a mi familia, en especial a mis padres y mi hermano que son los que más me han apoyado siempre. A mi padre por hacerme competitivo desde pronta edad. A mi madre por mantenerme durante toda mi formación de pequeño trabajando duro y animándome a no abandonar. Y a ellos dos y mis cuatro abuelos por animarme continuamente a convertirme en mi mejor versión. A mi hermano le agradezco su inestimable confianza en mí, que le hace no dudar en apoyarme en cada decisión que tomo. Por último, agradecer a los compañeros que me han acompañado a lo largo de estos 4 años de grado, las clases y las horas de estudio no habrían sido lo mismo sin la ayuda mutua, el apoyo y la amistad forjada en este tiempo. Esas amistades que me llevo de mi estancia en esta facultad y en Sevilla en general espero que me acompañen siempre. José María González Nieto Sevilla, 2021 viii Resumen El problema de decisión que se ha tratado busca determinar cuál es la mejor forma de integrar las camas en la programación de las operaciones de los pacientes en lista de espera quirúrgica de la especialidad de Cirugía Plástica y Quemaduras Mayores del Hospital Universitario “Virgen del Rocío”. Tradicionalmente, este problema no es abordado porque las camas necesarias para el posoperatorio no suelen suponer un cuello de botella para el problema de programación, pero este año, con la pandemia, se ha podido comprobar que en muchos hospitales la falta de camas ha supuesto un problema en el calendario de operaciones que se tenían programadas. Con el ánimo de comprobar hasta qué punto afecta esta situación a los pacientes que se pueden operar y las tardanzas de los mismos, se han estudiado tres formas diferentes de integrar las camas en el problema, una de las cuáles sería la de uso más común, la propagación, pero con la comprobación de validez que requiere la situación especial que se estudia. Por encima de esta integración, se ha empleado un algoritmo iterativo con recocido simulado para buscar la mejor solución para unos datos generados en el propio problema que buscan simular la situación en la especialidad del hospital. Este algoritmo iterativo tiene tres variantes distintas. Las diferentes propuestas que se plantean buscan establecer una programación de las operaciones que cumpla con las restricciones del problema. Fundamentalmente lo que se trata es de encontrar la secuencia de pacientes que reduzca la tardanza de estos y que además consiga introducir en el horizonte temporal todas las operaciones posibles. La tardanza de los pacientes viene determinada por la fecha que se ha establecido como máxima para que el paciente se opere, la fecha de vencimiento o límite. Ambos factores, tardanza y si el paciente es operado o no en el horizonte temporal estudiado, serán ponderados según la prioridad del paciente. ix 4 1.3 Algoritmos Los problemas, desde la perspectiva de la complejidad computacional, pueden ser clasificados en dos tipos: problemas polinomiales (P) y problemas no polinomiales (NP). El problema presentado en el actual trabajo es NP-hard al ser una generalización del taller de flujo híbrido con dos etapas. Por tanto, lo más conveniente es el uso de métodos aproximados con los que se puedan obtener buenos resultados tanto en calidad como en tiempo. Para este tipo de problemas, los algoritmos exactos no suelen tener un buen rendimiento en la literatura, por lo que se han desarrollado muchos algoritmos aproximados con la habilidad de proporcionar soluciones de calidad a los problemas combinatorios en breves tiempos computacionales. Las técnicas heurísticas y metaheurísticas están incluidas en estos algoritmos aproximados (de Antonio Suárez, 2014). Las heurísticas pueden ser definidas como algoritmos dependientes del problema, es decir, se define una heurística para un problema determinado. Mientras que las metaheurísticas son genéricas, con pocos cambios se pueden emplear en toda una variedad de problemas. El algoritmo que se utiliza en el presente trabajo es el algoritmo codicioso iterativo (Iterated Greedy) es un algoritmo metaheurístico de búsqueda que itera usando la ejecución repetida de dos fases principales, la destrucción parcial de un candidato y la reconstrucción del mismo. Está basado en un principio simple, pero a pesar de su simplicidad ha servido para la creación de algoritmos de alto rendimiento. En combinación con otras metaheurísticas de optimización como la búsqueda local, ha tenido resultado muy interesantes en su aplicación en multitud de problemas (Ruiz & Stüzle, 2007). En la literatura no hay un acuerdo completo acerca de si el algoritmo codicioso iterativo entra en la definición de heurística o metaheurística. En este trabajo se ha decidido adoptar la visión de la metaheurística por entender que las heurísticas son algoritmos que paran en un tiempo fijo definido por las variables del problema. Las metaheurísticas serían algoritmos que podrían ser alargados hasta el infinito si no se impusiera un tiempo de finalización. 5 2. Descripción del problema “Las obras se tienen medio terminadas cuando se han comenzado bien” - Séneca El problema que se aborda en este Trabajo Fin de Grado se localiza en la especialidad de Cirugía Plástica y Quemaduras Mayores del Hospital Universitario Virgen del Rocío. Poniendo en contexto, la especialidad ejecuta alrededor de 3000 cirugías por año, incluyendo emergencias. Más específicamente, la especialidad cuenta con 4 quirófanos, uno de los cuales no va a estar disponible para las operaciones listadas en espera, ya que será reservado para las emergencias. Por lo que, al final, existen 3 quirófanos disponibles para estas cirugías (Molina-Pariente et al., 2015). Estos 3 quirófanos no están siempre disponibles, siguen unos horarios. Por las mañanas todos los quirófanos pueden ser usados de 8:30 a 14:30, es decir, durante 6 horas. Por las tardes solo 1 quirófano de los anteriores va a poder emplearse, y su horario es de 15:30 a 19:30, está abierto durante 4 horas. La cantidad de quirófanos disponibles se representa por Q. En la especialidad se tiene acceso a dos tipos de camas (representadas por C) para la post operación del paciente. Por un lado, las camas PACU, que son unidades destinadas al ingreso de pacientes que han sido sometidos a anestesia general, regional o alguna sedación considerable. Su objetivo es la recuperación de las funciones orgánicas y los reflejos vitales del paciente, que pueden ser anulados tras la anestesia. En estas camas se monitorea el pulso del paciente, su presión sanguínea y sus niveles de oxígeno. Estas camas las necesitan más de la mitad de los pacientes, pues son sometidos a dosis de anestesia suficientes como para ser monitoreados durante un tiempo, que generalmente suele ser corto, entre 1 y 3 horas. Por otro lado, las camas UCI, son camas localizadas en la Unidad de Cuidados Intensivos. En estas unidades se proporciona medicina intensiva a los pacientes que tienen una condición grave que pone en riesgo su vida. La medicina intensiva se basa en dar soporte vital o soporte a sistemas orgánicos, para lo que se supervisa y monitoriza continuamente al paciente para seguir su evolución (Medicina intensiva, 2021). Las camas UCI son mucho menos usadas que las PACU, pero los pacientes que las necesitan suelen permanecer en estas entre 12 y 36 horas. En condiciones normales de funcionamiento, en las que el hospital no se encuentra saturado, la especialidad cuenta aproximadamente con un 200% de camas UCI respecto a la cantidad de quirófanos, y con un 167% de camas PACU, también respecto a la cantidad de quirófanos. Durante algunos momentos de la pandemia, este número se ha visto reducido y es objeto de análisis en este estudio. Previamente a la programación de los quirófanos se ha llevado a cabo una consulta con cada paciente de la lista de espera. El encargado de esta consulta es el que decide qué cirujano será el que tiene que operar al paciente, teniendo en cuenta los problemas que el paciente presenta y las habilidades de los cirujanos disponibles. Teniendo disponibles datos históricos de operaciones similares a las que los pacientes se van a someter, este encargado puede hacer una estimación del tiempo que se va a tardar en la cirugía (este tiempo se representa como duracion_operacion), de si el paciente va a necesitar recuperarse en alguna cama UCI o PACU (si esto ocurre, la representación es NC=1, para la necesidad de PACU o 2 para la necesidad de UCI), y de cuánto tiempo tiene que permanecer en la cama (dur_post_operacion). Según la gravedad del paciente se va a establecer una prioridad para el mismo. Además, conforme a la prioridad que se le ha asignado se le va a dar una fecha límite para la cirugía, que se tratará de no superar. Una vez el paciente está listo, se establece una fecha de lanzamiento, a partir de la cual puede ser operado. 6 El presente trabajo recoge la programación del calendario de operaciones y el quirófano en el que las mismas van a suceder durante los 5 días laborales de la semana (representados por D). En la Figura 4 se presenta un cuadro para entender el punto en el que se enmarca el problema. El problema integrado que se aborda en este trabajo consiste en la programación de las operaciones a pacientes en quirófanos, y su posterior etapa de postoperatorio, si lo necesitasen, en camas PACU o UCI (ver elementos en Figura 4 acotados por las líneas discontinuas). Como se puede observar, este problema recibe entonces información de la consulta previa. Con esa información, la estructura de la unidad, y las características específicas de los pacientes se realiza la asignación de pacientes a los quirófanos, teniendo en consideración que no pueden quedar pacientes con necesidad de camas PACU o UCI sin cama o sin poder permanecer en el quirófano después de la operación. Cuando los pacientes terminan de ser operados, o bien se les da el alta, que es el caso en el que los pacientes no necesitan una cama, o bien son atendidos en una cama PACU o UCI. Todos los pacientes que salen de la cama UCI pasan por una cama de hospitalización luego, mientras que solo algunos de los pacientes de las camas PACU necesitan luego la atención en la cama de hospitalización. Sin embargo, lo que ocurra después del uso de las camas UCI o PACU queda fuera del objetivo de este trabajo. 2.1 Restricciones del problema En cuanto a las restricciones del problema de estudio y comenzando por los cirujanos, éstos no pueden operar siempre, por lo que tienen asignados unos turnos en la semana. Así, cuando se quiera alojar la operación del paciente en un quirófano hay que revisar previamente que el cirujano asociado al mismo tenga el turno disponible, y no tenga otra operación ya programada a la misma hora. Como es comprensible, un solo cirujano solo puede operar a un paciente al mismo tiempo, y en un quirófano solo puede haber un paciente al mismo tiempo. También el paciente no puede ser incluido en calendario hasta que la fecha en la que podría estar disponible (denotado por fecha de lanzamiento) no se alcance. Como máximo los pacientes entran en el calendario el último día considerado en el horizonte temporal. Si no se ha podido incluir al paciente en ese momento, se queda en la lista de espera hasta que se programe la siguiente semana de cirugías. Las camas UCI y PACU, necesarias para muchos pacientes después de las operaciones para recuperarse, también van a suponer una restricción para la programación de las cirugías. En este trabajo se aborda el problema de la restricción de las camas de tres formas diferentes:  Las camas se integran en la decisión: no se puede operar a ningún paciente si no se está seguro de que va a existir una cama libre en el momento en el que el paciente acabe de ser operado.  Las camas no se integran en la decisión: se decide el calendario y los horarios sin contar con la disponibilidad de las camas. A posteriori, el resultado se propaga a las camas. Si dos pacientes tienen que usar una cama al mismo tiempo, la secuencia será inválida. Figura 4. Flujo de pacientes (Elaboración propia) 7 o En una de las versiones de las camas separadas, la condición es que todos los pacientes, al salir de la operación, deben tener una cama disponible obligatoriamente. o En la otra versión, al salir de la operación los pacientes que necesiten una cama pueden quedarse en el quirófano si las camas están todas ocupadas. Esto es posible siempre que ningún paciente necesite el quirófano durante ese tiempo. Los quirófanos están totalmente equipados, por lo que no hay problemas en dar a los pacientes los tratamientos que requieren en los mismos. 2.2 Objetivo El objetivo de la programación es crear una lista de pacientes para la entrada de estos en quirófanos. Se trata de que esta lista de pacientes esté ordenada de forma que se minimice la suma de la tardanza de los pacientes ponderada, 𝐹𝑂 =∑(𝑇𝑖 𝐷−𝑂𝑝𝑖)∗𝑃𝑟𝑖 𝑃 𝑖=1 En el primer término del sumatorio, el primer sumando divide la tardanza del paciente i (𝑇𝑖) entre el horizonte temporal del problema. Aunque el anterior es el objetivo principal, podría ocurrir que muy poca cantidad de pacientes (P) fuesen incluidos en los quirófanos y se obtuviese un buen resultado. Para evitar ese problema, se integra en la función objetivo una variable dependiente de si el paciente pudiera ser operado en el horizonte temporal del trabajo (𝑂𝑝𝑖). Esta variable sería igualmente ponderada según la prioridad del paciente (𝑃𝑟𝑖). Por supuesto, se trata de obtener la mejor secuencia para estos objetivos y cumpliendo con todas las restricciones del problema. La tardanza de un paciente es el tiempo que pasa entre la fecha de vencimiento, fecha antes de la cual debería haber sido operado, y el momento en el que verdaderamente es operado. El concepto de tardanza ponderada, en este trabajo, se refiere a dividir la tardanza del paciente entre el horizonte temporal que se está estudiando, que en este caso es de 5 días. Como se ha explicado en el punto anterior, en el código se han incluido diferentes formas de trabajar respecto a la restricción de las camas, estas modificaciones se encuentran tanto en la función que decodifica las secuencias para crear la matriz con información acerca de las operaciones y en el algoritmo iterativo. Entonces uno de los objetivos del trabajo es encontrar cuál de las diferentes versiones soluciona mejor el problema de programación que se aborda, si existiese alguna mejor que otra. En todos los algoritmos de decodificación del programa se emplea una solución matricial que guarda, las entradas de los pacientes en quirófanos por orden. En la matriz se guarda el paciente, el quirófano al que entra, el turno en el que lo hace, la hora a la que se empieza a operar, y a la hora que acaba. En lo que concierne a la función objetivo, esta matriz se utiliza para el cálculo inicial de la tardanza, ya que contiene la información de los turnos, y eso hace fácilmente extraíble el día de operación. En el dibujo descriptivo de esta matriz que se muestra en la Figura 5, las filas representan a las entradas de pacientes en los quirófanos. Figura 5. Matriz de entrada de pacientes (Elaboración propia) 8 3. Metodología “Ninguna pérdida debe sernos más sensible que la del tiempo, puesto que es irreparable” - Zenón de Citio Como se ha dicho anteriormente el objetivo del problema es el de ofrecer una ordenación de la lista de pacientes en espera que minimice la tardanza ponderada y maximice la cantidad de pacientes operados en el horizonte temporal. Para simular la realidad del hospital, se han generado toda una serie de datos acerca de los pacientes y los cirujanos (ver sección 4). Se crea una secuencia inicial de pacientes empleando la regla de despacho LPT. Esta función alimenta de datos a un algoritmo iterativo codicioso, que es el encargado de crear secuencias, buscar su óptimo local, y quedarse con la secuencia que mejor resultado ha ofrecido en la función objetivo (ver detalle en Sección 2.2). Dentro del algoritmo, cabe resaltar la función de decodificación (ver Sección 3.1), que es la función que recibe una secuencia y la transforma en un calendario del que el resultado es la matriz de la que se ha hablado previamente, y la función objetivo. Se crean diferentes algoritmos iterativos codiciosos empleando todas las combinaciones posibles entre las funciones de decodificación desarrolladas (ver Sección 3.1) y las formas de tratar los resultados de la función objetivo obtenidos con la secuencia que sale de la función de decodificación. Se crean estos diversos algoritmos para adaptar el problema a las posibles decisiones que la especialidad del hospital podría tomar en caso de que una situación de escasez de camas acontezca y no sea solucionable de forma inmediata. Cada uno de los pasos que se han seguido y las variaciones entre las diferentes versiones van a ser expuestas a continuación. 3.1 Función de decodificación de las secuencias Se han desarrollado dos funciones de decodificación diferentes, una para la versión de camas integradas, y otra para las dos versiones de camas separadas. Ahora se van a explicar en mayor profundidad. Cada una de ellas responde a una forma diferente de generar un problema completo a partir de la secuencia de trabajos. En todas ellas hay que tener en cuenta la secuencia temporal que siguen los distintos recursos del problema. En los quirófanos, el tiempo se expresa en turnos y horas, por lo que cada paciente es asignado a un quirófano en un turno y a una hora concreta. Las horas se reinician cada vez que se cambia de turno, los turnos de mañana son de 6 horas y los de tarde de 4 horas. Las camas siguen una configuración temporal distinta. El tiempo durante el cual un paciente necesita usar una cama PACU o UCI viene dado en horas totales, no en turnos y horas como los quirófanos, por lo que, conociendo el momento en el que el paciente se operaría en turno y hora, hay que traducir las horas de las camas para poder estimar en qué momento la cama estará libre de nuevo para albergar a otro paciente de la lista. En la Figura 6 se pone de manifiesto este hecho, el paciente comienza a operarse en el turno 0 (correspondiente al primer turno de mañana) a la hora 0:00, y termina de operarse en el turno 0 a la hora 03:00. Para la cama en la que entra el paciente, este paciente está entrando a las 11:30, permanece en la cama 12 horas y sale a las 23:30. La cama vuelve a estar disponible para la entrada de otros pacientes en el turno 2 (turno de mañana del día siguiente) a la hora 0:00. 9 Una de las restricciones del problema es que la operación no puede ser llevada a cabo si se acabara después de la hora máxima establecida para el turno, es decir, aunque la operación se pueda iniciar dentro de las restricciones temporales, si no acaba también dentro de las mismas esa operación no se añade al calendario en ese turno. El procedimiento de decodificación engloba a todos los pacientes listados, con lo que se estudian los pacientes por el orden en el que se encuentran en la lista, buscando en qué momento pueden entrar estos pacientes en los diferentes quirófanos. Cuando son conocidos los momentos en los que podría ser operado, tanto el turno (T), como la hora dentro del turno (H), los tiempos que han resultado son comparados y la función elige el tiempo que permite la entrada al paciente lo antes posible (TiempoT[quirofano] y TiempoH[quirofano]). En caso de empate, elige el quirófano que más tarde se haya estudiado. Durante el estudio de los posibles momentos de entrada del paciente en cada uno de los quirófanos, los tiempos de entrada en cada uno de los quirófanos se expresan con TiempoTAux[quirofano] y TiempoHAux[quirofano] de forma provisional hasta que se comparen los tiempos de los distintos quirófanos y se decida por el mejor. En el momento en el que un paciente no pueda entrar en ninguno de los quirófanos disponibles (𝑂𝑝𝑖= 0), la función acaba y el último paciente que se estaba estudiando es el primero en quedar fuera del calendario. Todos los pacientes que siguen a este también quedan fuera. Respecto a las camas, estas solo se tienen en cuenta en la función de decodificación en su versión de camas integradas, los tiempos de las camas se representan por TiempoTCama y TiempoHCama. Su dinámica se explica en la Sección 3.1.1. La salida de la función es la matriz (M), ya explicada en el punto 2.2. Esta matriz es vital, por razones obvias, para el equipo del hospital, y también lo es tanto para las funciones relacionadas con la decodificación, como para el algoritmo en el que la función se anida. Se detalla el pseudocódigo de la función en la Figura 7. Figura 6. Representación de la divergencia de secuencias temporales (Elaboración propia) 10 A continuación, en la Sección 3.1.1 se explica en detalle el funcionamiento de la función de decodificación que integra las camas en el proceso de decisión para establecer el turno y la hora en la que el paciente se puede operar. En la Sección 3.1.2 se desglosa la función que no considera las camas en el momento de asignar los turnos y horas de los quirófanos a los pacientes. Esta función de decodificación se usa en compañía de otra función, que cuenta con dos versiones distintas, que se encarga de comprobar si hay camas para los pacientes que salen de los quirófanos. 3.1.1 Camas integradas En esta versión de la función de decodificación se exige que haya una cama disponible cuando el paciente vaya a salir de la operación, por lo que nunca se tendrán pacientes en espera entre la fase de operaciones y la fase de las camas. Es una aplicación lógica del problema que se aborda, pues un paciente que requiere ser tratado de forma intensiva después de una operación nunca puede quedar sin esa atención, por el riesgo que entrañaría para la salud del paciente. En el código esto se exige no introduciendo el paciente hasta que el momento en el que su operación acabe coincida con el momento en el que una de las camas quede libre. A priori, sería la solución más lógica si verdaderamente se va a tener un problema en las camas y éstas se convierten en un cuello de botella. Pues lo que se vería es que acaba teniendo resultados similares a los que se tendrían en el caso de que no hubiese nunca problemas de camas y simplemente se propagase la solución de los quirófanos a las camas. Antes de que se compruebe si en un quirófano en un turno y hora determinada se puede operar al paciente en estudio, se comprueba si este necesita de una atención en cama posterior. Si no la necesita, la función solo comprueba la disponibilidad de quirófano y cirujano asociado. Si la necesita, la función comprueba si en el turno en el que se encuentra hay alguna cama libre, al menos que se quede libre durante algún momento del turno. En caso de que no haya libre OUTPUTS M Begin for i=0 to P do: for j=0 to Q do: for x=T to d*2 do: TiempoTAux[j], TiempoHAux[j] := T, H if 𝑂𝑝𝑖= 1 do: for j=0 to Q do: if j=0 do: j* := j TiempoT[j*] := TiempoTAux[j*] TiempoH[j*] := TiempoHAux[j*] else if TiempoTAux[j] < TiempoT[j*] or (TiempoTAux[j] = TiempoT[j*] and TiempoHAux[j] <= TiempoH[j*]) do: j* := j TiempoT[j*] := TiempoTAux[j*] TiempoH[j*] := TiempoHAux[j*] M := i, j*, TiempoT[j*], TiempoH[j*], TiempoH[j*] + duracion_operación if 𝑁𝐶𝑖= 1 or 𝑁𝐶𝑖= 2 do: # Solo para la versión Camas Integradas TiempoTCama, TiempoHCama := TiempoT[j*], TiempoH[j*] + dur_post_operacion end Figura 7. Pseudocódigo funciones de decodificación (Elaboración propia) 11 ninguna cama del tipo que necesita, ese turno no se estudia, se pasa al siguiente y se vuelve a intentar. Una vez que ya se conoce cuál es el mejor quirófano para operar al paciente, se actualiza el tiempo de la cama según el tiempo que el paciente tenga que permanecer en ella. Quedando fijado el nuevo tiempo al momento en el que se queda libre, puesto en turnos y horas. 3.1.2 Camas separadas En las versiones de camas separadas, se distinguen dos partes: la primera es la función de decodificación, y la segunda es una función especial que comprueba la validez de la secuencia que se ha decodificado. La función de decodificación de ambas camas es idéntica. En ella se suprime la parte en la que se tiene que comprobar que existan camas para incluir al paciente, haciendo la función más sencilla, pues solo hay que tener en cuenta los turnos de los quirófanos y los turnos en los que el cirujano asociado al paciente trabaja. Los tiempos de los quirófanos y los cirujanos son los únicos que hay que actualizar en esta función. El pseudocódigo de esta función se representó en la Figura 7. Ambas versiones de camas separadas responderían a lo que sería la solución normal del problema sin la restricción de las camas que se está estudiando el trabajo. La primera versión es la más pura, en la que, para que la secuencia tenga validez, la cama tiene que estar siempre disponible nada más el paciente termine de operarse. Para hacer las comprobaciones, se toma cada uno de los pacientes que han entrado en el calendario de operaciones, y, si el paciente necesita una cama, se comprueba que exista dicha cama en el momento en el que este paciente sale del quirófano. Si esta cama no existiese, es decir, no estuviese libre en el momento adecuado, la secuencia sería inválida. Si el paciente no necesita cama, se continúa estudiando el siguiente paciente. La Figura 8 contiene el pseudocódigo de esta primera versión de la función. La segunda versión permite algo más de laxitud, siendo posible que los pacientes permanezcan en los quirófanos después de operarse si no hay camas disponibles del tipo necesario en el momento de culminación de la operación. Esto es posible siempre que, durante ese tiempo en el que el paciente tiene que permanecer en el quirófano para el posoperatorio, no haya otro paciente que tenga que entrar en el quirófano (que no exista otro paciente luego se representa con existe_ProxP=0). Si existe ese paciente en el calendario, y sigue sin haber camas libres en el momento en el que tiene que entrar, la secuencia queda invalidada. El pseudocódigo de esta función se encuentra en la Figura 9. La matriz (M) contiene la información que las funciones de ambas versiones necesitan para comprobar la validez de la secuencia, pues es la que recoge los momentos en los que los pacientes que han conseguido entrar dentro de la programación con el horizonte temporal definido entran y salen de los quirófanos. En ambas funciones la información sobre la finalización de los pacientes en quirófano es imprescindible para la asignación de la camas (se representa como 𝑇𝑖𝑒𝑚𝑝𝑜𝑠𝑆𝑎𝑙𝑖𝑑𝑎𝑝𝑎𝑐𝑖𝑒𝑛𝑡𝑒). En la segunda versión, también es importante las horas de entrada en quirófanos, pues son el límite de tiempo que tienen los pacientes que se han tenido que quedar dentro del quirófano en la etapa de posoperatorio. 12 OUTPUTS Π𝑣𝑎𝑙 Begin Π𝑣𝑎𝑙 := True for i=0 to P do: if i en M do: if 𝑁𝐶𝑖= 0 do: continue else if 𝑁𝐶𝑖= 0 do: 𝑓𝑙𝑎𝑔𝑃𝐴 := 0 for c=0 to C do: if TiemposCama[c] <= 𝑇𝑖𝑒𝑚𝑝𝑜𝑠𝑆𝑎𝑙𝑖𝑑𝑎𝑖 do: 𝑓𝑙𝑎𝑔𝑃𝐴 := 1 break if 𝑓𝑙𝑎𝑔𝑃𝐴 = 0 do: Π𝑣𝑎𝑙 = False break else do: break end Figura 8. Pseudocódigo de la función de comprobación de camas separadas versión 1 (Elaboración propia) 13 3.2 Algoritmo Iterativo Codicioso Se proponen tres variantes de la metaheurística iterated local search. La primera variante de la metaheurística acepta todos los resultados obtenidos al invocarse la función objetivo. Aplica una primera fase en la que se obtiene el resultado para la primera secuencia, que se aporta como una entrada al algoritmo. En la segunda fase se destruye y vuelve a construir la secuencia, y en la tercera se realiza una búsqueda local en la que se estudian los vecinos de la secuencia buscando el que aporte la mejor solución a la función objetivo. La primera variante se encuentra en la Sección 3.2.1. La segunda y tercera variantes solo se emplean con la función de decodificación de camas separadas, pues son las funciones que pueden devolver secuencias no válidas. La segunda versión tiene las mismas fases que la primera, pero cuando estudia el resultado obtenido de la primera secuencia, comprueba la validez del resultado, si no es válido, incluye una fase de destrucción y construcción de la secuencia inicial. Luego, en la fase de búsqueda local incluye una penalización en la función objetivo a las secuencias que no aporten resultados válidos. Esta variante se encuentra en la Sección 3.2.2. Por último, la tercera versión difiere de la primera en la fase de búsqueda local, donde replica la fase de destrucción y construcción de la secuencia. Esta variante final se encuentra en la Sección 3.2.3. 3.2.1 Algoritmo iterativo codicioso. Variante 1, ILS_1 El algoritmo, que se basa en la Iterated Greedy propuesta en Ruiz & Stützle, (2007) se inicia siempre con la regla de despacho LPT (Longest Processing Time), por lo que la secuencia inicial está ordenada tal que los pacientes que necesitan más tiempo en el quirófano son los primeros en entrar a estos. El algoritmo se puede ver a grandes rasgos divido en cuatro partes claras. La primera parte es OUTPUTS Π𝑣𝑎𝑙 Begin Π𝑣𝑎𝑙 := True for i=0 to P do: if i en M do: if 𝑁𝐶𝑖= 0 do: continue else if 𝑁𝐶𝑖 ! = 0 do: 𝑓𝑙𝑎𝑔𝑃𝐴 := 0 for c=0 to C do: if TiempoTCama[c], TiempoHCama[c] <= 𝑇𝑖𝑒𝑚𝑝𝑜𝑠𝑆𝑎𝑙𝑖𝑑𝑎𝑖 do: 𝑓𝑙𝑎𝑔𝑃𝐴 := 1 break if 𝑓𝑙𝑎𝑔𝑃𝐴 = 0 do: if existe_𝑃𝑟𝑜𝑥𝑃 = 1 do: for r = 0 to C do: 𝑓𝑙𝑎𝑔𝑇, 𝑓𝑙𝑎𝑔𝐻 := TiempoTCama[c], TiempoHCama[c] if 𝑓𝑙𝑎𝑔𝑇, 𝑓𝑙𝑎𝑔𝐻 <= 𝑇𝑖𝑒𝑚𝑝𝑜𝑠𝑆𝑎𝑙𝑖𝑑𝑎𝑖 do: Actualización TiempoTCama, TiempoHCama else do: Π𝑣𝑎𝑙 := False break else do: break end Figura 9. Pseudocódigo de la función de comprobación de camas separadas versión 2 (Elaboración propia) 20 PACU UCI CI CSM1V1 CSM1V2 CSM2V1 CSM2V2 2 2 0,0754 0,0380 0,0309 0,0312 0,0159 2 4 0,0715 0,0310 0,0224 0,0311 0,0133 2 5 0,0890 0,0352 0,0198 0,0355 0,0174 2 6 0,0835 0,0367 0,0246 0,0335 0,0194 3 2 0,0502 0,0255 0,0264 0,0301 0,0184 3 4 0,0702 0,0291 0,0265 0,0245 0,0166 3 5 0,0618 0,0288 0,0289 0,0269 0,0277 3 6 0,0729 0,0267 0,0254 0,0243 0,0209 4 2 0,0505 0,0346 0,0277 0,0264 0,0258 4 4 0,0401 0,0334 0,0349 0,0326 0,0352 4 5 0,0510 0,0252 0,0305 0,0281 0,0317 4 6 0,0523 0,0220 0,0254 0,0257 0,0323 5 2 0,0357 0,0200 0,0278 0,0290 0,0274 5 4 0,0221 0,0350 0,0322 0,0338 0,0370 5 5 0,0336 0,0351 0,0335 0,0352 0,0257 5 6 0,0317 0,0322 0,0264 0,0373 0,0320 En la Tabla 1, así como en las posteriores, el color verde se emplea para hacer referencia al mejor resultado del ARPD para una combinación concreta de variables, el turquesa para los segundos mejores resultados, el amarillo, el naranja y el rojo representan, respectivamente, el tercer mejor valor, el segundo peor resultado, y el peor resultado. La figura anterior (Figura 10) muestra un resultado claro, el algoritmo de camas integradas no ofrece buenas soluciones en casi ningún caso. Mientras el resto de los algoritmos son más o menos equiparables en sus resultados, encontrándose comprendidas en un menor espacio del gráfico la mayoría de sus soluciones. En contra de lo que se podría haber pensado en un principio, el algoritmo CI funciona mejor cuando la cantidad de camas aumenta. En el gráfico es claro como la media de sus resultados baja con la subida de la cantidad de camas, siendo más influyentes las PACU que las UCI. Estos resultados se ha consolidado con más pruebas que serán expuestas a continuación. El análisis del por qué puede ocurrir esto será hecho al final, después de que se hayan podido agrupar todas las conclusiones derivadas de los distintos estudios. Analizando en la figura otros algoritmos, es evidente que en la primera mitad de la tabla el algoritmo que mejor ha funcionado es el de CSM2V2, y según van aumentando el número de camas PACU, el algoritmo va empeorando e igualándose con todos los demás. El resto de los algoritmos se han comportado bastante planos, sin grandes cambios de tendencia. Por lo que en cómputo general el algoritmo que mejores resultados ofrecería sería el CSM2V2. Para el siguiente estudio se han considerado el número de cirujanos y la variable 𝛽. El número de cirujanos es producto de las combinaciones de las variables 𝛼 y 𝑚𝑑𝑠, por lo que se podría decir que se están estudiando estas dos variables y 𝛽 en este estudio. Los resultados obtenidos se representan a continuación, en la Tabla 2. Siendo su representación expuesta en la Figura Figura 10. Representación del ARPD de los algoritmos según la cantidad de camas PACU y UCI (Elaboración propia) Tabla 2. Soluciones del ARPD para las combinaciones de PACU y UCI (Elaboración propia) 21 11. Beta N Cirujanos CI CSM1V1 CSM1V2 CSM2V1 CSM2V2 110 0,0332 0,0335 0,0295 0,0319 0,0287 1 8 0,0526 0,0258 0,0229 0,0297 0,0264 113 0,0497 0,0237 0,0206 0,0260 0,0158 1,25 10 0,0657 0,0287 0,0310 0,0287 0,0235 1,25 8 0,0703 0,0361 0,0313 0,0336 0,0221 1,25 13 0,0751 0,0344 0,0259 0,0321 0,0295 En este estudio, se observa que el algoritmo CI obtiene buenos resultados en el primer caso cuando la variable 𝛽 es 1 y los cirujanos 10. Es fácil ver que este algoritmo funciona mejor con 10 cirujanos que con cualquier otra combinación, y que empeora con el crecimiento de la variable 𝛽, es decir, con el crecimiento en el número de pacientes. El resto de los algoritmos se mueven en un pequeño rango, sin muchas variaciones. Se vuelve a confirmar que el mejor de los algoritmos es el CSM2V2, siendo el que ofrece mejor resultado en 4 de las 6 combinaciones de variables, seguido del CSM1V2 y luego las variantes de la versión 1. Dos últimos estudios se han realizado para terminar de confirmar resultados. Uno en el que se consideran las variables 𝛽, camas PACU, camas UCI y cantidad de cirujanos, y otro en el que se estudian las variables 𝛼, 𝛽, 𝑚𝑑𝑠, camas PACU y camas UCI. Ambos son prácticamente iguales pues, como se ha dicho antes, la cantidad de cirujanos es una buena aproximación a las variables 𝛽 y 𝑚𝑑𝑠. Sin embargo, se ha decidido explorar más resultados y ver si había algo que resaltar. Solo se van a mostrar las tablas que contengan alguna información relevante en los resultados del ARPD. Tabla 3. Soluciones del ARPD para las combinaciones de 𝛽 y cirujanos (Elaboración propia) Figura 11. Representación del ARPD de los algoritmos según los valores de 𝛽 y el número de cirujanos (Elaboración propia) 22 Alpha Beta Mds PACU UCI CI CSM1V1 CSM1V2 CSM2V1 CSM2V2 1,5 1 3 2 2 0,0506 0,0378 0,0497 0,0361 0,0291 1,5 1 3 2 4 0,0170 0,0325 0,0343 0,0326 0,0199 1,5 1 3 2 5 0,0147 0,0313 0,0256 0,0300 0,0255 1,5 1 3 2 6 0,0449 0,0615 0,0135 0,0501 0,0344 1,5 1 3 3 2 0,0330 0,0218 0,0153 0,0305 0,0154 1,5 1 3 3 4 0,0081 0,0316 0,0293 0,0313 0,0227 1,5 1 3 3 5 0,0210 0,0242 0,0297 0,0318 0,0330 1,5 1 3 3 6 0,0749 0,0318 0,0225 0,0223 0,0204 1,5 1 3 4 2 0,0170 0,0733 0,0598 0,0656 0,0637 1,5 1 3 4 4 0 0,0501 0,0537 0,0488 0,0465 1,5 1 3 4 5 0,0088 0,0414 0,0292 0,0175 0,0384 1,5 1 3 4 6 0,0428 0,0268 0,0191 0,0278 0,0404 1,5 1 3 5 2 0,0127 0,0458 0,0464 0,0558 0,0594 1,5 1 3 5 4 0 0,0298 0,0384 0,0467 0,0516 1,5 1 3 5 5 0 0,0336 0,0412 0,0418 0,0355 1,5 1 3 5 6 0,0030 0,0446 0,0423 0,0483 0,0422 En las soluciones del ARPD lo más relevante es esta Tabla 3 que deja ver que para la combinación de 𝛼 = 1.5,𝛽 = 1 𝑦 𝑚𝑑𝑠 = 3, el algoritmo CI obtiene resultados bastante buenos. Esto para el caso en el que la cantidad de pacientes ronda los 55 pacientes, y el número de cirujanos los 10, siendo prácticamente independiente de la cantidad de camas que existan en el modelo. CI CSM1V1 CSM1V2 CSM2V1 CSM2V2 0,0557059 0,03053038 0,02770425 0,03033043 0,02478223 Resultados ARPD Global Revisando el ARPD global que se ha obtenido en la Tabla 6, los resultados de los casos particulares parecen ser completamente plausibles. El mejor algoritmo ha sido el CSM2V2, seguido de su misma versión, pero con el método 1. El CSM2V1 ha sido ligeramente mejor que el CSM1V1, y a un par de distancia se encuentra el CI. Tabla 4. Soluciones parciales del ARPD para las combinaciones de 𝛼, 𝛽, 𝑚𝑑𝑠, camas PACU y camas UCI (Elaboración propia) Tabla 5. ARPD global (Elaboración propia) 23 5. Conclusiones “La vida es el arte de sacar conclusiones suficientes a partir de datos insuficientes” - Samuel Butler Se han compuesto 5 algoritmos para tratar un posible problema en la programación de operaciones por una escasez en las camas PACU y UCI. Todos los algoritmos han sido iterativos codiciosos, diferenciándose entre ellos en el tratamiento que le dan en las camas para integrarlas en un problema en el que típicamente solo se tienen en cuenta los quirófanos. En los algoritmos se ha tenido en cuenta que se está estudiando un horizonte temporal de una semana. El objetivo de todos es el de conseguir que los pacientes de la lista de espera sean operados antes de su fecha de vencimiento, y que todos los pacientes posibles sean operados dentro del marco temporal del problema. En la evaluación de los algoritmos, se han creado 640 instancias para estudiar los resultados de los 5 algoritmos. Con los 3.200 resultados encima de la mesa, se han hecho comprobaciones teniendo en cuenta diferentes variables para ver cuáles de los algoritmos funcionan mejor. En el primer estudio en el que se consideraban solo las variables de las camas, se observó que el algoritmo CI, que había sido creado con el pensamiento de que fuese una buena solución para el problema de escasez de camas, actúa justamente, al contrario, mejorando conforme aumentan la cantidad de camas. Las camas PACU son las que más afectan a su resultado, esperable al ser las camas PACU mucho más requeridas por los pacientes que las camas UCI. Una posible explicación para este comportamiento no intuitivo es el incremento de complejidad en el algoritmo de las camas integradas frente a las separadas. La experimentación está limitada por tiempo a unos 12 segundos por algoritmo, que es el resultado medio de la operación (𝑚∙𝑄∙𝑑 2∙25) 𝑚𝑖𝑙𝑖𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠, usada para el cálculo del límite de tiempo del algoritmo. La función de decodificación para las camas integradas es bastante más lenta que la versión de camas separadas, pues esta tiene que comprobar en cada paso en qué momento hay camas disponibles. Esto conlleva mayor tiempo de procesamiento que las decodificaciones de camas separadas, que simplemente asignan a quirófanos sin mirar las camas para luego pasar por una función a parte que comprueba ese problema. Esa función en cuanto encuentra una irregularidad ya anuncia que la secuencia no es válida. Por esto se puede pensar que la limitación temporal provoca estos malos resultados, porque, comparativamente con la velocidad del algoritmo, las camas separadas se ejecutan mucho más rápidamente. Además, esto justificaría que el algoritmo mejore cuantas más camas hay, las camas para los pacientes se encuentran con mayor velocidad si hay camas libres y no hay que esperar a que las haya. El algoritmo que mejor se comporta para el problema de escasez es el CSM2V2. Esto es explicable por el hecho de que las versiones 2 permiten que los pacientes se queden en los quirófanos una vez han concluido las operaciones, lo que hace que este algoritmo este contando con “camas extras” en los momentos en los que el resto están muy limitados por este problema. Por eso tiene sentido que, según el número de camas va aumentando, este algoritmo se vaya igualando con los demás en sus resultados. El algoritmo CI, solo parece ser algo mejor que los demás para una combinación específica de todas las variables que se han tenido en cuenta en la experimentación, que es para el caso en el que la generación de pacientes se encuentra en sus mínimos valores, y los cirujanos en la parte media de la tabla, entrono a unos 10, siendo independiente de las camas. Este resultado también es visible en el gráfico del caso 𝛽, cirujanos, en el que la primera combinación de valores era la mejor para el algoritmo CI y que contenía 𝛽 = 1 y cirujanos = 10. Habiendo dejado claro cuál es el peor de los algoritmos y el mejor de ellos, se pueden extraer algunas posibles conclusiones sobre por qué se han obtenido estos resultados. Primero, el factor de que las versiones 2 permitan que los pacientes se queden en los quirófanos ha propiciado que estas versiones sean las mejores para el problema que nos ocupa. Esto ocurre sin importar el método usado, ya que la versión 2 de ambos métodos supera a la versión 1 de estos. 24 Segundo, independientemente del tipo de versión, los algoritmos que emplean el segundo método son por lo general mejores que los que emplean el primer método, CSM2V1 es mejor que el CSM1V1 y el CSM2V2 es mejor que el CSM1V2. De esto se puede concluir que es una buena idea hacer nuevas fases de construcción y de destrucción cada vez que se obtienen secuencias que no son válidas en el problema. Hacer esto aporta una mayor perturbación de la secuencia, por lo que se alcanzan más valles en el limitado tiempo que se tiene para el algoritmo. Que estos valles no se puedan estudiar al completo parece no haber sido algo muy influyente en los resultados obtenidos. En lo que se refiere a los algoritmos que no son CSM2V2 o CI, se puede concluir que funcionan bien prácticamente siempre y que no tienen una tendencia clara, al menos no en los estudios realizados en este trabajo. Con los experimentos que se han llevado a cabo, se puede concluir que los métodos utilizados hasta el momento en el hospital para organizar las camas, es decir, la propagación del resultado en quirófanos hasta las camas es bastante potente, solo habría que modificar la programación en la integración de las funciones que comprueban la validez en las camas dentro del modelo, y en la perturbación de las secuencias al obtener resultados no válidos en la función anterior. Por último, quedaría como una posibilidad dejar que los quirófanos se utilicen como camas para obtener un mayor rendimiento. Principalmente, si el hospital vuelve a tener problemas de camas por algún hecho como el acontecido por la pandemia. 25 6. Bibliografía Graves, Stephen. (1981). A Review of Production Scheduling. Operations Research. 29. 646675. https://doi.org/10.1287/opre.29.4.646 MacCarthy, Bart & Liu, Jiyin. (1993). Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling. International Journal of Production Research – int j prod res. 31. 59-79. https://doi.org/10.1080/00207549308956713 Framinan, J. M., Leisten, R., & García, R. R. (2014). Manufacturing Scheduling Systems: An Integrated View on Models, Methods and Tools (English Edition) (2014.a ed.). Springer. Entender ITIL 2011 Normas y mejores prácticas para avanzar hacia ISO 20000 – Los niveles decisionales. (n.d.). Retrieved May 26, 2021, from https://www.edicioneseni.com/open/mediabook.aspx?idR=1d149467a559fd2acbc4aab12e413dd5 Vahidian, N. (2012). Comparison of Deterministic and Stochastic Production Planning Approaches in Sawmills by Integrating Design of Experiments and MonteCarlo simulation. https://spectrum.library.concordia.ca/975078/1/Vahidian_MASc_S2013.pdf Roland, B., Di Martinelly, C., Riane, F., & Pochet, Y. (2010). Scheduling an operating theatre under human resource constraints. Computers & Industrial Engineering, 58(2), 212–220. https://doi.org/10.1016/j.cie.2009.01.005 González-Busto, B., & García, R. (1999). Waiting lists in Spanish public hospitals: a system dynamics approach. System Dynamics Review, 15(3), 201–224. https://doi.org/10.1002/(sici)1099-1727(199923)15:3<201::aid-sdr170>3.0.co;2-5 Cardoen, B., Demeulemeester, E., & Beliën, J. (2010). Operating room planning and scheduling: A literature review. European Journal of Operational Research, 201(3), 921–932. https://doi.org/10.1016/j.ejor.2009.04.011 Molina-Pariente, J. M., Hans, E. W., Framinan, J. M., & Gomez-Cia, T. (2015). New heuristics for planning operating rooms. Computers & Industrial Engineering, 90, 429–443. https://doi.org/10.1016/j.cie.2015.10.002 de Antonio Suárez, O. (2014). Una aproximación a la heuristica y metaheuristicas. inge@uan – tendencias en la ingeniería, 1(2). Recuperado a partir de http://revistas.uan.edu.co/index.php/ingeuan/article/view/217 Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–2049. https://doi.org/10.1016/j.ejor.2005.12.009 Molina Pariente, J.M. (2016). Operating theatre planning and scheduling in real-life settings. Problem analysis, models, and solution procedures. (Tesis doctoral inédita). Universidad de Sevilla, Sevilla. Marcon, E., Kharraja, S., & Simonnet, G. (2003). The operating theatre planning by the follow-up of the risk of no realization. International Journal of Production Economics, 85(1), 83–90. https://doi.org/10.1016/s0925-5273(03)00088-4 Medicina intensiva. (2021, 25 de febrero). Wikipedia, La enciclopedia libre. Fecha de consulta: 07:47, junio 20, 2021 desde https://es.wikipedia.org/w/index.php?title=Medicina_intensiva&oldid=133518354 Molina-Pariente, J. M., Fernandez-Viagas, V., & Framinan, J. M. (2015). Integrated operating room planning and scheduling problem with assistant surgeon dependent surgery durations. Computers & Industrial Engineering, 82, 8–20. https://doi.org/10.1016/j.cie.2015.01.006 26 7. Anexos 7.1 Código principal using System; using System.IO; namespace TFG { class Program { public static void Main(string[] args) { // PARÁMETROS FIJOS DEL PROBLEMA int dias = 5; // El horizonte temporal para la programación de las operaciones es de 5 días. int numero_quirofanos = 3; // Hay 3 quirofanos pero no están siempre disponibles. Depende del día y si es horario de mañana o de tarde. int[,] disponibilidadquirofano_turno = new int[numero_quirofanos, dias * 2]; // Para 5 días de programación existen 10 turnos (mañana y tarde). // Suponiendo que los 5 dias que se programan es una semana de lunes a viernes tanto por la mañana como por la tarde, los quirofanos que estarán disponibles en cada turno serán: for (int j = 0; j < dias * 2; j++) { // Para las mañanas los 3 quirófanos están disponibles if (j == 0 || j == 2 || j == 4 || j == 6 || j == 8) { for (int i = 0; i < numero_quirofanos; i++) { disponibilidadquirofano_turno[i, j] = 1; } } // De lunes a jueves por las tardes solo hay 1 quirófano disponible else if (j == 1 || j == 3 || j == 5 || j == 7) { disponibilidadquirofano_turno[0, j] = 1; disponibilidadquirofano_turno[1, j] = 0; disponibilidadquirofano_turno[2, j] = 0; } // Para viernes por la tarde 0 quirófanos estarán disponibles else { disponibilidadquirofano_turno[0, j] = 0; disponibilidadquirofano_turno[1, j] = 0; disponibilidadquirofano_turno[2, j] = 0; } } // PARAMETROS VARIABLES DEL PROBLEMA double[] alpha = new double[] { 1.5, 2 }; // Factor para determinar el número de cirujanos int[] mds = new int[] { 3, 4 }; // Número máximo de turnos por semana en los que el cirujano está disponible para realizar cirugías. Se usa para determinar el número de cirujanos double[] beta = new double[] { 1, 1.25 }; // Porcentaje que la suma de las duraciones de las operaciones excede el tiempo total disponible en los quirofanos. 27 Se usa para determinar el número de cirugías en lista de espera double[] porcentaje = new double[] { 2, 3, 4 }; int[] cantidad_camas_PACU = new int[] { 2, 3, 4, 5 }; int[] cantidad_camas_UCI = new int[] { 2, 4, 5, 6 }; // DATOS int m; // Cantidad de pacientes en lista de espera int numero_cirujanos; double[] duracion_operacion; int[] dia_disponible; // Fecha de lanzamiento de la operación int[] fecha_limite; // Fecha antes de la cual el paciente debería haber sido operado double[] prioridad; int[] cirujano_asociado; double[,] horascirujano_turno; // Indica la disponibilidad de un cirujano en un turno int[] necesidad_paciente_cama; // 0 si el paciente no necesita cama, 1 si necesita PACU, 2 si necesita UCI double[] duracion_paciente_cama; // Depende de la cama que necesite, 0 si no necesita // EXPORTACIÓN String ruta = AppDomain.CurrentDomain.BaseDirectory; Console.WriteLine($"{ruta}"); ruta = ruta.Replace("\\", "/").ToString(); DirectoryInfo DIRESC = new DirectoryInfo(ruta + "/temp"); if(!DIRESC.Exists) { DIRESC.Create(); } String ficBatBorrar = ruta + "temp" + "/Experimentacion.csv"; FileInfo FicheroEliminar = new FileInfo(ficBatBorrar); if(FicheroEliminar.Exists) { File.Delete(ficBatBorrar); } String ficCSV = ruta + "temp" + "/Experimentacion.csv"; System.IO.StreamWriter FicheroCSV1 = new System.IO.StreamWriter(ficCSV, true); FicheroCSV1.Write("Alpha" + ";" + "Beta" + ";" + "Mds" + ";" + "N Cirujanos" + ";" + "N Pacientes" + ";" + "N Camas PACU" + ";" + "N Camas UCI" + ";" + "Instancia" + ";" + "Resultado" + ";" + "Algoritmo" + "\n"); // GENERACIÓN DE INSTANCIAS int count = 0; for (int a = 0; a < alpha.Length; a++) { for(int b = 0; b < beta.Length; b++) { for (int c = 0; c < mds.Length; c++) { for(int d = 0; d < cantidad_camas_PACU.Length; d++) { for (int e = 0; e < cantidad_camas_UCI.Length; e++) { for (int f = 0; f < 5; f++) { generacion_datos(dias, alpha[a], beta[b], mds[c], f, numero_quirofanos, disponibilidadquirofano_turno, out duracion_operacion, out dia_disponible, out fecha_limite, out prioridad, out cirujano_asociado, out horascirujano_turno, out m, out numero_cirujanos, out necesidad_paciente_cama, out duracion_paciente_cama); // Creación de secuencia por regla de despacho LPT int[] secuencia = new int[m]; double[] dur_operaciones = new double[m]; 28 Array.Copy(duracion_operacion, dur_operaciones, duracion_operacion.Length); for (int u = 0; u < m; u++) { secuencia[u] = u; } orden_mayor_menor_y_secuencia(dur_operaciones, dur_operaciones.Length, secuencia); count++; Console.WriteLine($"{count}. CAMAS INTEGRADAS"); iterated_greedy_algorithmCI(secuencia, prioridad, fecha_limite, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, necesidad_paciente_cama, cantidad_camas_PACU[d], cantidad_camas_UCI[e], duracion_paciente_cama, alpha[a], beta[b], mds[c], f, FicheroCSV1); count++; Console.WriteLine($"{count}. CAMAS SEP V1 por MÉTODO 1"); iterated_greedy_algorithmCSM1V1(secuencia, prioridad, fecha_limite, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, necesidad_paciente_cama, cantidad_camas_PACU[d], cantidad_camas_UCI[e], duracion_paciente_cama, alpha[a], beta[b], mds[c], f, FicheroCSV1); count++; Console.WriteLine($"{count}. CAMAS SEP V2 por MÉTODO 1"); iterated_greedy_algorithmCSM1V2(secuencia, prioridad, fecha_limite, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, necesidad_paciente_cama, cantidad_camas_PACU[d], cantidad_camas_UCI[e], duracion_paciente_cama, alpha[a], beta[b], mds[c], f, FicheroCSV1); count++; Console.WriteLine($"{count}. CAMAS SEP V1 por MÉTODO 2"); iterated_greedy_algorithmCSM2V1(secuencia, prioridad, fecha_limite, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, necesidad_paciente_cama, cantidad_camas_PACU[d], cantidad_camas_UCI[e], duracion_paciente_cama, alpha[a], beta[b], mds[c], f, FicheroCSV1); count++; Console.WriteLine($"{count}. CAMAS SEP V2 por MÉTODO 2"); iterated_greedy_algorithmCSM2V2(secuencia, prioridad, fecha_limite, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, necesidad_paciente_cama, cantidad_camas_PACU[d], cantidad_camas_UCI[e], duracion_paciente_cama, alpha[a], beta[b], mds[c], f, FicheroCSV1); } } } } } } FicheroCSV1.Close(); } 29 7.2 Código auxiliar // GENERACIÓN DE DATOS DE PARTIDA static void generacion_datos(int dias, double alpha, double beta, int mds, int instancia, int numero_quirofanos, int[,] disponibilidadquirofano_turno, out double[] duracion_operacion, out int[] dia_disponible, out int[] fecha_limite, out double[] prioridad, out int[] cirujano_asociado, out double[,] horascirujano_turno, out int m, out int numero_cirujanos, out int[] necesidad_paciente_cama, out double[] duracion_paciente_cama) { Random aleatorio = new Random(instancia); // NÚMERO CIRUJANOS int l = 1; // Número de semanas de trabajo en el horizonte de planificación double SumRjh = (3 * 6) * 5 + 4 * 5; // Sumatorio de la capacidad de los quirófanos en todo el horizonte de planificación double a = SumRjh / 20; // Capacidad media de un quirófano double cirujanos = alpha * (SumRjh / (l * a * mds)); numero_cirujanos = (int)Math.Round(cirujanos); // NÚMERO DE PACIENTES EN LISTA DE ESPERA m = 1; duracion_operacion = new double[m]; double aux = 0; while (aux < beta * SumRjh) { int mean = aleatorio.Next(1, 4); // La media esperada tomará un valor aleatorio entre 1, 2,3 o 4 horas double SD = mean * ((aleatorio.Next(0, 2) * 0.4) + 0.1); // El coeficiente de variación se genera aleatoriamente a partir del intervalo [0.1μ. . .0.5μ]. double cv = SD / mean; double variance = Math.Pow(mean * cv, 2.0); double mu = Math.Log(mean / Math.Sqrt(1 + variance / (mean * mean))); double sigma = Math.Sqrt(Math.Log(1 + variance / (mean * mean))); MathNet.Numerics.Distributions.Normal normalDist = new MathNet.Numerics.Distributions.Normal(mu, sigma); double randomGaussianValue = normalDist.Sample(); duracion_operacion[m - 1] = Math.Exp(randomGaussianValue); duracion_operacion[m - 1] = Math.Round(duracion_operacion[m - 1], 2); // Redondeo aux = aux + duracion_operacion[m - 1]; m++; Array.Resize(ref duracion_operacion, m); } for (int j = 0; j < m; j++) { if (duracion_operacion[j] > 6) { duracion_operacion[j] = 6; } if (duracion_operacion[j] == 0) { duracion_operacion[j] = 1; } } // CIRUJANOS DISPONIBLES EN CADA TURNO horascirujano_turno = new double[numero_cirujanos, dias * 2]; 36 double[,] horascirujano_turno, int numero_quirofanos, int numero_cirujanos, int dias, out double[,] info_paciente) { info_paciente = new double[secuencia.Length, 5]; for (int l = 0; l < secuencia.Length; l++) { for (int w = 0; w < 5; w++) { info_paciente[l, w] = 1001; } } double[,] tiempos_quirofanos = new double[numero_quirofanos, 2]; //Para cada QUIRÓFANO el turno y la hora en la que nos encontramos double[,] tiempos_quirofanos_auxiliar = new double[numero_quirofanos, 2]; //Inicializo ambos vectores en 0 setval_IMatriz(tiempos_quirofanos, numero_quirofanos, 2, 0); setval_IMatriz(tiempos_quirofanos_auxiliar, numero_quirofanos, 2, 0); double[,] tiempos_cirujanos = new double[numero_cirujanos, 2]; //CIRUJANO, TURNO, HORAS double[,] tiempos_cirujanos_auxiliar = new double[numero_cirujanos, 2]; //Inicializo ambos vectores a 0 setval_IMatriz(tiempos_cirujanos, numero_cirujanos, 2, 0); setval_IMatriz(tiempos_cirujanos_auxiliar, numero_cirujanos, 2, 0); int[] paciente_incluido = new int[secuencia.Length]; setval_IVector(paciente_incluido, 0); for (int i = 0; i < secuencia.Length; i++) //Bucle de los PACIENTES en lista de espera { for (int j = 0; j < numero_quirofanos; j++) //Bucle entre los QUIRÓFANOS: el trabajo se incluye en el quirófano que antes lo pueda procesar { tiempos_quirofanos_auxiliar[j, 0] = tiempos_quirofanos[j, 0]; tiempos_quirofanos_auxiliar[j, 1] = tiempos_quirofanos[j, 1]; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 0] = tiempos_cirujanos[cirujano_asociado[secuencia[i]], 0]; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 1] = tiempos_cirujanos[cirujano_asociado[secuencia[i]], 1]; if (dia_disponible[secuencia[i]] > tiempos_quirofanos[j, 0]) //Actualizo el tiempo del quirófano al momento en el que llega el paciente { tiempos_quirofanos_auxiliar[j, 0] = dia_disponible[secuencia[i]]; tiempos_quirofanos_auxiliar[j, 1] = 0; } //Actualizo el tiempo quirófano o cirujano, según cuál vaya más adelantado if (tiempos_quirofanos_auxiliar[j, 0] < tiempos_cirujanos[cirujano_asociado[secuencia[i]], 0] || (tiempos_quirofanos_auxiliar[j, 0] == tiempos_cirujanos[cirujano_asociado[secuencia[i]], 0] && tiempos_quirofanos_auxiliar[j, 1] < tiempos_cirujanos[cirujano_asociado[secuencia[i]], 1])) //Arreglar para las horas { tiempos_quirofanos_auxiliar[j, 0] = tiempos_cirujanos [cirujano_asociado[secuencia[i]], 0]; tiempos_quirofanos_auxiliar[j, 1] = tiempos_cirujanos [cirujano_asociado[secuencia[i]], 1]; } else { tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 0] = tiempos_quirofanos_auxiliar[j, 0]; 37 tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 1] = tiempos_quirofanos_auxiliar[j, 1]; } double tiempo_inicio_operacion; int turno_actual = Convert.ToInt32(tiempos_quirofanos_auxiliar[j, 0]); int paciente_entraria_en_quirofano = 0; //Se usa para salir del bucle de los turnos cuando ya se ha podido meter al paciente en uno for (int x = turno_actual; x < dias * 2; x++) //Aquí meto la restricción del horizonte temporal (dependiente de los días) { if (disponibilidadquirofano_turno[j, x] == 1 && horascirujano_turno [cirujano_asociado[secuencia[i]], x] != 0) {//Si el quirófano está disponible en este TURNO, y si el cirujano también lo está, sigo con el código, si no ni entro. tiempo_inicio_operacion = tiempos_quirofanos_auxiliar[j, 1]; //ya está actualizado double tiempo_maximo; tiempo_maximo_turno(x, out tiempo_maximo); if (tiempo_inicio_operacion + duracion_operacion[secuencia[i]] <= tiempo_maximo) {//Se puede llevar a cabo la operación tiempos_quirofanos_auxiliar[j, 1] = tiempo_inicio_operacion + duracion_operacion[secuencia[i]]; paciente_incluido[secuencia[i]] = 1; paciente_entraria_en_quirofano = 1; } else {//Actualizar variables tiempos_quirofanos_auxiliar[j, 0]++; tiempos_quirofanos_auxiliar[j, 1] = 0; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 0]++; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 1] = 0; } } else {//Actualizar las variables tiempos_quirofanos_auxiliar[j, 0]++; tiempos_quirofanos_auxiliar[j, 1] = 0; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 0]++; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 1] = 0; } if (x == dias * 2 - 1 && paciente_entraria_en_quirofano == 0) //Si estamos en el último turno y el paciente no ha entrado { tiempos_quirofanos_auxiliar[j, 0] = 1001; tiempos_quirofanos_auxiliar[j, 1] = 1001; //Tiempos imposibles con las limitaciones del problema } //Salgo del bucle si el paciente ya ha podido entrar en el quirófano en el turno actual if (paciente_entraria_en_quirofano == 1) { break; } } } if (paciente_incluido[secuencia[i]] == 1) { int quirofano_asociado = 1001; //Imposible por las limitaciones del problema 38 double turno_minimo_posible = 1001; double hora_minima_posible = 1001; for (int j = 0; j < numero_quirofanos; j++) {//Busco el quirófano que cumple con la regla FAM de asignación del paciente if (tiempos_quirofanos_auxiliar[j, 0] < turno_minimo_posible) { turno_minimo_posible = tiempos_quirofanos_auxiliar[j, 0]; hora_minima_posible = tiempos_quirofanos_auxiliar[j, 1]; quirofano_asociado = j; } else if (tiempos_quirofanos_auxiliar[j, 0] == turno_minimo_posible) {//Si para dos quirófanos o los tres se coincide en turnos, compruebo sus horas para quedarme con el mejor if (tiempos_quirofanos_auxiliar[j, 1] <= hora_minima_posible) { turno_minimo_posible = tiempos_quirofanos_auxiliar[j, 0]; hora_minima_posible = tiempos_quirofanos_auxiliar[j, 1]; quirofano_asociado = j; } } } //Actualizo las variables generales de quirófano y cirujano tiempos_quirofanos[quirofano_asociado, 0] = turno_minimo_posible; tiempos_quirofanos[quirofano_asociado, 1] = hora_minima_posible; tiempos_cirujanos[cirujano_asociado[secuencia[i]], 0] = turno_minimo_posible; tiempos_cirujanos[cirujano_asociado[secuencia[i]], 1] = hora_minima_posible; info_paciente[i, 2] = turno_minimo_posible; info_paciente[i, 4] = hora_minima_posible; info_paciente[i, 0] = secuencia[i]; info_paciente[i, 1] = quirofano_asociado; info_paciente[i, 3] = hora_minima_posible - duracion_operacion [secuencia[i]]; } else { break; } } } // ITERATED GREEDY ALGORITHM CAMAS INTEGRADAS static void iterated_greedy_algorithmCI(int[] secuencia, double[] prioridad, int[] fecha_limite, int[,] disponibilidadquirofano_turno, double[] duracion_operacion, int[] dia_disponible, int[] cirujano_asociado, double[,] horascirujano_turno, int numero_quirofanos, int numero_cirujanos, int dias, int[] necesidad_paciente_cama, int cantidad_camas_PACU, int cantidad_camas_UCI, double[] duracion_paciente_cama, double alpha, double beta, int mds, int instancia, StreamWriter FicheroCSV1) { Random random = new Random(); double numAleat = random.NextDouble(); if (numAleat == 0.0) { numAleat = 0.1; } double temperatura = 0.4; // Primero, con la secuencia que llega al algoritmo, se saca la primera solución inicial, y se elige la secuencia como la mejor, por el momento double[,] info_paciente; decodificacionCI(secuencia, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, necesidad_paciente_cama, cantidad_camas_PACU, cantidad_camas_UCI, duracion_paciente_cama, out info_paciente); //Se decodifica la secuencia // Se asigna el resultado como el mejor hasta el momento 39 double resultado_mejor = funcion_objetivo(info_paciente, secuencia, prioridad, fecha_limite, dias); double resultado_final = resultado_mejor; double resultado_LS = resultado_mejor; // Se va a guardar también el resultado de la mejor secuencia: double[,] mejor_info_paciente = new double[secuencia.Length, 5]; copiar_matriz(info_paciente, mejor_info_paciente, secuencia.Length, 5); double[,] info_paciente_temporal = new double[secuencia.Length, 5]; copiar_matriz(info_paciente, info_paciente_temporal, secuencia.Length, 5); int[] mejor_secuencia = new int[secuencia.Length]; Array.Copy(secuencia, mejor_secuencia, secuencia.Length); int[] secuencia_LS = new int[secuencia.Length]; Array.Copy(secuencia, secuencia_LS, secuencia.Length); DateTime tiempoFinal = DateTime.Now.AddMilliseconds(secuencia.Length * numero_quirofanos * dias / 2 * 25); while (DateTime.Now <= tiempoFinal) { // Primera fase: Destrucción y construcción int[] secuencia_final; fase_destruccion_construccion(secuencia_LS, out secuencia_final, 4); decodificacionCI(secuencia_final, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, necesidad_paciente_cama, cantidad_camas_PACU, cantidad_camas_UCI, duracion_paciente_cama, out info_paciente); resultado_final = funcion_objetivo(info_paciente, secuencia_final, prioridad, fecha_limite, dias); //Segunda fase: Local Search bool improvement; do { improvement = false; double resultado_nuevo; for (int i = 0; i < secuencia_final.Length; i++) { for (int j = 0; j < secuencia_final.Length; j++) { //La secuencia que se va a usar ya no es la mejor secuencia es la secuencia en uso, que se llama secuencia_final int[] secuencia_final_aux = new int[secuencia_final.Length]; // Para evitar cambios accidentales en la mejor_secuencia actual Array.Copy(secuencia_final, secuencia_final_aux, secuencia_final.Length); int[] nueva_secuencia = new int[secuencia_final.Length]; // La que dará la nueva secuencia en la iteración actual int[] secuencia_auxiliar = new int[secuencia_final.Length - 1]; int trabajo; if (i != j && j != i - 1) { trabajo = sacar_trabajo_LS(secuencia_final_aux, secuencia_auxiliar, i); introducir_trabajo_LS(secuencia_auxiliar, nueva_secuencia, j, trabajo); } else { continue; } //Cuando se tiene la nueva secuencia, se decodifica y se saca su valor en la función objetivo decodificacionCI(nueva_secuencia, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, 40 horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, necesidad_paciente_cama, cantidad_camas_PACU, cantidad_camas_UCI, duracion_paciente_cama, out info_paciente); resultado_nuevo = funcion_objetivo(info_paciente, nueva_secuencia, prioridad, fecha_limite, dias); //Si se obtiene mejor resultado en la funcion objetivo, se usa la nueva secuencia, y el nuevo valor a batir es el suyo if (resultado_nuevo < resultado_final) { resultado_final = resultado_nuevo; Array.Copy(nueva_secuencia, secuencia_final, nueva_secuencia.Length); copiar_matriz(info_paciente, info_paciente_temporal, secuencia.Length, 5); improvement = true; } } } } while (improvement == true); //Simulated Annealing para decidir si la secuencia que sale de LS se emplea en la siguiente ronda if (resultado_final < resultado_LS) { Array.Copy(secuencia_final, secuencia_LS, secuencia_final.Length); resultado_LS = resultado_final; if (resultado_final < resultado_mejor) { Array.Copy(secuencia_final, mejor_secuencia, secuencia_final.Length); resultado_mejor = resultado_final; copiar_matriz(info_paciente, mejor_info_paciente, secuencia.Length, 5); } } else if (numAleat <= Math.Exp(-(resultado_final - resultado_LS) / temperatura)) { Array.Copy(secuencia_final, secuencia_LS, secuencia_final.Length); resultado_LS = resultado_final; } } Console.WriteLine($"El mejor resultado de la FO obtenido en IGCmsInt: {resultado_mejor}\n"); // Impresión FicheroCSV1.Write(alpha + ";" + beta + ";" + mds + ";" + numero_cirujanos + ";" + secuencia.Length + ";" + cantidad_camas_PACU + ";" + cantidad_camas_UCI + ";" + instancia + ";" + resultado_mejor + ";" + "CI" + "\n"); } // ITERATED GREEDY ALGORITHM MÉTODO 1 VERSIÓN 2 static void iterated_greedy_algorithmCSM1V2(int[] secuencia, double[] prioridad, int[] fecha_limite, int[,] disponibilidadquirofano_turno, double[] duracion_operacion, int[] dia_disponible, int[] cirujano_asociado, double[,] horascirujano_turno, int numero_quirofanos, int numero_cirujanos, int dias, int[] necesidad_paciente_cama, int cantidad_camas_PACU, int cantidad_camas_UCI, double[] duracion_paciente_cama, double alpha, double beta, int mds, int instancia, StreamWriter FicheroCSV1) { Random random = new Random(); double numAleat = random.NextDouble(); if (numAleat == 0.0) { numAleat = 0.1; } 41 double temperatura = 0.4; // Primero, con la secuencia que llega al algoritmo, se saca la primera solución inicial, y se elige la secuencia como la mejor, por el momento double[,] info_paciente; bool secuencia_valida; int cont = 0; int[] sec = new int[secuencia.Length]; do // Bucle para asegurar que sale una secuencia válida antes de entrar al LS { if (cont != 0) { fase_destruccion_construccion(secuencia, out sec, 4); } else { Array.Copy(secuencia, sec, secuencia.Length); } decodificacionCS(sec, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, out info_paciente); //Se decodifica la secuencia secuencia_valida = camas_separadas_V2(cantidad_camas_PACU, cantidad_camas_UCI, necesidad_paciente_cama, duracion_paciente_cama, info_paciente, secuencia.Length); if (info_paciente[0, 0] == 1001) { secuencia_valida = false; } cont++; } while (secuencia_valida == false); // Se asigna el resultado como el mejor hasta el momento double resultado_mejor = funcion_objetivo(info_paciente, sec, prioridad, fecha_limite, dias); double resultado_final = resultado_mejor; double resultado_LS = resultado_mejor; // Se va a guardar también el resultado de la mejor secuencia: double[,] mejor_info_paciente = new double[secuencia.Length, 5]; copiar_matriz(info_paciente, mejor_info_paciente, secuencia.Length, 5); double[,] info_paciente_temporal = new double[secuencia.Length, 5]; copiar_matriz(info_paciente, info_paciente_temporal, secuencia.Length, 5); int[] mejor_secuencia = new int[secuencia.Length]; Array.Copy(sec, mejor_secuencia, sec.Length); int[] secuencia_LS = new int[secuencia.Length]; Array.Copy(mejor_secuencia, secuencia_LS, mejor_secuencia.Length); DateTime tiempoFinal = DateTime.Now.AddMilliseconds(secuencia.Length * numero_quirofanos * dias / 2 * 25); while (DateTime.Now <= tiempoFinal) { // Primera fase: Destrucción y Construcción int[] secuencia_final; fase_destruccion_construccion(secuencia_LS, out secuencia_final, 4); decodificacionCS(secuencia_final, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, out info_paciente); resultado_final = funcion_objetivo(info_paciente, secuencia_final, prioridad, fecha_limite, dias); if (camas_separadas_V2(cantidad_camas_PACU, cantidad_camas_UCI, necesidad_paciente_cama, duracion_paciente_cama, info_paciente, secuencia.Length) == false) { resultado_final = 1; } 42 //Segunda fase: Local Search bool improvement; do { improvement = false; double resultado_nuevo; for (int i = 0; i < secuencia_final.Length; i++) { for (int j = 0; j < secuencia_final.Length; j++) { bool sec_val; int[] secuencia_final_aux = new int[secuencia_final.Length]; Array.Copy(secuencia_final, secuencia_final_aux, secuencia_final.Length); int[] nueva_secuencia = new int[secuencia_final.Length]; int[] secuencia_auxiliar = new int[secuencia_final.Length - 1]; int trabajo; if (i != j && j != i - 1) { trabajo = sacar_trabajo_LS(secuencia_final_aux, secuencia_auxiliar, i); introducir_trabajo_LS(secuencia_auxiliar, nueva_secuencia, j, trabajo); } else { continue; } decodificacionCS(nueva_secuencia, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, out info_paciente); sec_val = camas_separadas_V2(cantidad_camas_PACU, cantidad_camas_UCI, necesidad_paciente_cama, duracion_paciente_cama, info_paciente, secuencia.Length); if (sec_val == true) { resultado_nuevo = funcion_objetivo(info_paciente, nueva_secuencia, prioridad, fecha_limite, dias); } else { resultado_nuevo = 100; // Gran penalización por ser una secuencia no válida } if (resultado_nuevo < resultado_final) { resultado_final = resultado_nuevo; Array.Copy(nueva_secuencia, secuencia_final, nueva_secuencia.Length); copiar_matriz(info_paciente, info_paciente_temporal, secuencia.Length, 5); improvement = true; } } } } while (improvement == true); //Simulated Annealing para decidir si la secuencia que sale de LS se emplea en la siguiente ronda if (resultado_final < resultado_LS) { Array.Copy(secuencia_final, secuencia_LS, secuencia_final.Length); resultado_LS = resultado_final; 43 if (resultado_final < resultado_mejor) { Array.Copy(secuencia_final, mejor_secuencia, secuencia_final.Length); resultado_mejor = resultado_final; copiar_matriz(info_paciente, mejor_info_paciente, secuencia.Length, 5); } } else if (numAleat <= Math.Exp(-(resultado_final - resultado_LS) / temperatura)) { Array.Copy(secuencia_final, secuencia_LS, secuencia_final.Length); resultado_LS = resultado_final; } } Console.WriteLine($"El mejor resultado de la FO obtenido en IGCmsSepV2: {resultado_mejor}\n"); //Impresion FicheroCSV1.Write(alpha + ";" + beta + ";" + mds + ";" + numero_cirujanos + ";" + secuencia.Length + ";" + cantidad_camas_PACU + ";" + cantidad_camas_UCI + ";" + instancia + ";" + resultado_mejor + ";" + "CSM1V2" + "\n"); } // ITERATED GREEDY ALGORITHM MÉTODO 1 VERSIÓN 1 static void iterated_greedy_algorithmCSM1V1(int[] secuencia, double[] prioridad, int[] fecha_limite, int[,] disponibilidadquirofano_turno, double[] duracion_operacion, int[] dia_disponible, int[] cirujano_asociado, double[,] horascirujano_turno, int numero_quirofanos, int numero_cirujanos, int dias, int[] necesidad_paciente_cama, int cantidad_camas_PACU, int cantidad_camas_UCI, double[] duracion_paciente_cama, double alpha, double beta, int mds, int instancia, StreamWriter FicheroCSV1) { Random random = new Random(); double numAleat = random.NextDouble(); if (numAleat == 0.0) { numAleat = 0.1; } double temperatura = 0.4; //Primero, con la secuencia que llega al algoritmo, se saca la primera solución inicial, y se elige la secuencia como la mejor, por el momento double[,] info_paciente; bool secuencia_valida; int cont = 0; int[] sec = new int[secuencia.Length]; do //Bucle para asegurar que sale una secuencia válida antes de entrar al LS { if (cont != 0) { fase_destruccion_construccion(secuencia, out sec, 4); } else { Array.Copy(secuencia, sec, secuencia.Length); } decodificacionCS(sec, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, out info_paciente); //Se decodifica la secuencia secuencia_valida = camas_separadas_V1(cantidad_camas_PACU, cantidad_camas_UCI, necesidad_paciente_cama, duracion_paciente_cama, info_paciente, secuencia.Length); if (info_paciente[0, 0] == 1001) { secuencia_valida = false; } cont++; 44 } while (secuencia_valida == false); //Se asigna el resultado como el mejor hasta el momento double resultado_mejor = funcion_objetivo(info_paciente, sec, prioridad, fecha_limite, dias); double resultado_final = resultado_mejor; double resultado_LS = resultado_mejor; //Se va a guardar también el resultado de la mejor secuencia: double[,] mejor_info_paciente = new double[secuencia.Length, 5]; copiar_matriz(info_paciente, mejor_info_paciente, secuencia.Length, 5); double[,] info_paciente_temporal = new double[secuencia.Length, 5]; copiar_matriz(info_paciente, info_paciente_temporal, secuencia.Length, 5); int[] mejor_secuencia = new int[secuencia.Length]; Array.Copy(sec, mejor_secuencia, sec.Length); int[] secuencia_LS = new int[secuencia.Length]; Array.Copy(mejor_secuencia, secuencia_LS, mejor_secuencia.Length); DateTime tiempoFinal = DateTime.Now.AddMilliseconds(secuencia.Length * numero_quirofanos * dias / 2 * 25); while (DateTime.Now <= tiempoFinal) { // Primera fase: Destrucción y Construcción int[] secuencia_final; fase_destruccion_construccion(secuencia_LS, out secuencia_final, 4); decodificacionCS(secuencia_final, disponibilidadquirofano_turno, duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, out info_paciente); resultado_final = funcion_objetivo(info_paciente, secuencia_final, prioridad, fecha_limite, dias); if (camas_separadas_V1(cantidad_camas_PACU, cantidad_camas_UCI, necesidad_paciente_cama, duracion_paciente_cama, info_paciente, secuencia.Length) == false) { resultado_final = 1; } // Segunda fase: Local Search bool improvement; do { improvement = false; double resultado_nuevo; for (int i = 0; i < secuencia_final.Length; i++) { for (int j = 0; j < secuencia_final.Length; j++) { bool sec_val; int[] secuencia_final_aux = new int[secuencia_final.Length]; Array.Copy(secuencia_final, secuencia_final_aux, secuencia_final.Length); int[] nueva_secuencia = new int[secuencia_final.Length]; int[] secuencia_auxiliar = new int[secuencia_final.Length - 1]; int trabajo; if (i != j && j != i - 1) { trabajo = sacar_trabajo_LS(secuencia_final_aux, secuencia_auxiliar, i); introducir_trabajo_LS(secuencia_auxiliar, nueva_secuencia, j, trabajo); } else { continue; } decodificacionCS(nueva_secuencia, disponibilidadquirofano_turno, 45 duracion_operacion, dia_disponible, cirujano_asociado, horascirujano_turno, numero_quirofanos, numero_cirujanos, dias, out info_paciente); sec_val = camas_separadas_V1(cantidad_camas_PACU, cantidad_camas_UCI, necesidad_paciente_cama, duracion_paciente_cama, info_paciente, secuencia.Length); if (sec_val == true) { resultado_nuevo = funcion_objetivo(info_paciente, nueva_secuencia, prioridad, fecha_limite, dias); } else { resultado_nuevo = 100; // Gran penalización por ser una secuencia no válida } if (resultado_nuevo < resultado_final) { resultado_final = resultado_nuevo; Array.Copy(nueva_secuencia, secuencia_final, nueva_secuencia.Length); copiar_matriz(info_paciente, info_paciente_temporal, secuencia.Length, 5); improvement = true; } } } } while (improvement == true); //Simulated Annealing para decidir si la secuencia que sale de LS se emplea en la siguiente ronda if (resultado_final < resultado_LS) { Array.Copy(secuencia_final, secuencia_LS, secuencia_final.Length); resultado_LS = resultado_final; if (resultado_final < resultado_mejor) { Array.Copy(secuencia_final, mejor_secuencia, secuencia_final.Length); resultado_mejor = resultado_final; copiar_matriz(info_paciente, mejor_info_paciente, secuencia.Length, 5); } } else if (numAleat <= Math.Exp(-(resultado_final - resultado_LS) / temperatura)) { Array.Copy(secuencia_final, secuencia_LS, secuencia_final.Length); resultado_LS = resultado_final; } } Console.WriteLine($"El mejor resultado de la FO obtenido en IGCmsSepV1: {resultado_mejor}\n"); //Impresion FicheroCSV1.Write(alpha + ";" + beta + ";" + mds + ";" + numero_cirujanos + ";" + secuencia.Length + ";" + cantidad_camas_PACU + ";" + cantidad_camas_UCI + ";" + instancia + ";" + resultado_mejor + ";" + "CSM1V1" + "\n"); } // ITERATED GREEDY ALGORITHM MÉTODO 2 VERSIÓN 1 static void iterated_greedy_algorithmCSM2V1(int[] secuencia, double[] prioridad, int[] fecha_limite, int[,] disponibilidadquirofano_turno, double[] duracion_operacion, int[] dia_disponible, int[] cirujano_asociado, double[,] horascirujano_turno, int numero_quirofanos, int numero_cirujanos, int dias, int[] necesidad_paciente_cama, int cantidad_camas_PACU, int cantidad_camas_UCI, double[] duracion_paciente_cama, double alpha, double beta, int mds, int instancia, StreamWriter FicheroCSV1) 52 for (int i = 0; i < pacientes_totales; i++) { if (info_paciente[i, 0] != 1001) { if (necesidad_paciente_cama[Convert.ToInt32(info_paciente[i, 0])] == 0) { continue; } else if (necesidad_paciente_cama[Convert.ToInt32(info_paciente[i, 0])] == 1) { int paciente_asignado = 0; for (int j = 0; j < camas_PACU; j++) { if (tiempos_camas_PACU[j, 0] <= info_paciente[i, 2] || (tiempos_camas_PACU[j, 0] == info_paciente[i, 2] && tiempos_camas_PACU[j, 1] <= info_paciente[i, 4])) { duracion_a_turnos_horas(info_paciente[i, 2], info_paciente[i, 4], duracion_paciente_cama, Convert.ToInt32(info_paciente[i, 0]), tiempos_camas_PACU, j); paciente_asignado = 1; break; } } if (paciente_asignado == 0) { secuencia_valida = false; break; } } else { int paciente_asignado = 0; for (int j = 0; j < camas_UCI; j++) { if (tiempos_camas_UCI[j, 0] <= info_paciente[i, 2] || (tiempos_camas_UCI[j, 0] == info_paciente[i, 2] && tiempos_camas_UCI[j, 1] <= info_paciente[i, 4])) { duracion_a_turnos_horas(info_paciente[i, 2], info_paciente[i, 4], duracion_paciente_cama, Convert.ToInt32(info_paciente[i, 0]), tiempos_camas_UCI, j); paciente_asignado = 1; break; } } if (paciente_asignado == 0) { secuencia_valida = false; break; } } } else { break; } } return secuencia_valida; } static bool camas_separadas_V2(int camas_PACU, int camas_UCI, int[] necesidad_paciente_cama, double[] duracion_paciente_cama, double[,] info_paciente, int pacientes_totales) { double[,] tiempos_camas_PACU = new double[camas_PACU, 2]; double[,] tiempos_camas_UCI = new double[camas_UCI, 2]; setval_IMatriz(tiempos_camas_PACU, camas_PACU, 2, 0); setval_IMatriz(tiempos_camas_UCI, camas_UCI, 2, 0); bool secuencia_valida = true; 53 for (int i = 0; i < pacientes_totales; i++) { if (info_paciente[i, 0] != 1001) { if (necesidad_paciente_cama[Convert.ToInt32(info_paciente[i, 0])] == 0) { continue; } else if (necesidad_paciente_cama[Convert.ToInt32(info_paciente[i, 0])] == 1) { int paciente_asignado = 0; for (int j = 0; j < camas_PACU; j++) { if (tiempos_camas_PACU[j, 0] <= info_paciente[i, 2] || (tiempos_camas_PACU[j, 0] == info_paciente[i, 2] && tiempos_camas_PACU[j, 1] <= info_paciente[i, 4])) { duracion_a_turnos_horas(info_paciente[i, 2], info_paciente[i, 4], duracion_paciente_cama, Convert.ToInt32(info_paciente[i, 0]), tiempos_camas_PACU, j); paciente_asignado = 1; break; } } if (paciente_asignado == 0) { int proximo_paciente = proximo_paciente_en_quirofano(i, info_paciente, pacientes_totales); if (proximo_paciente != -1) { double minimo_turno = 0; double minima_hora = 0; int primera_cama = 0; for (int r = 0; r < camas_PACU; r++) { //Se busca la primera cama disponible, junto al turno en el que está disponible y la hora if (r == 0) { minimo_turno = tiempos_camas_PACU[r, 0]; minima_hora = tiempos_camas_PACU[r, 1]; } else { if (tiempos_camas_PACU[r, 0] < minimo_turno || (tiempos_camas_PACU[r, 0] == minimo_turno && tiempos_camas_PACU[r, 1] <= minima_hora)) { minimo_turno = tiempos_camas_PACU[r, 0]; minima_hora = tiempos_camas_PACU[r, 1]; primera_cama = r; } } } if (minimo_turno < info_paciente[proximo_paciente, 2] || (minimo_turno == info_paciente[proximo_paciente, 2] && minima_hora <= info_paciente[proximo_paciente, 4])) { //Ahora comprobar que el tiempo de arriba no sea mayor al tiempo que el paciente tiene asignado en CAMA duracion_a_turnos_horas_V2(info_paciente[i, 2], info_paciente[i, 4], duracion_paciente_cama, Convert.ToInt32(info_paciente[i, 0]), tiempos_camas_PACU, primera_cama); } else { secuencia_valida = false; 54 break; } } // Si no hay pacientes después en el mismo quirófano, se supone siempre que se va a poder quedar ahi } } else { int paciente_asignado = 0; for (int j = 0; j < camas_UCI; j++) { if (tiempos_camas_UCI[j, 0] <= info_paciente[i, 2] || (tiempos_camas_UCI[j, 0] == info_paciente[i, 2] && tiempos_camas_UCI[j, 1] <= info_paciente[i, 4])) { duracion_a_turnos_horas(info_paciente[i, 2], info_paciente[i, 4], duracion_paciente_cama, Convert.ToInt32(info_paciente[i, 0]), tiempos_camas_UCI, j); paciente_asignado = 1; break; } } if (paciente_asignado == 0) { int proximo_paciente = proximo_paciente_en_quirofano(i, info_paciente, pacientes_totales); if (proximo_paciente != -1) { double minimo_turno = 0; double minima_hora = 0; int primera_cama = 0; for (int r = 0; r < camas_UCI; r++) { if (r == 0) { minimo_turno = tiempos_camas_UCI[r, 0]; minima_hora = tiempos_camas_UCI[r, 1]; } else { if (tiempos_camas_UCI[r, 0] < minimo_turno || (tiempos_camas_UCI[r, 0] == minimo_turno && tiempos_camas_UCI[r, 1] == minima_hora)) { minimo_turno = tiempos_camas_UCI[r, 0]; minima_hora = tiempos_camas_UCI[r, 1]; primera_cama = r; } } } if (minimo_turno < info_paciente[proximo_paciente, 2] || (minimo_turno == info_paciente[proximo_paciente, 2] && minima_hora <= info_paciente[proximo_paciente, 3])) { // Se mete al paciente en la cama cuando se quede libre la primera, o acaba su tiempo en quirófano si esto ocurre antes de que una de las camas quede libre duracion_a_turnos_horas_V2(info_paciente[i, 2], info_paciente[i, 4], duracion_paciente_cama, Convert.ToInt32(info_paciente[i, 0]), tiempos_camas_UCI, primera_cama); } else { 55 secuencia_valida = false; break; } } } } } else { break; } } return secuencia_valida; } // FUNCIÓN OBJETIVO: minimizar la tardanza ponderada con la prioridad static double funcion_objetivo(double[,] info_paciente, int[] secuencia, double[] prioridad, int[] fecha_limite, int dias) { double funcion_objetivo = 0; // Acumuladas de todos los pacientes que han ido pasando double tardanza_ponderada; // De cada uno de los pacientes for (int i = 0; i < secuencia.Length; i++) { //Lo primero que se necesita saber es si el paciente se ha operado, si lo ha sido, debe tener la misma posición en secuencia que en info_paciente: int paciente_operado = 0; if (secuencia[i] == info_paciente[i, 0]) { paciente_operado = 1; } // Ahora se distingue entre si los pacientes se han operado o no para asignar los días de operación int dia_operacion; if (paciente_operado == 1) { if (info_paciente[i, 2] == 0) { dia_operacion = 0; } else { dia_operacion = Convert.ToInt32(Math.Round(info_paciente[i, 2] / 2, MidpointRounding.AwayFromZero)); } } else { dia_operacion = dias + 1; } // Una vez asignados los días de operación se puede ver si los pacientes van tarde. Se ha supuesto que, si los pacientes no han sido operados en el último día del horizonte temporal, estos van a ser operados el día siguiente. // Esto solo tiene importancia para los pacientes con fecha límite dentro del horizonte temporal. double tardanza = dia_operacion - fecha_limite[Convert.ToInt32(secuencia[i])]; if (tardanza < 0) { tardanza_ponderada = 0; } else { tardanza_ponderada = tardanza / dias; } //Calculo la funcion objetivo sumando los resultados de los pacientes y ponderando con la prioridad de estos funcion_objetivo += (tardanza_ponderada - paciente_operado) * prioridad[secuencia[i]]; } return funcion_objetivo; } // Pasar las horas de las camas a turnos y horas 56 static void duracion_a_turnos_horas(double turno_operacion, double hora_finalizacion_operacion, double[] duracion_paciente_cama, int paciente, double[,] tiempos_camas, int cama_actual) { double auxiliar; int tipo; if (turno_operacion == 0 || turno_operacion % 2 == 0) //Significa que estoy por la mañana { auxiliar = 8.5 + hora_finalizacion_operacion + duracion_paciente_cama[paciente]; tipo = 1; } else //Significa que es por la tarde { auxiliar = 15.5 + hora_finalizacion_operacion + duracion_paciente_cama[paciente]; tipo = 2; } tiempos_camas[cama_actual, 0] = turno_operacion; double x = auxiliar / 24; if (tipo == 1) //Estoy colocándome en el primer turno del día al que voy { tiempos_camas[cama_actual, 0] += Math.Floor(x) * 2; } else { tiempos_camas[cama_actual, 0] += 2 * Math.Floor(x) - 1; } double y = auxiliar - 24 * Math.Floor(x); if (y < 8.5) { tiempos_camas[cama_actual, 1] = 0; } else if (y >= 8.5 && y < 14.5) { tiempos_camas[cama_actual, 1] = y - 8.5; } else if (y >= 14.5 && y < 15.5) { tiempos_camas[cama_actual, 0]++; tiempos_camas[cama_actual, 1] = 0; } else if (y >= 15.5 && y <= 19.5) { tiempos_camas[cama_actual, 0]++; tiempos_camas[cama_actual, 1] = y - 15.5; } else { tiempos_camas[cama_actual, 0] += 2; tiempos_camas[cama_actual, 1] = 0; } } static void duracion_a_turnos_horas_V2(double turno_operacion, double hora_finalizacion_operacion, double[] duracion_paciente_cama, int paciente, double[,] tiempos_camas, int cama) { double auxiliar; //Hora a la que acabaría el tiempo en cama (puede pasar de las 24horas) int tipo; double turno_auxiliar; //Turno en el que acabaria la estancia del paciente en la cama double hora_auxiliar; //Hora a la que acabaria la estancia del paciente en la cama 57 if (turno_operacion == 0 || turno_operacion % 2 == 0) //Significa que estoy por la mañana { auxiliar = 8.5 + hora_finalizacion_operacion + duracion_paciente_cama[paciente]; tipo = 1; } else //Significa que es por la tarde { auxiliar = 15.5 + hora_finalizacion_operacion + duracion_paciente_cama[paciente]; tipo = 2; } turno_auxiliar = turno_operacion; double x = auxiliar / 24; //Para conocer si ha pasado más de un día en la cama if (tipo == 1) { turno_auxiliar += Math.Floor(x) * 2; //La función Floor se usa para redondear hacia abajo } else { turno_auxiliar += 2 * Math.Floor(x) - 1; } double y = auxiliar - 24 * Math.Floor(x); //Para las horas después de ver si ha pasado más de un día en la cama if (y < 8.5) { hora_auxiliar = 0; } else if (y >= 8.5 && y <= 14.5) { hora_auxiliar = y - 8.5; } else if (y > 14.5 && y < 15.5) { turno_auxiliar++; hora_auxiliar = 0; } else if (y >= 15.5 && y <= 19.5) { turno_auxiliar++; hora_auxiliar = y - 15.5; } else { turno_auxiliar += 2; hora_auxiliar = 0; } // En este punto esta guardado el turno y la hora a la que el paciente saldría de cama si entrase tras acabar operación. // Ahora hay que hacer la comparación entre este momento y el momento en el que la cama se queda libre if (turno_auxiliar > tiempos_camas[cama, 0] || (turno_auxiliar == tiempos_camas[cama, 0] && hora_auxiliar > tiempos_camas[cama, 1])) { // Recalculo el tiempo que pasa en la cama y actualizo las variables de tiempo de la cama // El paciente saldráa de cama en turno_auxiliar y hora_auxiliar tiempos_camas[cama, 0] = turno_auxiliar; tiempos_camas[cama, 1] = hora_auxiliar; } // Si no se da el if anterior, significa que el paciente sale antes de que haya cama libre y antes de que otro paciente entre en quirófano, no actualizo ninguna variable 58 } // Encontrar al próximo paciente en el quirófano (para la Versión 2) static int proximo_paciente_en_quirofano(int indice, double[,] info_paciente, int pacientes_totales) { double quirofano = info_paciente[indice, 1]; int indice_devuelto = -1; int auxiliar = 0; for (int x = indice + 1; x < pacientes_totales; x++) { if (auxiliar == 0) { if (info_paciente[x, 1] == quirofano) { indice_devuelto = x; } } else { break; } } return indice_devuelto; } // Igualar tiempos auxiliares con generales static void igualar_tiempos_auxiliares_a_generales(double[,] tiempos_quirofanos, double[,] tiempos_quirofanos_auxiliar, double[,] tiempos_cirujanos, double[,] tiempos_cirujanos_auxiliar, double[,] tiempos_camas_PACU, double[,] tiempos_camas_PACU_auxiliar, double[,] tiempos_camas_UCI, double[,] tiempos_camas_UCI_auxiliar, int cantidad_camas_PACU, int cantidad_camas_UCI, int[] secuencia, int orden, int[] cirujano_asociado, int quirofano) { tiempos_quirofanos_auxiliar[quirofano, 0] = tiempos_quirofanos[quirofano, 0]; tiempos_quirofanos_auxiliar[quirofano, 1] = tiempos_quirofanos[quirofano, 1]; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[orden]], 0] = tiempos_cirujanos[cirujano_asociado[secuencia[orden]], 0]; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[orden]], 1] = tiempos_cirujanos[cirujano_asociado[secuencia[orden]], 1]; for (int x = 0; x < cantidad_camas_PACU; x++) { tiempos_camas_PACU_auxiliar[x, 0] = tiempos_camas_PACU[x, 0]; tiempos_camas_PACU_auxiliar[x, 1] = tiempos_camas_PACU[x, 1]; } for (int w = 0; w < cantidad_camas_UCI; w++) { tiempos_camas_UCI_auxiliar[w, 0] = tiempos_camas_UCI[w, 0]; tiempos_camas_UCI_auxiliar[w, 1] = tiempos_camas_UCI[w, 1]; } } // Actualizar los tiempos al día disponible e igualar los momentos en los que se encuentra el cirujano y el quirófano (a nivel auxiliar para comenzar) static void release_y_tiempos_quirofano_cirujano(int[] dia_disponible, int[] secuencia, int orden, double[,] tiempos_quirofanos_auxiliar, double[,] tiempos_cirujanos_auxiliar, int[] cirujano_asociado, int quirofano) { if (dia_disponible[secuencia[orden]] > tiempos_quirofanos_auxiliar[quirofano, 0]) //Actualizo el tiempo del quirófano al momento en el que llega el paciente { tiempos_quirofanos_auxiliar[quirofano, 0] = dia_disponible[secuencia[orden]]; tiempos_quirofanos_auxiliar[quirofano, 1] = 0; } 59 //Actualizo el tiempo quirófano o cirujano, según cuál vaya más adelantado if (tiempos_quirofanos_auxiliar[quirofano, 0] < tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[orden]], 0]) { tiempos_quirofanos_auxiliar[quirofano, 0] = tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[orden]], 0]; tiempos_quirofanos_auxiliar[quirofano, 1] = tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[orden]], 1]; } else if (tiempos_quirofanos_auxiliar[quirofano, 0] > tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[orden]], 0]) { tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[orden]], 0] = tiempos_quirofanos_auxiliar[quirofano, 0]; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[orden]], 1] = tiempos_quirofanos_auxiliar[quirofano, 1]; } } // Necesidad de camas static void comprueba_necesidad_camas(int[] necesidad_paciente_cama, int[] secuencia, int orden, out bool resultado_camas, int cantidad_camas_PACU, int cantidad_camas_UCI, double[,] tiempos_camas_UCI, double[,] tiempos_camas_PACU, int turno) { if (necesidad_paciente_cama[secuencia[orden]] == 1) { resultado_camas = cama_en_turno(cantidad_camas_PACU, tiempos_camas_PACU, turno); } else if (necesidad_paciente_cama[secuencia[orden]] == 2) { resultado_camas = cama_en_turno(cantidad_camas_UCI, tiempos_camas_UCI, turno); } else { resultado_camas = true; } } // Búsqueda de la cama necesaria static void busqueda_cama(double[,] tiempos_camas_auxiliar, double[,] tiempos_quirofanos_auxiliar, double tiempo_inicio_operacion, double[] duracion_operacion, int[] secuencia, int i, int[] cama_asociada_quirofano, double mejor_turno_cama, double mejor_hora_cama, int quirofano_actual, int cantidad_camas, out double mejor_turno_cama_out, out double mejor_hora_cama_out) { int y; for (y = 0; y < cantidad_camas; y++) { // Si esto se cumple, no hace falta seguir buscando if (tiempos_camas_auxiliar[y, 0] < tiempos_quirofanos_auxiliar[quirofano_actual, 0] || (tiempos_camas_auxiliar[y, 0] == tiempos_quirofanos_auxiliar[quirofano_actual, 0] && tiempos_camas_auxiliar[y, 1] <= tiempo_inicio_operacion + duracion_operacion[secuencia[i]])) { cama_asociada_quirofano[quirofano_actual] = y; mejor_turno_cama = tiempos_camas_auxiliar[y, 0]; mejor_hora_cama = tiempos_camas_auxiliar[y, 1]; break; } else { if (y == 0) { mejor_turno_cama = tiempos_camas_auxiliar[y, 0]; mejor_hora_cama = tiempos_camas_auxiliar[y, 1]; 60 cama_asociada_quirofano[quirofano_actual] = y; } if (tiempos_camas_auxiliar[y, 0] < mejor_turno_cama) { mejor_turno_cama = tiempos_camas_auxiliar[y, 0]; mejor_hora_cama = tiempos_camas_auxiliar[y, 1]; cama_asociada_quirofano[quirofano_actual] = y; } else if (tiempos_camas_auxiliar[y, 0] == mejor_turno_cama) { if (tiempos_camas_auxiliar[y, 1] < mejor_hora_cama) { mejor_hora_cama = tiempos_camas_auxiliar[y, 1]; cama_asociada_quirofano[quirofano_actual] = y; } } } } mejor_turno_cama_out = mejor_hora_cama; mejor_hora_cama_out = mejor_hora_cama; } // Coloca los tiempos de quirófanos y cirujanos temporalmente static void asignacion_temporal_camas(double[,] tiempos_quirofanos_auxiliar, double mejor_turno_cama, double mejor_hora_cama, double tiempo_inicio_operacion, int[] paciente_incluido, int[] secuencia, int i, int paciente_entraria_en_quirofano, int[] cama_asociada_quirofano, double[] duracion_operacion, double[,] tiempos_cirujanos_auxiliar, int[] cirujano_asociado, double tiempo_maximo, int quirofano_actual, int turno_actual, out int paciente_entraria_en_quirofano_out) { if (mejor_turno_cama < tiempos_quirofanos_auxiliar[quirofano_actual, 0] || (mejor_turno_cama == tiempos_quirofanos_auxiliar[quirofano_actual, 0] && mejor_hora_cama <= tiempo_inicio_operacion + duracion_operacion[secuencia[i]])) { tiempos_quirofanos_auxiliar[quirofano_actual, 1] = tiempo_inicio_operacion + duracion_operacion[secuencia[i]]; paciente_incluido[secuencia[i]] = 1; paciente_entraria_en_quirofano = 1; } else if (mejor_turno_cama > tiempos_quirofanos_auxiliar[quirofano_actual, 0]) { tiempos_quirofanos_auxiliar[quirofano_actual, 0]++; tiempos_quirofanos_auxiliar[quirofano_actual, 1] = 0; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 0]++; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 1] = 0; } else if (mejor_turno_cama == tiempos_quirofanos_auxiliar[quirofano_actual, 0] && mejor_hora_cama > tiempo_inicio_operacion + duracion_operacion[secuencia[i]]) { if (mejor_hora_cama + duracion_operacion[secuencia[i]] <= tiempo_maximo) { tiempo_inicio_operacion = mejor_hora_cama; tiempos_quirofanos_auxiliar[quirofano_actual, 1] = tiempo_inicio_operacion + duracion_operacion[secuencia[i]]; paciente_incluido[secuencia[i]] = 1; paciente_entraria_en_quirofano = 1; } else {//No daría tiempo de completarse la operacion en el turno actual tiempos_quirofanos_auxiliar[quirofano_actual, 0]++; tiempos_quirofanos_auxiliar[quirofano_actual, 1] = 0; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 0]++; tiempos_cirujanos_auxiliar[cirujano_asociado[secuencia[i]], 1] = 0; } } 61 paciente_entraria_en_quirofano_out = paciente_entraria_en_quirofano; } // Comprueba si hay camas en el turno static bool cama_en_turno(int numero_camas, double[,] tiempo_camas, int turno_actual) { bool resultado = false; for (int t = 0; t < numero_camas; t++) { if (tiempo_camas[t, 0] <= turno_actual) { resultado = true; break; } } return resultado; } static void duracion_a_turnos_horasCI(double turno_operacion, double hora_finalizacion_operacion, double[] duracion_paciente_cama, int paciente, double[,] tiempos_camas, int[] cama_asociada_quirofano, int quirofano_asociado) { double auxiliar; int tipo; if (turno_operacion == 0 || turno_operacion % 2 == 0) //Significa que estoy por la mañana { auxiliar = 8.5 + hora_finalizacion_operacion + duracion_paciente_cama[paciente]; tipo = 1; } else //Significa que es por la tarde { auxiliar = 15 + hora_finalizacion_operacion + duracion_paciente_cama[paciente]; tipo = 2; } tiempos_camas[cama_asociada_quirofano[quirofano_asociado], 0] = turno_operacion; double x = auxiliar / 24; if (tipo == 1) //Estoy colocandome en el primer turno del día al que voy { tiempos_camas[cama_asociada_quirofano[quirofano_asociado], 0] += Math.Floor(x) * 2; } else { tiempos_camas[cama_asociada_quirofano[quirofano_asociado], 0] += 2 * Math.Floor(x) - 1; } double y = auxiliar - 24 * Math.Floor(x); if (y < 8.5) { tiempos_camas[cama_asociada_quirofano[quirofano_asociado], 1] = 0; } else if (y >= 8.5 && y < 14.5) { tiempos_camas[cama_asociada_quirofano[quirofano_asociado], 1] = y - 8.5; } else if (y >= 14.5 && y < 15.5) { tiempos_camas[cama_asociada_quirofano[quirofano_asociado], 0]++; tiempos_camas[cama_asociada_quirofano[quirofano_asociado], 1] = 0; } else if (y >= 15.5 && y <= 19.5) { tiempos_camas[cama_asociada_quirofano[quirofano_asociado], 0]++; tiempos_camas[cama_asociada_quirofano[quirofano_asociado], 1] = y - 15;