Programación de Operaciones

Alcides Santander Mercado Ph.D.

asantand@[Link]
Introducción

Definiciones
 Scheduling
“Organización, elección y asignación de tiempos al “La programación de operaciones es un proceso de
uso de recursos para ejecutar todas las actividades toma de decisiones... se ocupa de la asignación de
requeridas, producir las salidas en los tiempos recursos a tareas durante períodos de tiempo
deseados, teniendo en cuenta las restricciones de determinados y su objetivo es optimizar uno o más
tiempo y las relaciones entre recursos y objetivos.”
actividades”
M. Pinedo
T. E. MORTON Y D. W. PENTICO
asantand@[Link]
Universidad del Norte
Scheduling
Caracterización del problema

• Función Objetivo • Buffers

• Set de Trabajos • Tiempos de Entrega

• Set de Recursos • Penalizaciones
• Secuencias de Producción • Tiempos de Servicio

• Alistamientos • Variabilidad

• Modos de Fallas • No Conformidades

• Mantenimientos • Reproceso

• Cancelación de trabajos • Descansos de Personal

asantand@[Link]
Universidad del Norte
Scheduling
Notación del problema

Métricas de desempeño
Control del proceso
Tiempos
Caracterización de la interacción del trabajo ▪ Lateness ( Lj )
Elementos con el Sistema de producción y de demanda
Trabajos y recursos ▪ Tardiness ( Tj )
pij: Tiempo de Procesamiento del
n : Número finito de trabajos a trabajo j en la máquina i ▪ Earliness ( Ej )
programar
m: Número finito de recursos a rj: Tiempo liberación del trabajo j. ▪ Makespan ( Cmax )
programar dj: Tiempo de Entrega del trabajo j. ▪ Trabajo Tardío ( Uj )
j: Subíndice que denota a los
trabajos a programar wj: Importancia relativa del trabajo j. ▪ Lmax= max ( Lj )
i: Subíndice que denota a las cj: Tiempo de finalización del trabajo j.
recursos a programar ▪ Tmax= max ( Tj )
▪ Emax= max ( Ej )

asantand@[Link]
Universidad del Norte
Métricas de desempeño
Caracterización del problema

Lateness ( Lj ): Se entiende como una medida de sincronización del sistema con respecto a la fecha de
entrega.
Lj = cj - dj

Tardiness ( Tj ): Si Lj es positivo implica que el trabajo se entregó de manera tardía, entonces:

Tj = max ( cj – dj , 0 ) = max ( Lj , 0 )

Earliness ( Ej ): Si Lj es negativo implica que el trabajo se entregó de manera adelantada, entonces:

Ej = | min ( cj – dj , 0 ) |= | min ( Lj , 0 ) |

asantand@[Link]
Universidad del Norte
Métricas de desempeño
Caracterización del problema

Estos indicadores se pueden analizar en términos de sus valores extremos, representando métricas de nivel
de servicio y sincronización del programa.

Lmax= max ( Lj ) Tmax= max ( Tj ) Emax= max ( Ej )

Makespan ( Cmax ): Se define como el tiempo de finalización del último trabajo programa do en la
secuencia.

Cmax = Max ( cj )

Trabajo Tardío (Uj ): Se define como un indicador binario que toma el valor de 1 si el trabajo se entrego
tarde, 0 en otros casos.
1 𝑇𝑗 > 0
𝑢𝑗 =
0 𝑇𝑗 = 0

asantand@[Link]
Universidad del Norte
 Tipología de los Problemas de Programación de Operaciones
En términos de la solución del problema, se pueden tener las siguientes alternativas:
Sequence (Secuencia): Se limita la permutación de los n trabajos disponibles para programar.
Schedule (Programa de Trabajo): Incluye una secuencia con su respectiva interacción con recursos bajo
restricciones encontradas.
Scheduling Policy (Política de Programación): Generalmente usada en ambientes estocásticos, y se refiere a
la acción que se tiene que implementar dado que el sistema se encuentra en un estado determinado.
asantand@[Link]
Universidad del Norte
 Diagramas de Gantt
Se define como la representación gráfica de un programa de ejecución de un proyecto, en nuestro caso un
programa de producción. En el eje Y se muestran las actividades desarrolladas por cada recurso a través del
tiempo (eje X). Permite observar gráficamente:
▪ Tiempos Ociosos
▪ Tiempos Activos
▪ Precedencia de actividades
▪ Tiempos de inicio y finalización de trabajos asantand@[Link]
Universidad del Norte
Ambientes de Programación

Single Machine
Scheduling
 Secuencia óptima de trabajos Recurso

La secuencia óptima depende de la función objetivo seleccionada

▪ Tardanza máxima ▪ Utilización de recursos
▪ Sumatoria de trabajos tardíos ▪ Tiempo de flujo
▪ Sumatoria de tardanzas ▪ Sumatoria de adelantos
▪ Makespan ▪ Adelanto máximo

Single Machine Scheduling

En el modelo de programación de una sola máquina, todos los trabajos compiten por la capacidad de una
única máquina, sin tener necesariamente los mismos tiempos de procesamiento.
Solo se requiere de una etapa de procesamiento.
asantand@[Link]
Universidad del Norte
Single Machine Scheduling
Complejidad del problema

El problema de programación de operaciones

de una máquina es el más sencillo dentro de
programación de operaciones.
El objetivo es lograr un ordenamiento de una
lista de trabajos a desarrollar de acuerdo a un
criterio o regla que beneficie un(os) objetivo(s)
específico.
No se abordarán metodologías enumerativas
dado la complejidad del problema...

n!
asantand@[Link]
Universidad del Norte
Single Machine Scheduling
Objetivo: Tiempo mínimo de flujo

El problema del tiempo de flujo mínimo en sistemas de una sola máquina implica que la secuencia seleccionada
asegure que los trabajos pasen el menor tiempo posible en el sistema.

Esta dinámica genera menor inventario en proceso, menores filas y menor consumo de espacio físico.

On-line Scheduling Systems

asantand@[Link]
Universidad del Norte
Single Machine Scheduling
Objetivo: Tiempo mínimo de flujo

Para el caso del siguiente listado de órdenes, ¿Cómo asegurar el cumplimiento de este objetivo?

En el caso de off-line scheduling systems, el analista tiene conocimiento preliminar de una estimación de los
tiempos de procesamiento de los trabajos, y los puede ordenar a su conveniencia.

Shortest Processing Time (SPT) – Tiempo de Procesamiento más corto

Esta regla permite la minimización del tiempo de flujo. Este objetivo es equivalente a la minimización del tiempo de
espera y de trabajo en proceso (WIP).

Trabajo 1 2 3 4 5
Tiempo Estimado 4 2 3 2 4

asantand@[Link]
Universidad del Norte
Single Machine Scheduling
Objetivo: Tiempo de flujo ponderado

De acuerdo con la Teoría de Restricciones, no todos los productos en el sistema entregan el mismo rendimiento
económico en el tiempo.

Por lo tanto un trabajo que contribuya mayormente al throughput debe ser priorizado por el sistema.

Weigthed Shortest Processing Time (WSPT)

Esta regla permite considerar la importancia relativa de un trabajo con respecto a los demás.

Trabajo 1 2 3 4 5
Tiempo Estimado 4 2 3 2 4
Margen de Contribución $10 $15 $12 $7 $9

asantand@[Link]
Universidad del Norte
Single Machine Scheduling
Objetivo: Tardanza Máxima

Si no es posible entregar todos los trabajos a tiempo, la regla EDD (Earliest Due Date) permite obtener la
minimización de la tardanza máxima.

Este tipo de problema se fundamenta en la programación de un trabajo lo antes posible de acuerdo con su tiempo
de entrega.

Trabajo 1 2 3 4 5
Tiempo Estimado 4 2 3 2 4
Due Date - dj 16 10 7 7 5

asantand@[Link]
Universidad del Norte
Single Machine Scheduling
Objetivo: Número de Trabajos Tardíos

En caso que se tengan trabajos tardíos, la regla EDD tiende a entregar tardanzas pequeñas en muchos trabajos. Esto
genera que el nivel de servicio se vea afectado al incumplirle a más clientes.

Este tipo de problema también se puede tratar desde la óptica del número de trabajos tardíos. Esta función
objetivo se aborda utilizando el algoritmo de Hudgson que se describe a continuación:

Algoritmo de Hudgson

Paso 1. Identificar el primer trabajo tardío de la secuencia.

Paso 2. Identificar el trabajo más largo, en posiciones anteriores a la del primer trabajo tardío.

Paso 3. Eliminar de la secuencia el trabajo identificado en paso 2.

Paso 4. Los trabajos eliminados se ubican al final de la secuencia.

asantand@[Link]
Universidad del Norte
Ambientes de Programación

Parallel Machine
Scheduling
 Etapa 2: Modelo de asignación

Etapa 1: Secuencia óptima de trabajos

Parallel Machine Scheduling

En el modelo de programación de máquinas en paralelo, todos los trabajos compiten por la capacidad de una de
las m-máquinas disponibles. Todas las máquinas podrían procesar el trabajo, pero no necesariamente tienen los
mismos tiempos de procesamiento. Solo se requiere de una etapa de procesamiento.
asantand@[Link]
Universidad del Norte
 Parallel Machine Scheduling
El problema de scheduling utilizando m-máquinas en paralelo se convierte realmente en un problema de
asignación (como por ejemplo el problema del bin-packing, balance de línea, entre otros con la estructura
del Knapsack Problem.

Adicionalmente de las medidas de desempeño comunes, el tiempo de flujo y el Makespan tienen

consideraciones especiales de utilización de recursos.
asantand@[Link]
Universidad del Norte
Parallel Machine Scheduling
Consideraciones sobre funciones objetivo.

Para minimizar el tiempo de flujo los trabajos se ordenan de acuerdo a una secuencia SPT, realizando la asignación
de manera cíclica en los m-recursos.

Trabajo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Tiempo Estimado 1 3 4 6 9 10 10 11 12 13 13 14 16 18 19

Sin embargo, se observa baja eficiencia en el uso de los recursos disponibles.

asantand@[Link]
Universidad del Norte
Parallel Machine Scheduling
Consideraciones sobre funciones objetivo.

Como una aproximación para reducir el Makespan, los trabajos se ordenan de acuerdo a una secuencia LPT, realizando la
asignación de manera cíclica en los m-recursos.

Trabajo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Tiempo Estimado 1 3 4 6 9 10 10 11 12 13 13 14 16 18 19

En este caso se balancea la utilización de recursos, pero se afecta el tiempo de flujo.

¿Cómo abordar el problema de manera integral? ¿Optimización multiobjetivo? ¿Optimización lexicográfica?
asantand@[Link]
Universidad del Norte
Parallel Machine Scheduling
Las reglas de despacho no aseguran optimalidad en la solución en ambientes de máquinas en paralelo

Evaluación de Optimalidad
LPT Lower Bound para el Makespan

SPT
෍ 𝑝𝑗 = 159
∀𝑗

σ∀𝑗 𝑝𝑗 159
𝐿𝐵 = = = 53
𝑚 3

¿Es posible encontrar una solución

con Cmax igual a 53?

asantand@[Link]
Universidad del Norte
 Parallel Machine Scheduling
Consideraciones sobre funciones objetivo.

Debido a que el problema se convierte en m-ambientes de una sola máquina, se podría abordar el objetivo de la
minimización tardanza máxima, la sumatoria de las tardanzas, el número de trabajos tardíos, la sumatoria del
tiempo de flujo entre otras funciones aplicables al problema de una sola máquina (basada en la solución óptima
con respecto al makespan en la etapa de asignación).

Trabajo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Tiempo Estimado 1 3 4 6 9 10 10 11 12 13 13 14 16 18 19
Tiempo de Entrega 21 12 9 35 35 53 51 40 37 53 50 53 37 53 39

asantand@[Link]
Universidad del Norte
Parallel Machine Scheduling
Consideraciones sobre funciones objetivo.

asantand@[Link]
Universidad del Norte
Ambientes de Programación

Flow Shop
Scheduling
 m=2

m=3

m=4

m=5

m=6

m=7

Flow Shop Scheduling

En el modelo de programación de líneas de producción, todos los trabajos tienen la misma secuencia de
visita a un grupo de m-máquinas en serie, sin tener necesariamente los mismos tiempos de procesamiento.

asantand@[Link]
Universidad del Norte
 Cálculo del Lower Bound para el Makespan - Flow Shop Scheduling
𝑘−1 𝑛 𝑚

𝐿𝐵𝑘 = 𝑚𝑖𝑛 ෍ 𝑝𝑖𝑗 + ෍ 𝑝𝑘𝑗 + 𝑚𝑖𝑛 ෍ 𝑝𝑖𝑗

𝑖=1 𝑗=1 𝑖=𝑘+1

De acuerdo con la complejidad del sistema el óptimo puede o no alcanzarse. Este es un cálculo teórico por lo cual no
hay certeza en que realmente una exista una secuencia que lo logre.
asantand@[Link]
Universidad del Norte
Flow Shop Scheduling
Cálculo del Lower Bound para el Makespan

De acuerdo con la complejidad del sistema el óptimo puede o no alcanzarse. Este es un cálculo teórico por lo cual no
hay certeza en que realmente una exista una secuencia que lo logre.

LB1 = 0 + 13 + Min ( 8 , 7 , 8 , 5 )
LB1 = 0 + 13 + 5 = 18
Trabajo \ Recurso M1 M2 M3 M4
LB2 = Min( 2 , 5 , 2 , 4 ) + 10 + Min ( 4 , 4 , 6 , 4 )
Trabajo 1 2 4 2 2 LB2 = 2 + 10 + 4 = 16
Trabajo 2 5 3 3 1
Trabajo 3 2 2 5 1 LB3 = Min( 6 , 8 , 4 , 5 ) + 13 + Min ( 2 , 1 , 1 , 1 )
LB3 = 4 + 13 + 1 = 18
Trabajo 4 4 1 3 1
LB4 = Min( 8 , 11 , 9 , 8 ) + 5 + 0
LB4 = 8 + 5 + 0 = 13

asantand@[Link]
Universidad del Norte
Flow Shop Scheduling
Algoritmo de Johnson: Para Flow Shops con m = 2

Paso 0: Sea Y el conjunto de todos los trabajos no programados

Paso 1: Identificar el pij más corto e identifique el trabajo clave j* y máquina clave i* respectivamente.
Paso 2: Si i* es 1, el trabajo j* se envía a la posición más cercana posible en la secuencia.
Paso 3: Si i* es 2, el trabajo j* se envía a la posición más lejana posible en la secuencia.
Paso 4: Determinar el vector de posiciones en la secuencia.

Máquinas \ Trabajos T1 T2 T3 T4
Máquina 1 5 4 3 2
Máquina 2 2 5 2 6

asantand@[Link]
Universidad del Norte
Flow Shop Scheduling
Heurística CDS (Cambell, Dudek and Smith)

Se fundamente en la creación de escenarios mediante la reducción del sistema de m>2 a m=2, con el
objetivo de aplicar el algoritmo de Johnson.
𝑘

Sea 𝑝′1𝑗 = ෍ 𝑝𝑖𝑗 el tiempo de procesamiento en la pseudo-máquina 1

𝑖=1

Sea 𝑝′2𝑗 = ෍ 𝑝𝑖𝑗 el tiempo de procesamiento en la pseudo-máquina 2

𝑖=𝑙

k representa el índice de la última máquina incluida en el set de pseudo-máquina 1.

l representa el índice de la primera máquina incluida en el set de pseudo-máquina 2.

asantand@[Link]
Universidad del Norte
Flow Shop Scheduling
Heurística CDS (Cambell, Dudek and Smith)

La heurística sugiere que se calculen todas las combinaciones posibles para el problema y se
seleccione la de menor Cmax.

asantand@[Link]
Universidad del Norte
Flow Shop Scheduling
Heurística CDS (Cambell, Dudek and Smith)

La heurística sugiere que se calculen todas las combinaciones posibles para el problema y se
seleccione la de menor Cmax.

asantand@[Link]
Universidad del Norte
Flow Shop Scheduling
Heurística CDS (Cambell, Dudek and Smith)

La heurística sugiere que se calculen todas las combinaciones posibles para el problema y se
seleccione la de menor Cmax.

asantand@[Link]
Universidad del Norte
Flow Shop Scheduling
Heurística CDS (Cambell, Dudek and Smith)

La heurística sugiere que se calculen todas las combinaciones posibles para el problema y se
seleccione la de menor Cmax.

asantand@[Link]
Universidad del Norte
Flow Shop Scheduling
Algoritmo de Gupta
El algoritmo busca analizar potenciales cuellos de botella en la operación y programar con respecto al
recurso restrictivo.

1 𝑝1𝑗 < 𝑝𝑚𝑗

𝑒𝑗 =
−1 𝑝1𝑗 ≥ 𝑝𝑚𝑗

𝑒𝑗
𝑆𝑗 =
𝑚𝑖𝑛𝑘=1,𝑚−1 𝑝𝑘𝑗+ 𝑝𝑘+1 𝑗
asantand@[Link]
Universidad del Norte
Ambientes de Programación

Job Shop
Scheduling
Dentro se un sistema de producción con n = 3 y m = 4 se tienen las siguientes secuencias de visita a máquinas:

Trabajo 1 = {M4, M3, M1}

Trabajo 2 = {M1, M2, M3}
Trabajo 3 = {M3, M4, M1, M2} M2 Salida j = 3

Salida j = 1 Entrada j = 3
M1 M3
Entrada j = 2 Salida j = 2

Entrada j = 1 M4

Job Shop Scheduling

En el modelo de programación de talleres de producción intermitente, al menos uno de los trabajos no
tiene la misma secuencia de visita a un grupo de m-máquinas. Además, no necesariamente se tienen los
mismos tiempos de procesamiento.
asantand@[Link]
Universidad del Norte
Job Shop Scheduling
Generalmente se ataca el problema como un problema de redes

Determinar la ruta mínima para terminar todos los trabajos en el tiempo mínimo.

9 8 4
1,1 1,2 1,3 1,4
4

5 6 3 6
b 2,1 2,2 2,4 2,3 e
2
10 4 9
3,3 3,1 3,2 3,4
Notación del grafo j,i

Generalmente, el problema también se aborda por medio de metaheurísticas dada su complejidad .

Recuerden (n!)m secuencias posibles

asantand@[Link]
Universidad del Norte
Job Shop Scheduling
Estrategias de solución

Dentro de las estrategias de solución se encuentran la modelación matemática, reglas de despacho,

programación de cuello de botella, shifting bottleneck o metaheurísticas.

Minimizar Cmax
Sujeto a:

skj − sij  pij , (i, j ) → (k , j )  A

Cmax − sij  pij , (i, j )  N
sij − sil  pil  sil − sij  pij , (i, l )  (i, j ), i = 1,..., m
sij  0, (i, j )  N
asantand@[Link]
Universidad del Norte
Job Shop Scheduling
Implementación

▪ Importancia de tener un software para

programación de Job Shops.
▪ Complejidad elevada para desarrollar
soluciones de calidad de manera intuitiva.
▪ Reglas ofrecen criterios sobre como
programar cuando no se tienen software
especializado.

Recuerden (n!)m secuencias posibles

asantand@[Link]
Universidad del Norte
 Questions
Alcides R. Santander M. Ph.D.
email: Website:
asantand@[Link] [Link]