SCHEDULING
SCHEDULING
▪ La Programación de Operaciones es la
secuenciación de actividades siguiendo un
orden lógico en búsqueda de cumplir con
uno o varios objetivos.
▪ Las actividades pueden ser de cualquier tipo,
la única restricción que existe para las
actividades es que éstas se puedan
secuenciar.
OBJETIVOS
1. Cumplir con las fechas de entrega. Ayudan a tener un
alto nivel de
2. Minimizar el tiempo promedio de flujo servicio con el
en el sistema. cliente.
3. Minimizar el tiempo de inventario de
trabajo en proceso.
4. Alcanzar una alta utilización de los
recursos. Es equivalente a minimizar Se obtiene un
los tiempos muertos de los mismos. gran nivel de
5. Suministrar información exacta del eficiencia en la
planta.
estado de los trabajos.
6. Reducir los tiempos de preparación.
7. Minimizar costos de producción y de
personal.
ELEMENTOS A
CONSIDERAR
TRABAJOS
• Son las actividades a realizar.
• Se supone que cada trabajo tiene un tiempo de procesamiento
conocido.
• A menos que se establezca de otra manera, una vez que comienza a
realizarse un trabajo, debe procesarse continuamente hasta
terminarlo, es decir, no se permiten interrupciones.
• Puede tener una fecha de entrega estimada.
• Un trabajo puede tener un tiempo de alistamiento asociado.
• Un trabajo puede depender de otro. Se supone que los trabajos son
independientes a menos que se diga lo contrario.
ELEMENTOS A
CONSIDERAR
MÁQUINA
• Procesan trabajos.
• Los entornos de las máquinas se pueden dividir en:
– Una sola máquina
– Máquinas en paralelo
– Talleres de producción continua (Flowshop)
– Producción intermitente (Jobshop): Ruta única de
producción
UNA SOLA
MÁQUINA
MÁQUINAS EN
PARALELO
PRODUCCIÓN CONTINUA
(FLOWSHOP)
PRODUCCIÓN
INTERMITENTE
(JOBSHOP)
CARACTERÍSTICAS
Y RESTRICCIONES
Notación matemática para el campo a:
1 : 1 máquina.
Pm : Máquinas idénticas en paralelo.
Rm : Máquinas en paralelo con velocidades diferentes.
Fm : m Máquinas en serie.
FFc : Flowshop flexible con c estaciones en serie.
Jm : Jobshop con m máquinas.
FJc : Jobshop flexible (híbrido) con c estaciones de m máquinas idénticas.
CARACTERÍSTICAS
Y RESTRICCIONES
Notación matemática para el campo b:
pj : Tiempo de procesamiento del trabajo j cuando las
máquinas son idénticas.
pij : Tiempo de procesamiento del trabajo j en la máquina i.
rj : Fecha o tiempo de liberación del trabajo j.
dj : Fecha o tiempo sugerido de entrega del trabajo j.
sj : Tiempo de alistamiento del trabajo j.
wj : Ponderación (importancia) del trabajo j.
CARACTERÍSTICAS
Y RESTRICCIONES
Notación generales:
Cj : Tiempo de terminación del trabajo j. (Tiempo de flujo)
Lj = Cj - dj : Retraso del trabajo j (Lj < 0 significa anticipación).
Tj = máx.(0, Lj): Tardanza del trabajo j.
Ej = máx.(0, -Lj): Adelanto del trabajo j.
CARACTERÍSTICAS
Y RESTRICCIONES
Notación matemática para el campo g:
Cmáx = máx.(Cj): Tiempo máximo de terminación de todos los
trabajos.
Lmáx = máx.(Lj): Retraso máximo de todos los trabajos.
Tmáx = máx.(Tj): Tardanza máxima de todos los trabajos.
Emáx = máx.(Ej): Adelanto máximo de todos los trabajos.
ΣUJ : Número de trabajos tardíos
DIAGRAMA 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.
Permite observar gráficamente:
• Tiempos Ociosos
• Tiempos Activos
• Precedencia de actividades
• Tiempos de inicio y finalización
de trabajos
SINGLE
MACHINE
• El problema de una máquina es el problema 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.
• Para todos los tipos de problemas, no se abordarán
metodologías enumerativas dado la complejidad del problema...
SINGLE
MACHINE
Dentro de los problemas de
scheduling trabajaremos con
dos metodologías de solución:
• Reglas de despacho
• Algoritmos
• Meta heurísticas
REGLAS DE
DESPACHO
▪ Las reglas de despacho son políticas uni-
criterio para desarrollar ordenamiento en
una fila de trabajos a ser procesados.
▪ La efectividad de la regla depende del
sistema en el cual se esté implementando y
sobre la expectativa de servicio que espera el
cliente.
• SPT: El tiempo de procesamiento más
corto
• LPT: El tiempo de procesamiento más
largo
• FIFO: Primero en llegar primero en ser
atendido
• EDD: Fecha de entrega más próxima
Objetivo: Tiempo
de Flujo Mínimo
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.
• Cuando las fechas de liberación de trabajos es la misma, la
regla que minimiza el tiempo de flujo es la SPT (Shortest
Processing Time – Tiempo de Procesamiento más corto)
• Este objetivo es equivalente a la minimización del tiempo de
espera y de trabajo en proceso.
Objetivo: Tiempo
de Flujo Mínimo
• Para el caso del siguiente listado de órdenes, ¿Cómo asegurar
el cumplimiento de este objetivo?
Objetivo: Tiempo de
Flujo Ponderado
Mínimo
De acuerdo con la TOC 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.
• Para el caso del siguiente listado de órdenes, ¿Cómo asegurar
el cumplimiento de este objetivo?
Objetivo:
Tardanza
Con respecto a la tardanza existen varias
funciones que son factibles de evaluar
independientemente o de manera
simultánea
• Objetivo 1: Minimizar la Tardanza
Máxima.
El trabajo más tardío tenga la menor
tardanza posible.
• Objetivo 2: Minimizar la Número de
Trabajos Tardíos
Este número pierde relación con que tan
tarde se entregan los pocos trabajos
tardíos.
Objetivo: Minimizar
Tardanza Máxima
• Para poder calcular la tardanza se debe conocer la fecha de
entrega de cada trabajo (dj)
• La regla que minimiza esta expresión es ordenamiento de
acuerdo a la fecha de entrega más cercana (EDD - Earliest Due
Date)
Número de
Trabajos Tardíos
• Si es posible entregar todo a tiempo la regla EDD no entrega
trabajos tardíos. En caso que se tengan trabajos tardíos,
tiende a la tardanza es pequeña en muchos trabajos.
• En este tipo de problema se resuelve utilizando el algoritmo
de Hodgson que se describe a continuación:
Objetivo: Minimizar
Número de Trabajos
Tardíos
ALGORITMO DE HODGSON
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.
Objetivo: Tiempo Flujo
Mínimo sin Trabajos
Tardíos
Es una situación ideal. No siempre se puede dar una solución optima
para este problema.
• Paso 1. Se desarrolla la sumatoria de los tiempos de operación.
• Paso 2. Se programa de último en la secuencia el trabajo con fecha de
entrega mayor al valor calculado en el paso 1.
• Paso 3. Recalcular la sumatoria de tiempos de operación, sin incluir a
los trabajos ya asignados.
Repetir el algoritmo hasta asignar todos los trabajos. Los empates se
rompen de acuerdo al tiempo de procesamiento mas largo
EJERCICIOS
1. Un centro de maquinado local tiene cinco trabajos pendientes por
procesar. Los trabajos se representan con 1, 2, 3, 4, y 5, en el orden en
que entraron al taller. Los tiempos respectivos de procesamiento y las
fechas de entrega se registran en la tabla. Resolver por las diferentes
reglas y algoritmos vistos en clases (SPT, LPT, EDD, FIFO, Algoritmo
Hodgson), determinando tiempo promedio de flujo, tardanza máxima
y número de trabajos tardíos. Para este caso, ¿cuál es la secuencia
que optimiza el rendimiento del sistema en general?
Tiempo de Fecha de
Trabajo
procesamiento entrega
1 11 61
2 29 45
3 31 31
4 1 33
5 2 32
EJERCICIOS
2. Encuentre el programa que minimiza el tiempo de flujo
ponderado para el siguiente problema de una máquina.
3. Encuentre la tardanza máxima y el número de trabajos tardíos
para los siguientes trabajos:
