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 » 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={pij},
    • pij tempo di processamento dell’operazione j del job i;
  • una matrice di routing R={rij},
    • rij 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 Cmax si analizzeranno i problemi:

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

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

Un problema job shop su due macchine

Regola di Jackson per J2 |nj≤2| Cmax

Si suddividono i jobs in 4 sottoinsiemi:

J12 jobs che passano per la macchina 1 e poi per la macchina 2;
J21 jobs che passano per la macchina 2 e poi per la macchina 1;
J1 jobs da processare solo sulla macchina 1;
J2 jobs da processare solo sulla macchina 2;

e si assegnano alle macchine secondo il seguente ordine:

macchina 1: J12J1J21;

macchina 2: J21J2J12;

Poiché i jobs di J12 (J21) 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||Cmax.

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, S1=Ø; O1 è costituito dall’insieme delle prime operazioni di ogni job (O1={(i,1,k): i∈J}.

2. Selezione nuovo elemento da aggiungere alla soluzione parziale
Si calcola C(Ot)=min(i,j,k)Ot {rijk+pijk}
Si indica con k‘ la macchina corrispondente a C(Ot) e con Ot={(i,j,k’): (i,j,k’)Otrijk’<C(Ot)}
Si schedula al più presto un’operazione (i’,j’,k’)Ot a caso o secondo un criterio prestabilito.
Si pone St+1=St∪{(i’,j’,k’)}, Ot+1=Ot-(i’,j’,k’)}∪{i’,j’+1,k’}

3. Criterio di arresto
Se la schedulazione è completa (Ot =Ø), 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.

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 Ot, 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 ri’j'k’=min(i,j,k’)∈Ot rijk e si pone St+1= St∪{(i’,j’,k’)} e
Ot+1=Ot-{(i’,j’,k’)}∪{i’,j’+1,k’} e t=t+1.

  • 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