Programación de Trabajos Archivos - Gestión de Operaciones

Regla de la Razón Crítica

La Regla de la Razón Crítica (conocido en inglés por CR o Critical Ratio) es una heurística que permite la secuenciación de trabajos en una máquina. El criterio que establece la Regla de la Razón Crítica es que los trabajos se deban procesar en orden creciente de acuerdo al cuociente ente el tiempo que falta a la entrega y el tiempo de proceso (recomendamos al lector revisar el artículo Reglas de Prioridad para la Programación de n Trabajos en una Máquina donde se detalla a través de un ejercicio resuelto la aplicación de otras heurísticas típicas de la programación de operaciones).

En este contexto la fórmula para el cálculo del ratio crítico es:

Ejemplo Regla de la Razón Crítica (Ratio Crítico)

Hoy es el día 22 en un centro de trabajos y 4 trabajos están esperando ser atendidos en una máquina. La máquina puede procesar sólo un trabajo a la vez. Determine el ratio crítico para cada trabajo y establezca un ranking de prioridad para su procesamiento.

Por ejemplo, el trabajo A tiene como fecha de entrega el día 28 y requiere 8 días de proceso en la máquina.

Utilizando la Regla de la Razón Crítica los trabajos deben ser asignados en la siguiente secuencia: D, A, C, B. Se puede observar que sólo el trabajo B tiene holgura (esto debido a que su CR es mayor a 1). Por otra parte los trabajos A y D tienen ratios críticos menores a 1, lo cual significa que dichos trabajos no serán terminados a tiempo a menos que sean apurados. Finalmente el trabajo C tiene un ratio crítico igual a 1 que implica que podría ser terminado a tiempo en la medida que sea el primer trabajo en ser considerado en la secuencia (situación que no es la que ocurre en este caso).

Cabe recordar que los resultados propuestos al utilizar distintas reglas de prioridad deben ser analizados en virtud de su desempeño y en lo general no existe una regla que garantice el mejor desempeño en todos los aspectos.

Método de Johnson (Ejercicio Resuelto)

El Método de Johnson permite determinar una secuencia u orden para realizar trabajos en un taller que considera 2 máquinas, donde todos los trabajos siguen un orden común (por ejemplo, primero se ejecutan labores en una máquina 1 y luego en una máquina 2), asumiendo que todos los trabajos se encuentran disponibles para su programación al inicio del horizonte de evaluación y que los tiempos requeridos para pasar por cada máquina son conocidos (es decir, se asume que no existe incertidumbre). De esta forma se busca determinar el tiempo mínimo para completar los trabajos en el taller lo cual se conoce como makespan. En este contexto a continuación se presenta un ejemplo resuelto del Método o Algoritmo de Johnson.

Ejercicio Resuelto del Método de Johnson

Una imprenta se dedica a la copia y encuadernación de documentos. Esta mañana recibió los trabajos que se muestran a continuación, todos los cuales requieren ambas operaciones en ese orden:

La imprenta comienza a trabajar puntualmente a las 09:00 y no se detiene hasta que termina de procesar todos los trabajos. La hora de entrega para todos los trabajos corresponde a las 13:00. Determine una secuencia de manera que el tiempo que tardan en ser procesados los trabajos sea el menor posible, esto es minimizando el makespan. Construya una Carta Gantt para complementar su respuesta.

Este problema trata de máquinas en paralelo sin interrupción con trabajos cuyo tiempo de proceso es determinista y la llegada al comienzo (estática), de modo que se puede aplicar el Algoritmo de Johnson.

El tiempo más breve corresponde al trabajo A en encuadernación, por tanto se asigna en primer lugar y se ejecuta al final de la secuencia. Luego el tiempo más breve es para el trabajo B en encuadernación, siendo este trabajo asignado en segundo lugar y ejecutado penúltimo. De los trabajos remanentes el tiempo más breve es 40[min] existiendo un empate en encuadernación (trabajo C) y copia (trabajo E). En caso de empate el Método de Johnson establece que se prioriza la máquina 1 (en este caso copia) y por tanto E se asigna en tercer lugar y se ejecuta primero. A continuación naturalmente se asigna el trabajo C en cuarto lugar y se ejecuta antepenúltimo. El quinto trabajo en asignar será el D el cual se realiza inmediatamente antes del trabajo C (al tener su menor tiempo en encuadernación). Finalmente se asignan los trabajos F y G (en ese orden) ejecutándolos en segundo y tercer lugar, respectivamente. De esta forma la secuencia es:

E-G-F-D-C-B-A

El makespan para este problema de Programación de Trabajos es de 440 minutos, terminando de atender el último trabajo a las 16:20.

En relación a los resultados obtenidos anteriormente determine: ¿A qué hora se termina de atender el último trabajo?, ¿Cuántos trabajos atrasados tiene la imprenta?, ¿Cuál es el tiempo de flujo promedio?, ¿Cuál es el atraso promedio?, ¿Cuál es el atraso máximo?.

Para responder a esta pregunta confeccionamos una tabla resumen la cual se basa en los resultados obtenidos a través de la Carta Gantt y los horarios de entrega de los trabajos.

Total Atrasos: 5 (Trabajos A, B, C, D y F)
El último trabajo se termina de atender a las 16:20 (Trabajo A)
Tiempo de Flujo Promedio: 06:01
Atraso Promedio: 1:48
Atraso Máximo: 3:20

Cabe recordar que el Tiempo de Flujo (TF) corresponde al tiempo total que cada trabajo se encuentra en el taller, es decir, esto es la suma del tiempo de espera más el tiempo de atención o procesamiento en las distintas máquinas. Por ejemplo si bien el trabajo A requiere en total un tiempo de 30[min] éste comienza a ser atendido recién a las 15:20 en copia, terminando a las 16:20 en encuadernación (total 60[min] o 1[hora]). Adicionalmente el trabajo A debe esperar 7 horas con 5 minutos (es decir, de las 08:15 a las 15:20) para comenzar su atención en copia. Luego el Tiempo de Flujo es 1:00+7:05=8:05 (8 horas y 5 minutos).

Algoritmo del Plano de Corte en el Problema del Vendedor Viajero

Según lo descrito en el artículo Solución del Problema del Vendedor Viajero, una de las situaciones potenciales a la que nos podemos enfrentar es que la solución de asignación obtenida represente un subcircuito, lo cual naturalmente no da respuesta a la problemática que el modelo de agente viajero desea abordar. En este contexto existen diversas estrategias algorítmicas que permiten enfrentar esta situación entre las cuales destaca el Algoritmo de Plano de Corte.

La idea del Algoritmo del Plano de Corte es agregar un conjunto de restricciones que, cuando se incorporan al Problema de Asignación garanticen evitar la formación de un subcircuito. Consideremos un problema con n ciudades, asociar una variable continua $u_{j}\geq 0$ con las ciudades 2,3,…,n. A continuación definir un conjunto de restricciones adicionales de la siguiente forma:

Estas restricciones al añadirse al Modelo de Asignación, eliminarán todas las soluciones de subcircuito de forma automática, pero no eliminarán alguna solución de circuito.

A modo de ejemplo consideremos nuevamente el problema de secuenciamiento de la producción donde nos interesa determinar el orden en el cual se deben producir 4 colores de pintura.

A continuación se define un modelo de optimización haciendo uso del lenguaje de programación matemática AMPL. Para ello se puede utilizar un editor de texto como Bloc de Notas o WordPad. La siguiente imagen muestra la sintaxis utilizada en la definición del modelo del ejemplo propuesto donde se incorpora las restricciones que evitan los subcircuitos. Notar que es importante guardar el archivo con el formato adecuado (.mod) para lo cual simplemente en el caso de utilizar Bloc de Notas seleccionamos «Archivo», seguido de «Guardar como …» y luego en «Nombre» se ingresa un nombre arbitrario seguido de .mod (por ejemplo, modelo.mod).

El siguiente paso es generar un nuevo archivo con los datos o parámetros del problema. Básicamente aquellos que resumen el tiempo (en minutos) necesarios para la limpieza al realizar un cambio de colores, según se describe al inicio de este artículo. Notar que para evitar aquellas asignaciones infactibles (como que a un color le precede el mismo en la secuencia) se asignan «constantes grandes» a los elementos en la diagonal. El archivo se procesa y guarda de forma similar al caso del modelo pero con la extensión .dat (por ejemplo, matriz.dat).

Finalmente será necesario construir un tercer archivo con extensión .run que provee de instrucciones adicionales para efectos de la resolución computacional y que facilita la interpretación de los resultados (por ejemplo, solucion.run).

Una vez definido el modelo, datos y archivo run, podemos utilizar un solver de Programación Entera Mixta de los disponibles en el Servidor NEOS. En particular recomendamos utilizar el solver XpressMP donde se deberá adjuntar los archivos con extensión .mod, .dat y .run (respectivamente) según se muestra a continuación (recordar que el nombre asignado al archivo es arbitrario, no así su extensión).

Luego seleccionamos «Submit to NEOS» y los resultados se mostraran en el navegador de Internet, además de recibir un informe de respuestas en la dirección de correo electrónico que ingresamos. La siguiente imagen muestra un extracto de dichos resultados:

Notar que XpressMP encuentra como recorrido óptimo la secuencia 1-2-4-3-1, es decir, corresponde a producir en el siguiente orden: Blanco, Amarillo, Rojo, Negro, con un tiempo total de setup de 98 minutos.

Solución del Problema del Vendedor Viajero

El Problema del Vendedor Viajero (conocido también como Travelling Salesman Problem o simplemente TSP) consiste en encontrar el circuito óptimo (en términos del viaje más corto) que deberá seguir un vendedor en un caso con n ciudades, en el que cada ciudad se visita exactamente una vez. Básicamente es una adaptación del Problema de Asignación que considera restricciones adicionales que garantiza la exclusión de subcircuitos en la solución óptima.

Específicamente en el caso de n ciudades se define las variables de decisión de la siguiente forma:

Sea $d_{ij}$ la distancia de la ciudad i a la ciudad j, donde $d_{ij}=\infty$ , el modelo del agente o vendedor viajero corresponde a:

El conjunto de restricciones (1) y (2) definen un modelo de asignación tradicional. Lamentablemente en general, el problema de asignación producirá soluciones de subcircuito más que circuitos completos que abarque las n ciudades.

Para ilustrar los conceptos de circuito y subcircuito en el contexto del Problema del Vendedor Viajero, consideremos un agente de venta que vive en la ciudad 1. Miami (Florida) en Estados Unidos y debe visitar a importantes clientes en las siguientes ciudades: 2. Chicago (Illinois), 3. Houston (Texas), 4. Las Vegas (Nevada) y 5. San Francisco (California). Para mayor claridad se han destacado los estados mencionados anteriormente con un color distintivo.

Un circuito factible sería viajar en el siguiente orden: Miami (FL), Chicago (IL), Houston (TX), Las Vegas (NV), San Francisco (CA), Miami (FL). Es decir, $x_{12}=x_{23}=x_{34}=x_{45}=x_{51}=1$ .

Por otra parte un subcircuito correspondería, por ejemplo, a Miami (FL), San Francisco (CA), Las Vegas (NV), Miami (FL), junto a Houston (TX), Chicago (IL), Houston (TX). Es decir, $x_{15}=x_{54}=x_{41}=x_{32}=x_{23}=1$ , lo que naturalmente no es una solución factible para el problema que se busca resolver.

El modelo del vendedor viajero se caracteriza por su versatilidad para representar otros casos prácticos en optimización. Uno de ellos es el Problema de Secuenciamiento de la Producción como el que se presenta a continuación:

El programa de producción diaria de una empresa de pinturas incluye lotes de color Blanco (B), Amarillo (A), Negro (N) y Rojo (R). Como la empresa utiliza las mismas instalaciones en las cuatro clases de pintura, es necesario hacer una limpieza entre los lotes. La siguiente tabla resume el tiempo de limpieza, en minutos, donde al color de la fila sigue el color de la columna. Por ejemplo, cuando después de la pintura Blanca sigue la Amarilla, el tiempo de limpieza en 10 minutos. Como un color no puede seguir a sí mismo, a los elementos correspondientes se les asigna un tiempo de setup infinito. Se desea determinar la secuencia óptima para la producción diaria de los cuatro colores, que minimice el tiempo total de limpieza necesario.

Se puede hacer una analogía con el problema del vendedor viajero, asumiendo que cada pintura es una «ciudad» y que las «distancias» representan el tiempo de limpieza necesario para cambiar de un lote de pintura al siguiente. En consecuencia, el problema se reduce a determinar el circuito más corto que se inicie en un lote de pintura y pase exactamente una vez por cada uno de los tres lotes restantes, para regresar al punto de partida.

En este contexto dada la cantidad de pinturas, la secuencia óptima se puede encontrar por enumeración exhaustiva de los 6 circuitos posibles $(n-1)!$ , es decir, $(4-1)!=3!=6$ . En el ejemplo dicha secuencia óptima corresponde a Blanco, Amarillo, Rojo, Negro, Blanco, con un tiempo total de setup de 98 minutos. Naturalmente esta estrategia no es eficiente y queda limitada a problemas muy pequeños.

Alternativamente se puede utilizar implementar en Solver el modelo de asignación presentado anteriormente, haciendo uso de los parámetros descritos en el ejemplo del secuenciamiento de la producción de pinturas. A continuación un extracto de los resultados donde se observa que no se alcanza una solución de circuito.

En la actualidad existen programas computacionales que permiten enfrentar estas dificultades que establece el problema del vendedor viajero. Uno de ellos es el software TSPSG (TSP Solver and Generator) que se caracteriza por una interfaz intuitiva y que a continuación se detalla la implementación de nuestro problema (recordar que la Ciudad 1 correspondería al color Blanco, y así sucesivamente).

Una vez ingresado los datos al seleccionar «Solve» el programa se ejecuta entregando los resultados alcanzados que por cierto coincide con aquellos que identificamos por enumeración.

En términos algorítmicos los métodos disponibles para resolver el problema del agente o vendedor viajero tienen su base en las ideas de los algoritmos generales de ramificación y acotamiento (Branch and Bound) o de Plano de Corte, en los cuales abordaremos en próximos artículos.

Cómo enfrentar una Solución Infactible obtenida con el Método Húngaro

En algunos casos los ceros que se producen en los Pasos 1 y 2 del Método Húngaro no producen una solución factible en forma directa, es decir, la asignación alcanzada es infactible. En este caso se necesitan más pasos para alcanzar la asignación óptima (factible). Para ilustrar esta situación consideremos el siguiente ejemplo que consiste en la asignación a costo mínimo de 4 ingenieros a 4 tareas, donde cada ingeniero debe desempeñar exactamente una tarea:

Al aplicar los Pasos 1 y 2 del Método Húngaro se obtiene la siguiente matriz reducida:

Notar que los elementos cero (marcados con color azul) no permiten asignar una tarea por ingeniero. Por ejemplo, si se asigna el ingeniero 1 a la tarea 1, se eliminará la columna 1, y el ingeniero 3 no tendrá elemento cero en las tres columnas restantes. Para solucionar este obstáculo se agrega el siguiente paso al procedimiento:

Paso 2a: Si no se puede asegurar una asignación factible (con todos los elementos cero) con los Pasos 1 y 2.

Trazar la cantidad mínima de líneas horizontales y verticales en la última matriz reducida que cubran todos los elementos cero.
Seleccionar el elemento mínimo no cubierto, restarlo de todo elemento no cubierto y a continuación sumarlo a todo elemento en la intersección de dos líneas.
Si no se puede encontrar una asignación factible entre los elementos cero que resulten, repetir el Paso 2a. En caso contrario, seguir en el Paso 3 para determinar la asignación óptima.

Al aplicar el Paso 2a a la matriz reducida presentada anteriormente, se obtienen las celdas color amarillo según se aprecia a continuación:

La celda de valor mínimo sin fondo amarillo es igual a $1 (destacada con color rojo). Este elemento se resta de todas las celdas sin fondo amarillo y se suma a a las celdas de las intersecciones (destacadas con color azul).

La solución óptima (por cierto factible) se ha marcado con fondo azul: el ingeniero 1 realiza la tarea 1, el ingeniero 2 la tarea 3, el ingeniero 3 la tarea 2 y el ingeniero 4 la tarea 4 . El costo total (valor óptimo) de esta asignación es $1+$10+$5+$5=$21.