Algoritmos aproximados para la resolución de la planificación de intervenciones quirúrgicas

1604 QUANTITATIVE METHODS 4th International Conference on Industrial Engineering and Industrial Management XIV Congreso de Ingeniería de Organización DonostiaSan Sebastián , September 8th -10th 2010 Algoritmos aproximados para la resolución de la planificación de intervenciones quirúrgicas José Manuel Molina Pariente1, José Manuel Framiñán Torres1, Paz Pérez Gonzalez1, José Luis Andrade Pineda1 1 Dpto. de Organización. Escuela Superior de Ingenieros. Universidad de Sevilla. Camino de los Descubrimientos s/n. 41092. Sevilla. jm[email protected], [email protected], [email protected], [email protected] Resumen La planificación de intervenciones quirúrgicas consiste en determinar el plan quirúrgico a ejecutar en un horizonte temporal determinado. El plan quirúrgico establece que pacientes de la lista de espera de la especialidad quirúrgica son planificados, además de especificar la fecha (turno de quirófano) y el lugar (quirófano) donde se llevará a cabo la intervención. En este trabajo se presentan una serie de algoritmos constructivos para la resolución aproximada de la planificación de intervenciones. Para evaluar y comparar los algoritmos propuestos con la resolución mediante programación lineal, se diseña una batería de 640 instancias basadas en una revisión de la literatura. Palabras clave: planificación, quirófanos, algoritmos aproximados, constructivos 1. Introducción La planificación quirúrgica es un proceso de toma de decisiones empleado en la programación de quirófanos, que puede estructurarse en tres fases (Testi et al. ,2007). En una primera fase (en la que el decisor es la Dirección del hospital) se distribuye el tiempo de quirófano disponible entre las especialidades quirúrgicas (Session Planning Problem o SPP). En la segunda fase se determina cómo se distribuye dicho tiempo de quirófano a lo largo del horizonte de planificación (Master Surgical Schedule o MSS), es decir, se especifican los turnos de quirófanos ocupados por cada especialidad quirúrgica. En la tercera fase (en la que el decisor es el Director de la especialidad quirúrgica), las decisiones a tomar son: 1) asignar a cada paciente una fecha en la que se realizará la operación y 2) secuenciar los pacientes planificados en un turno de quirófano (Elective Case Scheduling o ECS). En general, la fase ECS es resuelta en dos etapas: una primera etapa (Advance Scheduling) que se refiere a la asignación de pacientes a turnos de quirófano, mientras que en la segunda etapa (Allocation Scheduling) se programan las operaciones que han sido asignadas dentro de cada turno de quirófano. En este trabajo nos centramos en la etapa Advance Scheduling. El problema objeto de estudio es la planificación de las intervenciones con el objetivo de maximizar la calidad de servicio de la especialidad quirúrgica y el cumplimiento de las fechas límites de las intervenciones En trabajos anteriores (ver Molina Pariente et al. ,2009), los autores han desarrollado y resuelto modelos de programación entera (IP) para la resolución de dicho problema de acuerdo a diferentes políticas de planificación. Dada la naturaleza NP-dura del problema (Guinet and 1605 Chaabane ,2003), el tiempo de computación para la resolución de problemas de tamaño medio y grande mediante IP es excesivamente largo, por lo que en este artículo se desarrollan métodos aproximados de resolución. Dada la equivalencia existente entre el problema objeto de estudio y el problema bin packing (asignación de ítems a cajas de capacidad limitada) (Galambos and Woeginger ,1995), el objetivo del presente trabajo es adaptar a nuestro problema heurísticas basadas en algoritmos empleados en el problema bin packing, además de desarrollar nuevas heurísticas constructivas. Para la evaluación y comparación de los algoritmos aproximados propuestos con la resolución exacta, se diseña una batería de experimentos basada en la literatura de la etapa Advance Scheduling. 2. Estado del arte La asignación de una intervención a un determinado quirófano es equivalente matemáticamente a la asignación de un ítem a una caja (problema bin packing). Por esta razón, la mayoría de autores emplean algoritmos de tipo bin packing como métodos constructivos para la resolución de problemas de asignación de intervenciones a quirófanos. Los principales algoritmos bin packing empleados en la literatura para la resolución de este problema son (Dexter et al. ,1999b): Best Fit (BF), la intervención es planificada en aquel quirófano en el que la intervención puede ser realizada sin incurrir en tiempo extra y donde la capacidad disponible es la menor. Worst Fit (WF), la intervención es planificada en aquel quirófano en el que la intervención puede ser realizada sin incurrir en tiempo extra y donde la capacidad disponible sea la mayor. First Fit (FF), la intervención es planificada lo antes posible en aquel quirófano en el que existe capacidad disponible para realizar la intervención. El algoritmo bin packing requiere, como dato principal de entrada, el orden en el que debe asignar las intervenciones a los turnos de quirófano. Dependiendo de si se conoce o no a priori dicho orden, se pueden contemplar los siguientes escenarios: si las intervenciones a planificar no se conocen a priori (como puede ser el caso de la intervenciones de urgencia), el algoritmo bin packing planifica las intervenciones en función del orden de llegada de las mismas. Estos algoritmos reciben el nombre de algoritmos on-line. En el caso de que las intervenciones a planificar se conocen a priori (como es el caso de una lista de espera en una unidad quirúrgica), el algoritmo bin packing selecciona los pacientes de la lista de espera. Estos algoritmos reciben el nombre de algoritmos off-line. Esta lista de espera puede tener un orden aleatorio, es decir, en función del orden de llegada a la lista de espera, o por el contrario puede estar ordenada respondiendo a un determinado criterio (Dexter et al. ,1999a). Algunas de las reglas de secuenciación empleadas en la literatura para secuenciar listas de espera son (Hans et al. ,2008;Marcon and Dexter ,2006): Longest processing time (LPT), las intervenciones son ordenadas en orden decreciente de duración. Shortest processing time (SPT), las intervenciones son ordenadas en orden creciente de duración. HIHD (Half Increase operating room time and Half Decrease operating room time), comprende dos etapas: (1) la lista de espera es ordenada en base a la regla SPT, resultado la siguiente lista: {L(1),L(2),…,L(n)}, donde n es el número de intervenciones en lista de 1606 espera, L(1) es la intervención con la duración más corta y L(n) es la intervención con la duración más larga. (2) Las intervenciones se secuencian de la siguiente forma: {L(1), L(3),…, L(n),…, L(4), L(2)}. HDHI (Half Decrease operating room time and Half Increase operating room time), comprende dos etapas: (1) la lista de espera es ordenada en base a la regla LPT, resultado la siguiente lista: {L(n),L(n-1),…,L(1)}, donde n es el número de intervenciones en lista de espera. (2) Las intervenciones se secuencian de la siguiente forma: {L(n), L(n-2),…, L(1),…, L(n-3), L(n-1)}. Desde nuestro conocimiento, estos métodos aproximados constructivos no han sido aplicados al problema de planificación de intervenciones quirúrgicas, descrito en Molina Pariente et al. ,2009, en los que se asigna el quirófano y la fecha de intervención (antes de la fecha límite de la intervención) para cada uno de los pacientes planificados, sino a problemas como los de planificar el número de intervenciones (sin especificar los pacientes planificados) a realizar por cada especialidad quirúrgica en cada turno de quirófano del horizonte de planificación (Hans et al. ,2008) o planificar intervenciones de urgencias (Dexter et al. ,1999a). Por ello, en la próxima sección se presentan una serie de algoritmos específicamente diseñados para este problema y que recogen alguna de las ideas anteriores. 3. Algoritmos de resolución En este apartado se describen los algoritmos propuestos para la resolución de la asignación de intervenciones a turnos de quirófano, con el objetivo de maximizar la calidad de servicio de una especialidad quirúrgica mientras que la fecha de la intervención es menor o igual que una fecha límite determinada en función del diagnóstico del paciente. La calidad de servicio se define como la suma de los cocientes entre la ponderación clínica asignada a cada paciente (función de la prioridad clínica y número de días en lista de espera) y la fecha de operación de los pacientes programados (ver Molina Pariente et al. ,2009). 3.1 Algoritmos Sorting Bin Packing (SBP) Los algoritmos presentados en esta sección están estructurados en dos pasos: (1) secuenciar la lista de espera en base a regla de secuenciación y (2) planificar la lista de espera resultante de (1) con algoritmo bin packing. El objetivo de la primera etapa consiste en ordenar la lista de espera en base a un determinado criterio. En este trabajo, las reglas de secuenciación empleadas para la secuenciación de la lista de espera son: Dado que una restricción crítica del problema es la realización de la intervención antes de su fecha límite, se considera la regla de ordenar la lista de espera en orden ascendente de fecha límite de la intervención. Esta regla es aplicada en el ámbito de la producción, en la que los trabajos con menor fecha límite son secuenciados en primer lugar (Earliest Due Date, EDD). Dado que la ponderación clínica juega un papel fundamental en la optimización del problema propuesto, se considera la regla de ordenar la lista de espera en orden descendente de ponderación clínica de la intervención (Highest Clinical Weight, HCW). Por último, se considera una regla de secuenciación (EDD-HCW), en la que los pacientes son secuenciados de forma separada, dependiendo de si su fecha límite está o no dentro del horizonte de planificación. Los primeros pacientes se programan antes que los segundos, ordenados de acuerdo a EDD, mientras que los segundos pacientes se ordenan de acuerdo a la regla HCW. 1607 En el segundo paso, la lista de espera resultante se planifica en base a un algoritmo bin packing. A continuación se detalla el pseudocódigo del algoritmo SBP desarrollado en este trabajo. 1. lista ordenada:= Lista de espera ordenada en base a regla de secuenciación 2. plan quirúrgico:= Ø 3. for j:=1 to Nº Pacientes do i:= paciente (lista ordenada [j]) plan quirúrgico [i]:= fecha y quirófano asignado con algoritmo bin packing endfor Figura 1. Pseudocódigo del algoritmo SBP 3.2 Algoritmo Constructive Bin Packing (CBP) La principal diferencia del algoritmo CBP, respecto de los algoritmos SBP, es que la regla de secuenciación está basada en la idea de la heurística de Nawaz, Enscore y Ham (NEH) empleada en problemas de flujo taller de permutación con el objetivo de minimizar el makespan (Nawaz et al. ,1983). La heurística NEH está estructura en tres etapas: (1) calcular el tiempo de proceso total de todos los trabajos, (2) ordenar los trabajos en orden descendiente de tiempo de proceso total y (3) obtener la mejor secuencia de trabajos siguiendo el orden establecido en la etapa (2). Para ello se evalúan todas las posiciones posibles en las que un determinado trabajo puede ser colocado dentro de una secuencia de trabajos ya secuenciados, quedándose con aquella que da lugar al menor makespan. El algoritmo CBP se estructura en dos etapas: (1) determinar la mejor lista de espera basándose en la idea de la heurística NEH y (2) planificar la lista de espera resultante en (1) con un algoritmo bin packing. De forma general, la primera etapa consiste en aplicar los pasos (2) y (3) de la heurística NEH con las siguientes modificaciones: Las reglas de secuenciación empleadas en el algoritmo CBP serán: EDD, HCW ó EDDHCW. La evaluación de las posiciones se realiza a través de un algoritmo bin packing. A continuación se detalla el pseudocódigo del algoritmo CPB desarrollado en este trabajo. 1. lista ordenada:= Lista de espera ordenada en base a regla de secuenciación 2. lista parcial:= Ø, plan quirúrgico:= Ø 3. for j:=1 to Nº Pacientes do i:= paciente (lista ordenada [j]) Evaluar las j posiciones en las que el paciente i puede ser ubicado en lista parcial (algoritmo bin packing) lista parcial:= lista con el paciente j insertado con la que se obtiene mayor valor de la función objetivo endfor 4. for j:=1 to Nº Pacientes do i:= paciente (lista parcial [j]) plan quirúrgico [i]:= fecha y quirófano asignado con algoritmo bin packing endfor Figura 2. Pseudocódigo del algoritmo CBP 1608 4. Experimentos 4.1. Generación de la batería de experimentos Con el objeto de evaluar la calidad de las soluciones obtenidas por los algoritmos propuestos, se ha diseñado una batería de problemas basada en el resultado de una revisión de la literatura en baterías de experimentos empleadas para la resolución de la fase Advance Scheduling. A continuación, se especifican tanto los procedimientos de generación de los principales parámetros como los valores que toman para cada uno de los trabajos analizados. En la Tabla 1, se recogen los parámetros relativos a los pacientes necesarios para la resolución del problema de planificación de intervenciones propuesto en (Molina Pariente et al. ,2009), que son: número de pacientes que componen la lista de espera (número fijo o número generado en función de la capacidad total de quirófanos, duración de la intervención (minutos), fecha límite de la intervención (día), responsable cirujano de la intervención. Además, en la última columna, se recoge el número de instancias resueltas en cada trabajo. Tabla 1. Generación y valores de los parámetros de pacientes Pacientes Referencia Número Pacientes Duración intervención (minuto) Fecha límite (día) Asignación cirujano Batería (Jebali et al. ,2006) {11, 12, 13, 14, 15} Log-normal [180,60] Aleatoria Aleatoria 25 (Lamiri et al. ,2008b) Capacidad total quirófano Uniforme [30, 180] - - 16 (Fei et al. ,2009a) {40,…,160} (20) Pearson III [40, 150] Uniforme [1,14] Aleatoria 70 (Guinet and Chaabane ,2003) {10,…,85} (5) Log-normal [120,60] Log-normal [4, 1] - 608 (Hans et al. ,2008) 11380 Datos reales - Datos reales 1 (Lamiri et al. ,2008a) Capacidad total quirófano Uniforme [30, 180] - - 1 (Fei et al. ,2007) {40,…,160} (40) Pearson III [30, 150] Uniforme [1,20] - 40 (Fei et al. ,2008) {10,…,160} (10) Uniforme [15, 480] Uniforme [1,20] - 320 (Fei et al. ,2009b) {80,…,120} (10) Pearson III - - 120 (Chaabane et al. ,2006) 103 Datos reales - Datos reales 53 (Adan and Vissers ,2002) 26 {120,…,480} (120) Datos reales - 1 (Vissers et al. ,2005) 89 {120-480} (120) - - 1 (Marcon et al. ,2003) {24,…,31} (1) Log-normal, normal [60-180, 01-0,5 Dur.] - - 200 1609 En la Tabla 2, se recogen los parámetros relativos a: Horizonte de planificación. La mayoría de contribuciones fijan un número determinado de días de duración del horizonte de planificación, planificando el mayor número de intervenciones posibles en función de las restricciones de los recursos quirúrgicos (quirófanos, cirujanos, anestesistas, etc.) disponibles en la especialidad. Sin embargo, (Jebali et al. ,2006) fija la duración del horizonte en función de los pacientes en lista de espera, planificando todos los pacientes. Quirófanos. Los parámetros relevantes son: número de quirófanos disponibles en el horizonte de planificación (número fijo ó fijado por la fase MSS), capacidad regular (minuto) de los turnos de quirófano (la capacidad puede variar de un día a otro del horizonte de planificación) y, por último, la capacidad extra (minuto) en la que se puede incurrir en un turno. Cirujanos: Los parámetros considerados son: número de cirujanos disponibles y capacidad disponible (minuto) para realizar intervenciones en el horizonte. Tabla 2. Parámetros relativos al horizonte temporal, quirófanos y cirujanos Referencia Horizonte Quirófanos Cirujanos Longitud (día) Número quirófanos Capacidad regular (minuto) Capacidad extra (minuto) Número cirujanos Capacidad (minuto) (Jebali et al. ,2006) Pacientes 3 480 240 4 {420, 480, 720} (Lamiri et al. ,2008b) 5 {3, 6, 9, 12} 480 180 - - (Fei et al. ,2009a) 5 6 {0, 480} {0, 180} 8 {0, 720} (Guinet and Chaabane ,2003) 5 {1, 2, 3} 480 240 - - (Hans et al. ,2008) 260 16 450 - 11 {0, 1350} (Lamiri et al. ,2008a) 5 6 480 Sin límite - - (Fei et al. ,2007) 5 MSS MSS MSS 8 MSS (Fei et al. ,2008) 5 {1, 2, 3, 4} Uniforme [0, 480] Uniforme [0, 480] - - (Fei et al. ,2009b) 5 2 {240, 420} 120 8 Pacientes (Chaabane et al. ,2006) 5 6 720 - 9 Variable (Adan and Vissers ,2002) 5 1 360 - 4 360 (Vissers et al. ,2005) 20 4 360 - NA NA (Marcon et al. ,2003) 200 8 480 - - - 1610 En base a los resultados recogidos en las tablas anteriores, los principales factores que se han tenido en cuenta en el diseño de la batería empleada en este trabajo son: Número de días en el horizonte de planificación. Sólo se consideran los días laborables (5 días por semana). Número de quirófanos disponibles en la especialidad quirúrgica en el horizonte de planificación. Número de cirujanos disponibles en la especialidad quirúrgica en el horizonte de planificación. Número de turnos disponibles por cirujano para operar en cada semana del horizonte de planificación. Capacidad regular del turno de quirófano (minutos). Se considera que todos los quirófanos disponen de la misma capacidad. No se admite capacidad extra en ningún turno. Número de pacientes en lista de espera. El número de pacientes en lista de espera se determina en función de un porcentaje de la capacidad total de quirófano disponible en el horizonte de planificación, de forma que se generan pacientes mientras que la duración total de las intervenciones de éstos sea menor o igual que dicho porcentaje. La duración de la intervención (minutos) se asume que sigue una distribución log-normal [180,45]. La asignación de paciente a cirujano sigue una distribución uniforme y pueden ser planificados en cualquier quirófano disponible en la especialidad. La fecha límite de una intervención se asume que sigue una distribución log-normal. Los factores que se consideran en la generación de esta fecha es la media (μ) y el coeficiente de variación (relación entre la desviación típica y la media) de la distribución. La ponderación clínica de una intervención sigue una distribución uniforme [150, 450]. En la Tabla 3, se especifican los valores de los factores considerados para la generación de la batería. Estos valores están basados en los valores que se emplean en la literatura. Tabla 3. Factores del diseño de la batería de experimentos Factor Valor Nº de días {5,20} Nº de quirófanos {3,6} Nº de cirujanos {4,8} Nº turnos disponibles por cirujano 4 Capacidad quirófano (minuto) 480 % Capacidad total de quirófano {75, 100} μ 1 Coeficiente de variación {0.2, 0.3} La combinación de los valores de estos factores conduce a la generación de 32 tipos de problemas, generándose 20 instancias por problema, por lo que se obtiene una batería de 640 problemas. 1611 4.2. Resultados En este apartado se muestran los resultados obtenidos de comparar, para cada uno de los problemas, la solución obtenida mediante IP con la solución de las heurísticas propuestas. Para obtener la solución mediante IP, los problemas han sido resueltos con el software PARALLEL CPLEX en un equipo con un procesador Intel Core 2 Quad Q6600, 2,40 GHz con 4,00 GB de RAM. Para comparar la calidad de las soluciones de los métodos propuestos se emplea el porcentaje de desviación relativa (relative percentage deviation, RPD) sobre el óptimo o la mejor solución conocida (best bound). Dado que el problema considerado es de maximización, el RPD viene dado por 100 sol solsol Best HeuBest RPD , donde sol Best es la mejor solución encontrada por PARALLEL CPLEX en un tiempo de computación de 300 segundos. En la Tabla 4, se muestra un resumen de los resultados obtenidos en la experimentación. El RPD medio es calculado sólo para las instancias en las que el algoritmo o la IP encuentran al menos una solución factible. Tabla 4. Resultados Algoritmo Regla secuenciación Bin Packing RPD medio (%) Solución no factible (%) Tiempo Medio (sg) SBP EDD FF 27,61 4,70 0,0015 BF 30,45 6,81 0,0170 WF 43,72 57,21 0,0175 HCW FF 96,97 99,84 0,0015 BF 100 100 0,0170 WF 100 100 0,0175 EDD-HCW FF 25,77 4,70 0,0015 BF 28,81 6,81 0,0170 WF 41,11 57,21 0,0175 CBP EDD FF 16,34 3,24 19,98 HCW FF 68,06 90,76 19,98 EDD-HCW FF 14,01 3,24 19,98 IP 5,85 8,91 300 Los resultados muestran como para el algoritmo SBP, la regla de secuenciación EDD-HCW es la que mejor resultados obtiene (menor RPD medio). Sin embargo, la regla HCW con la que se esperaba que se obtuvieran los mejores resultados (dada la definición de la función objetivo del problema) es la peor. Al ordenar la lista de espera de acuerdo a esta regla, puede ocurrir que intervenciones con fecha límite dentro del horizonte de planificación presenten ponderaciones clínicas bajas (por lo que quedan ordenadas al final de la lista de espera), conduciendo a soluciones inadmisibles al aplicar los algoritmos bin packing, debido a la criticidad de la restricción de la fecha límite. En lo que respecta a los algoritmos bin packing, el algoritmo FF es el que mejor resultados obtiene. El algoritmo CBP se ha resuelto con todas las reglas de secuenciación (EDD, HCW, EDDHCW) y, únicamente, con el algoritmo FF (dado que es con él que mejor resultados se obtiene). Como se puede ver en la Tabla 4, el algoritmo CBP obtiene mejores resultados que el SBP, obteniendo él mejor para la regla de secuenciación EDD-HCW. 1612 5. Conclusiones El algoritmo CBP basado en la heurística NEH para la secuenciación de la lista de espera obtiene mejores resultados que los algoritmos bin packing empleados para la asignación de pacientes a turnos de quirófanos en la literatura. El porcentaje de problemas en los que los algoritmos no encuentran soluciones factibles es menor, siendo la calidad media de las soluciones, para problemas en los que el algoritmo encuentra solución factible, mejor (menor RPD medio). A la vista de los resultados, las futuras líneas de investigación podrían ser: Desarrollar reglas de secuenciación más sofisticadas que puedan mejorar los resultados obtenidos con el algoritmo CBP. Desarrollar algoritmos de búsqueda local y metaheurísticas para la resolución del problema de planificación de intervenciones quirúrgicas. Referencias Adan, I.J.B.F.;Vissers, J.M.H. (2002). Patient mix optimisation in hospital admission planning: A case study. International Journal of Operations and Production Management, Vol 22, No. 4, pp. 445-461. Chaabane, S.; Meskens, N.; Guinet, A.; Laurent, M. (2006). Comparison of Two Methods of Operating Theatre Planning: Application in Belgian Hospital. International Conference on Service Systems and Service Management, Vol 1, pp. 386-392. Dexter, F.; Macario, A.; Traub, R.D. (1999a). Which algorithm for scheduling add-on elective cases maximizes operating room utilization? Use of bin packing algorithms and fuzzy constraints in operating room management. Anesthesiology, Vol 91, No. 5, pp. 1491-1500. Dexter, F.; Macario, A.; Traub, R.D.; Hopwood, M.; Lubarsky, D.A. (1999b). An operating room scheduling strategy to maximize the use of operating room block time: computer simulation of patient scheduling and survey of patients' preferences for surgical waiting time. Anesth.Analg., Vol 89, No. 1, pp. 7-20. Fei, H.; Chu, C.; Meskens, N. (2009a). Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria. Annals of Operations Research, Vol 166, No. 1, pp. 91-108. Fei, H.; Meskens, N.; Combes, C.; Chu, C. (2009b). The endoscopy scheduling problem: A case study with two specialised operating rooms. Int J Prod Econ, Vol 120, No. 2, pp. 452462. Fei, H.; Chu, C.; Meskens, N.; Artiba, A. (2008). Solving surgical cases assignment problem by a branch-and-price approach. Int J Prod Econ, Vol 112, No. 1, pp. 96-108. Fei, H.; Meskens, N.; Chu, C. (2007). An operating theatre planning and scheduling problem in the case of a "block scheduling" strategy. Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management, Vol 1, pp. 422-428. Galambos, G.;Woeginger, G.J. (1995). On-line bin packing - A restricted survey. ZOR Zeitschrift für Operations Research Methods and Models of Operations Research, Vol 42, No. 1, pp. 25-45. Guinet, A.;Chaabane, S. (2003). Operating theatre planning. International Journal of Production Economics, Vol 85, No. 1, pp. 69-81.