PROGRAMACION DE OPERACIONES
PROGRAMACION DE OPERACIONESTRANSPORTE
DISTRIBUCION
PROCESAMIENTO DE INFORMACION
PRODUCCIONTOMA DE DECISIONESASIGNACION DE RECURSOS A UNA SECUENCIA DE ACTIVIDADES
PROGRAMACION DE OPERACIONESORGANIZACION, ELECCION Y ASIGNACION DE TIEMPOS AL USO DE RECURSOS PARA EJECUTAR TODAS LAS ACTIVIDADES REQUERIDAS, PRODUCIR LAS SALIDAS DESEADAS EN LOS TIEMPOS DESEADOS, Y TENIENDO EN CUENTA LAS RESTRICCIONES DE TIEMPO Y LAS RELACIONES ENTRE LAS ACTIVIDADES Y LOS RECURSOS
T. E. MORTON Y D. W. PENTICO (1993) .
PLANES DE PRODUCCIONLNEAS DE PRODUCTOSPRODUCTOSINDIVIDUALESCOMPONENTESOPERACIONESPLANEACINAGREGADAPROGRAMA MAESTRODE LA PRODUCCINREQUERIMIENTOS DEMATERIALES (PLAN)PROGRAMACINDEL TALLER
PROGRAMACION VS. SECUENCIACIONUN PROGRAMA ESPECIFICA TANTO EL TIEMPO EN QUE CADA TRABAJO DEBE SER COMENZADO Y COMPLETADO EN CADA MAQUINA COMO LOS RECURSOS ADICIONALES REQUERIDOS
UNA SECUENCIA ES SIMPLEMENTE UN ORDENAMIENTO DE TRABAJOS
NOTACINNotacin matemtica:
n : NUMERO DE TRABAJOS A PROCESAR
m : NUMERO DE MAQUINAS
p i k : TIEMPO DE PROCESO DEL TRABAJO i EN MAQUINA k
r i : TIEMPO DE LIBERACION DE LA ORDEN DEL TRABAJO i
d i : FECHA DE ENTREGA DEL TRABAJO i
w i : IMPORTANCIA RELATIVO DEL TRABAJO i
NOTACINNotacin matemtica:
Un problema de scheduling se describe como una tripleta del tipo a l b l g. a describe la configuracin de recursos, b proporciona detalles sobre las caractersticas de procesamiento del taller y g describe el objetivo a optimizar.
NOTACINNotacin matemtica para el campo a:
1 : 1 mquina
Pm : Mquinas idnticas en paralelo Rm : Mquinas en paralelo con velocidades diferentesFm : m Mquinas en serieFFc : flowshop flexible (hbrido) con c estaciones en serie Jm : Jobshop con m mquinasFJc : jobshop flexible (hbrido) con c estaciones de m mquinas idnticas
NOTACINNotacin matemtica para el campo b:
r i : Tiempo de liberacion de la orden del trabajo i
Sjk : Tiempos de preparacin dependientes de la secuenciaprpm : la posibilidad de culminar la operacin sobre un trabajo (orden) en diferentes mquinas prec : Restricciones de precedenciabrkdwn: Fallas en los recursos Mj : Elegibilidad de recursos (para problemas Pm)prmu : programa de Permutacin (secuencia se mantiene)
NOTACINNotacin matemtica para el campo b:
block : bloqueos (flowshop) debido a buffers insuficientesnwt : no-waitrecrc : Recirculacin de trabajos
Cualquier otra informacin en el campo b es auto-explicatoria, por ejemplo pi = p implica que todos los tiempos de procesamiento son iguales.
MEDIDAS DE DESEMPEOC i : TIEMPO DE TERMINACION DEL TRABAJO i
F i = C i r i : TIEMPO DE FLUJO DEL TRABAJO i
L i = C i d i : RETRASO DEL TRABAJO i
T i = mx { 0, L i } : TARDANZA DEL TRABAJO i
E i = mx { 0, L i } : ADELANTO DEL TRABAJO i
MEDIDAS DE DESEMPEOC mx : MAKESPAN (LAPSO), TIEMPO MAXIMO DE TERMINACION DE TODOS LOS TRABAJOS
L mx : RETRASO MAXIMO DE TODOS LOS TRABAJOS
T mx : TARDANZA MAXIMA DE TODOS LOS TRABAJOS
NOTACINNotacin completa abg : ejemplos
FFc ri , di SwiTi: flowshop flexible (hbrido) con c estaciones en serie, fechas de liberacin y de entrega, cuyo objetivo es minimizar la tardanza total ponderada.Pm ri , Mj SwiTi: sistema con m recursos en paralelo, fechas de liberacin y de entrega, cuyo objetivo es minimizar la tardanza total ponderada.FJc ri , sik, di Cmax: jobshop flexible con c estaciones, fechas de liberacin y de entrega, tiempos de alistamiento dependientes de la secuencia y cuyo objetivo es minimizar el lapso (makespan) de produccin.
PROGRAMACION DEUNA SOLA MAQUINA
PROGRAMACION DEUNA SOLA MAQUINAOBJETIVO: TIEMPO DE FLUJO MINIMO (TF) CMO PROGRAMAR LOS TRABAJOS DE MODO QUE SE MINIMICE EL TIEMPO DE FLUJO TOTAL PROMEDIO?
SUPUESTOS: TODOS LOS TRABAJOS ESTAN DISPONIBLES EN EL TIEMPO CERO, POR LO CUAL EL TIEMPO DE FLUJO ES IGUAL AL TIEMPO DE TERMINACION.
Trabajo i12345 p i42324
PROGRAMACION DEUNA SOLA MAQUINASPT (TIEMPO DE PROCESAMIENTO MAS CORTO)ES LA SECUENCIA DE TRABAJOS ORDENADOS DEL MAS CORTO AL MAS LARGO
TF = C 1 + C 2 + C 3 + C 4 + C 5 = ( 2 ) + ( 2 + 2 ) + ( 2 + 2 + 3 )+ ( 2 + 2 + 3 + 4 ) + ( 2 + 2 + 3 + 4 + 4 ) = 39
TF PROMEDIO = 7.8 ES DECIR EN PROMEDIO UN TRABAJO DURA 7.8 UNIDADES DE TIEMPO EN EL SISTEMA
SPT MINIMIZA TAMBIEN EL INVENTARIO PROMEDIO DE TRABAJO EN PROCESO (WIP)
PROGRAMACION DEUNA SOLA MAQUINAOBJETIVO: BUSCAR RETRASO (L max ) Y TARDANZA (T max ) MINIMOS
TIPO DE PROBLEMA : 1 | | Lmax , 1 | | Tmax
EDD (FECHA DE ENTREGA MAS CERCANA) ES LA SECUENCIA DE TRABAJOS ORDENADOS DE LA FECHA DE ENTREGA MAS PROXIMA A LA MAS LEJANA
Trabajo i12345 p i42324 d i1064516
PROGRAMACION DEUNA SOLA MAQUINAEDD (TIEMPO DE ENTREGA MAS CERCANA)ES LA SECUENCIA DE TRABAJOS ORDENADOS DE LA FECHA DE ENTERGA MAS CERCANA A LA MAS LEJANA, EN CASO DE HABER EMPATE SE ROMPE CON EL TIEMPO DEPROCESO MAS LARGO ( CONWAY et al., 1967 )
Tardanzas (0,0,1,1,0) Tmax = 1
Objetivo: TIEMPO DE FLUJO MINIMO PONDERADO (TFP)
CMO PROGRAMAR LOS TRABAJOS DE MODO QUE SE MINIMICE EL TIEMPO DE FLUJO TOTAL TENIENDO EN CUENTA QUE ALGUNOS TRABJOS TIENEN PRIORIDADES?
SUPUESTOS:TODOS LOS TRABAJOS ESTAN DISPONIBLES EN EL TIEMPO CERO, POR LO CUAL EL TIEMPO DE FLUJO ES IGUAL AL TIEMPO DE TERMINACION. Y CADA TRABAJO TIENE UNA PRIORIDAD DE TERMNACION W
PROGRAMACION DEUNA SOLA MAQUINA
Trabajo i12345 p i42324 wi14313
PROGRAMACION DEUNA SOLA MAQUINAWSPT (TIEMPO DE PROCESAMIENTO MAS CORTO PONDERADO)ES LA SECUENCIA DE TRABAJOS ORDENADOS DE LA RELACION ENTER EL TIEMPO DE PROCESAMIENTO Y LA PONDERACION MAS GRANDE, EN CASO DE HABER EMPATE SE ROMPE CON EL TIEMPO DEPROCESO MAS LARGO
TPP = 2/1, 3/3, 2/3, 4/1, 4/3.
231501234567891011121314154
PROGRAMACION DEUNA SOLA MAQUINAOBJETIVO: MINIMIZACION DE TIEMPO DE ALISTAMIENTENTOALGORITMO DE ARREPENTIMIENTO
Lo que busca este algoritmo es tratar de buscar que el lapso de alistamiento sea tan grande como el elemento n mas pequeo, trabajando con una reduccin por filas y columnas. Para ello se plantea una matriz origen destino donde se muestra el costo tiempo de alistamiento de ir de un trabajo a otro, se sigue una serie de 5 pasos para trabajarlos:
Hoja1
TrabajoABCDE
A18336
B199105
C9181320
D6612
E1711317
PASO 1Se calcula el mnimo valor por fila, y se busca que este valor este en cada una de las columnas, si este no fuese el caso se halla tambin el Valor mnimo por columna. En caso que todo los mnimos sean cero siga al paso tresPROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimiento
Hoja1
TrabajoABCDEMin
A183363
B1991055
C91813209
D66121
E17113171
Suma19
PASO 2Se resta el valor mnimo ya sea por fila por fila y columna.PROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimiento
Hoja1
TrabajoABCDEMin
A150033
B144505
C094119
D55011
E16012161
Suma19
PASO 3Se calcula el arrepentimiento en cada valor que obtuvimos como cero, este valor es obtenido de la suma de los mnimos valores hallados en la fila y columna de la celda con cero.
Se toma la celda con mayor arrepentimiento (E-B)PROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimiento
Hoja1
TrabajoABCDEMin
A15000430
B1445050
C0994110
D550110
E1601712160
Suma0
PASO 4Se elimina la columna y las filas de la celda seleccionadas se penaliza con el programa inverso al seleccionado. En caso de llegar a una matriz de 2x2 pase al PASO 5, si no vuelva al paso 1
Programas seleccionados (E-B)PROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimiento
Hoja1
TrabajoACDEMin
A0033
B14455
C04119
D5011
Suma18
PASO 1PROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimientoNo hay, mnimo, toca hallarlos tambin en columnaProgramas seleccionados (E-B)
Hoja1
TrabajoACDEMin
A0030
B14454
C04110
D5010
Suma00014
Hoja1
TrabajoACDEMin
A0030
B14454
C04110
D5010
Min0001
PASO 2PROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimientoProgramas seleccionados (E-B)
Hoja1
TrabajoACDEMin
A0020
B10014
C04100
D5000
Suma0001
PASO 3PROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimientoProgramas seleccionados (E-B), (C-A)
Hoja1
TrabajoACDEMin
A000122
B100114
C094104
D500025
Suma501122
PASO 4PROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimientoProgramas seleccionados (E-B), (C-A)
Hoja1
TrabajoCDEMin
A020
B010
D000
Suma0000
PASO 1 y PASO 2PROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimientoProgramas seleccionados (E-B), (C-A), (A-D).COMO LOS DOS ULTIMOS SE PUEDEN UNIR Y QUEDAR COMO UNO SOLO DE TRES TRABAJOS (C-A-D)PASO 3
Hoja1
TrabajoCDEMin
A0020
B010
D000
Suma0000
Hoja1
TrabajoCDEMin
A0320
B0110
D00020
Suma0000
PASO 5 Se escogen los programas restantes con cero como opcionales y se evala con cual de los 2 programas completos es el mejor, teniendo en cuenta la union correcta de los programas antes seleccionados.Programas seleccionados(E-B),(C-A-D)Programas opcionales(B-C) (D-E)Soluciones posibles (E-B-C-A-D) Costo 22 (C-A-D-E-B) Costo 15PROGRAMACION DEUNA SOLA MAQUINAHeurstica del arrepentimiento
Hoja1
TrabajoCEMin
B00
D00
Suma000
PROGRAMACION DEMAQUINAS EN PARALELO
MAQUINAS PARALELASOBJETIVO: TIEMPO DE FLUJO MINIMO (TF)
3 MAQUINAS PARALELAS
SUPUESTOS: CUALQUIER TRABAJO SE PUEDE PROCESAR EN CUALQUIERA DE LAS MAQUINAS Y SU TIEMPO DE PROCESO ES IGUAL EN CUALQUIERA DE ELLAS
Trabajo i12345678910 p i3.54.03.02.51.04.51.52.04.21.8
SPT (TIEMPO DE PROCESAMIENTO MAS CORTO) ORDENAMIENTO DE TRABAJOS DEL MAS CORTO AL MAS LARGO, EN LA MAQUINA CON MAYOR DISPONIBILIDAD
TF = C 1 + C 2 + C 3 + C 4 + C 5 + C 6 + C 7 + C 8 + C 9 = (6,5) + ( 8) + (4.8) + (4) + (1) + ( 11) +(1.5) + (3) +(7.2) + ( 1.8) = 48.8
C mx = 11TF PROM= 4.88
MAQUINAS PARALELAS
OBJETIVO:MINIMO MAKESPAN (C mx )
3 MAQUINAS PARALELAS
LPT (TIEMPO DE PROCESO MAS LARGO)ORDENAMIENTO DE TRABAJOS DEL MAS LARGO AL MAS CORTO, EN LA MAQUINA CON MAYOR DISPONIBILIDAD
MAQUINAS PARALELAS
Trabajo i12345678910 p i3.54.03.02.51.04.51.52.04.21.8
MAQUINAS PARALELASLPTC mx = 10
PROGRAMACION DETALLERES EN FLUJO
TALLERES DE PRODUCCION CONTINUAMINIMO MAKESPAN (C mx ) PARA TALLERES DE DOS MAQUINAS
ALGORITMO DE JHONSON (1954) EN UNA MAQUINA EL ORDENAMIENTO TIENDE A SER SPT MIENTRAS QUE EN LA OTRA TIENDE A SER LPT
Trabajo i1234TotalMquina 1543214Mquina 2252615
TALLERES DE PRODUCCION CONTINUA2 MAQUINAS.OBJETIVO: MINIMIZAR EL MAKESPAN (Cmax) ALGORITMO DE JHONSON
Se buscar los mnimos de todos los tiempos, Si se encuentra en la mquina 1, ubquela lo ms temprano posible en la secuencia de sta mquina; si se halla en la mquina 2, ubquela lo ms tarde posible en la respectiva secuencia, si hay empate, selecciono el que tenga mayor tiempo en la maquina contraria a donde se encontr el valor mnimo. Luego busque el mnimo siguiente sucesivamente.S{ 4, 2, 3, 1 }
Trabajo i1234TotalMquina 1543214Mquina 2252615
TALLERES DE PRODUCCION CONTINUAALGORITMO DE JHONSON: S{4,2,3,1}S{1,2,3,4}Cmax = 21Cmax = 17
PROGRAMACION DEFLOWSHOPS (M>2) Y JOBSHOPS
PROGRAMACION DE CUELLOS DE BOTELLAFLOWSHOPS (M>2) Y JOBSHOPSOBJETIVO: MINIMO MAKESPAN (C mx ) SI ES POSIBLE PROGRAMAR EL CUELLO DE BOTELLA, LAS OTRAS MAQUINAS PUEDEN AJUSTARSE A ESTE PROGRAMA
PROGRAMACION DE CUELLOS DE BOTELLAFLOWSHOPS (M>2) Y JOBSHOPSIDENTIFICACION DEL CUELLO DE BOTELLA EJEMPLO FLOW SHOP DE TRES MAQUINAS.Maquina cuello de botella (CB)
PROGRAMACION DE CUELLOS DE BOTELLAFLOWSHOPS (M>2) Y JOBSHOPSEn este caso la operacin se centra con el cuello de botella. Para realizar la heurstica se trabaja como si este fuese una solo maquina, donde: Pi(tiempo de procesamiento) :es el tiempo de procesamiento del CB
Ri (fecha de liberacin) : Es la suma de los procesos anteriores al CB
Di(Fecha de entrega): Es la relacin que hay entre la suma de los tiempos de proceso en la CB menos los tiempos de proceso de las estaciones siguientes a CB
PROGRAMACION DE CUELLOS DE BOTELLAFLOWSHOPS (M>2) Y JOBSHOPSHEURISTICA DE DESPACHO
Datos de la mquina cuello de botella y los trabajos:
Trabajo i12345r i310646d i6259675560p i122112185
PROGRAMACION DE CUELLOS DE BOTELLAFLOWSHOPS (M>2) Y JOBSHOPSPara realizar la secuencia se trabaja bajo la siguiente regla: Paso 1:Colocar de primero en la secuencia el trabajo con menor Ri
Paso 2:Una vez encontrado el tiempo en que acaba el producto secuenciado en la maquina cuello de botella revisar cuales son los trabajos que se encuentran disponibles a programar segn ese tiempo e ir al paso 3, si no hay ningn trabajo vaya al paso 1.
Paso 3:De los trabajos disponibles a programar selecciono el de menor Ri, en caso de haber empate el de menor Ri, si insiste el empate con el Pi si persiste se hace de manera aleatoria.
PROGRAMACION DE CUELLOS DE BOTELLAFLOWSHOPS (M>2) Y JOBSHOPS
S {1,4,2,5,3} MAKESPAN MAQUINA B, Cmx = 71
ITERACIONTiempoTrabajos disponibles en ese tiempo[Ini,fin]1mx { mn r bi , 0 } = 3{ 1}[3,15]2mx { 4 , 15 } = 15{ 2,3,4,5}[15,33]3mx {6 , 33 } = 33{2,3,5}[33,54]454{ 3,5}[54,59]559{ 3}[59,71]
*
Top Related