Programmazione operativa della produzione

Programmazione operativa della produzione

Laurea magistrale in ingegneria gestionale

C. Scimeca, R. Scimeca

Università degli Studi di Palermo | Scuola Politecnica

Prefazione

Il presente testo costituisce una sintesi completa del corso di Programmazione operativa della produzione, di G. Passannanti. Il corso prevede nozioni teoriche di scheduling e algoritmi di programmazione della produzione e l’applicazione di alcuni di questi in linguaggio VBA su foglio elettronico. Per scrivere quanto segue si è preso spunto da appunti¹ presi a lezione, materiale didattico fornito dal professore e approfondimenti sul web.

Riteniamo che l’implementazione su calcolatore degli algoritmi proposti in questo corso sia di importanza rilevante ai fini di una comprensione ottima (o quanto euristica!!) dei concetti di programmazione operativa. Per questo un ultimo capitolo è dedicato alle esercitazioni. La struttura del file è la seguente.

Il Capitolo 1 introduce il lettore alla programmazione operativa trattando i suoi elementi costitutivi, quali obiettivi, vincoli e misure di prestazione.

Il Capitolo 2 è interamente dedicato ai sistemi monostadio, esponendo le regole e le procedure migliori (ottimizzanti o sub-ottimizzanti) a seconda delle situazioni particolari e degli obiettivi che si vogliono perseguire.

Il Capitolo 3 definisce il modello unidirezionale Pure Flow Shop ed espone l’algoritmo ottimizzante di Johnson e le sue estensioni.

Nel Capitolo 4 troviamo diverse tematiche legate ancora al Flow Shop: il Branch&Bound, un algoritmo di ricerca intelligente ottimizzante molto diffuso in Ricerca Operativa, gli algoritmi euristici costruttivi, gli algoritmi di ricerca locale e un approfondimento relativo al paper¹ Minimizing the cycle time in serial manufacturing systems with multiple dual-gripper “robots” (2006, G. Galante, G. Passannanti) pubblicato sull’International Journal of Production Research.

Il Capitolo 5 passa al modello multidirezionale Job Shop, esponendo due algoritmi euristici non delay) e le regole di carico su (uno con schedulazione attiva ed uno con schedulazione cui si fondano.

Il Capitolo 6 espone due famosi algoritmi euristici di ricerca non specifici, applicabili ad una moltitudine di problemi, tra cui la programmazione operativa. Il primo paragrafo è dedicato al Taboo Search, il secondo al Simulated Annealing.

Il Capitolo 7, ultimo tra quelli di teoria, è interamente dedicato alla classe degli algoritmi genetici. Vedremo le caratteristiche generali di un siffatto algoritmo, un’applicazione banale ed infine le tecniche più utilizzate per risolvere problemi di programmazione operativa con un genetico.

Nel Capitolo 8 troviamo, come annunciato, esempi di implementazione degli algoritmi visti nei paragrafi precedenti. In particolare abbiamo: schedulazioni ottimizzanti per sistemi monostadio, applicazione del Johnson, euristici per Flow Shop, un TABOO per la risoluzione di un salesman travel problem, e infine una schedulazione non delay per un Job Shop. Per ogni esercizio è riportato nell’ordine il codice nell’estensione VBA di Excel ed i risultati ottenuti.

Si augura una buona lettura,

I Dottori, Riccardo Scimeca – Claudio Scimeca

¹ Il corso prevede inoltre la realizzazione di un progetto di ottimizzazione attraverso algoritmo genetico. Gli autori, insieme ad altri colleghi, hanno realizzato un progetto di ottimizzazione bi-obiettivo di un problema di knapsack modificato. Per questi contenuti si rimanda al file “Ottimizzazione di un problema di knapsack modificato” (C. Scimeca, R. Scimeca). C S – R S Claudio Cimeca Riccardo Cimeca

Indice

Indice ..................................................... 3

Capitolo 1. ..................................................................................................................................................... 3

....................... 3

........................................................................ 4

................................................................................................... 6

Capitolo 2. ......................................................................................................... 6

................................................................................. 7

.................................................................................................. 7

.................................................................................................................. 9

Capitolo 3. ................................................................................................................................................... 9

.................................................................................................................................. 9

...................................................................................................... 10

....................................................... 11

Capitolo 4. ............................................................................................................................................. 11

................................................................................................................... 13

......................................................................................................................... 14

................................ 15

.................................................................................................................... 17

Capitolo 5. ..................................................................................................... 17

.............................................................................................................................................. 17

........................................................................... 19

Capitolo 6. ............................................................................................................................................................... 19

.................................................................................................................................... 19

.................................................................................................... 21

Capitolo 7. ............................................................................................................. 21

...................................................................................... 21

........................................................ 22

................................................................. 23

................................................................................................................................. 23

................................................................................ 24

.............................................................................. 25

Capitolo 8. ......................................................................................................................................... 25

............................................................................................................................................................ 25

SPT – Codice ........................................................................................................................................................ 26

SPT – Risultati ........................................................................................................................................................ 27

WSPT – Codice 1..................................................................................................................................................... 28

WSPT – Risultati.......................................................................................................................................................... 29

EDD – Codice ....................................................................................................................................................... 30

EDD – Risultati ................................................................................................................................... 31

Algoritmo di Moore – Codice ................................................................................................................................ 32

Algoritmo di Moore – Risultati ......................................................................................... 33

Macchine in parallelo (no preemption allowed) – Codice ..................................................................................... 35

Macchine in parallelo (no preemption allowed) – Risultati................................................................................................................................... 36

...................................................................................................................................................................... 36

Codice .................................................................................................................................................................. 37

Risultati .................................................................................................................................. 38

.......................................................................................................................................................... 38

CDS – Codice ...................................................................................................................................................... 40

CDS – Risultati ............................................................................................................................................. 40

Rapid Access – Codice ......................................................................................................................................... 41

Rapid Access – Risultati ................................................................................................................................. 41

Algoritmo di Grasso – Codice .............................................................................................................................. 42

Algoritmo di Grasso – Risultati...................................................................................................................................................... 43

Palmer – Codice ................................................................................................................................................... 44

Palmer – Risultati ...................................................................................................................................... 44

Gupta modificato – Codice ................................................................................................................................... 46

Gupta modificato – Risultati ................................................................................................................................. 46

Algoritmo di Nawaz – Codice .............................................................................................................................. 49

Algoritmo di Nawaz – Risultati ........................................................... 50

...................................................................................................................................................................... 50

Codice .................................................................................................................................................................. 53

Risultati ............................................................................................................................................................. 56

...................................................................................................................................................................... 56

Codice .................................................................................................................................................................. 59

Risultati²

Capitolo 1.

La programmazione operativa della produzione (o più semplicemente scheduling) può estendersi ad una moltitudine di problemi non strettamente legati all’ambito della produzione industriale. Questi sono accomunati dal problema dell’allocazione delle risorse disponibili nel tempo. Solitamente si parla di programmazione a breve e schedulazione di dettaglio, in quanto la programmazione operativa è vincolata da scelte di livello superiore ed è caratterizzata da un elevato livello di dettaglio nella modellazione delle attività.

Le attività oggetto di programmazione spesso sono legate da vincoli di precedenza tecnologici, che prescrivono che un insieme di attività debba rispettare una precisa sequenza di “lavorazione”. Abbiamo inoltre i vincoli di capacità delle risorse, ovvero il rispetto della loro disponibilità massima nel tempo. Il rispetto dei vincoli di un problema di scheduling è necessario affinché questo risulti ammissibile (o fattibile).

Data una funzione obiettivo da perseguire, è necessario tradurre i vincoli di cui sopra in equazioni, affinché il problema di schedulazione sia formulabile e risolvibile. Spesso si ottengono soluzioni sub-ottimali, a causa della vastità delle possibili soluzioni ammissibili (i.e. con n oggetti da processare su m stazioni, in assenza di vincoli, si hanno n! possibili sequenze). La schedulazione deve dunque affrontare due aspetti fondamentali: m

• Sequencing: stabilire la sequenza delle attività sulle risorse in base a vincoli e algoritmi;
• Timing: determinare gli istanti di inizio e fine di ciascuna attività necessaria per la lavorazione del mix.

Uno strumento utile che consente la rappresentazione di una soluzione ammissibile è il Diagramma di Gantt, che riporta l’allocazione delle risorse nel tempo (in ascissa il tempo e in ordinata le macchine). Una schedulazione dicesi permutazionale quando la sequenza di servizio su tutte le stazioni è uguale per ogni job, e pertanto per ottenere schedule differenti è sufficiente permutare i nomi dei job; dicesi inoltre semiattiva se tutti i job sono programmati al più presto, ovvero non appena il job ha completato il lavoro sulla macchina precedente e la stazione successiva ha completato tutti i job schedulati in precedenza.

Per una schedulazione semiattiva non è possibile fare iniziare prima alcuna operazione senza modificare la sequenza, altrimenti si violerebbe un vincolo di capacità; inoltre minimizza le misure di prestazione regolari, ovvero non decrescenti col tempo di completamento (makespan). Nel caso in cui un flusso multidirezionale di job costringa ad ammettere sequenze non permutazionali, si può restringere lo spazio delle soluzioni a quelle dette attive o a quelle non-delay; le prime sono schedulazioni per le quali un job non viene tenuto in coda se può essere completato prima della data di inizio programmata per il job successivo su una data stazione,¹ mentre nelle seconde nessuna risorsa viene mantenuta inattiva se vi è un job in coda, anche qualora il caricamento di questo comportasse il ritardo dell’attività seguente (non è detto che la soluzione ottima sia contenuta in questo sottoinsieme).

Scriviamo in forma di disuguaglianza i vincoli di cui si è accennato nel primo paragrafo:² ;, , , , ,

Il primo vincolo impone il rispetto del vincolo di precedenza tra due operazioni consecutive, mentre il secondo tiene conto anche del tempo di trasferimento del pezzo da una stazione all’altra ( ).

I vincoli relativi alla capacità delle risorse possono invece esprimersi come segue: ; ;, , , , , , , ,

Il primo vincolo assicura che l’attività i sulla stazione m inizi solo dopo che sia finita l’attività precedente, il secondo assicura che l’attività i sulla stazione m non inizi prima dell’istante DT in cui la risorsa dedicata al i,m trasporto è disponibile più il tempo di trasporto; indicando con Da l’istante in cui sono disponibili le, i,m³

¹ In pratica viene violata la sequenza dei job sulla stazione, ma non la sequenza con cui i job visitano le stazioni, pertanto la soluzione è ancora ammissibile, anzi è possibile dimostrare che l’insieme contenente le schedulazioni attive contiene anche la soluzione ottima.

² Si ipotizzi che si stia trattando un flow-shop di tipo permutazionale: ciò consente di trascurare l’indice (relativo alla lavorazione) poiché si può porre =k m.

attrezzature necessarie per svolgere l’attività i sulla stazione m e con tsu i relativi tempi di set up, il terzo i,m vincolo esprime la disponibilità degli utensili e attrezzature. Nel caso in cui tutti i tipi di vincoli descritti sino ad ora siano attivi, la condizione più restrittiva diventa: max max , , max ,, , , , , , ,

Possiamo calcolare tempo di completamento dell’operazione, della parte e del mix (o makespan) rispettivamente come: ; max ; max, , , , ,

Riguardo a quanto è stato detto fin ora e a ciò che verrà detto in seguito, vi sono delle assunzioni implicite di seguito riportate: tutto il necessario per la produzione è già disponibile a t 0, ciascuna parte è indivisibile e non è possibile effettuare sulla stessa più lavorazioni allo stesso tempo ed una volta cominciata non può interrompersi (no preemption allowed), le stazioni hanno capacità finita e sono uniche ed esenti da guasti, i tempi sono deterministici e indipendenti dalla sequenza di servizio, è ammesso il WIP e la sua entità è illimitata,¹ l’inizio di ciascuna operazione è al più presto e, infine, non è ammesso il sorpasso tra le parti (no job passing). Sotto queste assunzioni il problema è statico e deterministico.

Per classificare i problemi che verranno affrontati utilizziamo la notazione di Conway, Maxwell e Miller, secondo la quale un problema è identificato da n/m/A/B, con n ed m numero di job e