Giuseppe Bruno » 18.Flow Shop Scheduling

Argomenti della lezione

• Definizioni generali
• Il problema F2||C_max
• Il problema Fm||C_max

Definizioni generali

Nei problemi multifase ogni job è individuato da una sequenza di operazioni, tali che due operazioni consecutive sono eseguite su macchine diverse.

Con la terna (i, j, k) si indicherà l’operazione j relativa al job i da eseguirsi sulla macchina k. Ad esempio (1,2,4) indica l’operazione 2 del job 1 sulla macchina 4.

Due operazioni consecutive dello stesso job i sono indicate da (i, j, k) e (i, j+1, k‘) dovendo essere k≠k’.

Definizioni generali (segue)

I problemi fondamentali di tipo multifase sono i problemi

Open shop
Tra le operazioni di ciascun job non ci sono vincoli di precedenza.

Flow Shop
Tutti i jobs sono costituiti dalla stessa successione di operazioni.

Job Shop
I jobs possono essere costituiti da un diverso numero di operazioni e/o da diverse successioni di operazioni.

Definizioni generali (segue)

I problemi Flow Shop sono in generale molto complessi.

Con riferimento al classico problema con obiettivo Cmax si analizzeranno i seguenti problemi:

F2 || C_max
Problema polinomiale risolvibile con la regola di Johnson.

Fm || C_max (m≥3)
Problema NP-hard.

Il problema F2||C_max

Regola di Johnson

Siano
p_j1 tempo processamento dell’operazione j sulla prima macchina;
p_j2 tempo processamento dell’operazione j sulla seconda macchina.

Si individuino gli insiemi di job

L’={j∈J: p_j1≤p_j2}: jobs con tempi di processamento sulla prima macchina inferiori o uguali a quelli sulla seconda macchina;
L”=J-L’: jobs che richiedono, al contrario, tempi di processamento sulla seconda macchina inferiori a quelli sulla prima macchina.

Si effettui una schedulazione con permutazione secondo l’ordine L’→L”. In particolare

• i jobs di L’ saranno schedulati secondo la regola SPT considerando i tempi di processamento sulla prima macchina;
• i jobs di L” saranno schedulati secondo la regola LPT considerando i tempi di processamento sulla seconda macchina.

Il problema F2||C_max (segue)

Il problema F2||C_max (segue)

Il problema Fm||C_max (segue)

Il problema Fm||C_max (segue)

Il problema Fm||C_max (segue)

Il problema Fm||C_max (segue)

Approccio bottleneck

Si determina la soluzione con riferimento ad una macchina che rappresenta un collo di bottiglia del processo.

Si supponga di aver individuato la macchina bottleneck m* scegliendo, ad esempio, quella per la quale si registra la somma maggiore dei tempi di processamento

L’approccio trasforma opportunamente il problema originario Fm||C_max in un problema dinamico su macchina singola 1|r_j|T_max nel tentativo di individuare una soluzione con un prefissato C”_max.

C”_max può essere posto pari a C’_max-1 essendo C‘_max il valore di funzione obiettivo ottenuto con un’altra euristica.

L’approccio si articola nei passi indicati di seguito.

Il problema Fm||C_max (segue)

Approccio bottleneck

1. Calcolo parametri delle operazioni
Per ogni job j si valutano i seguenti parametri:
h_j:somma tempi di processamento operazioni che precedono m*;

t_j: somma tempi di processamento operazioni che seguono m*;

d_j= C”_max- t_j: tempo massimo di completamento che l’operazione del job j sulla macchina m* deve avere per evitare che si abbia C_max> C”_max;

2. Risoluzione problema di scheduling 1|r_j|T_max
Si risolve un problema 1|r_j|T_max sulla macchina m* assumendo p_j=p_jm*, r_j=h_j e d_j= C”_max- t_j .
Se la soluzione corrispondente alla permutazione così ottenuta migliora il makespan si sostituisce alla soluzione corrente.

Il problema Fm||C_max (segue)

Il problema Fm||C_max (segue)