7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 1/12
BALANCE DE LÍNEAS DE PRODUCCIÓN:
Asignar tareas individuales a las estaciones de trabajo, de manera que se optimice
una medida de desempeño para tal fin.
Si una línea de producción esta perfectamente balanceada, todas las estaciones
tienen igual carga de producción por unidad de tiempo, y se reduce al máximo los
tiempos muertos en cada estación.
LOS PROBLEMAS DE SECUENCIACIÓN SE CLASIFICAN DE ACUERDO A:
a) El patrón de llegada de los trabajos.
b) El número de Maquinas.
c) De acuerdo al flujo de producción.
Serie
Aleatorios
d) De acuerdo al objetivo que se desea optimizar.
Minimizar el tiempo de ejecución de las tareas programadas.
Minimizar la demora media.
Minimizar la tardanza media.
Minimizar la tardanza máxima.
Maximizar el numero de trabajos tempranos
NOTACIÓN PARA DISTINGUIR LOS DIFERENTES PROBLEMAS DESECUENCIACIÓN.
Donde
A: Llegadas de Trabajos
A/B/C/D
SECUENCIACION
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 2/12
B: Número de Maquinas
C: Tipo de Flujo
F. En serieR:Aleatorio
G: GeneralD: Criterio deOptimización
Ejemplo:
Indica la secuencia de 3 trabajos en serie en 2 maquinas, tal que minimice el
tiempo de flujo máximo.
3 2 F F
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 3/12
PARÁMETROS IMPORTANTES EN LOS MODELOS DESECUENCIACIÓN.
Considere n trabajos que requieren un proceso en una maquina se definen por:
Parámetros que se conocen anticipadamente.
tj= Tiempo de proceso requerido por el trabajo j
rj= Periodo de tiempo en el que el trabajo j esta listo para procesarse
dj= Tiempo de entrega, es decir el periodo de tiempo en el que el trabajo j deberíaentregarse
Parámetros o información que se generan durante la ejecución.
Cj= Tiempo de terminación del trabajo j
Fj= Tiempo de flujo del trabajo j
Lj= Retraso del trabajo j
Tj= Tardanza del trabajo j
Ej= Tempranza del trabajo j
PARAMETRO RELACIONFj Cj - rj
Lj Cj - Dj
Tj si Lj es positivo
Ej si Lj es negativo
MÉTODOS PARA RESOLVER PROBLEMAS DE SECUENCIACIÓN
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 4/12
Consiste en una serie de graficas horizontales que permiten ordenar trabajos deacuerdo a:
Su tiempo de proceso.
Tiempos de reposo de maquinaria tiempos muertos.
Tiempos de espera.
EJEMPLO:
Suponga que se requieren 2 trabajos A y B, cada uno con 2 procesos P1, P2 que se
realizan respectivamente en 2 maquinas herramientas distintas. Suponga que la
duración de cada proceso es:
TrabajoProceso
M1 M2A 2 7
B 5 4
Horas por 1000 piezas
SOLUCIÓN
Existen solo 2! = 2 posibles secuencias, A-B o la B-A
n trabajos y 1maquina
n trabajos y 2maquinas
n trabajos y 3maquinas
2 trabajos y mmaquinas
n trabajos y mmaquinas
1) Graficas de
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 5/12
Las graficas anteriores demuestran que secuencia AB es mejor que la BA: en la
primera se completan los dos trabajos en 13 horas; en la segunda se utilizan 16
horas.
Sea t1, t1,…, tn, Los tiempos conocidos de n procesos diferentes e independientes en una
maquina, entonces existe n! maneras diferentes de ordenar la secuenciación, cada
una de estas con un tiempo promedio total de flujo.
Se requiere encontrar la secuencia que minimice este tiempo.
TEOREMA:
2) n Trabajos en Una Maquina
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 6/12
El promedio de flujo F , se minimiza con la secuencia tI1I < tI2I <……………….< tInI esta
secuencia se denomina Tiempo de procesamiento mas corto TPC
ALGORITMO.
Se busca aquel trabajo cuya t j sea mínima entre todas y se hace tI1I , de los que
queda se busca el mínimo y se hace tI2I , y así sucesivamente hasta encontrar tInI.
Este algoritmo también funciona si los trabajos si los trabajos tienen asignados una
ponderación que denota su importancia.
Wj = Ponderación asignada al trabajo j.
tI1I / wI1I < tI2I / wI2I < ………………. < tInI / wInI
EJEMPLO.
Encuentre el TPC de los 8 trabajos
Trabajo (j) tj (horas)
1 52 23 14 45 7
6 37 108 0,5
SOLUCIÓN
Se considera un problema (8/1/F/Fmáx. ) la secuencia se minimiza bajo elcriterio del TPC (tiempo promedio más corto) quedando la secuencia de lasiguiente manera:
T |1|
< T |2|
< T |3|
< T |4|
< T |5|
< T |6|
< T |7|
< T |8|
½ < 1 < 2 < 3 < 4 < 5 < 7 < 10
Es decir, que la secuencia óptima de trabajo es: {8, 3, 2, 6, 4, 1, 5, 7}.
REGLAS DE PRIORIDAD.
Operación mas Corta (OMC)
Operación mas Larga (OML)
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 7/12
Trabajo más corto (TMC)
Trabajo mas largo (TML)
Menor tiempo restante (MTR)
Menor fecha de entrega. (MFE)
Menor tiempo de holgura. (MTH)
EJEMPLO.
Encuentre el TPC de los 8 trabajos del problema anterior, si la importancia de cada
trabajo es:
Trabajo(j)
Wj
1 32 7
3 24 105 206 157 88 2
SOLUCIÓN
Trabajo (j) tj (horas) Wj ti/Wj
1 5 3 1,72 2 7 0,33 1 2 0,54 4 10 0,45 7 20 0,46 3 15 0,27 10 8 1,38 0,5 2 0,3
El TPC es: 0.20 < 0.25 < 0.29 < 0.35 < 0.40 < 0.50 < 1.25 < 1.67
Por lo que la secuencia óptima es: {6, 8, 2, 5, 4, 3, 7, 1}
ALGORITMO DE JOHSON.
tji= Tiempo de proceso j (j= 1, 2) del trabajo i (i = 1,2, …
3) n Trabajos y 2 Maquinas (n/2/F/ FMAX)
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 8/12
1. Se hace K = 1 y P = n
j = 1 =>K = K +1
2. Encontrar elmínimo tij
j = 2 =>P = P -1
3. Y se elimina el análisis posterior.
4. Con los tij restantes se repite los dos anteriores procedimientos anteriores.
Nota: los empates se resuelven arbitrariamente.
EJEMPLO.
Suponga un problema de ordenación de 5 trabajos, cada uno de los cuales requiere
dos procesos secuenciales (forjar y pintar), en dos maquinas distintas. Los tiempos del
proceso se muestran a continuación.
TRABAJO
PROCESOS
FORJAR
PINTAR
1 4 3
2 1 2
3 5 44 2 3
5 5 6
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 9/12
SOLUCIÓN
Interacción 1
1. Se hace K=1 y P=5.
2. El mínimo valor de las tij corresponde a t 21 = 1, como j=1 se asigna el primer
lugar al trabajo numero 2.
3. Se elimina el segundo trabajo del análisis y se hace K=2 y P=5.
Interacción 2
1. Se tiene K=2 y P=5.
2. El mínimo valor de las tij corresponde a t 41 = 2, como j=1 se asigna el segundo
lugar al trabajo numero 4.
3. Se elimina el cuarto trabajo del análisis y se hace K=3 y P=5.
Interacción 3
1. Se tiene K=3 y P=5.
2. El mínimo valor de las tij corresponde a t 12 = 3, como j=2 se asigna el quinto
lugar al trabajo numero 5.
3. Se elimina el cuarto trabajo del análisis y se hace K=3 y P=4.
Interacción 4
1. Se tiene K=3 y P=4.
2. El mínimo valor de las tij corresponde a t 32 = 4, como j=2 se asigna el cuarto
lugar al trabajo numero 3.
3. Se elimina el cuarto trabajo del análisis y se hace K=3 y P=3.
Como el único trabajo que no ha sido ordenado es el quinto, y la única
secuencia que no ha sido asignada es la tercera, queda implícita que el quinto
trabajo se ubica en el tercer lugar.
La secuencia óptima es la: {2, 4, 5, 3, 1}
ALGORITMO DE JACKSON.
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 10/12
Divide a los trabajos en 4 grupos
GRUPO
A Conjunto de Trabajos que requierensolo del primer proceso
B Conjunto de Trabajos que requierensolo del segundo proceso
ABEl conjunto de Trabajos que requierendel primer proceso y después delSegundo
BA
El conjunto de Trabajos que requierendel segundo proceso y después delPrimero
EJEMPLO.
Resuelva el problema siguiente, suponiendo que el trabajo 6 requiere solo de la
máquina 1, el 3 de la máquina 2, el 4 y 5 primero de la máquina 2 y
después de la máquina 1, y el 1 y 2 de la máquina 1 y después de la maquina
2.
SOLUCIÓN
TRABAJO
M1 M2
Grupode
Trabajo
1 1º 2º {AB}
2 1º 2º {AB}
3 1º {B}4 2º 1º {BA}
5 2º 1º {BA}
6 1º {A}
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 11/12
Finalmente se combinan los resultados anteriores de la siguiente manera
PROCESO 1: Secuencia {AB}, seguida de la {A} y finalizada por la {BA}
PROCESO 2: Secuencia {BA}, seguida de la {B} y finalizada por la {AB}
Algoritmo de Johnson
(n/3/F/ FMAX)
Algoritmo de bifurcación y acotación ignall y schrage
ALGORTIMO DE JOHNSON (n trabajos, 3 máquinas).
Sirve para resolver un caso particular (n/3/F/Fmáx), la particularidad el caso la
proporciona que el segundo proceso está totalmente dominado por el
proceso 1 y 3, en donde, se debe cumplir una de las siguientes condiciones:
Mín {ti1} ≥ Máx {ti2} ó Mín {ti3} ≥ Máx {ti2}
EJEMPLO
Considere 4 trabajos que requieren de 3 procesos secuenciales cada uno. Los
detalles se proporcionan a continuación.
TRABAJO PROCESOSP 1 P 2 P 3
1 8 2 4
2 5 4 5
3 6 1 3
4 7 3 2
SOLUCIÓNComo Mn{t i1} = 5 > Máx. {t i2} = 4, entonces, se crean dos nuevos procesos:
TRABAJ PROCESOS
4) n Trabajos y 3 Maquinas (n/3/F/ FMAX)
7/23/2019 INTRODUCCION SECUENCIACION
http://slidepdf.com/reader/full/introduccion-secuenciacion 12/12
O P1 P21 10 6
2 9 9
3 7 4
4 10 5
Una vez se tenga el anterior cuadro, se resuelve por algoritmo de Johnson
Generando la secuencia {2, 1, 4, 3}