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

1

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

1 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

LAUDIO CIMECA ICCARDO CIMECA

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

salesman travel problem

di un , 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, R S – C S

ICCARDO CIMECA LAUDIO CIMECA

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

2

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

1) Sequencing: stabilire la sequenza delle attività sulle risorse in base a vincoli e algoritmi;

2) 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 ,

1

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 :

2

;

, , , , ,

Il primo vincolo impone il rispetto del vincolo di precendenza 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 3

1 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.

2 Si ipotizzi che si stia trattando un flow-shop di tipo permutazionale: ciò consente di trascurare l’indice (relativo alla

k

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

, ciascuna parte è indivisibile e non

seguito riportate: tutto il necessario per la produzione è già disponibile a t 0

è 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,

1

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