Date post: | 23-Jan-2016 |
Category: |
Documents |
Upload: | martin-vea |
View: | 218 times |
Download: | 4 times |
1
Introducción a la secuenciación
Paz Pérez GonzálezSistemas de Producción Integrados
Curso 2008/2009
Índice
Ejemplo: Los aprendices de Adriá Secuenciación de tareas Problema de secuenciación Algoritmo Complejidad Conclusiones
2
Índice
Ejemplo: Los aprendices de Adriá Secuenciación de tareas Problema de secuenciación Algoritmo Complejidad Conclusiones
3
4
Ejemplo: Los aprendices de Adrià
Juan y Antonio: Compañeros de piso y estudiantes de ingeniería
Quieren impresionar a dos chicas con sus habilidades en la cocina
Prepararán una cena espectacular para los cuatro Problema:
Juan sólo sabe manejar el microondas Antonio sólo sabe manejar el libro de recetas de su
madre
5
Ejemplo: Los aprendices de Adrià
Lista de platos: 1er plato: Ensalada con almendras fundidas
Lavar y cortar verduras Plato frío, sólo fundir las almendras (5 minutos de
horno) Preparar
2º plato: Pato a la naranja Preparar pato con el zumo de naranja Hornear durante 60 minutos a 250 ºC
Postre: Bizcocho Comprado en el supermercado, solo desenvolver,
calentar en el horno 90 minutos a 200 º C y presentar
6
Ejemplo: Los aprendices de Adrià
Organización: Antonio queda a cargo de la preparación y vigilar el
horno Juan queda a cargo de la presentación final
Estimación de tiempos (minutos):
Preparación(Antonio)
HornoPresentación
(Juan)
1er plato 30 5 20
2º plato 20 60 5
postre 5 90 5
7
Ejemplo: Los aprendices de Adrià
Decisión: ¿cuál debería ser el orden de cada una de las tareas para acabar lo antes posible?
Intentar dar una solución en 5 minutos
Preparación(Antonio)
HornoPresentación
(Juan)
1er plato 30 5 20
2º plato 20 60 5
postre 5 90 5
8
Ejemplo: Los aprendices de Adrià
Diagrama de Gantt: Herramienta básica para la representación y cálculo de soluciones a los problemas de secuenciación
Ejemplo: representar decisión primer plato ( ), segundo plato ( ), postre ( )
Presentación
Horno
Preparación
T. terminación = 205 min.
9
Ejemplo: Los aprendices de Adrià
¿Son decisiones relevantes? ¿Existe alguna diferencia entre una decisión y
otra? Lista exhaustiva de todas las decisiones posibles:
Decisión Tiempo terminación (min.)
(primero, segundo, postre) 205
(segundo, primero, postre) 180
(postre, primero, segundo)
162
(segundo, postre, primero) 195
(primero, postre, segundo) 190
(postre, segundo, primero) 177
10
Ejemplo: Los aprendices de Adrià
Entre la mejor decisión y la peor, hay un 26,5% de diferencia:
Ahorro de tiempo Ahorro de costes
Índice
Ejemplo: Los aprendices de Adriá Secuenciación de tareas Problema de secuenciación Algoritmo Complejidad Conclusiones
11
12
Secuenciación de tareas
Definición: Asignación de tareas a recursos escasos a lo largo del
tiempo. Se trata de adoptar una decisión (de entre un conjunto de
decisiones posibles) para optimizar uno o varios objetivos ¿Dónde aparecen problemas de secuenciación?
En la mayor parte de decisiones en la ingeniería de organización, tanto en la industria como en los servicios
Relevancia de la secuenciación ¿Es importante tomar la decisión de secuenciación
correcta? En el ejemplo quedaba claro, pero… ¿también en la práctica?
Algunos estudios sobre el impacto de la secuenciación: Taillard Wein
13
Secuenciación de tareas
Dificultad de la secuenciación ¿Es difícil tomar la mejor decisión del conjunto
posible? Depende del tamaño del problema En general, sí
De hecho, se demuestra que para muchos problemas no es factible encontrar la mejor solución del conjunto posible
Restricción adicional: intervalo de decisión
Índice
Ejemplo: Los aprendices de Adriá Secuenciación de tareas Problema de secuenciación Algoritmo Complejidad Conclusiones
14
15
Problema de secuenciación
Formulación general de una decisión a tomar Un problema se caracteriza por un conjunto de
parámetros o datos de entrada que son necesarios para resolver el problema.
Cuando se le dan unos valores concretos a los parámetros de un problema se genera una instancia de ese problema
Proceso de toma de decisiones para planificar la producción, con el propósito de optimizar uno o más objetivos
Decisión sobre el orden de paso de los trabajos/pedidos por los centros de trabajo (máquinas)
Problema de secuenciación
En general es un problema de optimización en el que se busca la secuencia (orden de los trabajos en las máquinas) para minimizar un objetivo, bajo ciertas restricciones.
Hallar la secuencia óptima paraMin f.o
s.a r1 … rn
¿De qué datos disponemos? ¿Qué funciones objetivos, y qué restricciones?
16
Problema de secuenciación
Parámetros del problema (datos) n: número de trabajos m: número de máquinas pij: tiempo de proceso del trabajo j en la máquina i rj: release del trabajo j dj: fecha de entrega del trabajo j wj: peso del trabajo j
17
pij
rj dj
wj
Problema de secuenciación
Parámetros del problema (para una secuencia dada)
Sij: tiempo de comienzo del trabajo j en la máquina i Cij: tiempo de terminación del trabajo j en la máquina
i [j]: trabajo en la posición j-ésima
18
M1
M2
M3
Sij Cij
Problema de secuenciación
Parámetros del problema (Relacionados con las fechas de entrega)
Cj : tiempo de terminación del trabajo j en el sistema Lj : retraso/adelanto del trabajo j con respecto a la
fecha de entrega; Lj=Cj-dj
Tj : tardanza; Tj=max(Lj, 0) Uj : trabajos tardíos; Uj=1 si Cj>dj , Uj=0 si Cj≤dj
19
Problema de secuenciación
Objetivos (Funciones objetivo (Minimizar)) No relacionados con fechas de entrega:
Cmax=max(C1,…,Cn): Tiempo máximo de terminación (makespan). Instante en el que el último trabajo sale del sistema
F= ΣCj: Tiempo de terminación total (flowtime) Fw= ΣwjCj: Tiempo de terminación ponderado total
Relacionados con fechas de entrega: Lmax=max(L1,…,Ln): Máximo retraso. El peor de los casos
en los que no se cumpla la fecha de entrega Tmax=max(T1,…,Tn), con Tj=max(Lj,0): Máxima tardanza.
Considera sólo los retrasos, no los adelantos. T= ΣTj: Tardanza total nT= ΣUj: Número de trabajos tardíos
20
Problema de secuenciación
Algunos entornos típicos: Una máquina (1) Máquinas iguales en paralelo (Pm) Taller de flujo. Flow Shop. Máquinas en serie (Fm) Taller de flujo flexible. Flexible Flow Shop. Varios
bloques en serie de máquinas en paralelo (FFs) Taller de trabajo. Job shop. Rutas predefinidas (Jm) Taller abierto. Open shop. Rutas a determinar (Om)
21
22
Problema de secuenciación
Ejemplo: problema AIRCOND Planta de ensamblado de aparatos de aire
acondicionado. Una máquina de ensamblaje procesa los
componentes 1 máquina Los componentes de cada aparato (distintos en cada
caso) llegan a lo largo del tiempo rj
Cada aparato tiene un tiempo de ensamblaje distinto pj
Decisión: cómo secuenciar los pedidos de forma que se minimice el tiempo total de flujo (suma de los tiempos de terminación de cada componente) F= ΣCj
23
Problema de secuenciación
Modelado (abstracción) del problema: Se tienen n trabajos a procesar en una máquina,
cada uno con su tiempo de proceso pj y su instante mínimo de comienzo rj
El objetivo del problema es determinar el orden de los trabajos de forma que se minimice la suma de los tiempos de flujo (Min F= ΣCj)
Parámetros del problema: Número de trabajos (n) Tiempo de proceso del trabajo j (pj) Tiempo mínimo de comienzo de j (rj)
24
Problema de secuenciación
Instancia Caso concreto de un problema
Ejemplo: Instancia del problema AIRCON El día 10.01.2009 a las 8:00 se debe decidir el orden
de los siguientes trabajos:
Trabajo
Tiempo proceso (pj)
T. Mínimo comienzo (rj)
#1 20 8:00
#2 10 8:00
#3 25 8:30
#4 15 8:30
#5 30 9:00
25
Problema de secuenciación
Solución La solución es una respuesta a una instancia de un
problema de decisión A veces se distingue entre solución admisible y
solución inadmisible Solución óptima
Si una solución es la mejor (respecto al objetivo que se ha fijado) entre todas las soluciones posibles, la solución se dice que es óptima
Índice
Ejemplo: Los aprendices de Adriá Secuenciación de tareas Problema de secuenciación Algoritmo Complejidad Conclusiones
26
27
Algoritmo
Conjunto de pasos que se aplican de forma sistemática para resolver un problema
En el contexto de secuenciación, servirán para evaluar soluciones o resolver instancias de un problema.
Se suelen expresar en forma de pseudo-código
28
Algoritmo
Algoritmo calcula_tiempo_flujo(n, ri, pi, S) Evaluamos una solución S del problema AIRCOND [i] indica la posición i ([i] i ) C[i]: tiempo de finalización del trabajo que ocupa la
posición i en la secuencia dada S Por ejemplo:
p[i] tiempo de proceso del trabajo que ocupa la posición i en S r[i] tiempo mínimo de comienzo del trabajo que ocupa la posición i en
S Pseudocódigo:C[1]= r[1] + p[1]Tiempo_flujo = 0For i=2 to i=n
C[i]= max{r[i], C[i-1]} + p[i]Tiempo_flujo = Tiempo_flujo + C[i]
29
Algoritmo
Un algoritmo también puede describir una forma de generar soluciones admisibles (o incluso óptimas) para un problema
Ejemplo: algoritmo ERT (Earliest Release Time) para el problema AIRCOND
Descripción de ERT: Ordenar los trabajos de menor a mayor rj (primero se
procesan los que llegan antes)
Índice
Ejemplo: Los aprendices de Adriá Secuenciación de tareas Problema de secuenciación Algoritmo Complejidad Conclusiones
30
31
Complejidad
La complejidad de un algoritmo define cómo se incrementan el número de cálculos necesarios en función de los parámetros del problema
La complejidad se denota como O(parametros) Ejemplos:
calcula_tiempo_flujo es O(n) ordenar una lista de n elementos es O(n log (n) ) Resolver el problema de AIRCOND mediante la
evaluación de todas las opciones posibles es O(n!)
32
Complejidad
A grandes rasgos, se definen dos tipos de algoritmos en función de la complejidad:
POLINOMIALES (P): Su complejidad es una función polinómica
Ejemplo: ordenar una lista es P NO POLIMONIALES (NP): Su complejidad es mayor
que la de una función polinómica Ejemplo: evaluar todas las soluciones de AIRCOND es
NP Dicho de otra manera, el tiempo de
computación de un algoritmo P (NP) crece de forma (no) polinomial con el tamaño del problema
Ya se ha visto la importancia de encontrar métodos P para resolver los problemas
33
Complejidad
Historia Años 50-70: No se encuentran métodos P (simplex no
lo es) para la mayoría de los problemas de secuenciación
… pero se seguía buscando Años 70: Cook (1974) demuestra que existen 6
modelos ‘padres’ de los que se derivan muchos otros modelos (hijos): conjunto de problemas NP
Si se encuentra un método P para un modelo ‘padre’, se puede aplicar a los modelos ‘hijos’
Años 80: Practicamente todos los modelos de secuenciación plantean problemas NP
Luego basta con encontrar un método eficiente para resolver el problema ‘padre’
Año 2009: Todavía no se ha encontrado un método P para los modelos ‘padres’
Luego no se ha encontrado un método P para los problemas ‘hijos’ de SCM
Índice
Ejemplo: Los aprendices de Adriá Secuenciación de tareas Problema de secuenciación Algoritmo Complejidad Conclusiones
34
35
Conclusiones
A día de hoy, no se han encontrado métodos para resolver de forma óptima la mayor parte de problemas de secuenciación
Además, hay pocas esperanzas ¿Cómo se aborda este problema en la
práctica? Métodos aproximados Instancias pequeñas
36
Conclusiones
Métodos aproximados Similitud
Algunos modelos sí se resuelven en P. Las soluciones óptimas de modelos en P se utilizan para obtener buenas soluciones de modelos NP
Ejemplo: una máquina flujo regular Métodos genéricos
Heurísticas ad hoc reglas ‘de sentido común’ Metaheurísticas procedimientos generales
37
Conclusiones
Instancias pequeñas Aunque los problemas sean NP, si se trata de una
instancia pequeñas (pocas máquinas, pocos trabajos), si puede ser factible resolver el problema en poco tiempo
Métodos eficientes (exactos) de resolución de problemas
Métodos de enumeración Branch & bound (ramifica y acota)
38
Entornos en secuenciación
Paz Pérez GonzálezSistemas de Producción Integrados
Curso 2008/2009
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
39
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
40
41
Secuenciación
Asignación de tareas a recursos a lo largo del tiempo
Proceso de toma de decisiones para planificar la producción, con el propósito de optimizar uno o más objetivos
Decisión sobre el orden de paso de los trabajos/pedidos por los centros de trabajo (máquinas)
¿Dónde aparecen problemas de secuenciación? En la mayor parte de decisiones en la ingeniería de
organización, tanto en la industria como en los servicios
42
Secuenciación
Notación: α|β|γ α Entorno máquina
1, Pm, Fm, Jm, Om β Condiciones del sistema
prmu, dj, rj,…
γ Función objetivo Cmax, Lmax, Tmax, F, T,…
Recordar: n: número de trabajos, 1≤ j ≤ n m: número de máquinas, 1 ≤ i ≤ m
Ejemplo: Fm|prmu|Cmax
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
43
Entornos máquina
Una máquina (1) Máquinas iguales en paralelo (Pm) Taller de flujo. Flow Shop. Máquinas en serie
(Fm) Taller de trabajo. Job shop. Rutas predefinidas
(Jm) Taller abierto. Open shop. Rutas a determinar
(Om)
44
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
45
46
Condiciones del sistema
Fechas de disponibilidad del trabajo (rj) Fechas de entrega (dj) Tiempo de preparación entre trabajos (setup
times) (sjk) Interrupción (preemption, prmp) Precedencia (prec) – Una máquina o en paralelo Rotura de la máquina (brkdwn) Permutación (prmu) – Taller de flujo Bloqueo (block) – Taller de flujo No espera (nwt) – Taller de flujo
Condiciones del sistema
Release del trabajo (rj) Instante de disponibilidad del trabajo j P. ej. Un taller de reparaciones. Cada trabajo llega
cuando el cliente entrega el objeto a reparar
Fechas de entrega (dj) Instante en el que el trabajo debe de estar terminado Pueden estar dadas por el cliente, o ser estimadas
en la planificación
r1 r2 d1 d2
48
Condiciones del sistema
Tiempo de preparación entre trabajos (setup times) (sjk). Si depende de la máquina se nota sijk.
Tiempo de espera del trabajo k después de procesarse el trabajo j.
P. ej. Cambiar una pieza o limpiar la máquina antes de procesar un trabajo
S12S12
49
Condiciones del sistema
Interrupción (preemption,prmp) Se permite parar de procesar un trabajo, para
procesar otro. Luego el anterior o se reanuda, o empieza de nuevo.
P. ej. Por distintas causas: llegada de un trabajo mas urgente, por necesidad (falta una pieza), para obtener menos tiempos ociosos de las máquinas, etc.
Rotura de la máquina (brkdwn)
26 22
Trabajo a iterrumpirTrabajo iterrumpido
50
Presentación
Horno
Preparación
Presentación
Horno
Preparación
prmu Sin prmu, el bizcocho necesita enfriarse más tiempo, y el pato debe reposar para macerarse, y estar caliente para llevarlo a la mesa
Condiciones del sistema
Permutación (prmu) El orden de los trabajos es el mismo para todas las
máquinas P.ej. El ejemplo de los aprendices de Adrià. Primer
plato ( ), segundo plato ( ), postre ( )
51
Condiciones del sistema
Bloqueo (block) Si el búffer (almacenaje) entre máquinas es limitado
y se llena, la máquina que ha terminado el trabajo no puede liberarse (se bloquea). Cuando la máquina siguiente quede libre entra el siguiente trabajo, desbloqueando la anterior.
Se supone búffer infinito cuando los ítems son pequeños (p.ej. tornillos)
Si el búffer es cero, el trabajo no deja la máquina hasta que la siguiente está libre.
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
52
Función Objetivo
No relacionados con fechas de entrega: Cmax=max(C1,…,Cn): Tiempo máximo de terminación
(makespan). Instante en el que el último trabajo sale del sistema
F= ΣCj: Tiempo de terminación total (flowtime) Fw= ΣwjCj: Tiempo de terminación ponderado total
Relacionados con fechas de entrega: Lmax=max(L1,…,Ln): Máximo retraso. El peor de los casos
en los que no se cumpla la fecha de entrega Tmax=max(T1,…,Tn), con Tj=max(Lj,0): Máxima tardanza.
Considera sólo los retrasos, no los adelantos. T= ΣTj: Tardanza total nT= ΣUj: Número de trabajos tardíos
53
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
54
55
Una máquina
1|β|γ Simpleza Caso especial de los demás medios Un medio más complejo se puede estudiar como una
sola máquina Una consulta de un médico suele estar secuenciada
mediante la regla FIFO (First In First Out)
Una máquina 1||Cmax
Makespan o tiempo máximo de terminación: Cmax=max(C1,…,Cn), con Cj tiempo de terminación del trabajo j en el sistema (instante en el que sale del sistema)
El problema se denota 1||Cmax
Ejemplo: Secuenciar en una máquina 4 trabajos con el objetivo de minimizar el makespan, si los tiempos de proceso son:p1=4 p2=10 p3=6 p4=18
56
57
Secuencia [1,2,3,4]
Secuencia [3,4,1,2]
Secuencia [4,2,1,3]
38
38
38
M1
M1
M1
Cuando no hay ninguna restricción la resolución de este problema es inmediato
Cmax=Σ pj
Una máquina 1||Cmax
58
Una máquina 1||ΣCj
Flowtime o tiempo de flujo para un trabajo j de una secuencia dada es el tiempo que transcurre desde que entra el primer trabajo de la secuencia hasta que sale el trabajo j-ésimo
El tiempo de flujo total es: F=ΣCj = C1+…+Cn
El problema se denota 1||ΣCj
Una máquina 1||ΣCj
Ejemplo: Secuenciar en una máquina 4 trabajos con el objetivo de minimizar el tiempo de flujo total, si los tiempos de proceso son:p1=4 p2=10 p3=6 p4=18
59
60
Una máquina 1||ΣCj
Se observa que en una máquina el tiempo de flujo es Cj=p[1]+…+p[j]
La regla SPT (Shortest Processing Time) es óptima para este problema.
SPT: secuenciar primero el trabajo con menor tiempo de proceso
p[1]<p [2] <…<p[n]
ΣCj=C1+…
+Cn=
p[1]+
p[1]+p[2]+
p[1]+p[2]+p[3]+
+……+p[1]+p[2]+…… +p[n]
np[1]+ (n-1)p[2]+……+p[n]
Una máquina 1||ΣCj
Regla SPT para el ejemplo anterior
61
1 3 42
Secuencia [1,2,3,4]
Secuencia [3,4,1,2]
Secuencia [4,2,1,3]
Secuencia optima
ΣCj
=72
ΣCj =82
ΣCj
=96
ΣCj = 120
62
Una máquina 1||ΣwjCj
Tiempo de flujo total ponderado: Fw=ΣwjCj = w1C1+…+wnCn
Es la extensión del problema anterior El problema se denota 1||ΣwjCj
El peso es un factor de importancia añadido a cada trabajo j.
63
Una máquina 1||ΣwjCj
Ejemplo: Secuenciar en una máquina 4 trabajos minimizando el tiempo de flujo total ponderado, si los tiempos de proceso y los pesos asociados son:p1=3 p2=6 p3=6 p4=5
w1=0 w2=18 w3=12 w4=8
64
Una máquina 1||ΣwjCj
La regla WSPT (Weighted Shortest Processing Time) es óptima para este problema.
Esta regla secuencia los trabajos según:w[1]/p[1] > w[2]/p[2] > …> w[n]/p[n]
65
Una máquina 1||ΣwjCj
Ejemplo: Secuenciar en una máquina 4 trabajos minimizando el tiempo de flujo total ponderado, si los tiempos de proceso y los pesos asociados son:p1=3 p2=6 p3=6 p4=5
w1=0 w2=18 w3=12 w4=813 42
Secuencia [1,2,3,4]
Secuencia optima
ΣwjCj
=388
ΣwjCj
=502
ΣwjCj
=520
Secuencia [3,4,1,2]
66
Una máquina 1||Lmax
El retraso para un trabajo j es la diferencia entre el instante en el que el trabajo sale del sistema y la fecha de entrega. Lj = Cj-dj
Minimizar el máximo retraso es :Min Lmax=Min max(Cj – dj)
El problema se denota 1||Lmax
Una máquina 1||Lmax
Ejemplo: Secuenciar en una máquina 4 trabajos con el objetivo de minimizar el máximo retraso, si los tiempos de proceso y las fechas de entrega son:p1=4 p2=10 p3=6 p4=18
d1=8 d2=12 d3=11d4=10
67
68
Una máquina 1||Lmax
La regla EDD (Earliest Due Date) es óptima para este problema.
EDD: secuenciar primero el trabajo con menor fecha de entrega d[1]<d[2]<…<d[n]
Una máquina 1||Lmax
Ejemplo: Secuenciar en una máquina 4 trabajos con el objetivo de minimizar el máximo retraso, si los tiempos de proceso y las fechas de entrega son:p1=4 p2=10 p3=6 p4=18
d1=8 d2=12 d3=11d4=10
69
1 34 2
Lmax = max {C[1]-d[1], C[2]-d[2], C[3]-d[3], C[4]-d[4]} =
max {4-8,14-12,20-11,38-10} = max{-4,2,9,28}
= 28
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
70
71
Máquinas en paralelo
Máquinas iguales en paralelo (Pm) Los trabajos pueden ser procesados en cualquiera de
las máquinas P. ej. Un consultorio con varias consultas de médicos.
Las cajas de un supermercado.
Máquinas en paralelo
Pm|β|γ Generalización del caso con una máquina Caso especial del taller de flujo flexible Es un caso muy común en la vida real Un ejemplo puede ser las cajas de un
supermercado
72
Máquinas en paralelo Pm||Cmax
Este problema es NP La regla LPT es un algoritmo que proporciona
buenas soluciones, con un determinado error en comparación con la óptima (si ésta se puede hallar).
LPT: Longest Processing Time first. LPT: Asignar primero los m trabajos con mayor
tiempo de proceso a las m máquinas. Cuando una máquina se quede libre, asignar el siguiente trabajo a dicha máquina, hasta que se hayan asignado todos.
73
74
Ejemplo: Secuenciar en 3 máquinas en paralelo 9 trabajos con los siguientes tiempos de proceso:p1=3 p4=10 p7=6
p2=18 p5=9 p8=9
p3=4 p6=15 p9=10
Máquinas en paralelo Pm||Cmax
75
M1
M2
M3
6 3
7
2
5
194
8
29
Máquinas en paralelo Pm||Cmax
La regla LPT da una solución buena, pero no la óptimap1=3 p4=10 p7=6
p2=18 p5=9 p8=9
p3=4 p6=15 p9=10
76
M1
M2
M3
6
372
5
19
4 8
28
Máquinas en paralelo Pm||Cmax
Existe una cota para la relación entre la solución óptima y la que da la regla, por lo que sabemos cómo es de buena nuestra solución
Cmax(LPT)/Cmax(OPT) ≤ 4/3 – 1/3m 29 ≤ (4/3 – 1/9)* Cmax(OPT) = 1.22* Cmax(OPT)
Máquinas en paralelo Pm||ΣCj
Este problema es P La regla SPT es óptima. SPT: Shortest Processing Time first. SPT: Asignar primero los m trabajos con menor
tiempo de proceso a las m máquinas. Cuando una máquina se quede libre, asignar el siguiente trabajo a dicha máquina, hasta que se hayan asignado todos.
Ejercicio: Resolver el problema con los datos del anterior para este caso.
77
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
78
79
Taller de flujo
Taller de flujo. Flow Shop. Máquinas en serie (Fm)
Todos los trabajos deben de pasar por todas las máquinas, con la misma ruta, empezando por una primera hasta la última
Cuando un trabajo termina en una máquina, espera en la cola de la siguiente si esta está ocupada. Las salidas de los trabajos de las colas se determinan con la regla FIFO.
80
Preparación Horno Presentación
Trabajos Máquinas
Taller de flujo
El aprendiz de Adrià es un problema de tipo flowshop
Taller de flujo F2||Cmax
El algoritmo de Johnson es óptimo para este problema
Sea C1={j/ p1j<p2j} y C2={j/ p1j>p2j} Ordenar C1 según la regla SPT para p1j
Ordenar C2 según la regla LPT para p2j
La secuencia [SPT(1)-LPT(2)] es óptima para nuestro problema
81
Taller de flujo F2||Cmax
Ejemplo: Secuenciar en un taller de flujo de dos máquinas 5 trabajos, con los siguientes tiempos de proceso:
Dar el valor del makespan. Hallar el makespan para otra secuencia cualquiera y comprobar que da igual o peor que para la secuencia dada por el algoritmo de Johnson.
82
j 1 2 3 4 5
p1j 3 4 5 1 2
p2j 2 4 1 3 4
Taller de flujo F2||Cmax
Secuencia óptima: [4,5,2,1,3]
Otra secuencia [5,1,3,4,2]
83
M1
M2
1 2 3 4 5
16
M1
M2
19
Taller de flujo Fm|prmu|Cmax
Fm||Cmax es NP para más de dos máquinas Fm|prmu|Cmax es NP también
Numerosos métodos heurísticos proporcionan buenas soluciones para estos problemas
La heurística constructiva NEH da buenas soluciones para Fm|prmu|Cmax en tiempos de cómputo razonables
84
Taller de flujo Fm|prmu|Cmax
NEH Paso 1: Ordenar los trabajos en función de la suma
de los tiempos de proceso (pj= ∑ipij) de forma descendente. La secuencia obtenida es la secuencia inicial.
Paso 2: Tomar los dos primeros trabajos de la secuencia inicial y seleccionar de los dos órdenes posibles el que de mejor valor de Cmax
Paso 3: Para cada trabajo j de la secuencia inicial, hallar el makespan de las j posibles secuencias obtenidas tras insertar el trabajo en todas las posiciones posibles, seleccionando aquella que de menor valor.
85
Taller de flujo Fm|prmu|Cmax
Ejemplo: Secuenciar en 3 máquinas en serie 3 trabajos con los siguientes tiempos de proceso (pij, 1≤i≤m, 1≤j≤n)
p11=3p21=4 p31=2 1
p12=2p22=1 p32=4 2
p13=4p23=5 p33=4 3
86
Taller de flujo Fm|prmu|Cmax
Ejemplo: Secuenciar en 3 máquinas en serie 3 trabajos con los siguientes tiempos de proceso (pij, 1≤i≤m, 1≤j≤n)
p11=3p21=4 p31=2 1
p12=2p22=1 p32=4 2
p13=4p23=5 p33=4 3
p1=3+4+2=9 p2=2+1+4=7p3=4+5+4=13
Secuencia inicial: [3,1,2]
87
Taller de flujo Fm|prmu|Cmax
88
M1
M2
15
16
M3
[3,1]
[1,3]M1
M2
M3
Taller de flujo Fm|prmu|Cmax
89
17
19
[3,1,2]
M1
M2
M3
M1
M2
M3
[2,3,1]
19
[3,2,1]
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
90
91
Trabajo1
Trabajo2
Trabajo3
Taller de trabajo
Taller de trabajo. Job shop. Rutas predefinidas (Jm)
Los trabajos deben pasar por todas las máquinas, y las rutas están predefinidas.
Taller de trabajo J2||Cmax
Se puede reducir al problema F2||Cmax, por lo que es resoluble en tiempo polinomial
J1= {j/ M1-M2} y J2= {j/ M2-M1} Ordenar los trabajos de J1 mediante el algoritmo de
Johnson. Ordenar los trabajos de J2 mediante el algoritmo de
Johnson intercambiando la máquinas, es decir, tomando como máquina 1 la máquina 2 y viceversa.
Secuenciar los trabajos de J= J1 U J2 en cada una de las máquinas, priorizando los trabajos de J1 en la máquina 1, y los trabajos de J2 en la máquina 2.
92
Taller de trabajo J2||Cmax
Ejemplo: Secuenciar en un taller de trabajo de dos máquinas 5 trabajos, con los siguientes tiempos de proceso y rutas de paso por las máquinas:
93
j 1 2 3 4 5
p1j 3 4 5 1 2
p2j 2 4 1 3 4
Ruta M2-M1 M2-M1 M1-M2 M1-M2 M1-M2
Taller de trabajo J2||Cmax
J1={3,4,5}: C1={4,5}, C2={3} [4,5,3] J2={1,2}: C1={1,2}, C2=Ø [1,2]
94
j 1 2 3 4 5
p1j 3 4 5 1 2
p2j 2 4 1 3 4
Ruta M2-M1 M2-M1 M1-M2 M1-M2 M1-M2
M1
M2
15
[4,5,3,1,2]
[1,2,4,5,3]
Taller de trabajo Jm||Cmax
Jm||Cmax es NP pq es una generalización de Fm||Cmax, y éste último es NP
La heuristica Shifting Bottleneck proporciona buenos resultados. Este método reduce el problema en varios subproblemas 1|rj|Lmax mediante un procedimiento basado en caminos críticos (que indican la localización del cuello de botella). Como 1|rj|Lmax es NP, un método de Branch and Bound que proporciona buenas soluciones es aplicado para cada subproblema de Jm||Cmax
95
Índice
Secuenciación Entornos máquina Condiciones del sistema Función Objetivo Una máquina Máquinas en paralelo Taller de flujo Taller de trabajo Taller abierto Conclusiones
96
97
Taller abierto
Taller abierto. Open shop. Rutas a determinar (Om)
Los trabajos deben pasar por todas las máquinas, pero no hay restricción en la ruta. Cada trabajo puede pasar primero por la máquina que mejor convenga.
Taller abierto O2||Cmax
La Regla LAPT (Longest Alternate Processing Time first) es óptima para este problema.
Cuando una máquina está libre, seleccionar el trabajo con el mayor tiempo de proceso en la otra máquina.
Al principio, puede que un trabajo pueda ser seleccionado para ser secuenciado primero en las dos máquinas. En este caso da igual la máquina en el que éste sea procesado.
Cuando una máquina está libre, los trabajos que ya han sido completados en la otra máquina tienen prioridad cero para procesarse en la máquina libre.
Dos trabajos que ya han sido procesados en una de las máquinas tienen la misma prioridad para la otra.
98
Taller abierto O2||Cmax
Ejemplo: Secuenciar en un taller abierto de dos máquinas 5 trabajos, con los siguientes tiempos de proceso:
99
j 1 2 3 4 5
p1j 3 4 5 1 2
p2j 2 4 1 3 4
Taller abierto O2||Cmax
El trabajo con mayor tiempo de proceso es el trabajo 3 en la máquina 1, por lo tanto es secuenciado primero en la máquina 2.
100
M1
M2
15
j 1 2 3 4 5
p1j 3 4 5 1 2
p2j 2 4 1 3 4
Taller abierto Om||Cmax
Es NP Si los tiempos de proceso son 0 ó 1, el
problema es resoluble en tiempo polinomial Om|prmp|Cmax es resoluble en tiempo
polinomial también
101
Conclusiones
Hay algunos problemas de secuenciación que se pueden resolver mediante algoritmos que proporcionan la solución óptima
La mayoría de los problemas son NP:
102
1 Pm Fm Jm Om
1||T P2||Cmax F2||∑Cj Jm||Cmax O2||∑Cj
1||∑wjUj P2||∑wjCj
F2||Lmax O2||Lmax
Paz Pérez González
Departamento de Organización Industrial y Gestión de Empresas
http:// taylor.us.es/paz
103