secuencia Archivos - Gestión de Operaciones

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 secuenciar n Trabajos en una Máquina para minimizar Setup

El orden o secuencia en el cual se programan n trabajos en una máquina es significativo a la hora de estimar los tiempos de setup para pasar de un determinado trabajo a otro o incluso comenzar con cualquiera de ellos al inicio de la planificación.

En este contexto se reconoce formalmente como tiempo de setup la cantidad de tiempo necesario para preparar una máquina para realizar una operación diferente y cumplir con las especificaciones del cliente (estos tiempos de setup pueden representar por ejemplo calibración de la máquina, cambio de formatos, limpieza, mantención preventiva, etc).

En el siguiente artículo formularemos y resolveremos un modelo de Programación Entera que permita encontrar una secuenciación óptima de n trabajos en una máquina, lo cual será contrastado con la solución que se puede obtener por simple enumeración de secuencias, naturalmente para un número de trabajos «pequeño» (para fines académicos).

En general si se deben programar n trabajos en una máquina, la cantidad de secuencias posibles son n!.

Por ejemplo si tenemos 3 trabajos (n=3) que debemos asignar a una máquina la cantidad de secuencias posibles son 6 (3!=3*2*1). Lo anterior implica que aún para centros de trabajos pequeños es útil contar con un procedimiento que permita identificar aquella secuencia que minimice el makespan sin tener la necesidad de hacer una evaluación exhaustiva de cada una de ellas.

Consideremos un conjunto de trabajos que necesitan ser asignados a una cierta máquina, todos los cuales están disponibles al inicio de la programación y se conoce los tiempos de proceso y fechas de entrega como muestra la siguiente tabla:

Sin embargo, el tiempo de setup, correspondiente al tiempo requerido para preparar la máquina antes de cada trabajo, depende del trabajo que le precede. A continuación se indica los tiempos de setup aij cuando al trabajo j le precede el trabajo i:

Adicionalmente hay un tiempo de setup a0j asociado al primer trabajo a programar de acuerdo a los siguientes valores:

El objetivo entonces es programar las actividades de modo de minimizar el tiempo de utilización de la máquina (makespan) como resultado de la asignación propuesta. Notar que según lo descrito anteriormente el problema admite 6 secuencias posibles las cuales se enumeran a continuación para poder obtener el makespan de la programación.

Secuencia 1-2-3: 1+9+1+13+3+10=37[t]
Secuencia 1-3-2: 1+9+0+10+1+13=34[t]
Secuencia 2-1-3: 3+13+2+9+0+10=37[t]
Secuencia 2-3-1: 3+13+3+10+3+9=41[t]
Secuencia 3-1-2: 4+10+3+9+1+13=40[t]
Secuencia 3-2-1: 4+10+1+13+2+9=39[t]

Naturalmente la secuencia óptima es 1-3-2 con un makespan de 34[t]. Como el trabajo 1 es el que inicia la secuencia tiene un setup inicial de a01=1 y requiere de 9[t] para ser completado. A continuación sigue el trabajo 3 que dura 10[t] y como es el trabajo 1 el que le precede no se requiere tiempo de setup (a13=0). Finalmente se realiza el trabajo 2 con duración de 13[t], necesitándose 1[t] para pasar del trabajo 3 al trabajo 2 (a32=1).

Para abordar el problema anterior a través de un modelo de optimización definiremos el siguiente problema de Programación Entera que claramente permite extender su aplicación a problemas de mayor tamaño (número de trabajos):

Variables de Decisión:

Para i=1,2,3 y j=0,1,2,3 con i≠j. Por ejemplo si X10=1 esto indica que el trabajo 1 es el que se realiza inmediatamente después del trabajo 0, es decir, el trabajo 1 es el que inicia la secuencia.

Función Objetivo:

En la implementación computacional con Solver de Excel la función objetivo se representa a través de la siguiente fórmula:

Para mayor claridad a continuación un extracto de la pantalla del modelo computacional:

Se busca minimizar el makespan de la secuencia. Notar que se suman las constantes asociadas al tiempo de proceso de cada trabajo (las cuales son independientes de la secuencia y justifican que inicialmente el valor de la celda que representa la función objetivo sea igual a 32[t]) y que eventualmente se pueden omitir de la función objetivo (en dicho caso el valor óptimo representaría la sumatoria de los tiempos de setup de la secuencia y no el makespan de la programación).

Restricciones:

Se deben realizar los 3 trabajos:

A lo más una tarea sigue a la j-ésima al menos que sea la última de la secuencia:

Alternativas infactibles: (celdas color rojo en la planilla de cálculo)

Debe existir un trabajo inicial en la secuencia:

Luego de resolver con Solver el problema anterior se alcanza la siguiente solución óptima y valor óptimo:

Donde se corrobora que la secuencia óptima es 1-3-2 con un makespan de 34[t]. A continuación puedes descargar el archivo Excel con la resolución del problema anterior en el siguiente enlace: Minimizar Tiempos de Setup.