Programmazione della produzione: MRP e regole di sequenza

Una fabbrica deve decidere ogni giorno che cosa produrre, in quali quantità e in quale ordine sulle macchine. La programmazione della produzione traduce gli ordini e le previsioni in piani, e la schedulazione stabilisce la sequenza dei lavori. In questa lezione vediamo la pianificazione gerarchica e la logica MRP, le regole di sequenza su una macchina con le dimostrazioni dell’ottimalità di SPT ed EDD, e la regola di Johnson per due macchine con un esempio di cui si dimostra l’ottimalità.

Dalla pianificazione alla sequenza

La programmazione procede per livelli, con orizzonti sempre più brevi:

1. il piano aggregato (mesi): capacità, turni, livelli di magazzino per famiglie di prodotti;
2. il piano principale di produzione (MPS, settimane): quali prodotti finiti, quanti e quando;
3. il calcolo dei fabbisogni di materiali (MRP): partendo dall’MPS e dalla distinta base (l’elenco dei componenti di ogni prodotto, livello per livello), si calcolano per ogni componente le quantità nette da produrre o acquistare, sottraendo le scorte disponibili, e le date di rilascio degli ordini, anticipandole del tempo di approvvigionamento;
4. la schedulazione (giorni, ore): la sequenza dei lavori su ciascuna risorsa.

Un’automobile ha migliaia di componenti; una scheda elettronica centinaia. Calcolare a mano i fabbisogni sarebbe impossibile: l’MRP è stato una delle prime grandi applicazioni dei calcolatori nelle aziende, ed è il cuore dei sistemi ERP.

Una macchina: SPT ed EDD

Si devono eseguire lavori su una macchina, con durate e date di consegna . Diverse regole ottimizzano obiettivi diversi.

Teorema (SPT). Eseguire i lavori in ordine di durata crescente (shortest processing time) minimizza il tempo medio di completamento.

Dimostrazione. È lo stesso argomento di scambio della pianificazione della CPU (lezione sulla pianificazione di Sistemi operativi): se due lavori consecutivi sono in ordine “lungo prima di breve”, scambiandoli il completamento del breve anticipa della durata del lungo e quello del lungo ritarda della durata del breve, quindi la somma diminuisce; gli altri lavori non cambiano. L’ottimo non ha inversioni. ∎

Teorema (EDD). Eseguire i lavori in ordine di data di consegna crescente (earliest due date) minimizza il ritardo massimo .

Dimostrazione. Si considerino due lavori consecutivi e con e prima di , che iniziano all’istante e finiscono entrambi entro . Prima dello scambio finisce in , con ritardo , che è il maggiore dei due (perché finisce prima di e ha scadenza più lontana). Dopo lo scambio finisce prima di , e finisce in con ritardo . Il massimo dei due non aumenta, e gli altri lavori non cambiano. Eliminando una a una le inversioni si arriva all’ordine EDD senza peggiorare. ∎

Nessuna delle due regole è buona per tutto: SPT può far aspettare a lungo i lavori lunghi; EDD ignora le durate. Per minimizzare il numero di lavori in ritardo esiste un algoritmo apposito (Moore-Hodgson); per obiettivi più complessi i problemi diventano rapidamente intrattabili e si usano euristiche.

Due macchine: la regola di Johnson

Ogni lavoro passa prima sulla macchina (durata ) e poi su (durata ), nello stesso ordine. Si vuole minimizzare il tempo totale (makespan). Johnson (1954) ha dato la regola ottima:

1. i lavori con vanno all’inizio, in ordine di crescente;
2. gli altri vanno alla fine, in ordine di decrescente.

L’idea è tenere occupata il prima possibile (all’inizio i lavori brevi su ) e non lasciarla con molto lavoro alla fine (in fondo i lavori brevi su ).

Esempio. Cinque lavori : J1 (3, 6), J2 (5, 2), J3 (1, 2), J4 (6, 6), J5 (7, 5). Primo gruppo, per crescente: J3, J1, J4. Secondo gruppo, per decrescente: J5, J2. Sequenza J3, J1, J4, J5, J2.

Su i lavori finiscono agli istanti 1, 4, 10, 17, 22; su a 3, 10, 16, 22, 24. Il makespan è 24.

Ottimalità nell’esempio. Qualunque sequenza deve impegnare per , e dopo l’ultimo lavoro su serve ancora almeno la sua durata su , che vale almeno . Quindi nessuna sequenza finisce prima di 24, e la sequenza di Johnson raggiunge il limite. (La dimostrazione generale usa ancora uno scambio tra lavori adiacenti.)

Con tre o più macchine il problema diventa NP-difficile e si usano euristiche; la regola di Johnson resta utile quando due macchine dominano, per esempio una stazione di montaggio seguita da un collaudo.