Giuseppe Bruno » 19.Job Shop Scheduling

Argomenti della lezione

• Definizioni generali
• Un problema job shop su due macchine
• Il problema job shop su m macchine

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:

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

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

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

Definizioni generali (segue)

Siano dati

• n jobs (i=1,..,n) e m macchine (k=1,..,m);
• Ogni job i è composto da qi operazioni in serie (ogni coppia di operazioni consecutive viene effettuata su macchine distinte).

Per definire un Job Shop è necessario fornire:

• una matrice dei tempi di processamento P={p_ij},
  • p_ij tempo di processamento dell’operazione j del job i;
• una matrice di routing R={r_ij},
  • r_ij macchina su cui deve essere eseguita l’operazione j del job i.

Definizioni generali (segue)

Definizioni generali (segue)

Una soluzione di un problema di scheduling può essere:

Senza ritardo
Se non si verifica mai che una macchina, pur potendo effettuare un’operazione, resti inattiva.

Attiva
Se, per anticipare il completamento di una qualsiasi operazione, si provoca un ritardo nel completamento di altre operazioni.

Non attiva
Se non è attiva.

Una soluzione senza ritardo è anche attiva. Una soluzione attiva può essere con ritardo.

La soluzione ottima di un problema di scheduling è una soluzione attiva ma non necessariamente senza ritardo.

Definizioni generali (segue)

Definizioni generali (segue)

Definizioni generali (segue)

I problemi Job Shop sono in generale molto complessi.

Con riferimento al problema con obiettivo C_max si analizzeranno i problemi:

J2 |n_j≤2| C_max
(Job Shop su 2 macchine in cui ogni job è costituito al massimo da 2 operazioni)
Problema polinomiale risolvibile con la regola di Jackson.

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

Un problema job shop su due macchine

Regola di Jackson per J2 |n_j≤2| C_max

Si suddividono i jobs in 4 sottoinsiemi:

J₁₂ jobs che passano per la macchina 1 e poi per la macchina 2;
J₂₁ jobs che passano per la macchina 2 e poi per la macchina 1;
J₁ jobs da processare solo sulla macchina 1;
J₂ jobs da processare solo sulla macchina 2;

e si assegnano alle macchine secondo il seguente ordine:

macchina 1: J₁₂, J₁, J₂₁;

macchina 2: J₂₁, J₂, J₁₂;

Poiché i jobs di J₁₂ (J₂₁) sono tutti caratterizzati dalla stessa sequenza di operazioni 1→2 (2→1) per la loro schedulazione è possibile utilizzare la regola di Johnson per un problema F2||C_max.

Un problema job shop su due macchine (segue)

Un problema job shop su m macchine

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Metodo per la generazione di soluzioni attive
Sintesi della procedura

1. Inizializzazione
Si pone t=1, S₁=Ø; O₁ è costituito dall’insieme delle prime operazioni di ogni job (O₁={(i,1,k): i∈J}.

2. Selezione nuovo elemento da aggiungere alla soluzione parziale
Si calcola C(O_t)=min_(i,j,k)∈Ot {r_ijk+p_ijk}
Si indica con k‘ la macchina corrispondente a C(O_t) e con O‘_t={(i,j,k’): (i,j,k’)∈O_t, r_ijk’<C(O_t)}
Si schedula al più presto un’operazione (i’,j’,k’)∈O_t a caso o secondo un criterio prestabilito.
Si pone S_t+1=S_t∪{(i’,j’,k’)}, O_t+1=O_t-(i’,j’,k’)}∪{i’,j’+1,k’}

3. Criterio di arresto
Se la schedulazione è completa (O_t =Ø), l’algoritmo si arresta; altrimenti si ritorna al passo 2.

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Un problema job shop su m macchine (segue)

Individuazione e schedulazione operazione che assicura la realizzazione di una soluzione attiva.

Un problema job shop su m macchine (segue)

Metodo per la generazione di soluzioni senza ritardo

Una schedulazione senza ritardo, oltre ad essere attiva, non deve lasciare in nessun istante una macchina inattiva nel caso tale macchina possa processare qualche operazione.

La procedura è simile a quella per le soluzioni attive con la differenza che, all’interno di O_t, si seleziona l’operazione con il tempo di rilascio minore e si schedula a partire da esso: in questo modo la macchina non è mai lasciata inattiva.

2. Selezione nuovo elemento da aggiungere alla soluzione parziale
Si calcola r_i’j'k’=min_{(i,j,k’)∈Ot} r_ijk e si pone S_t+1= S_t∪{(i’,j’,k’)} e
O_t+1=O_t-{(i’,j’,k’)}∪{i’,j’+1,k’} e t=t+1.