Programmazione operativa della produzione

O

j t+1 j una siffatta soluzione non delay ha il pregio di avere

aggiungendo quelle eventualmente disponibili grande semplicità ed è di gran lunga la più diffusa)

per vincoli tecnologici. Porre t=t+1.

5. Se t< n×m andare al passo 2, altrimenti stop.

Le regole di carico o dispatching rules, sono necessarie per dare una priorità alla operazioni da assegnare. Per

scegliere il pezzo da sequenziare si scelgono solitamente più regole, organizzate in gerarchia, in modo da

scongiurare eventuali ambiguità di assegnazione. Con le regole di carico è possibile scegliere in particolari

istanti di decisione (i.e. viene completata una operazione o fuori servizio di una risorsa, etc.), ma nulla è possibile

stabilire su istanti futuri. Per prima cosa vediamo le regole basate sui tempi di lavorazione:

SPT. Già vista per sistemi monostadio, si tratta di selezionare il pezzo con tempo di lavorazione più breve.

o WSPT. Anche questa già vista nel caso monostadio; come SPT, ma con tempi pesati.

o TSPT (Truncated Shortest Processing Time). Si sceglie il pezzo che soddisfa il criterio SPT, a meno che per un

o job in coda non venga superato un tempo massimo di attesa prefissato; in tal caso si sequenzia quel job.

SPTEX (SPT with EXpediting). Un SPT che prevede la possibilità di conferire priorità massima a job urgenti.

o MSUT (Minimum Set Up Time). Si sceglie il job che minimizza il tempo di set‐up.

o LPT (Longest Processing Time). Intuitivamente, si sceglie il job con il tempo di lavorazione più lungo.

o 17

LWKR (Least WorK Remaining). Viene selezionato il job avente il minimo carico di lavoro rimanente.

o MWKR (Most WorK Remaining). Al contrario del precedente, si sceglie quello col carico rimanente più alto.

o

Anche in questo caso vi sono regole basate sulle due date; in più ve ne sono altre basate sia su DD che su tl:

 EDD. Già vista per sistemi monostadio. Si sceglie l’operazione del pezzo con data di consegna più breve.

 OPNDD (OPeratioN Due Date). Si seleziona il pezzo con operation due date più vicina: essa è pari al rapporto

tra la differenza tra la data di consegna e la data d’ingresso nel sistema e il numero di operazioni del job.

 MST (Minimum Slack Time). Si sceglie il pezzo più urgente in termini di slack tra tempo restante alla data

∑

di consegna e tempo operativo ancora da effettuare, cioè secondo .

 S/OPN (Slack per OPeratioN). Come MST, ma lo slack viene rapportato al numero di operazioni restanti.

 CR (Critical Ratio). Si assegna priorità più elevata al pezzo con rapporto più basso dell’indice .

∑

Due regole particolari si basano invece sullo stato attuale del sistema: con NINQ (Number in the Next Queue) si

sceglie il pezzo che richiede per l’operazione successiva la stazione con minor numero di pezzi in coda, mentre

job che richiede per la prossima operazione la stazione

con WINQ (Work In the Next Queue) viene selezionato il

con il carico di lavoro minore per pezzi già in coda. Abbiamo poi regole basate su attributi dei pezzi:

 FIFO (First In First Out). Si sceglie il pezzo da più tempo in coda.

 FISFO (First In the System First Out). Si sceglie il pezzo da più tempo nel sistema.

 LIFO (Last In First Out). Si seleziona il pezzo da meno tempo in coda.

 FROP (Fewest Remaining OPerations). Viene selezionato il job con minor numero di operazioni rimanenti.

 MROP (Most Remaining OPerations). Viene schedulato il job con maggior numero di operazioni restanti.

Ovviamente la scelta delle regole di carico dipende dagli obiettivi della schedulazione. Sappiamo infatti che

per ed la regola migliore è SPT (alla quale a volte si preferise la regola TSPT, nel caso in cui ci siano tempi

si usa EDD (o eventualmente MST).

di lavorazione troppo lunghi rispetto ad altri), o che per

Per concludere, abbiamo regole di carico basate su una stima delle attese dei job. La prima regola si chiama

COVERT (Cost OVER Time remaining) e si basa sulla stima di un costo c per ritardo nel completamento e sul

i

tempo tl . Viene assegnata una priorità maggiore ai job con rapporto c / tl più alto. Calcolato infatti lo slack

i,k i i,k

time del job (come nel caso della regola MST) si attribuisce a c il valore:

i

1 se 0

0 se ,

∈ 0,1 , , altrimenti

,

numero di operazioni rimanenti e t un tempo di attesa medio stimato. In questo modo accade che: se

con , w

lo slack è maggiore delle attese previste, il job sarà finito in tempo e il suo costo sarà nullo, se è sufficiente per

viene

neutralizzare solo parzialmente i ritardi stimati, la sua urgenza sarà tanto maggiore quanto più tardi

lavorato, se è negativo il suo costo sarà massimo e viene fissato pari all’unità.

La seconda si chiama ATC (Apparent Tardiness Cost). Anche questa si basa su una valutazione stimata delle

attese, e viene proposto anche questa per la minimizzazione della tardiness pesata. L’indice di priorità è:

∑

, , ,

exp max 0, X , X

,

è il peso del job i, il suo tempo operativo su m, è la stima dell’attesa del job davanti alla q‐

dove , ,

esima stazione, mentre la sommatoria è estesa a tutte le stazioni che il job deve ancora visitare. Poi k è un

parametro da selezionare da parte del programmatore e è il tempo di lavorazione medio dei job in coda. La

∑

quantità può interpretarsi come l’istante di inizio al più tardi

, , ,

dell’operazione che consente di rispettare la due date, tenendo conto di una stima dei ritardi che il job subisce

nel completare il routing. Poi il calcolo dell’indice fa sì che quando si è in ritardo (l’esponente diventa nullo)

viene assegnata al job la massima priorità possibile.

18

Capitolo 6.

Gli algoritmi che vedremo in questo capitolo (e nel successivo) sono algoritmi non specifici, ovvero applicabili

anche a problemi diversi da problemi di programmazione della produzione. Tali algoritmi sono euristici, e si

pongono l’obiettivo di ottimizzare una funzione obiettivo. In particolare l’algoritmo TABOO SEARCH è una

evoluzione degli algoritmi di ricerca, che cerca di scongiurare la possibilità di fermarsi troppo presto ad un

ottimo locale. Infatti, scelta una regola di perturbazione, il search tradizionale seleziona unicamente soluzioni

migliori di quella di partenza e, se non ce ne sono di nuove, si ferma. Il TABOO invece permette, una volta

raggiunto un ottimo locale, di continuare ad analizzare altre soluzioni ammissibili, accettando

momentaneamente soluzioni peggiori o equivalenti, evitando di tornare su passi già visitati (scongiurando

così il rischio di ciclare), ma tenendo sempre a mente la miglior soluzione trovata sino a quel momento.

Vediamone gli elementi costitutivi:

 TABOO list: lista delle ultime t “mosse” effettuate e che saranno scartate a priori nella prossima iterazione.

Ad ogni iterazione verrà inserita in lista l’ultima mossa appena effettuata e cancellata la più antica.

 Tenure t: valore della lunghezza della TABOO list, ovvero numero delle ultime mosse da ricordare.

Coincide, dunque, con il “tempo” durante la quale una particolare mossa effettuata rimane “taboo”.

Solitamente la scelta di t è dettata dall’esperienza e dalla dimensione del problema. Se essa è statica la

TABOO list prevede t mosse, ma può anche variare. È inoltre possibile assegnare ad una mossa non

migliorativa una penale basata sulla frequenza con cui si verifica.

 Criterio di generazione del vicinato: in un problema job‐shop potrebbe essere ad esempio una permutazione.

 Inizializzazione: scelta della soluzione ammissibile iniziale (i.e. casuale, o con regole di carico).

 Oscillazione: variazione facoltativa in corso d’opera del criterio di generazione (search).

 Criterio di aspirazione: criterio che prescrive l’accettazione di una mossa attualmente presente nella TABOO

list (i.e. il best cost prescrive di accettare un taboo se comporta un miglioramento assoluto, l’influenza

prescrive di accettarla se il grado di variazione introdotto nella struttura della soluzione è elevato).

 Intensificazione: scegliere se basare il criterio di aspirazione sulle frequenze.

 Criterio di chiusura: criterio che impone la fine dell’algoritmo (i.e. numero totale di iterazioni, numero di

iterazioni dall’ultimo miglioramento).

Quando si verifica il criterio di chiusura, la soluzione euristica dell’algoritmo è la migliore in assoluto trovata

durante la ricerca. Pertanto è necessario fare in modo che si tenga sempre in memoria la soluzione migliore

fino a quel momento. La figura a fianco mostra un esempio di TABOO list relativo ad un problema di

schedulazione della sequenza del job i

sulle M=4 macchine, con una tenure t=3

fissa e che utilizza la permutazione tra

due posti in sequenza come criterio di

generazione del vicinato; in particolare la

figura mostra la prima mossa (mossa di

scambio 2–3) e le due successive.

Anche l’algoritmo chiamato simulated annealing parte dalla considerazione che i local search giungono troppo

velocemente ad un ottimo locale, e pertanto è necessario adottare una strategia che non sia solamente

discendente/ascendente (a seconda che si cerchi il minimo o il massimo), ma che dia la possibilità di accettare

momentaneamente soluzioni non migliorative. Inoltre un algoritmo non dovrebbe dipendere dalla soluzione

iniziale. Tale algoritmo, sotto alcune condizioni, ha la proprietà di essere asintoticamente esatto, anche se per

giungere all’ottimo potrebbe richiedere più iterazioni di un’analisi esaustiva. Esso si fonda su studi di

termodinamica statistica secondo cui, per ottenere un massimo energetico da un sistema, bisogna sottoporlo

a perturbazioni successive e, di volta in volta, accettare il nuovo stato con certezza se si ha una variazione

exp /

positiva di energia δE, accettarlo con probabilità P se δE<0, con , dove T è la temperatura

e K la costante di Boltzmann, non accettarlo con probabilità 1 – P se δE<0. Dopo un certo numero di

perturbazioni si riduce la temperatura, fintantoché si giunge ad uno stato frozen, ovvero la probabilità di

19

accettare una soluzione non migliorativa diventa bassissima. L’algoritmo si basa dunque sui seguenti

parallelismi: gli stati del sistema sono le soluzioni ammissibili di un problema combinatorio, l’energia è la

funzione obiettivo, il cambiamento di stato è il vicinato, la temperatura è un parametro di controllo e lo stato

frozen rappresenta poi la soluzione euristica. La costante K viene elimanata, mentre si è soliti denotare

comunque T come “temperatura” e de