Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giuseppe Bruno » 18.Flow Shop Scheduling


Argomenti della lezione

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

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)

Nel Flow Shop tutti i jobs sono costituiti dalla stessa successione di operazioni. Le operazioni quindi seguono tutte lo stesso percorso dando luogo ad un flusso (flow) unico.

Le schedulazioni Flow Shop sono tipiche delle produzioni caratterizzate da volumi elevati e notevole livello di standardizzazione (es: catena di montaggio).

Poiché ogni operazione è eseguita su una macchina diversa nella terna (i,j,k) si può porre j=k. Pertanto ciascuna operazione può essere indicata con due soli indici (i, j).


Definizioni generali (segue)

Tra le soluzioni di un Flow Shop vi sono quelle caratterizzate dalla stessa successione delle operazioni su ogni macchina (soluzioni con permutazione).

In questo caso bisogna definire la successione dei jobs che si ripete su tutte le macchina; il numero di possibili soluzioni è quindi dato da n!.

In Figura è rappresentata una soluzione con permutazione; la tempificazione è tale che la non vi è sovrapposizione tra operazioni dello stesso job.


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 || Cmax
Problema polinomiale risolvibile con la regola di Johnson.

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

Il problema F2||Cmax

Regola di Johnson

Siano
pj1 tempo processamento dell’operazione j sulla prima macchina;
pj2 tempo processamento dell’operazione j sulla seconda macchina.

Si individuino gli insiemi di job

L’={j∈J: pj1pj2}: 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||Cmax (segue)


Il problema F2||Cmax (segue)


Il problema Fm||Cmax (segue)


Il problema Fm||Cmax (segue)


Il problema Fm||Cmax (segue)


Il problema Fm||Cmax (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||Cmax in un problema dinamico su macchina singola 1|rj|Tmax nel tentativo di individuare una soluzione con un prefissato C”max.

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

L’approccio si articola nei passi indicati di seguito.

Il problema Fm||Cmax (segue)

Approccio bottleneck

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

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

dj= Cmax- tj: tempo massimo di completamento che l’operazione del job j sulla macchina m* deve avere per evitare che si abbia Cmax> Cmax;

2. Risoluzione problema di scheduling 1|rj|Tmax
Si risolve un problema 1|rj|Tmax sulla macchina m* assumendo pj=pjm*, rj=hj e dj= C”max- tj .
Se la soluzione corrispondente alla permutazione così ottenuta migliora il makespan si sostituisce alla soluzione corrente.

Il problema Fm||Cmax (segue)


Il problema Fm||Cmax (segue)


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion