Un homenaje a dos fiestas

Quizás el subtítulo anterior pueda ser percibido de manera bastante extraña por el lector -¿qué relación tiene una fiesta con el título principal del artículo?-. Sin embargo, el autor desea referirse con término “fiesta” a dos asuntos que pueden parecer muy distintos en una primera instancia, pero que en este caso guardan una relación entre sí. Existen dos fiestas de las cuales se quiere hacer especial mención: la primera radica en aprovechar esta publicación relacionada precisamente con aeronaves como una manera académica de festejar el año donde la Aviación Naval cumple 100 años de vida, y la segunda consiste en aceptar -aunque un poco tarde- la cordial invitación que hiciese Soto, (2009) en su publicación de hace más de 15 años atrás con respecto a la fiesta de la Investigación de Operaciones (I.O).

Breve introducción a la programación lineal

Dentro del extenso universo de la I.O., existe el popular mundo de la programación lineal -conocido por cualquier persona que haya aplicado alguna vez el método Simplex a un problema lineal-. Esta herramienta es muy útil para modelar y resolver problemas industriales y, en efecto, casi cualquier problema relacionado con la actividad humana, siendo aplicado en modelos matemáticos en los cuales las funciónes objetivo y restricciones son estrictamente lineales. La programación lineal produce algoritmos eficientes de cálculo para problemas con una gran cantidad de restricciones y variables, formando la columna vertebral de los algoritmos de solución para los demás modelos de investigación de operaciones, como la programación entera, la programación dinámica, la estocástica y la no lineal, entre otros (Taha, 2004). Claramente, estos modelos matemáticos poseen muchas ventajas sobre una descripción verbal de un problema en particular. La más obvia es que describe un problema en forma mucho más concisa, siendo más comprensible toda la estructura del problema, revelando las relaciones causa-efecto (Hillier and Lieberman, 2001).

Por otra parte, es importante hacer la distinción entre un modelo matemático y su técnica de resolución, dos cosas muy diferentes. Un modelo matemático intenta representar una abstracción de una realidad, sin embargo, ésta puede ser resuelta de variadas maneras. Por lo general, los métodos de resolución se clasifican en dos aproximaciones: los métodos exactos y heurísticos, donde se explota la estructura del modelo y los métodos aproximados donde predominan el uso y desarrollo de las metaheurísticas.

Esta distinción es muy relevante, debido a que muchos problemas industriales reales se caracterizan por ser gigantescos, por lo que las variables y restricciones de los modelos matemáticos pueden llegar a tal dimensionalidad que son intratables computacionalmente si se intentase resolver, por ejemplo, a través del método Simplex sin ningún tratamiento previo. Lo anterior se magnifica a niveles mucho más liosos cuando esas variables no pueden tomar valores continuos, sino que deben ser enteros o binarios (como los problemas de asignación o decisión), por lo que los convierte en problemas combinatorios muy complejos computacionalmente.

Introducción al mantenimiento de aeronaves

Las aeronaves poseen miles de piezas, sistemas y componentes que necesitan mantenimiento recurrente después de ciertas horas de vuelo (FH), ciclos de vuelo (FC), días calendario (DY) o meses (MO), los que son conocidos como parámetros de uso y sus máximos permitidos en las operaciones son definidos en intervalos de inspección. La asignación óptima de las tareas de mantenimiento a las mejores oportunidades de mantenimiento es un problema desafiante que los ingenieros resuelven a diario. El enfoque común que se sigue es agrupar las tareas en revisiones (checks) de mantenimiento (e.g. A-, B-,1 C- y D-check) que garantizan un programa de mantenimiento consistente, en el que todas las tareas se deben realizar antes de las fechas de vencimiento asociadas. Un típico A-check incluye la inspección del interior o exterior de la aeronave con áreas abiertas seleccionadas (e.g. revisión y mantenimiento de aceite, reemplazo del filtro y lubricación) (Ackert, 2010). El C-check requiere de inspecciones visuales exhaustivas a los sistemas y componentes individuales para verificar su capacidad de servicio y funcionamiento. El D-check2 descubre el fuselaje, la estructura de soporte y las alas para inspeccionar la mayoría de los elementos estructurales significativos.

El problema de asignación de tareas (o TAP por sus siglas en inglés) en el mantenimiento de aeronaves, se refiere al proceso de asignación óptima de tareas en revisiones de mantenimiento predefinidas. Determina las fechas óptimas de inicio de los trabajos de mantenimiento de aeronaves para que todas las tareas preventivas se realicen lo más cerca posible a sus respectivas fechas de vencimiento. El TAP es un problema complejo debido a su naturaleza combinatoria y debe ser resuelto para toda la flota al mismo tiempo. En aplicaciones reales, se pueden programar varias revisiones de aeronaves en paralelo donde las tareas asignadas a éstas compartirán los recursos de mantenimiento. Por ejemplo, la Figura 1 ilustra un caso para cinco C-checks superpuestos en el tiempo (Witteman et al., 2020).

En el presente artículo se presentará un enfoque apoyado en los trabajos de Witteman et al., 2020 para abordar de manera eficiente el TAP, pudiendo resolver este problema de una manera muy eficiente sin comprometer la calidad de la solución. Los planes de mantenimiento se ven afectados con frecuencia por interrupciones debido a horarios de vuelo no previstos o por la necesidad de tareas de mantenimiento no programadas, necesitando ser revisados o incluso replanificados de manera constante (Steiner, 2006). Basándose en el problema de empaquetado (bin packing problem, BPP), se considera los controles de mantenimiento preprogramados como bins3 de diferentes dimensiones (temporales) y que comparten una capacidad multidimensional referido a los múltiples tipos de especialidades laborales involucradas en la ejecución de tareas. Los ítems son las tareas que deberán “empaquetarse” en los bins, los cuales estarán sujetos a restricciones de tiempo que limitan las opciones de éste (Friesen & Langston, 1986). Como método de resolución, se presenta una heurística basada en el algoritmo worst-fit decreasing, WFD diseñada originalmente para el BPP, pero para resolver de manera eficiente el time-constrained – variable size (TC-VS-BPP).

Se puede decir que el trasfondo de este trabajo es buscar una manera eficiente de resolver este problema a grandes escalas4  y ser comparado en eficiencia contra un programa comercial de optimización lineal.5 No obstante, para problemas de baja dimensionalidad (flotas pequeñas), solo bastaría con programar linealmente el modelo matemático presentado en estos softwares para encontrar una solución óptima.

Formulación del problema

Consideraciones del modelo:

O    Segmentos de tiempo: En la práctica, los mantenedores suelen enfrentarse a situaciones de revisión de mantenimiento superpuestos, en los que varias aeronaves se someten al mismo tipo de control al mismo tiempo y, por lo tanto, compiten por los recursos limitados de mantenimiento. La Figura 2 muestra un ejemplo de dicha situación donde cinco aeronaves están programadas para realizar el mantenimiento C-check entre el 21 de abril y el 30 de mayo. Durante estos períodos de superposición los recursos deben compartirse, lo que limita la asignación óptima de tareas.

O    Elementos (ítems) de las tareas y oportunidades de mantenimiento: La mayoría de las tareas rutinarias deben programarse más de una vez para la misma aeronave durante el horizonte de tiempo considerado. Por ejemplo, una tarea que debe realizarse en cada A-check (aproximadamente cada 7 u 8 semanas), puede tener que ejecutarse 38 veces en un horizonte de 5 años. En el caso del TC-VS-BPP una tarea de rutina debe ejecutarse como máximo N veces en el horizonte de planificación, lo que se traducirá en N ítems de tareas en el modelo. Para ello, se estima el número máximo de repeticiones en el horizonte de planificación. En la tabla 1 se ilustra el enfoque planteado para una tarea determinada de una aeronave específica.

Formulación del modelo:

O    Conjuntos:

    - i: indicador de tarea.

    - K: conjunto de aeronaves.

    - Nk: conjunto de ítems – tareas para la aeronave 

    - Tk: conjunto de segmentos de tiempo para la aeronave 

    - Ri,k: conjunto de segmentos de tiempo para el ítem – tarea                de la aeronave 

    - j: conjunto de especialidades (o especialistas).

    - Oi,k: conjunto de unidades del ítem – tarea que sigue al ítem – tarea                            de la aeronave 

O    Parámetros:

         -    : costo de asignar el ítem – tarea 

                        de la aeronave         

    a la oportunidad de mantenimiento perteneciente al segmento 

    -       : cantidad de horas de trabajo disponible de la especialidad en el segmento de tiempo t

    -    〖: cantidad de horas de trabajo de la especialidad j prescritas para realizar el ítem – tarea i de la aeronave k

    -    σ: “ratio no rutinaria” que indica la cantidad de horas de trabajo necesitados de la especialidad l por cada hora de trabajo prescrita para la especialidad j (nota: σ

    - di,k : número máximo de días entre ítems – tareas reprogramados para la aeronave 

    - dt : número de días desde el inicio del horizonte de planificación hasta la oportunidad de mantenimiento perteneciente al segmento de tiempo t

    - fhi,k : número máximo de horas de vuelo entre el ítem – tarea reprogramada i para la aeronave k

    - fht: número de horas de vuelo acumuladas desde el inicio del horizonte de planificación hasta la oportunidad de mantenimiento perteneciente al segmento de tiempo t

    - fci,k : número máximo de ciclos de vuelo entre el ítem – tarea reprogramada i para la aeronave k

    - fct: número de ciclos de vuelo acumulados desde el inicio del horizonte de planificación hasta la oportunidad de mantenimiento perteneciente al segmento de tiempo t

    - O_diaj: total de días de operación de las aeronaves desde el inicio del horizonte de planificación hasta la fecha del vencimiento de la realización del ítem – tarea i, siguiendo el intervalo de tarea no considerando restricciones de recursos. 

    - 〖intervaloi: intervalo de reparación promedio para el ítem – tarea i medido en días.

    - tasa_trabajoj: tasa de mano de obra por hora por especialidad 

    - 〖otros_costosi,k: costos no laborales asociados con el ítem – tarea de la aeronave , como costos de repuestos y herramientas

O    Variables de decisión:

    - :1 si el ítem – tarea i es asignado a la oportunidad de mantenimiento al segmento de tiempo t para la aeronave k, 0 en otro caso.

La restricción (2) garantiza que cada ítem – tarea se asigne exactamente una vez, ya sea a un evento de mantenimiento o a uno ficticio después del horizonte de planificación. La restricción (3) asegura que las horas de mano de obra disponibles para cada tipo de especialidad no excedan en cada uno de los segmentos de tiempo de mantenimiento. La restricción (4) garantiza que un ítem – tarea posterior se programe dentro del número de días definido en el intervalo para la tarea respectiva. Las restricciones (5) y (6) reflejan el intervalo en términos de horas y ciclos de vuelo respectivamente. Finalmente, la restricción (7) refleja que la variable es del tipo binaria.

Heurística WFD

El problema TC-VS-BPP es NP-Hard (Garey & Johnson, 1990). Cómo se mencionó anteriormente, las soluciones óptimas para instancias pequeñas de este problema pueden ser calculadas utilizando métodos exactos. Sin embargo, cuando crece el tamaño del problema estos métodos se vuelven prohibitivos. Por esta razón, se propone una heurística constructiva basado en el WFD para resolver el TAP de manera eficiente (Witteman et al., 2020):

Breve análisis de resultados

Para ejecutar el algoritmo TAP propuesto, se utilizó una base de datos de entrada que incluyó la utilización de 40 aeronaves dentro de un programa de mantenimiento determinado previamente. El tiempo de ejecución del algoritmo demoró un promedio de 25 segundos, siendo codificado en lenguaje Python 3.7 y ejecutado en un procesador 1,8 GHz Intel Core i5 de dos núcleos con una memoria RAM de 8 GB 1600 MHz DDR3.6 Este código se encuentra publicado (privado) en el repositorio GitHub7 del autor en la siguiente dirección: https://github.com/AndresCatalanUrzua/TAP_Aeronaves, para tener acceso a él se solicita al lector ponerse en contacto a través de la dirección de correo electrónico dado en la portada del presente artículo.

De acuerdo a la base de datos utilizada, el algoritmo nos arroja los siguientes resultados8, los cuales pueden ser visualizados en las Tablas 2 y 3:

Conclusiones

Lo expuesto en el presente artículo es solo un pequeño ejemplo que demuestra el potencial que la Investigación de Operaciones puede tener sobre problemas complejos y que, además, poseen restricciones de recursos.9 No obstante, como bien lo describe Soto, (2009) en su publicación, estas herramientas poseen un sinfín de aplicaciones más, donde la OTAN las ha clasificado en tres grandes áreas relacionadas a la planificación de las operaciones militares: Planning (e.g. game theory, wargaming, decision trees), Deployment (e.g. scenario analysis, misión rehearsal) and Post-Operation (e.g. process modeling, causal mapping, data analysis).

Actualmente, la Dirección de Programas, Investigación y Desarrollo de la Armada posee un departamento que se encarga precisamente de temas que estén relacionados con la utilización de estas técnicas, específicamente en lo que respecta al área de análisis de operaciones, a través de desarrollo e investigación de modelos y sistemas que puedan ser una real ayuda a la toma de decisiones de los mandos operativos.

A pesar de los años, la fiesta sigue en su auge, solo falta que más personas se animen y acepten esta gran invitación.