Modelos de secuenciación de tareas en máquinas Andrés Ramos Universidad Pontificia Comillas

http://www.iit.comillas.edu/aramos/ [email protected]

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

1

Modelos de secuenciación de tareas en máquinas 1.

Introducción. Datos, hipótesis, medidas, criterios.

2.

Secuenciación en una máquina

3.

Secuenciación en varias máquinas

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

2

Objetivo Encontrar secuencia en la que los trabajos pasan por las máquinas, tal que a) bajo ciertas hipótesis, sea una planificación compatible con restricciones tecnológicas, es decir, sea factible b) óptima respecto a algún criterio

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

3

Datos • Job-shop: n trabajos o tareas procesadores {M 1 ,..., M m }.

{J 1 ,..., J n }

han ser procesados por m máquinas o

• Cada trabajo ha de pasar por cada máquina una y sólo una vez. • Operación oij : operación de procesar el trabajo i en la máquina j . • Restricciones tecnológicas: condiciones de orden en las operaciones de un trabajo. • Caso general: cada trabajo tiene su propio orden sin relación con el orden de otros. • Flow-shop: el orden es el mismo para todos los trabajos.

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

4

Más datos • Tiempo de proceso de oij : pij (incluye tiempo de ajuste de máquina o de transporte hasta la máquina). • Release date o ready time: ri instante en que el trabajo J i está listo para ser procesado o llega el pedido. • Due date: d i fecha de entrega de J i • ai amplitud del periodo planificación trabajo J i o plazo de entrega: ai = d i − ri

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

5

Ejemplo Se desean fabricar tres piezas de madera: • una escultura, un candelabro y una copa. Los recursos que se utilizan son: • banco de trabajo, torno y sala de barnizado. Los datos de que se dispone son los siguientes: • Tiempo en minutos necesario para realizar cada operación • Fecha de entrega también en minutos • Orden en que se deben realizar las operaciones para cada pieza. Banco Torno Sala barnizado Escultura 60 20 Candelabro 45 15 Copa 25 15 25

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

Fecha entrega 60 90 120

Orden B-S T-S T-B-S

6

Hipótesis del job-shop (i) 1.

Cada trabajo es una entidad: no se pueden realizar dos operaciones de un mismo trabajo a la vez.

2.

Cada trabajo incluye una y sólo una operación en cada máquina (en total m operaciones).

3.

No preemption (no se permite interrupción de operaciones).

4.

No cancelación (no se permite cancelación una vez iniciada).

5.

Tiempos de proceso independientes de la secuencia seguida.

6.

Se permite inventario intraproceso (las operaciones pueden esperar hasta que se acabe otra operación en la siguiente máquina).

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

7

Hipótesis del job-shop (ii) 7.

Sólo hay una máquina de cada tipo.

8.

Las máquinas pueden estar inactivas.

9.

Las máquinas no pueden procesar más de una operación a la vez.

10. Las máquinas están disponibles todo el periodo de planificación. 11. Las restricciones tecnológicas son conocidas e inmutables. 12. No existe aleatoriedad: conocidos y fijos todos los datos (número de trabajos, número de máquinas, tiempos de proceso).

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

8

Medidas de desarrollo • Wik tiempo de espera del trabajo J i antes de realizarse su k -ésima operación (no necesariamente en máquina k ) • Wi • Ci

m

tiempo total de espera del trabajo J i : Wi = ∑Wik k =1

m

instante de cumplimentación o suministro de J i : Ci = ri + ∑ (Wik + pij ( k ) ) . pij ( k ) es k =1

tiempo de proceso de k -ésima operación del trabajo J i que se realiza en máquina j • Fi tiempo de proceso o de cumplimentación (flow time) de J i : Fi = Ci − ri • Li desviación de J i respecto a su due date: Li = Ci − d i . Puede ser + o – • Ti demora en la entrega del trabajo J i : Ti = max {Li ,0} • Ei • Ij

adelanto en la entrega del trabajo J i : Ei = max {− Li ,0}

n

tiempo inactivo (idle) de la máquina M j : I j = Cmax − ∑ pij .

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

i =1

9

1 n Notación: X = ∑ X i media, X max = max { X 1 ,..., X n } máximo. n i =1

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

10

Ejemplo M

1

M

2

o ij ( m − 1 ) o ij ( m ) W im

M

o ij ( 2 )

j

W i2

M M

p ij ( 2 )

o ij (1 )

m −1 m

p ij ( m )

W i 1 p ij (1 )

o ij ( 3 )

ri

di

ai Fi

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

Ci

Li = Ti

11

Criterios (i) Criterios basados en los instantes de finalización F : tiempo medio de proceso • Fmax : tiempo máximo de proceso • Cmax : (make-span) tiempo máximo de cumplimentación o tiempo total de producción • C : tiempo medio de cumplimentación (minimizar F equivalente a minimizar C ) Pueden ponderarse estas medidas en función de importancia de artículos. Criterios basados en los plazos de entrega (due dates) Lmax : máxima desviación • L : media de desviaciones (positivas y negativas) Tmax : máximo retraso • T : media de retrasos • Minimizar número de trabajos fuera de plazo (aterrizaje de aviones)

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

12

Criterios (ii) Criterios basados en el nivel de inventario y el coste de utilización • • • • •

1 Cmax NW (t ) número de trabajos en espera en instante t , NW ( t ) = NW (t ) dt Cmax ∫0 1 Cmax NU (t ) número de trabajos en curso en instante t , NU ( t ) = NU (t ) dt Cmax ∫0 Minimizar número medio trabajos acabados (reduce coste inventario productos acabados) Maximizar número medio de trabajos que realmente están siendo procesados (uso de las máquinas) Minimizar la media o el máximo tiempo inactivo de las máquinas

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

13

Relaciones entre las medidas de desarrollo (i) a) Equivalentes (dan la misma solución) C , F , W y L b) No equivalentes las medidas análogas a las anteriores pero para su valor máximo, excepto: b.1) Si release dates=0 para todos los trabajos, equivalentes Cmax y Fmax . b.2)

Si due dates mismas para todos los trabajos, equivalentes Cmax y Lmax .

c) Si óptima para Lmax entonces también para Tmax , al revés no siempre. d) Equivalentes Cmax , N p (número medio de trabajos siendo realmente procesados) e I n 1 m 1 m (desocupación media de las máquinas I = ∑ I j = ∑ (Cmax − ∑ pij ) ). m j =1 m j =1 i =1

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

14

Relaciones entre las medidas de desarrollo (ii) e) Equivalentes NU y C / Cmax . f) Equivalentes NW y W / Cmax . g) En una sola máquina equivalentes C , F , W , L , NU y NW .

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

15

Secuenciación en una máquina (i) Hipótesis: • Instantes de comienzo ri = 0 ∀i y m = 1 . Resultados: • Para todo objetivo regular (no decreciente con los instantes de cumplimentación), existe una planificación óptima en la que la máquina no está inactiva • Permitir la interrupción no puede mejorar ninguna planificación. • La solución es una programación permutación. ( Cmax = Fmax son los mismos)

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

16

Secuenciación en una máquina (ii) Posibles permutaciones que optimizan algún criterio a) Minimización del tiempo medio de proceso, F ( C , W , L, N U , N W ) Programación según tiempo de proceso creciente b) Minimización de máxima desviación respecto a fechas de entrega, Lmax ( Tmax ) Programación de fecha de entrega creciente c) Minimización de número de trabajos demorados: algoritmo de Moore y Hodgson 1. Obtener programación de fecha de entrega creciente 2. Encontrar primer trabajo demorado en secuencia actual J i ( l ) . Si no, ir a 4. 3. Encontrar trabajo mayor tiempo proceso delante de J i ( l ) , incluido J i ( l ) , y rechazarlo. Ir a 2. 4. Secuencia óptima: actual y añadir al final trabajos rechazados sin orden. Esos trabajos rechazados serán los únicos demorados.

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

17

Secuenciación en una máquina (iii) • Condiciones precedencia entre trabajos: Evitar reformulando fechas entrega. Si no es posible: utilizar algoritmos específicos. • Problema de cadenas productos: K cadenas de n1 ,..., nK trabajos: con orden y proceso seguido → ¿Cómo secuenciar las cadenas? ni

pij : tiempo j -ésimo trabajo de la cadena i -ésima → pi′ = ∑ pij tiempo cadena. j =1

Secuencia óptima para minimizar el tiempo medio de proceso: p′ p′ p′ Ordenar por tiempo medio de proceso creciente: i (1) ≤ i (2) ≤ ⋯ ≤ i ( K ) . ni (1) ni (2) ni ( K )

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

18

Secuenciación en una máquina. Programación dinámica (i) • Otros métodos: programación entera, dinámica, etc. 1 4 Ejemplo: programar 4 trabajos para minimizar retraso medio ∑ max {Ci − d i ,0} 4 i =1 resuelto por programación dinámica

J1 J 2 J 3 J 4 Trabajos Tiempos proceso 8 6 10 7 Fecha entrega 14 9 16 16 Etapas: orden secuencia.

Decisiones: qué trabajo programar. 4

Estados: trabajos ya programados. Objetivo:

∑ max {C i =1

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

i

− d i ,0}

19

Secuenciación en una máquina. Programación dinámica (ii) Etapa 4 Decisiones J 14 J 24 J 34 J 44 Óptimo Objetivo Estados – – – 31–16 J 44 15 J1, J 2 , J 3 – – 31–16 – 15 J1, J 2 , J 4 J 34 – 31–9 – – 22 J1, J 3 , J 4 J 24 – – 17 J 2 , J 3 , J 4 31–14 – J 14

Etapa 3 Decisiones Óptimo Objetivo J 13 J 23 J 33 J 43 Estados – – 24–16+15 21–16+15 20 J1, J 2 J 43 – 24–9+15 – 25–16+22 30 J1, J 3 J 23 – 21–9+15 25–16+22 – 27 J1, J 4 J 23 – – 23–16+17 24 J 2 , J 3 24–14+15 J 43

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

20

J2, J4 J 3, J 4

21–14+15 – 23–16+17 25–14+22 23–9+17 –

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

– –

J 13 J 23

22 31

21

Secuenciación en una máquina. Programación dinámica (iii) Etapa 2 Decisiones Óptimo Objetivo J 12 J 22 J 32 J 42 Estados – 14–9+20 18–16+30 0+27 25 J1 J 22 14–14+20 – 16–16+24 0+22 20 J2 J 12 18–14+30 16–9+24 – 17–16+31 J 22 31 J3 15–14+27 13–9+22 17–16+31 – 26 J4 J 22

Etapa 1 Decisiones

J 11 J 21 J 31 J 41 Óptimo Objetivo 0+25 0+20 0+31 0+26 20 J 21

La secuencia óptima es ( J 21 , J 12 , J 43 , J 34 ) , con un retraso medio de 20/4=5 unidades de tiempo.

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

22

Secuenciación en varias máquinas (i) Hipótesis: • Instantes de comienzo ri = 0, i = 1,..., n . • Flow-shop 2 máquinas y minimizar máximo tiempo de cumplimentación Cmax : n trabajos, 2 máquinas, todos por máquina 1 y luego por la 2 en el mismo orden. Óptimo: buscar entre programaciones permutación.

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

23

Secuenciación en varias máquinas. Algoritmo de Johnson (i) ai = pi1 : tiempo proceso J i en máquina 1. bi = pi 2 : tiempo proceso J i en máquina 2 1. k = 1 y l = n . 2. Lista actual trabajos no programados = {J 1 , J 2 ,..., J n } 3. Encontrar mínimo de los ai y bi de trabajos no programados. 4. Si mínimo es un ai : 4.1. Programar J i en k -ésima posición, borrar J i lista trabajos no programados 4.2. k ← k + 1. Ir a 6 5. Si mínimo es un bi : 5.1. Programar J i en l -ésima posición, borrar J i lista trabajos no programados 5.2. l ← l − 1 . Ir a 6 6. Si hay trabajos sin programar ir a 3. En otro caso, parar.

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

24

Secuenciación en varias máquinas. Algoritmo de Johnson (ii) • Extensión: minimizar tiempo máximo cumplimentación con 4 tipos de trabajos tipo A: sólo por la máquina M 1 tipo B: sólo por la máquina M 2 tipo C: primero máquina M 1 y luego M 2 tipo D: primero máquina M 2 y luego M 1 1. Secuenciar tipo A cualquier orden → SA 2. Secuenciar tipo B cualquier orden → SB 3. Secuenciar tipo C algoritmo de Johnson → SC 4. Secuenciar tipo D algoritmo de Johnson (cambiar máquinas) → S D Orden Programación óptima: Máquina M1 ( SC , S A , S D ) M2 ( S D , S B , SC )

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

25

Secuenciación en varias máquinas. Optimización lineal entera (i) 2 trabajos, 3 máquinas. Objetivo: minimizar máxima demora.

M 1 M 2 M 3 Due dates Orden J 1 10 15 18 M1 M 2 M 3 50 J 2 20 12 15 M 3 M 2 M1 55 • Variables decisión: Tij → instante iniciar operación trabajo J i en máquina M j • Restricciones tecnológicas: Si J i va a antes en máquina M j que en M j′ , Tij + pij ≤ Tij′ :

T11 + 10 ≤ T12 T12 + 15 ≤ T13 T23 + 15 ≤ T22 T22 + 12 ≤ T21

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

26

Secuenciación en varias máquinas. Optimización lineal entera (ii) - No simultaneidad en una máquina: J i , J k y M j , Tij + pij ≤ Tkj Tkj + pkj − Tij ≤ M (1 − δ ikj ) Equivale , Tij + pij − Tkj ≤ M δ ikj 1 si J i se procesa después de J k en la máquina M j δ ikj =  : 0 en caso contrario 

o Tkj + pkj ≤ Tij .

M1 M2 M3 T11 + 10 − T21 ≤ M (1 − δ 211 ) T12 + 15 − T22 ≤ M (1 − δ 212 ) T13 + 18 − T23 ≤ M (1 − δ 213 ) T21 + 20 − T11 ≤ M δ 211

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

T22 + 12 − T12 ≤ M δ 212

T23 + 15 − T13 ≤ M δ 213

27

Secuenciación en varias máquinas. Optimización lineal entera (iii) - Objetivo: minimizar la máxima demora. Variables demora trabajo Ti , m(i ) Tim ( i ) + pim ( i ) − Ti ≤ d i y Ti ≤ Tmax :

última

operación

trabajo

Ji ,

entonces

min Tmax T1 ≤ Tmax T2 ≤ Tmax T13 + 18 − T1 ≤ 50 T21 + 20 − T2 ≤ 55 - Carácter de las variables: Tij ≥ 0, Ti ≥ 0, δ ikj ∈ {0,1}, Tmax ≥ 0

MODELOS DE SECUENCIACIÓN EN MÁQUINAS

28