Planificación de trabajos en intervalos.

Quantitative Methods 1575 II International Conference on Industrial Engineering and Industrial Management XII Congreso de Ingeniería de Organización September 3-5, 2008, Burgos, Spain Planificación de trabajos en intervalos Jose Manuel García1, Ricardo Galan de Vega2, Ignacio Eguia1, Jesús Racero1 1 Dpto. de Organización. Industrial y Gestión de Empresas. Escuela Superior de Ingenieros. Universidad de Sevilla. Avda. de los descubrimientos, s/n. 41092. Sevilla. [email protected], [email protected], [email protected] 2 Aguas y Estructuras, S.A. Isla de la Cartuja s/n, 41092, Sevilla. [email protected] Resumen La planificación de trabajos en intervalos aparece en los sistemas en los que cada tarea tiene que ser realizada dentro de un intervalo de tiempo. La planificación de la capacidad en estos sistemas trata tanto de la asignación de los recursos a las tareas atendiendo a un criterio de optimización (planificación operacional), como del cálculo de la capacidad necesaria para realizar todas las tareas (planificación táctica). En este trabajo se establece una clasificación de toda esta clase de problemas, realizando una revisión bibliográfica de los principales trabajos y describiendo las aplicaciones prácticas más relevantes. Palabras clave: Planificación operacional, Planificación táctica, Programación de trabajos en máquinas 1. Introducción En la mayoría de los trabajos sobre planificación y programación de tareas el tiempo de finalización de las tareas no se encuentra restringido por ventanas temporales, permitiéndose cualquier instante del horizonte temporal como tiempo de finalización. Tan sólo se describe el caso de una fecha límite ÿi que generalmente suele dar una holgura amplia de realización del trabajo, manteniendo la problemática del establecimiento de secuencias. Sin embargo, en algunos sistemas las tareas poseen restricciones fuertes de tiempo motivadas por calendarios prefijados, por aspectos físicos de los materiales involucrados en la fabricación, por estrictas normas de proceso, o simplemente por la imposición de un intervalo de procesamiento. En estos casos la programación de las tareas depende principalmente de la capacidad del sistema, es decir, de la cantidad de recursos disponibles. La planificación de trabajos en intervalos aparece en los sistemas en los que cada tarea tiene que ser realizada dentro de un intervalo de tiempo. La planificación de la capacidad en estos sistemas trata tanto de la asignación de los recursos o máquinas a las tareas atendiendo a un criterio de optimización (planificación operacional), como del cálculo de la capacidad necesaria para realizar todas las tareas (planificación táctica). Aplicaciones reales de estos sistemas van desde los procesos de mantenimiento de aviones y asignación de puertas en aeropuertos, la planificación de satélites de observación terrestre, asignación de aulas en escuelas, la asignación de conductores en líneas de autobuses, asignación de turnos de trabajo, etc. En general, estos sistemas se encuentran en multitud de disciplinas en el entorno de servicios donde existen actividades programadas de antemano. Todos los enfoques del problema estudiados hasta la actualidad han considerado una sola etapa para la realización de Quantitative Methods 1576 las tareas. Sin embargo, en algunas situaciones, las tareas pueden necesitar de varias etapas para ser completadas. Dado un conjunto de n trabajos J1,…,Jn cada uno con un intervalo [ai,bi] en el que debe ser procesado, un tiempo de proceso ti, un peso o prioridad wi y perteneciente a una determinada clase de trabajo di dentro de un conjunto de D diferentes clases de trabajos (Figura 1). Para la realización de los trabajos se dispone de un conjunto de máquinas M={M1,…, Mm} cada una con un intervalo de disponibilidad [ij, fj], un coste de utilización uj, y perteneciente a una determinada clase de máquina cj dentro de un conjunto de C clases diferentes de máquinas. La compatibilidad entre clases de trabajos y máquinas se expresa a través de una matriz de compatibilidad LAxB definida como sigue: 1 si un trabajo de clase puede ser procesado por una maquina de la clase 0 en otro caso (,) DxC dc LLdc  ® ¯ Hay que tener en cuenta que cada máquina no puede procesar más de un trabajo al mismo tiempo y, de forma genérica, cada trabajo se procesa de forma ininterrumpida sobre alguna de las máquinas del sistema. ti Ji ai bi Figura 1. Datos asociados al trabajo Ji Estos sistemas se han presentado en la literatura en un marco diferente a los sistemas clásicos de programación de operaciones. Sin embargo, pueden considerarse como un caso particular de los mismos, si bien, para casos particulares deben agregarse características nuevas. El objetivo de este trabajo es clasificar los trabajos realizados en esta área de la programación de tareas y describir las aplicaciones prácticas más sobresalientes del problema. 2. Clasificación de Problemas La planificación de trabajos en intervalos aparece en la literatura con diferentes variaciones, dependiendo de los intervalos de tiempo para el procesamiento de las tareas, del objetivo definido, del número de clases de recursos (máquinas), y de las características que motivan las diferentes clases de trabajos y recursos. Una primera clasificación de estos sistemas se produce según la amplitud del intervalo para el procesamiento de las tareas. Según ello se distingue entre: x Problemas donde el tiempo de proceso de las tareas coincide con la amplitud del intervalo. Este grupo recibe el nombre de Fixed job scheduling problem (FSP). x Problemas donde el tiempo de proceso de las tareas es menor o igual que la amplitud del intervalo. Este tipo se denomina Variable job scheduling problem (VSP). Con respecto a los objetivos, la optimización se orienta en dos direcciones: x Planificación táctica de la capacidad: Se optimiza el uso de los recursos necesarios para atender todas las tareas. Quantitative Methods 1577 x Planificación operacional de la capacidad: A partir de un conjunto de recursos, la planificación operacional es la asignación de recursos a tareas con objeto de maximizar el peso total de las tareas completadas. También se presenta, para el caso de varias clases de trabajos y máquinas, un problema de factibilidad consistente en averiguar si, para un conjunto de máquinas dado, es posible realizar todos los trabajos existentes. De acuerdo al número de clases de recursos o máquinas, los primeros trabajos sobre el problema consideraron una única clase de recurso, de forma que cada tarea podía ser procesada por cualquier recurso. Sin embargo, el caso más interesante es considerar varias clases de recursos. En este caso dos variantes se establecen: x License Class Scheduling: Los recursos están disponibles durante todo el horizonte de planificación. La compatibilidad entre tareas y recursos está motivada por aspectos técnicos. x Shift Class Scheduling: Cada recurso está sólo disponible en un intervalo o conjunto de intervalos de tiempo. Un recurso puede procesar únicamente las tareas que se producen dentro de su intervalo de tiempo. Otros parámetros que también han sido considerados para el problema son los siguientes: x La propiedad de interrumpir el procesamiento del trabajo en una máquina (preemption): Aunque las características del problema obligan a que no existan pausas en el procesamiento de un trabajo, puesto que el tiempo de proceso coincide con el intervalo de procesamiento, el caso de preemption se plantea en algunos escenarios en los que se considera admisible que el trabajo puede ser procesado por más de una máquina (el procesamiento del trabajo puede pasar de una máquina a otra). x Restricciones de Spread-time: Consideran un tiempo límite de disponibilidad para cada máquina. x Restricciones de Working-time: Consideran un tiempo límite de actividad de cada máquina. Tanto esta restricción como la anterior aparecen en casos asociados a turnos de trabajo. x Máquinas uniformes: No todas las máquinas operan a la misma velocidad por lo que los tiempos de proceso de los trabajos son variables, dependen de la máquina que los procese. La figura 1 resume la clasificación de los sistemas logísticos con restricciones de tiempo. En ocasiones toda esta clase de problemas ha recibido el nombre genérico de Interval scheduling problem. Sin embargo, como veremos en posteriores apartados, se han utilizado diversos nombres para denominar esta clase de problemas, dependiendo del escenario concreto. Los escenarios que han recibido más atención en la literatura han sido los de tipo FSP, incluyendo aquéllos con varias clases de recursos y trabajos. Estos últimos poseen una dificultad mayor y los métodos de resolución han ido encaminados tanto a una resolución exacta como aproximada. Los escenarios con trabajos variables han recibido una atención Quantitative Methods 1578 más somera. Son los que ofrecen mayor complejidad, incluso sin considerar clases de recursos. Figura 2. Clasificación de los problemas de planificación de trabajos en intervalos 3. Planificación de trabajos Fijo (FSP) A continuación analizaremos diversos enfoques del problema FSP, teniendo en cuenta una o varias clases de recursos o máquinas y los dos objetivos considerados en el problema. En Kovalyov et al (2007) se realiza una revisión de algoritmos y complejidad computacional para el problema FSP con objetivo operacional. En nuestro caso analizamos tanto objetivo táctico como operacional y dividimos el análisis en una o varias clases de recursos. 3.1. Una clase de recurso En el problema FSP, en su versión más simple, sin considerar clases de trabajos ni recursos, se disponen de n trabajos con fecha de inicio y tiempo de procesado dados. Se define para un trabajo Ji, si como el instante de comienzo, fi el instante de finalización y ti = si - fi la duración del mismo. Se asocia también con cada trabajo un valor o peso del trabajo wi, que representa el beneficio asociado a la realización del mismo. Los trabajos deben ser procesados sobre un conjunto de m máquinas(recursos) paralelas(Pm). FSP se reduce al problema de determinar el número de máquinas para procesar todos los trabajos (planificación táctica) o al de establecer una asignación de máquinas que maximice el peso de los trabajos procesados (planificación operacional). Objetivo Táctico Puede ser éste el escenario que dio nombre al problema FSP. La solución del problema se obtiene como una consecuencia directa del teorema de Dilworth (Diworth, 1950) sobre la descomposición de conjuntos parcialmente ordenados, donde se establece que en cualquier conjunto parcialmente ordenado el número mínimo de cadenas disjuntas que albergan todos los elementos es igual al número mayor de elementos mutuamente no relacionados en el conjunto. El problema fue considerado en primer lugar por Danzing y Fulkerson (1954), y posteriormente por Gupta et al(1979) y Nakajima et al (1982), mostrando algoritmos de resolución de orden O(n log n). Gertsbakh y Stern(1978) también definen FSP como un caso particular del problema de Dilworth y proponen un algoritmo basado en la construcción secuencial de programas de trabajo para máquinas hasta agotar todos los trabajos. PLANIFICACIÓNDE TRABAJOS EN INTERVALOS OBJETIVO A MPLITUD DEL INTERVALO DE PROCESAMIENTO Nº CLASES DE RECURSOS FSP V SP PLANIFICACI Ó N TÁCTICA UN RECURSO PLANIFICACI Ó N OPERACIONAL V ARIOS RECURSOS LICENSE CLASS SCHEDULING SHIFT CLASS SCHEDULING Quantitative Methods 1579 La idea para el cálculo del mínimo número de máquinas está basada en el cálculo del grado de solapamiento de los trabajos en el tiempo. El grado de solapamiento de los trabajos en un instante t del horizonte de planificación se define como el número de trabajos que se procesan durante el instante t. La expresión corresponde con Lt=|{Ji/sidt<fi}|. El número mínimo de máquinas correspondería con el mayor valor del grado de solapamiento en algún instante t. El mayor grado de solapamiento se define como L = max{Lt / 0dtdT}, siendo [0,T] el horizonte en el que se produce la ejecución de todos los trabajos. El problema también puede resolverse mediante un simple algoritmo de asignación avaricioso que obtiene además la asignación óptima de trabajos a máquinas (Fishetti et al, 1987). A pesar de asumir un número de máquinas ilimitado, es equivalente considerar un número de máquinas lo suficientemente grande de forma que siempre existan máquinas disponibles. Una cota superior para el número de máquinas podría ser el número de trabajos (cada máquina procesaría un trabajo). Como una variante a la formulación general del problema FSP en este escenario, Fishetti et al (1987, 1989, 1992) plantean el problema añadiendo restricciones de Spread-Time y Working- Time. Objetivo Operacional Cuando el número de máquinas es menor que el mayor grado de simultaneidad de los trabajos, el problema FSP llega a ser más interesante. En este caso el objetivo del problema pasa a ser el de encontrar el subconjunto de trabajos a ser procesados. Para la selección de trabajos se atiende al criterio del máximo valor total del conjunto de trabajos seleccionados. Cuando suponemos el mismo valor wi para todos los trabajos, el objetivo se convierte en maximizar el número de trabajos procesados. Encontramos por tanto un problema de secuenciación en el que no se realizan todos los trabajos, sino solamente un subconjunto de ellos, elegido en base a los pesos de los mismos. Con una única clase de máquinas y trabajos, FSP ha sido considerado, entre otros, por Arkin y Silverberg(1985), Kolen et al(1987) y Gabrel(1995), quienes muestran que puede ser resuelto en tiempo polinomial por un algoritmo de flujo a coste mínimo. Kroon et al(1995) proponen para la resolución del problema la aplicación de un algoritmo de flujo de coste mínimo a un grafo dirigido G(N,A) cuyo construcción es más directa que la propuesta por los autores anteriores. Para el caso de máquinas uniformes, Bekki y Azizoglu (2007) muestran que un problemas de clase NP y proponen un método de tipo branch&bound para su resolución. 3.2. Varias clases de recurso Sería éste el caso más complejo del problema FSP. Ahora un trabajo no puede ser procesado por cualquier recurso. El caso de varias clases de recursos y trabajos integra las dos variantes señaladas en la clasificación realizada en la sección 2 (incompatibilidad por motivos técnicos o por disponibilidad temporal de las máquinas). Ambas variantes presentan las mismas características respecto a su complejidad. A pesar de ello, han sido analizados en la bibliografía de forma independiente. Básicamente, puede concluirse que el problema en su objetivo táctico y operacional es de carácter NP a partir de 3 clases diferentes de máquinas (Kolen y Kroon, 1991, 1992, 1993, 1994). Quantitative Methods 1580 Objetivo Táctico Las técnicas de resolución de este problema se han centrado en métodos aproximados. Generalmente se emplean algoritmos de carácter greedy, que intenta aprovechar las máquinas que ya han realizado trabajos previos. El uso de métodos con empleo de cotas superiores también manifiesta buenos resultados (Kroon et al, 1997). Objetivo Operacional Cuando el peso de los trabajos es el mismo o, simplemente, la unidad, y el objetivo es maximizar el número de trabajos realizados, el problema FSP con objetivo operacional e intervalos de disponibilidad para máquinas aparece también en la literatura como k-Track Assignment Problem (TAP), donde k define el número de máquinas. TAP es considerado por Brucker y Nordmann (1994), quienes proponen un método exacto de resolución de orden O(nk-1kkk+1). El método construye un grafo que recoge todos los posibles programas admisibles del problema. La ruta máxima en el grafo obtiene la solución óptima del problema. El método se muestra muy ineficiente con un número de máquinas superior a 4. Para un caso particular del problema presenta un algoritmo de orden O(nm-1) basado también en el cálculo de la ruta máxima. Considera también el caso en el que únicamente existen dos intervalos distintos de trabajo para las máquinas, proponiendo un algoritmo de orden O(n). Este caso es contemplado también por Hsu y Tsai (1989). Faigle and Nawijin (1995) y Faigle et al (1999) que estudian también el problema TAP tanto en su forma normal como en una versión online. El problema con únicamente dos clases máquinas ha sido estudiado por Dondeti y Emmons (1992), mostrando que puede ser resuelto en tiempo polinomial. Para el caso genérico del problema, permitiendo pesos en los trabajos, Arkin y Silverberg(1987) proponen un método exacto con una filosofía parecida a la descrita por Brucker y Nordman, aunque presenta un comportamiento mejor, puesto que el orden del número de nodos y arcos del problema es, respectivamente, O(nm) y O(nm+1). Aproximaciones heurísticas para este problema han sido consideradas en Gabrel (1995) y Kroon et al (1995). En el primer caso, el problema FSP es modelado como un problema de máximo conjunto de nodos independientes (Problema MIS). Se analizan tres procedimientos heurísticos para su resolución. Siempre que no se consideren pesos, los problemas FSP y VSP con objetivo operacional pueden ser modelados como un problema MIS. El algoritmo que presenta Kroon et al(1995) está basado en la resolución de algoritmos de flujo a coste a mínimo sobre grafos construidos de forma análoga a la resolución del problema FSP sin clases. Va calculando cotas superiores e inferiores del problema hasta un número máximo de iteraciones o una cota de la diferencia. El problema FSP permitiendo preemption es considerado en Dondeti y Emmons (1993) probando que puede ser resuelto en tiempo polinomial transformando el problema en un grafo de transporte. Quantitative Methods 1581 4. Planificación de trabajos variable (VSP) El caso de sistemas con trabajos variables (VSP) es la forma genérica de los sistemas con restricciones de tiempo. En este caso, se posee un intervalo de posibles instantes de comienzo. El objetivo táctico ha sido considerado por Gertsbakh y Stern (1978) para el caso de una sola clase de máquina, mostrando que VSP es NP en todos los casos. El segundo objetivo es considerado por Gabrel(1995), asumiendo el mismo valor para todos los trabajos. Al igual que el problema FSP, VSP puede ser modelado como un problema de cálculo del máximo conjunto independiente de nodos en un grafo. Este problema ha recibido atención en la literatura, entre otros por Wolfe y Sorensen(2000), considerando únicamente una máquina (objetivo operacional). Simulan el problema que aparece en la planificación de satélites de observación terrestre. Para el caso de una sola máquina el problema se ha denominado también como Job Interval Selection Problem(JISP). 5. Aplicaciones Los sistemas logísticos en los que las tareas poseen restricciones de tiempo de preceos son numerosos. En general, aparecen en la organización de muchos servicios públicos. A continuación comentamos algunos de ellos. Gestión de líneas de autobuses: Fishetti (1987,1989,1992) La variable a considerar en este caso es la planificación de los horarios de trabajo de los conductores de autobuses de tal modo que se minimicen los costes asociados para dotar de servicio a todas las líneas de transporte existentes, entendiendo como costes el número de vehículos y conductores a utilizar. El problema corresponde con un problema FSP con objetivo táctico. Las tareas son todos los horarios de autobuses predefinidos. Son trabajos fijos puesto que los horarios de salida y llegada poseen un instante fijo en el tiempo. En principio, sólo se considera el objetivo táctico, puesto que todos los viajes tienen que estar disponibles diariamente. Esta aplicación ha sido considerada con restricciones de working time y spread time, con objeto de tener en cuenta las condiciones de trabajo de los conductores. Gestión de Aeropuertos. Proceso de mantenimiento de aviones en aeropuertos mediante la asignación de técnicos a tareas: Kolen y Kroon (1991/92/93/94); Janson (1994). Cada día, en todos los aeropuertos del mundo, son miles los aviones que aterrizan y despegan. Estos aparatos, por razones obvias de seguridad, deben ser sometidos a operaciones de mantenimiento durante el periodo de tiempo que permanecen en el aeropuerto. Dado que los horarios de salidas y llegadas de los aviones son conocidos de antemano, el problema planteado consiste en minimizar el número de operarios de forma que se garantice el mantenimiento de todos los aparatos que pasen por el aeropuerto de la forma lo más satisfactoriamente posible. Este caso correspondería con un problema FSP o VSP con objetivo táctico y varias clases de trabajos y máquinas. El hecho de considerar varias clases de máquinas radica en la especialización de los operarios o técnicos. Generalmente, no todos el personal de mantenimiento esta especializado en todas Quantitative Methods 1582 las operaciones, por lo que se hace necesario considerar clases. También se pueden considerar disponibilidad temporal de las máquinas. Este problema admite tanto la versión fija o variable tareas. Incluso, también ha sido considerado en la bibliografía el objetivo operacional. En este caso, los pesos de las tareas equivalen a prioridades de proceso o importancia de la tarea. Algunas de estas tareas, las de menor prioridad, pueden esperar para ser realizadas en otro aterrizaje del avión, por lo que se permite su no realización. Gestión de Aeropuertos. Asignación de puertas a vuelos en aeropuertos con el objeto de reducir el traslado de pasajeros hasta la terminal: Kroon(1991). El modelo consiste en asignar a aviones de diferentes tipos una puerta de embarque durante un intervalo de tiempo fijo. Dado que cada tipo de avión presenta unas características técnicas especiales, aparecen restricciones de compatibilidad entre las puertas de embarque y los aviones. Si no se consigue asignar una puerta a un avión, los pasajeros deben ser transportados hasta el mismo en autobús, con la consiguiente disminución de la calidad del servicio. El objetivo en este caso, consiste en encontrar la mejor solución para la asignación de puertas de embarque, para así minimizar el número de aeronaves que queden fuera de esta asignación y de este modo evitar el uso de autobuses. Obviamente, se trata de un objetivo operacional. Las puertas de embarque corresponderían con las máquinas del sistema, mientras que los vuelos serían las tareas. Se consideran varias clases de máquinas, debido a que las puertas de embarque poseen capacidades diferentes y también porque los aviones pueden poseer características técnicas diferentes que impidan la conexión con determinadas puertas. Planificación de satélites de Observación terrestre: Grabel (1995), Wolfe y Sorensen (2000) Consideremos un satélite que describe una órbita alrededor de la tierra y cuya misión es realizar distintas operaciones, como pueden ser por ejemplo la captura de imágenes de la superficie terrestre, mediciones (atmosféricas o de La Tierra), operaciones de telecomunicaciones, etc. Dado que son numerosas las zonas que demandan alguna de las operaciones mencionadas por parte del satélite, se plantea el problema de seleccionar cuál debe ser la secuencia de tareas a realizar durante un horizonte temporal dado, de manera que se maximice el número de trabajos ejecutados por cada satélite (problema operacional), siendo las restricciones del problema las siguientes: x Un satélite podrá realizar tareas en la parte de la superficie terrestre expuesta al sol. x Debido al movimiento del satélite, la ejecución de cada tarea requerida sólo podrá comenzar en una ventana de posibles instantes de tiempo determinados, dentro del horizonte temporal considerado. x El satélite sólo puede procesar una tarea en cada instante, teniendo además que dejar un tiempo de transición, supuesto constante, entre dos tareas pertenecientes a la misma secuencia. Ya que los recursos no se encuentran disponibles durante todo el horizonte de planificación es un problema del tipo “Shift Class Scheduling”. Quantitative Methods 1583 Asignación de aulas de clase: Carter (1989). El problema de la asignación de aulas de clase es un problema del tipo FSP, puesto que los horarios de clase son fijos. El número de aulas de clases o salas disponibles en cualquier edificio es limitado y las clases o sesiones se encuentran planificadas previamente. Se necesita una asignación de aulas que tenga en cuenta las siguientes restricciones: x La capacidad del aula tiene que ser suficiente para acoger al número de alumnos matriculados o un porcentaje de ello. x Algunas clases pueden necesitar aulas con recursos audiovisuales. Estaríamos por tanto en el caso de varias clases de máquinas y un objetivo operacional. Sin embargo, es necesario atender todas las clases. Es un problema un tanto especial puesto que estaríamos más ante un problema de viabilidad, es decir, el problema de determinar si es posible acoger todos las clases con las aulas disponibles. En caso de que no puedan atenderse todas, seria necesario, ocupar otro edificio o bien replantear el programa de clases. Otras aplicaciones. Otras aplicaciones en las puede verse reflejados esta clase de sistemas en cierta forma son el control del tráfico aéreo, la asignación de habitaciones en hoteles o la distribución de productos perecederos bajo pedido. Referencias Arkin, E.M., Silverberg, E.L. (1987). “Scheduling jobs with fixed starting and finishing times”. Discrete Applied Mathematics, 18:1-8. Bertolissi, E. (2000). “Heuristic algorithm for scheduling in the no-wait flow-shop”. Journal of Materials Processing Technology, 107:459-465. Bekki O. and Azizoglu M. (2007). “Operational fixed interval scheduling problem on uniform parallel machines”. International Journal of Production Economics, In Press, Corrected Proof, Available online 10 July 2007 Brucker, P. and Nordmann, L. (1994). ”The k-Track Assignment Problem”. Computing, 52:97-122. Carter, M.W. (1989). “A lagrangean relaxation approach to the classroom assignment problem”, INFOR, 27:230-246. Dantzig G.B. and Fulkerson, D.R. (1954). “Minimizing the number of tankers to meet a fixed schedule”. Naval Res. Logist. Quart, 1:217-222. Dilworth R.P. (1950). “A descomposition theorem for partially ordered sets”. Annals Mathematics, 51:161-166. Dondeti, V., and Emmons, H. (1992). “Interval scheduling with processors of two types”. Operations Research, 40:76-85. Dondeti, V.R., and Emmons, H. (1993). “Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times”. European Journal of Operational Research, 70:316-326.