Regola di Johnson
La regola di Johnson è un metodo facente parte dell'Operation Scheduling che si usa quando diverse lavorazioni devono essere eseguite sulle stesse macchine in una sequenza precisa. Per poter trovare l'ordine ottimo in cui realizzare queste lavorazioni occorre conoscere il tempo esatto che impiegherà ogni lavorazione su ogni macchina.
Esempio di applicazione
modificaVediamo come la regola di Johnson ci permette di risolvere un semplice problema di scheduling. Abbiamo un insieme di quattro lavorazioni che chiamiamo A, B, C e D che necessitano entrambe dei macchinari "MacchinaUno" e "MacchinaDue"; per ogni lavorazione conosciamo la durata esatta.
| MacchinaUno | MacchinaDue | |
|---|---|---|
| A | 2 minuti | 1 minuto |
| B | 6 minuti | 8 minuti |
| C | 4 minuti | 5 minuti |
| D | 5 minuti | 7 minuti |
Consideriamo ora il tempo minimo relativo alle lavorazioni eseguite su "MacchinaUno" e cioè "A" che ha durata 2 minuti. Confrontando il tempo di lavorazione su "MacchinaUno" e su "MacchinaDue" vediamo che dunque:
Aggiorniamo la tabella relativa alla soluzione ottima:
| Lavorazione | |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | A |
Passiamo ora al passo successivo prendendo il considerazione la lavorazione (tra quelle ancora "libere") con tempo di "MacchinaUno" minore ovvero la lavorazione C. Osserviamo subito che dunque:
.
Aggiorniamo la tabella relativa alla soluzione ottima:
| Lavorazione | |
|---|---|
| 1 | C |
| 2 | |
| 3 | |
| 4 | A |
Procedendo ulteriormente consideriamo prima la lavorazione D dove che viene processata per seconda (essendo il primo posto già occupato) e, infine, la lavorazione B che viene processata per terza (essendo i primi due posti già occupati) sempre secondo le due regole sopra riportate, infatti . La sequenza ottimale di scheduling secondo la regola di Johnson per questo esempio è, dunque:
| Lavorazione | |
|---|---|
| 1 | C |
| 2 | D |
| 3 | B |
| 4 | A |
