CL MSP Review - lcolleluori.altervista.org

Colleluori Livio

Prof. M. Caramia

Modelli di Sistemi di Produzione

A.A. 2020/2021

MSP - Review

Capitolo 1 - Introduzione 2Modelli di Sistemi di Produzione 2

Grandezze Fondamentali 2

Legge di LITTLE 3

Capitolo 2 - La Linea di Produzione (Sistemi Produttivi Orientati al Prodotto): 4Sistemi Make-To-Stock 4

Tempo di Attraversamento 4

Linee Sincrone vs Asincrone 5

Progettazione di una Linea di Produzione 5

DIMENSIONAMENTO di una LINEA di Produzione 5

BILANCIAMENTO di una LINEA di Produzione 9

Linee a Prodotto Misto e Linee Multiprodotto 10

Linea MULTIPRODOTTO 10

Linea a PRODOTTO MISTO 10

Gestione dei Tempi di Setup 13

Capitolo 3 - Produzione per Reparti (Sistemi Produttivi Orientati al Processo): 14Sistemi Make-To-Order 14

Progettazione di un sistema di produzione per reparti 14

Modello di Assegnamento Quadratico 15

Metodo dei Grafi Planari 17

SEQUENZIAMENTO del Layout a Reparti 19

Capitolo 4 - Group Technology (Sistemi Ibridi): 20Group Technology 20

Indice di Similarità 20

Indice di Similarità di Seiffodini-Wolfe 20

Meccanismo di Formazione delle Celle (per similarità) 20

Modello colorazione 21

Modello di assegnamento ad eterogeneità controllata 21

Colleluori MSP Review 2021 2/23

Capitolo 1 - Introduzione

Layout - disposizione dei macchinari e/o mezzi di produzione nel sistema produttivo.

Classificazione di sistemi di produzione - la classificazione può generalmente essere fatta su diversifattori, ma quella più comune e che studieremo è la classificazione sul tipo di layout.

Mix Produttivo - numero di prodotti diversi realizzati dallo stesso impianto.

Modelli di Sistemi di Produzione:1. Sistemi produttivi ORIENTATI AL PRODOTTO:

Sistema progettato attorno ad uno specifico prodotto con lo scopo di minimizzare i costi diproduzione e max l’output. Solitamente in caso di grandi volumi e dunque basso MixProduttivo.⇒ LINEA DI PRODUZIONE (Flow-Line).

2. Sistemi produttivi ORIENTATI AL PROCESSO:Sistema in cui il processo produttivo è fisso e vengono realizzati un alto numero di prodottidiversi (alto mix produttivo) a basso volume sfruttando questi processi.(es: paziente entra in un ospedale)

3. Sistemi produttivi Per CELLE PRODUTTIVE o IBRIDI o per CELLE ROBOTIZZATE:Sistemi ibridi, a metà tra 1 e 2 che cercando di mettere insieme le proprietà dei sistemi orientatial prodotto e di quelli orientati al processo.Attenzione però: l’ibridazione si fa sempre e solo da sistemi orientati al processo a sistemiorientati al prodotto, MAI al contrario.

4. Sistemi produttivi A POSTAZIONI FISSE:Sistema produttivo che viene organizzato intorno al prodotto a causa delle grandi dimensionidi quest’ultimo (es: produzione di barche, aeroplani, palazzi).

Grandezze Fondamentali:WIP (Work in Progress), T.A. (Throughput Time - Tempo di Attraversamento), P.R. (Production Rate - Tassodi Produzione).

WIP (Work in Progress) - numero di prodotti in produzione in un dato arco temporale. Il WIL èidealmente il minimo possibile.

PR (Production Rate) - Numero di articoli finiti prodotti in un determinato arco temporale (1 giorno, 1h, 1mese, 1 anno etc). Deve necessariamente essere commisurato alle richieste del mercato.

TA (Tempo di Attraversamento) o THROUGHPUT - Tempo che impiega ogni prodotto ad attraversaretutte le fasi produzione (idealmente minimo possibile). oppure Intervallo di tempo che intercorre dalmomento in cui sono disponibili i materiali/componenti in input, a quando è disponibile ilcomponente/prodotto in output (il primo elemento del lotto).In un sistema produzione in linea, dipende dalla stazione con carico massimo (stazione più lenta) edalla sua posizione nella linea.

Tasso di Produttività - 1/PR, ovvero ogni quanto tempo esce fuori un nuovo prodotto dall’impianto.


Legge di LITTLE:legge (universale) secondo cui in un sistema produttivo a regime (quindi nel suo steady-state) ilWork in Progress (WIP) in ogni istante è uguale al prodotto del Tempo di Attraversamento (TA)per il Production Rate (PR):

WIP = TA x PREd è valida per ogni tipologia di sistema di produzione.

Tempo di Completamento - tempo di uscita di ogni prodotto in ultima posizione dall’ultima stazione dilavorazione.

Tempo Carico - Tempo effettivo disponibile per la produzione (di solito 360gg o 365gg per 8h al gg oper 24h al gg).


Capitolo 2 - La Linea di Produzione (Sistemi Produttivi Orientati al Prodotto):

I sistemi produttivi orientati a prodotto sono sistemi incaricati di realizzare elevati volumi di produzione,ovvero sono sistemi MAKE-TO-STOCK, con un basso mix produttivo. ⇒ Sistemi RIGIDI.

Sistemi Make-To-Stock:il volume di produzione è così elevato e la domanda di così difficile misura puntuale che il produttorenon produce una quantità esatta ma fa una stima della domanda e produce sull’ordine di grandezza(in opposizione al MAKE-TO-ORDER ovvero su comanda che opera per volumi piccoli).Fondamentalmente quindi non potendo rivolgersi direttamente al cliente, l’impianto interloquisce conil magazzino, che comunicherà le esigenze di produzione e si occuperà poi della distribuzione delprodotto.

Buffer - entità che disaccoppia due attività.

Workstation (Stazione di Lavorazione) - Zona/area dell’impianto di produzione, delimitata, che svolgeuna FASE della produzione. All’interno di ogni workstation ci possono essere un numero di OPERAZIONI,organizzate in modo sequenziale. ⇒ il TEMPO che il prodotto rimane nella WS è la somma dei tempiimpiegati nelle singole operazioni.Inoltre quando un prodotto entra in una workstation non può entrare nessun altro prodotto finchéquello corrente non è terminato. ⇒ per questo si usano i BUFFER INTEROPERAZIONALI.

Carico t(WSj) o Cj - il carico di una stazione WSj è il tempo che la stazione impiega per completare tuttele sue operazioni. È importante poiché serve per definire il PRODUCTION RATE DELLA LINEA.

Production Rate (PR) della Linea di Produzione - definito come l’inverso del massimo carico presentesulla linea, ovvero:

max{Cj} = CMAX ⇒ 𝑃. 𝑅. = 1𝐶

𝑀𝐴𝑋

Tempo di Attraversamento:In un sistema produzione in linea, dipende dalla stazione con carico massimo (stazione più lenta) edalla sua posizione nella linea:

𝑇. 𝐴. = 𝑝 * 𝐶𝑀𝐴𝑋

+ 𝑗 = 𝑝+1

# 𝑊𝑆

∑ 𝐶𝑗

Con p = # o posizione della WS con il carico max.

Organizzazione della Linea di Produzione:L’impianto di produzione di un sistema orientato al prodotto sarà organizzato in aree di lavorochiamate WORKSTATIONS, disposte in modo lineare una accanto all’altra in modo tale che l’output diuna workstation funga da input per la workstation seguente (sono quindi organizzate in modosequenziale).In questo caso il TEMPO DI ATTRAVERSAMENTO non dipende solo dal CARICO MAX ma anche dallaPOSIZIONE delle workstations.


Efficienza del Sistema - l’efficienza rappresenta la presenza di idle-time, ovvero di tempo perso,durante la produzione. Per rappresentare matematicamente l’efficienza uso il concetto diINEFFICIENZA, ovvero quanto le stazioni sono lontane dall’ideale:

INEFFICIENZA = 𝑗=1

# 𝑠𝑡𝑎𝑧𝑖𝑜𝑛𝑖

∑ (𝐶𝑀𝐴𝑋

− 𝐶𝑗)

(# 𝑆𝑡𝑎𝑧𝑖𝑜𝑛𝑖)𝐶𝑀𝐴𝑋

Compresa ovviamente tra 0 e 1. Da questa definizione viene che l’EFFICIENZA sarà:EFFICIENZA = 1 - INEFFICIENZA

Linee Sincrone vs Asincrone:1. Linea Sincrona (Paced Line):

I sistemi di movimentazione tra le stazioni sono sincronizzati e si muovono tutti nello stessomomento; l’organizzazione è centralizzata.E’ quindi conveniente nel caso in cui i carichi sono tutti molto simili tra loro (o uguali,idealmente). Nella peggiore delle ipotesi lo spostamento avverrà dopo che la WS più lentaavrà finito la lavorazione.

⇒ Il WIP è in genere basso.

2. Linea Asincrona (Unpaced Line):Il sistema di movimentazione è decentralizzato ed ogni stazione decide per sé.È utile nel caso in cui i carichi non sono simili tra loro.

⇒ il WIP è notevolmente più alto, in quanto saranno necessari dei buffer e possonoessere presenti anche aree di stoccaggio.Sta quindi al management dell’impianto gestire in modo intelligente ed efficiente lemovimentazioni.

Progettazione di una Linea di Produzione:La progettazione di un sistema di produzione orientato al prodotto, composto da una linea diproduzione, consiste nella risoluzione di 3 problemi:

1. Dimensionamento della Linea;2. Bilanciamento della Linea;3. Sequenziamento della Linea (nel caso di Linea a Prodotto Misto);

DIMENSIONAMENTO di una LINEA di Produzione:Problema del minimizzare il numero totale (e quindi eventualmente il costo) delle Workstations utilizzatenella linea di produzione.

Formulazione del Problema del DIMENSIONAMENTO:

DATI:● O = {o1, o2, … , om} l’insieme delle Operazioni (BOM - Bills Of Materials o Distinta Base);● d = [d1, d2, … , dm ] vettore durata delle Operazioni;● D = domanda di mercato per il prodotto (Nel caso di Make-to-Stock si stima);


● T = Tempo (orizzonte temporale) pianificato per la produzione;● RP = {(i, i’) : i, i’ in O e i deve essere eseguito prima di i’} il grafo delle Relazioni di

Precedenza temporale tra le operazioni in O;

TROVARE:● Un assegnamento di operazioni a stazioni di lavorazione;

IN MODO TALE CHE:● Siano rispettate le relazioni di precedenza temporali;● Sia MIN il numero di stazioni lavorative (Workstations);

FORMULAZIONE:𝑣𝑎𝑟 𝑥

𝑖𝑗= 1 𝑠𝑒 𝑙'𝑜𝑝𝑒𝑟𝑎𝑧𝑖𝑜𝑛𝑒 𝑖 è 𝑎𝑠𝑠𝑒𝑔𝑛𝑎𝑡𝑎 𝑎𝑙𝑙𝑎 𝑊𝑆 𝑗; 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖{ }

𝑣𝑎𝑟 𝑦𝑗

= 1 𝑠𝑒 𝑙𝑎 𝑊𝑆 𝑗 è 𝑢𝑡𝑖𝑙𝑖𝑧𝑧𝑎𝑡𝑎; 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖{ }

𝑚𝑖𝑛𝑗∈ 𝑆∑ 𝑦

𝑗

(Vincolo di Assegnamento)𝑗 ∈ 𝑆∑ 𝑥

𝑖𝑗= 1 ∀ 𝑖 ∈ 𝑂

(Vincoli di Precedenza)𝑗 = 1

𝑗'

∑ 𝑥𝑖𝑗

≤𝑗 = 1

𝑗'

∑ 𝑥𝑖'𝑗

𝑗' = 1... 𝑛 𝑒 𝑖 ≠ 𝑖'

(Vincolo di Carico e Legame xij - yj)𝑖 ∈ 𝑂∑ 𝑑

𝑖 𝑥

𝑖𝑗≤ 𝑇

𝐷 𝑦𝑗 ∀ 𝑗 ∈ 𝑆

Risoluzione del Problema del DIMENSIONAMENTO:Il Problema del Dimensionamento, nella sua formulazione descrittiva, è un problema dicomplessità esponenziale, quindi NP-Completo. Per trovare una soluzione, od un Bound, cisono vari modi:

1. Rilassamento Lineare [LB0]:Si rilassano i vincoli di precedenza temporale, riconducendosi alla formulazione diBin-Packing Multidimensionale, in cui O è l’insieme degli oggetti, d (le durate) l’insiemedei pesi, S (stazioni) è l’insieme dei contenitori e T/D (carico max teorico) è la capacitàmax dei contenitori (W).In realtà anche questa formulazione sarebbe di complessità esponenziale, marilassando linearmente la variabile xij il problema risulta risolvibile.

⌉ e si prende la parte intera superiore.𝐿𝐵0 = ⌈ 𝑖 ∈ 𝑂

∑ 𝑑𝑖

𝑇/𝐷 ⌉ = ⌈ 𝑖 ∈ 𝑂∑ 𝑤

𝑖

𝑊

La qualità di questo LB non è particolarmente buona ma è il più facile e veloce dacalcolare.


2. Rilassamento Continuo da Set-Covering e P.L. Duale [LB]:a. Si riscrive la formulazione, già rilassata dei vincoli di precedenza, come una

formulazione di tipo Set-Covering: si definiscono collezioni di “riempimenti”(insiemi di operazioni) ammissibili e massimali.

b. Si fa il rilassamento continuo della formulazione di tipo Set Covering ⇒ P.L.Il problema è rilassato, ma ha comunque un numero esponenziale di variabili.

c. Essendo il problema rilassato un P.L. esiste la sua formulazione duale ⇒anch’essa P.L.Nel problema duale l’esponenzialità non si è cancellata ma è stata spostatasui vincoli.

Questa formulazione è più comoda perchè è risolvibile con il Metodo dei Pianidi Taglio:

i. Considero un sottoinsieme di vincoli del problema Duale;ii. Risolvo all’ottimo la P.L. Corrispondente;iii. Individuo uno o più vincoli non considerati che risultino violati dalla

soluzione ottenuta al Passo 2 ⇒ PROBLEMA DELLA SEPARAZIONE:1. I vincoli sono tutti soddisfatti ⇒ TROVATA SOL. OTTIMA.2. Trovo qualche vincolo che non viene soddisfatto ⇒ Li

reintegro e torno al Passo 2.

d. Problema della Separazione:i. Si definisce una variabile binaria φi = {1 se considero l’oggetto i; 0

altrimenti}

ii. Si definisce la funzione obiettivo , ovvero max il termine di𝑚𝑎𝑥∑ π𝑖*ϕ

𝑖

sinistra del vincolo duale, calcolato nella soluzione ottima π* al passo 2del metodo dei piani di taglio, per il sottoinsieme di oggetti relative adun Ok formato dagli oggetti a cui corrisponde la variabile binaria φi =1

iii. Impongo che la massimizzazione sia fatta solo sui termini ammissibili,

ovvero tale che (di < T/D)𝑖 ∈ 𝑂∑ ω

𝑖ϕ

𝑖≤ 𝑊

iv. Risolvendo il problema così formulato associo ad ogni sottoinsiemeammissibile massimale il suo Valore, quindi faccio la scelta sul valoremaggiore.

3. Rilassamento Combinatorio [LB(a)]:Si sceglie uno scalare 𝛂 compreso tra [0; ½W ), dove W = T/D, e poi si definiscono 3classi di oggetti:J1 = Oggetti “sufficientemente grandi”{𝑖 ∈ 𝑂: 𝑤

𝑖> 𝑊 − α }

J2 = Oggetti “intermedi”{𝑖 ∈ 𝑂: 𝑊2 + α < 𝑤

𝑖 ≤ 𝑊 − α }

J3 = Oggetti “piccoli”{𝑖 ∈ 𝑂: α ≤ 𝑤𝑖 ≤ 𝑊

2 }

A questo punto, si immagina che in ogni contenitore di dimensione W entrino un certonumero di J1, J2 e J3.


In particolare gli oggetti J1 richiederanno un contenitore per ogni oggetto, quindi cisaranno almeno |J1| contenitori.Anche gli oggetti J2 richiederanno un contenitore per ogni oggetto, ma avanzeràabbastanza spazio da far entrare alcuni elementi di J3. Quindi ci saranno almeno altri|J2| contenitori.In più serviranno tanti contenitori da contenere i J3 che non si sono potuti infilare innessun altro contenitore mezzo pieno. → si prende la parte intera superiore.La somma così descritta definisce il Lower Bound del rilassamento combinatorio:

𝐿𝐵(α) = 𝐽1| | + 𝐽

2| | + ⌈𝑚𝑎𝑥{0, 𝐽

3

∑𝑤𝑖 − ( 𝐽

2| |𝑊 − 𝐽

2

∑𝑤𝑖)

𝑊 }⌉

**N.B. : SEMPRE.𝐿𝐵(α) ≥ 𝐿𝐵0

4. RPWT - Ranked Positional-Weight Technique e Next-Fit [UB]:Il peso posizionale di un nodo è un numero che indica quanto una certa attività(nodo) si trova indietro nel grafo delle precedenze.

è il peso posizionale del nodo i (Positional-Weight).𝑃𝑊(𝑖) = 𝑑𝑖 +

𝑖' ∈ 𝑂: 𝑖' ∈ 𝑆𝑢𝑐𝑐(𝑖)∑ 𝑑

𝑖'

Per trovare il dimensionamento tramite i Pesi Posizionali:1. Si calcola il peso posizionale PW(i) di ogni nodo presente sul grafo delle

precedenze.2. Si ordinano in modo decrescente i nodi (operazioni) → Classificazione → Si

ottiene un sequenziamento che rispetta per costruzione i vincoli diprecedenza.

3. Si usa il Metodo Next-Fit per trovare quante WS sono necessarie:a. Si apre una WS (di capacità uguale T/D o CMAX) e si inserisce la prima

operazione non ancora assegnata, prendendola dalla classificaprima ottenuta tramite i PW.

b. Valutando la capacità residua della WS, si vede se si riesce ad inserirel’operazione successiva nella classifica.

c. Se entra, si torna al punto B.Se non entra, si apre la WS successiva e la si inserisce lì. Poi si torna alpunto B.

4. Contando quante WS sono state aperte si trova il risultato, che è un UB per ilproblema del Dimensionamento della Linea di Produzione.

**NB: La soluzione trovata con il Metodo Next-Fit non assicura un bilanciamentosignificativamente buono, quindi va poi verificato e, nel caso, cercato di migliorare.


BILANCIAMENTO di una LINEA di Produzione:La fase di bilanciamento valuta quanto i carichi siano “bene” o “mal” distribuiti sulle WS.Prima di iniziare il bilanciamento si calcola l’EFFICIENZA, in quanto potrebbe non essere necessariobilanciare se si hanno valori accettabili di efficienza (solitamente > 90%).

Fondamentalmente si tratta di cercare di disporre le operazioni in modo tale che le varie stazioniabbiano tutte un carico molto simile tra loro.Nel caso migliore (ideale) si parla di bilanciamento perfetto, in cui ogni stazione ha esattamente uncarico pari al carico ideale:

dove m sarebbe il numero di WS (ottenuto dal dimensionamento).µ = 𝑖 ∈ 𝑂∑ 𝑑

𝑖

𝑚

(Di fatto il carico ideale corrisponde ad un carico medio).

Se avessi il bilanciamento perfetto non avrei TEMPO DI ATTESA ⇒ NO-WAIT FLOW SHOP.Ovviamente questo è un caso puramente ideale, che si basa sul concetto di PRE-EMPTION, ovveroINTERROMPIBILITÀ’: esprime la possibilità di considerare le operazioni frazionarie e quindi poterleassegnare a più WS. Ovviamente è molto difficile ed implica costi enormi.

Risoluzione del Problema del BILANCIAMENTO:Analiticamente, massimizzare il bilanciamento (MAX BILANCIAMENTO) è equivalente alminimizzare lo sbilanciamento (MIN SBILANCIAMENTO). Infatti se lo sbilanciamento di un caricoè la sua distanza dal carico ideale:

allora ⇒𝑆𝐵𝑗 = µ − 𝑐

𝑗| | 𝑚𝑖𝑛 𝑗=1

𝑚

∑ 𝑆𝐵𝑗 =

𝑗=1

𝑚

∑ µ − 𝑐𝑗| |

mentre il poliedro (i vincoli) è esattamente lo stesso del problema del dimensionamento, con ladifferenza che il numero di stazioni è definito.

Prima di iniziare a bilanciare si calcolano le altre grandezze fondamentali: T.A. e P.R.

In generale, per bilanciare una linea dovrei provare tutte le possibili combinazioni di operazioni(riempimenti) nelle WS e trovare quella che rende l’efficienza migliore ( o, meglio, il T.A. ).

⇒ questo sarebbe un problema ESPONENZIALE.

Il problema diventa POLINOMIALE quando il grafo delle precedenze è una CATENA (poiché il# di precedenze è n(n-1)/2 = o(n2) ). Sfrutto quindi la SEQUENZA trovata per risolvere ilproblema del dimensionamento, la cui risoluzione è invece un problema POLINOMIALE.

→ da questa sequenza costruisco il LAYERED GRAPH (Grafo a Livelli):● Il layered graph è un grafo formato da “livelli” di Insiemi Stabili (indipendenti), che

supponiamo identici tra di loro ed in numero tanti quante sono le WS.


● I nodi sono tutti i possibili sottoinsiemi di operazioni ammissibili.● Si aggiungono poi un nodo pozzo P ed un nodo sorgente S● Si aggiungono gli archi necessari affinchè sia un layered graph: possono esistere archi

solo tra un layer e l’altro e tra un layer ed i nodi P/S. Colleghiamo un nodo di un livellocon un nodo del livello successivo se sono rispettate 2 Condizioni:

1. Ogni vincolo (insieme) p assegnato ad una sola coppia;2. La connessione dei due livelli non viola le relazioni di precedenza;

● S si collega con tutti i sottoinsiemi al livello 1 che contengono la sorgente temporaledel grafo delle precedenze (gli altri violerebbero le relazioni di precedenza).

● P si collega con tutti i sottoinsiemi che contengono il pozzo (nell’albero delleprecedenze)

● Si aggiungono i pesi degli archi: è il peso dell’arco (i, j), ovvero lo𝑢𝑖𝑗

= µ − 𝑐𝑗| |

sbilanciamento che comporterebbe attraversare l’arco.

⇒ una volta costruito il Layered Graph cerco il cammino di costo minimo. Il valore del costocomplessivo del cammino è esattamente lo sbilanciamento della linea e può servire ancheper confrontare con altri cammini, anche se spesso si trova solo 1 cammino ammissibile.

Linee a Prodotto Misto e Linee Multiprodotto:Quando una linea di produzione orientata al prodotto è incaricata di realizzare non un unico bene mauna gamma di prodotti, con lavorazioni simili ma non esattamente uguali (ovvero tale che ci sianell’insieme delle operazioni un sottoinsieme di operazioni richieste da un prodotto ed un altrosottoinsieme di operazioni richieste da un altro prodotto, e così via) si parla di Linea a Prodotto Misto oMultiprodotto.Spesso si tende a confondere le due, sia in letteratura che nella pratica, ma sono due cose bendistinte.

Linea MULTIPRODOTTO:sistema di produzione in linea in cui sono lavorati più prodotti ma in questo caso le tipologie di prodottorichiedono che il sistema si fermi per poter lavorare prodotti diversi, ovvero i tempi di setup sonosignificativi al punto che c’è bisogno che il sistema si fermi. In questo caso l’impatto dei tempi di setupnon può essere inserito all’interno delle durate, né a livello modellistico né tantomeno a livello reale. Es:produzione di saponi di tipi diversi.

Linea a PRODOTTO MISTO:Sistema di produzione in linea in cui sono lavorati più prodotti ma sostanzialmente non è necessarioeffettuare attrezzaggi significativi, e quindi i tempi di setup sono considerabili nulli. I prodotti si possonoalternare con dei micro-setup che dal punto di vista modellistico vengono incorporati all’interno delledurate delle operazioni. Es: produzione cerchi per auto.

Per progettare una linea a prodotto misto sono fondamentali 4 step:

STEP 1 - Generare l’input per la linea:Si prende l’input di sistema e si gestisce come se fosse, in maniera fittizia, un prodotto compostoP’ che è l’unione dei P1, P2, …, Pl prodotti che la linea deve produrre; per questo prodotto si


dovranno definire la Domanda aggregata D’, l’insieme delle operazioni O’, il grafo delleprecedenze G(R.P.), il vettore delle durate delle operazioni d’ e l’intervallo di tempo T’:

D’ = D1 + D2 + … + DL

O’ = O1 U O2 U … U O3

G(R.P) = unione dei grafi

di’ = media pesata della durata sulla domanda D per ogni operazione, ovvero:

𝑑𝑖' = 𝑙' = 1

𝑙

∑ 𝑑𝑖𝑙'𝐷𝑙'

𝑙'=1

𝑙

∑ 𝐷𝑙'

T’ = solitamente è uguale per tutti i prodotti, è semplicemente l’intervallo temporale dilavorazione.

STEP 2 - Dimensionamento e Bilanciamento rispetto a P’:Si dimensiona e si bilancia la linea considerando il sistema come se dovesse produrre un soloprodotto, ovvero P’, utilizzando le tecniche standard per il dimensionamento ed ilbilanciamento di una linea.⇒ Una volta che la linea per P’ è dimensionata e bilanciata si dice che P’ è “REALIZZATO”.

STEP 3 - Bilanciamento della Linea:Una volta realizzato P’, si verifica se la linea soddisfa i requisiti qualitativi prestabiliti. Nel casoquesti non fossero soddisfatti, in termini di solito di efficienza e varianza, si cerca dibilanciamento ottimo, utilizzando sempre i metodi visti precedentemente.

STEP 4 - Sequenziamento della Linea:Una volta bilanciata la linea ed ottenuto un livello di efficienza soddisfacente, si scorpora dinuovo il prodotto composto P’ e si passa alla fase di sequenziamento: ovvero, si studia in qualeordine i singoli prodotti devono entrare nella linea affinchè sia ottimizzato il Tempo diAttraversamento (T.A. min).

Formulazione del Problema del Sequenziamento dei prodotti:

Variabili:

𝑥𝑙,ℎ

= {1 𝑠𝑒 𝑎𝑠𝑠𝑒𝑔𝑛𝑜 𝑖𝑙 𝑝𝑟𝑜𝑑𝑜𝑡𝑡𝑜 𝑙 𝑎𝑙𝑙𝑎 𝑝𝑜𝑠𝑖𝑧𝑖𝑜𝑛𝑒 ℎ; 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖}

è la variabile di assegnamento

è l’istante di ingresso nella linea𝑡ℎ, 𝑗

≥ 0

Con l = indice prodotto (1…#prodotti)h = indice posizione (1…#posizioni)

Funzione Obiettivo:

𝑚𝑖𝑛 𝑡#𝑝𝑜𝑠, #𝑠𝑡𝑎𝑧=𝑚

(ovvero minimizzo il l’istante in cui l’ultimo elemento esce dall’ultima stazione)

Vincoli di precedenza temporale:


𝑡ℎ,𝑗

= 𝑚𝑎𝑥{𝑡ℎ−1, 𝑗+1

; 𝑡ℎ, 𝑗+1

+ 𝑙=1

#𝑝𝑟𝑜𝑑

∑ 𝑥𝑙,ℎ

𝐶𝑙,𝑗

} ∀ ℎ =... #𝑝𝑜𝑠, ∀ 𝑗 = 1... #𝑠𝑡𝑎𝑧

Vincoli di Assegnamento:

𝑙=1

#𝑝𝑟𝑜𝑑

∑ 𝑥ℎ,𝑙

= 1 𝑐𝑜𝑛 ℎ = 1... #𝑝𝑜𝑠𝑖𝑧𝑖𝑜𝑛𝑖

ℎ=1

#𝑝𝑟𝑜𝑑

∑ 𝑥ℎ,𝑙

= 1 𝑐𝑜𝑛 𝑙 = 1... #𝑝𝑜𝑠𝑖𝑧𝑖𝑜𝑛𝑖

Passi per il Sequenziamento della Linea:1. Si definisce una matrice PRODOTTI-CARICHI:

Matrice in cui si indica il carico relativo di ogni WSj perogni prodotto Pi.Da questa matrice si può inoltre valutare se può valerela pena separare alcuni prodotti su linee di produzioniindipendenti, nel caso ad esempio in cui un prodottosolo abbia uno sbilanciamento importante rispetto aglialtri.

2. Si usa il Teorema o Algoritmo di Johnson (1954) per determinare il sequenziamentoottimo:Il Teorema di D. Johnson offre in realtà, nella maggior parte dei casi, un Lower Bound.Questo perché in realtà, in generale quando m>2, il problema del sequenziamento èun problema NP-HARD, quindi di complessità esponenziale; tuttavia se m=2, ovvero seci sono solo 2 WorkStations, il problema diventa polinomiale e restituisce una soluzioneottima. Invece quando m>2 il teorema può comunque essere utilizzato, restituendoperò un LB e/o un UB alla soluzione ottima.Passi dell’algoritmo:

I. Prendo il prodotto con il carico minore in assoluto;II. Se il carico minore è su WS1 (SX) il prodotto va IN TESTA alla sequenza (tutto a

dx), se invece il carico minore è sulla WS2 (DX) il prodotto va IN CODA allasequenza.

III. Passo al prodotto successivo che ha il carico minore in assoluto (tra i prodottinon ancora assegnati) e torno al punto due. Proseguo fino ad aversequenziato tutti i prodotti.

3. Si calcola il Tempo di Attraversamento:IMPORTANTE: La matrice PRODOTTI-CARICHI si riordina mettendo i PRODOTTI nell’ordinedella sequenza, da quello in testa a quello in coda. Quindi si passa a calcolare il T.A.

● CASO m = 2:


𝑇. 𝐴. = 𝐶1,1

+ 𝑚𝑖𝑛{𝐶1,2

; 𝐶2,1

} + 𝑚𝑖𝑛{𝐶2,2

; 𝐶3,1

} + ... ... + 𝐶𝑙,𝑚=2

● CASO m > 2:LB: Quando m > 2 si può trovare un LB con l’algoritmo di Johnson, prendendocoppie di WS (quindi m=2) ed usando quindi la formula per m=2.Si possono valutare diversi abbinamenti di coppie di WS per trovare quello cheminimizza il tempo di attraversamento totale.

𝑇. 𝐴. = 𝐶1,ℎ

+ 𝑚𝑖𝑛{𝐶1,𝑘

; 𝐶𝑘,ℎ

} + 𝑚𝑖𝑛{𝐶2,𝑘

; 𝐶3,ℎ

} + ... ... + 𝐶𝑙,𝑘

(dove h e k sono le WS scelte per il sequenziamento e quindi valutare il T.A.).

UB: Si usa il ragionamento usato per la formula del LB (per Johnson) ma siestende valutando il minimo tra tutte le WS in questione (quindi, diciamo, sututta la matrice e non solo tra la coppia di WS analizzate per il LB).

⇒ trovo quindi un RANGE in cui è compreso il T.A. : LB < T.A. < UB .

Gestione dei Tempi di Setup:Nel caso fossero presenti tempi di setup tra ogni coppia di operazioni possibili, si può creare unaMatrice dei Tempi di Setup. Si nota facilmente che questa matrice è, fondamentalmente, una matricedi adiacenza per il problema del TSP.Dunque, tramite una semplice EURISTICA, si può trovare il TSP di costo minimo e quindi il CamminoHamiltoniano di costo minimo, ovvero il sequenziamento che minimizza i tempi di setup:

1. Dalla matrice dei tempi di setup scegliere il tempo minore in assoluto (e quindi selezionare inodi, ovvero i prodotti).

2. Tra gli archi incidenti sui nodi selezionati, scegliere il successivo arco di costo minimo (ovveroscegliere il successivo nodo adiacente raggiungibile con costo minimo)

3. Calcolare il costo totale del cammino trovato.

(il ciclo Hamiltoniano si può immaginare di trovarlo inserendo un nodo origine O collegato atutti i nodi del grafo, ed in questo caso il cammino hamiltoniano si trova semplicementeeliminando dal ciclo trovato il nodo O e gli archi che lo collegano).

Ovviamente la soluzione trovata in questo modo va poi confrontata con la soluzione trovataottimizzando rispetto ai tempi di produzione (problema del sequenziamento) in cui poi i tempi di setupsemplicemente si sommano così come occorrono per effetto dei cambi prodotto dovuti alla sequenzatrovata. Questa soluzione è quasi sempre MAGGIORE di quella trovata ottimizzando i tempi di setup.


Capitolo 3 - Produzione per Reparti (Sistemi Produttivi Orientati al Processo):

In un sistema produttivo orientato al processo, ovvero in generale un sistema di produzione per reparti,il processo produttivo è fisso ed i prodotti devono adattarsi alle risorse. Solitamente vi sono diversiprodotti (alto mix) e bassi volumi per ogni tipo di prodotto. E’ quindi ovvio che non può esserci un’unicasequenza, ma devono essercene diverse.

⇒ le operazioni sono al centro del contesto ottimizzatorio, e non si parla più di sequenziamentoma di parallelismo.

Con queste premesse, non valgono più le regole sul sequenziamento, quindi il Tempo diAttraversamento (T.A.) non è più legato al carico massimo.

Il Sistema produttivo orientato al processo è solitamente utilizzato per le produzioni Make-to-Order.

Sistemi Make-To-Order:I sistemi make-to-order, o sistemi su comanda, sono sistemi che non producono in grandi quantità, permettere scorte in magazzino, ma producono piccole quantità di una gamma varia di prodotti, esolitamente la produzione parte solo dopo la ricezione di un ordine da parte di un cliente. Non c’è piùquindi la dinamica di accumulo in magazzino, anche perchè i volumi sono così più bassi che nonsarebbe giustificato il costo.

Progettazione di un sistema di produzione per reparti:La progettazione di un sistema di produzione per reparti ha fondamentalmente 2 obiettivi:

1. PROGETTARE LAYOUT A REPARTI:Ridurre i costi logistici, ovvero minimizzare la movimentazione. Derivante dal fatto che nelsistema orientato al processo, non essendoci un processo rigido e lineare, i costi dimovimentazione da un reparto all’altro sono molto significativi.Bisogna quindi generare un layout in cui delle AREE sono specializzate in un solo tipo dioperazione, ovvero organizzato in REPARTI PRODUTTIVI.

(Immagine: Esempio di layout per reparti)

2. SEQUENZIAMENTO - RISOLVERE I CONFLITTI:Sequenziamento interno, ovvero dare un ordine di priorità di accesso alle singole operazioni, inquando più prodotti potrebbero provare ad accedere alla stessa operazionesimultaneamente. → ottimizzazione dei conflitti dovuti alla condivisione di risorse.


Modello di Assegnamento Quadratico:Il modello di assegnamento quadratico è un modello semplice ecomprensibile per la formulazione del problema della minimizzazione deicosti di movimentazione.Fondamentalmente parte dall’assunto che l’impianto produttivo abbiagià delle zone, o reparti, definiti. Rimane quindi solo il problema diassegnare le operazioni giuste alle aree dell’impianto, con l’obiettivo diminimizzare i costi logistici (e quindi i costi di movimentazione, e quindi ledistanze percorse per i trasporti tra reparti).Prendendo in input i grafi delle precedenze dei vari prodotti, il problemarestituisce l’assegnamento di operazioni (o reparti) i alle zone dell’impianto k tali da minimizzare i costidi movimentazione totali.

Dal grafo delle precedenze si definiscono:

l’insieme di tutte le operazioni (reparti) necessarie nello 𝑂 = {𝑂

𝑖

⋃} ∀ 𝑖 = 1 ... #𝑝𝑟𝑜𝑑

stabilimento

è l’insieme delle precedenze temporali(𝑖, 𝑖') = {(𝑖, 𝑖') ∈ 𝐴(𝑅.𝑃.)

⋃ }

è il flusso prodotto tra i e i’𝑓𝑖,𝑖'

=(𝑖, 𝑖') ∈ 𝑅.𝑃.(𝑃

𝑖)

∑ 𝐷𝑖 ∀ 𝑖 = 1 ... #𝑝𝑟𝑜𝑑, 𝑖 ≠ 𝑖'

(Il flusso è pari alla somma delle domande dei vari prodotti passanti sull’arco).

Formulazione del Modello:Variabile (di assegnamento):

𝑥𝑖𝑘

= {1 𝑠𝑒 𝑙'𝑜𝑝𝑒𝑟𝑎𝑧𝑖𝑜𝑛𝑒 (𝑜 𝑟𝑒𝑝𝑎𝑟𝑡𝑜) 𝑖 è 𝑎𝑠𝑠𝑒𝑔𝑛𝑎𝑡𝑜 𝑎𝑙𝑙𝑎 𝑝𝑜𝑠𝑖𝑧𝑖𝑜𝑛𝑒 𝑘 𝑛𝑒𝑙𝑙'𝑖𝑚𝑝𝑖𝑎𝑛𝑡𝑜; 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛

Funzione Obiettivo:

𝑚𝑖𝑛 (𝑖, 𝑖')∑

𝑘=1

#𝑝𝑜𝑠

∑𝑘'≠𝑘=1

#𝑝𝑜𝑠

∑ 𝑑𝑘,𝑘'

𝑥𝑖,𝑘

𝑥𝑖',𝑘'

Con tk,k’ o dk,k’ il tempo (o distanza) di movimentazione tra k e k’, e i, i’ in O tali cheesiste una richiesta di spostamento (quindi dal grafo delle precedenze).

Vincoli:

𝑘=1

#𝑝𝑜𝑠

∑ 𝑥𝑖𝑘

= 1 ∀ 𝑖 ∈ 𝑂

𝑖 ∈ 𝑂∑ 𝑥

𝑖𝑘= 1 𝑐𝑜𝑛 𝑘 = 1... #𝑝𝑜𝑠𝑖𝑧𝑖𝑜𝑛𝑖

⇒ in realtà però la F.O. così definita è NON LINEARE e quindi il problema NP-HARD.


→ Notando che i vincoli definiscono una matrice TUM, è possibile rilassarli e trasformarli invincoli continui. Tuttavia la F.O. è comunque NON LINEARE; diventa POLINOMIALE solo sequando la sua hessiana è definita positiva. (che non sappiamo cosa significhi).La F.O. si può LINEARIZZARE tramite una tabella di verità, definendo una nuova variabile edintroducendo due vincoli:

𝑥𝑖,𝑘

· 𝑥𝑖',𝑘'

= 𝑧𝑖𝑖',𝑘𝑘'

∈ {0, 1} ∀ (𝑖, 𝑖'), ∀ 𝑘, ∀ 𝑘' ≠ 𝑘

È la variabile tale che:

𝑧𝑖𝑖',𝑘𝑘'

≤ 𝑥

𝑖,𝑘 + 𝑥

𝑖',𝑘'

2 ∀ (𝑖, 𝑖'), ∀ 𝑘, ∀ 𝑘' ≠ 𝑘

&


≥ 𝑥𝑖,𝑘

+ 𝑥𝑖',𝑘'

− 1 ∀ (𝑖, 𝑖'), ∀ 𝑘, ∀ 𝑘' ≠ 𝑘

(I vincoli che selezionano il piano t.c. rende la variabile 1 solo quando le due x sonoentrambe 1 [AND] ).

Quindi la formulazione finale del modello risulta:

𝑚𝑖𝑛 (𝑖, 𝑖')∑

𝑘=1

#𝑝𝑜𝑠

∑𝑘'≠𝑘=1

#𝑝𝑜𝑠

∑ 𝑓𝑖,𝑖'

𝑑𝑘,𝑘'


S.t.

𝑘=1

#𝑝𝑜𝑠

∑ 𝑥𝑖𝑘

= 1 ∀ 𝑖 ∈ 𝑂

𝑖 ∈ 𝑂∑ 𝑥

𝑖𝑘= 1 𝑐𝑜𝑛 𝑘 = 1... #𝑝𝑜𝑠𝑖𝑧𝑖𝑜𝑛𝑖


≤ 𝑥

𝑖,𝑘 + 𝑥

𝑖',𝑘'

2 ∀ (𝑖, 𝑖'), ∀ 𝑘, ∀ 𝑘' ≠ 𝑘


≥ 𝑥𝑖,𝑘

+ 𝑥𝑖',𝑘'

− 1 ∀ (𝑖, 𝑖'), ∀ 𝑘, ∀ 𝑘' ≠ 𝑘

𝑥𝑖,𝑘

· 𝑥𝑖',𝑘'

= 𝑧𝑖𝑖',𝑘𝑘'

∈ {0, 1} ∀ (𝑖, 𝑖'), ∀ 𝑘, ∀ 𝑘' ≠ 𝑘

𝑥𝑖𝑘

∈ {0, 1}

**siamo passati da una problema di programmazione quadratica (non lineare) 0-1 ad unproblema di programmazione Lineare 0-1.⇒ il problema si può quindi risolvere con un Metodo Greedy per trovare un UB.

→ METODO dei GRAFI PLANARI

Grafo PLANARE:Un grafo è PLANARE quando è possibile disegnarlo (quindi se esiste un suo isomorfismo) senzaintersezioni tra archi (Es: K4).


In particolare:● Se il grafo è PLANARE → si trova in tempo polinomiale il layout ottimo.

**NB: ogni rappresentazione isomorfa PLANARE ha un LAYOUT A COSTO MINIMO.● Se il grafo NON è PLANARE → il problema diventa NP-Completo, e si dovranno cercare layout

sub-ottimi.Teorema di Kuratowski:Un grafo è planare se e solo se non contiene 2 strutture proibite: K5 ed il K3,3, che fanno perdere laproprietà di planarità a tutto il grafo.⇒ il teorema aiuta ad identificare se un grafo è planare in maniera semplice e veloce.

Metodo dei Grafi Planari:Prima di valutare se il grafo è planare o meno bisogna costruirlo.

Si costruisce la RETE che rappresenta le adiacenze tra i reparti -- i passi sono i seguenti:1. Si costruisce quindi una RETE in cui ogni nodo è un reparto.2. Si aggiungono quindi gli archi, seguendo i grafi delle precedenze (archi non orientati,

infatti in questo caso rappresentano solo le interazioni tra i reparti).

3. Si calcolano i flussi di prodotto, fii’, e si mettono sugli archi.

Ora si valuta se il grafo è planare o non planare, ed a seconda del caso si cerca di progettare il layout:

● CASO A - IL GRAFO È PLANARE:**NB: ogni rappresentazione isomorfa PLANARE ha un LAYOUT A COSTO MINIMO.

1) COSTRUIRE IL GRAFO DUALE AL GRAFO PLANARE:**NB: i grafi duali dei grafi planari sono planari!*FACCIA - area (poligono) del grafo chiusa e delimitata da archi. Un grafo planare hatante facce quante se ne possono identificare +1, ovvero le facce interne + la facciaesterna (degenere).

- Ha tanti nodi quante sono le FACCE del primale (planare);- Gli archi sono uguali al

# di archi del primaleche rendonoadiacenti i lati di 2facce;

2) COSTRUIRE IL LAYOUT:Dato che i grafi duali di grafi planari sono planari, anche il duale avrà delle facce. Inparticolare, avrà un unico nodo per ogni faccia → rappresentante l’area da dedicareal reparto (la forma è arbitraria).

Un metodo per rappresentare il layout è il DIAGRAMMA A BLOCCHI:


- Si parte dal nodo o reparto con più adiacenze;- Si procede aggiungendo nodi/reparti adiacenti, modificando ove necessario

la forma dei blocchi per soddisfare tutte le condizioni di adiacenza o nonadiacenza.

● CASO B - IL GRAFO NON È PLANARE:Nel caso in cui il grafo di partenza non fosse planare, bisogna “creare” un grafo planare primadi poter costruire il duale (da cui poi ricavare il layout), ovvero bisogna PLANARIZZARE ILGRAFO.Planarizzare il grafo significa, sostanzialmente, decidere a quali archi rinunciare per ottenereun grafo planare. Bisogna quindi definire un Meccanismo di Eliminazione degli Archi.

Di questi meccanismi ne esistono diversi, ad esempio l’INDUCED-SET PROBLEM:Consiste nell’eliminare gli archi meno pesanti (meno importanti quindi), o meglio,trovare il sottoinsieme di archi eliminabili di peso complessivo minimo ( o trovare ilsottoinsieme di archi di peso complessivo max che induce un grafo planare)→ ma il problema è un problema NP-COMPLETO, quindi possiamo al massimo trovareun bound con un Metodo Euristico.

TOTAL CLOSENESS RATE (TCR):Simile al RPWT, il TCR rappresenta la quantità totale di flusso che si dovrebbe scambiare tra unreparto e tutti i reparti a questo adiacenti. Ovviamente, tanto maggiore è il peso e tantomaggiori saranno le movimentazioni necessarie e quindi i costi. Conseguentemente, tanto piùil rating è alto tanto più è importante che le adiacenze siano soddisfatte, e viceversa.

1) Si calcolano i TCR(i) per ogni operazione/nodo i del grafo;2) Si ordinano i TCR in un ranking, ovvero in ordine decrescente;3) A partire dal ranking si crea il grafo planare, tenendo conto delle strutture proibite

secondo il Teorema di Kuratowski. → dovendo evitare n=5 (K5) e n=6 (K3,3) scegliamon=4 in modo tale che il grafo sarà sempre, per definizione, planare:

a) Si selezionano le prime 4 posizioni del ranking, e si rappresentano i nodi conuna rete fittizia che mi permette di costruire progressivamente una reteplanare → si costruiscono TETRAEDRI.Quindi si prendono i primi 4 nodi e si costruisce un tetraedro.

b) Si vanno a considerare quindi i nodi rimanenti (pericolosi!) uno alla volta,mettendoli in sicurezza: si posiziona il nodo successivo sulla faccia deltetraedro che è più profittevole, e si collega a tutti i nodi adiacenti → creandoun nuovo tetraedro.La faccia più profittevole si sceglie con un CRITERIO EURISTICO:Si aggiunge il nodo in modo tale che l’aggiunta renda MASSIMO il “profitto”della faccia, valutando tra tutti quelli possibili. → si trova così un nuovotetraedro.(ovviamente al variare del numero di iterazioni, il numero di valutazioni da fareaumenta in modo polinomiale).

c) Si itera il passo B fino a che non sono inseriti tutti i nodi del ranking.d) Alla fine, inseriti tutti i nodi, ci si riconduce al grafo planare eliminando dal

grafo di supporto gli archi che sul grafo originario non esistono.


⇒ così facendo dal grafo sintetico si ottiene il GRAFO PLANARE4) Una volta trovato il grafo planare si crea il grafo duale e si continua la creazione del

layout come visto nel CASO A.

SEQUENZIAMENTO del Layout a Reparti:1. Si prendono grafici dei routing dei prodotti (ovvero i loro grafici delle R.P.);2. Si crea un GRAFO DISGIUNTIVO (formato cioè da archi orientati e non orientati):

a. Si inseriscono degli archi (non orientati) che rappresentano i possibili conflitti; ovvero, sicollegano tra loro i nodi in comune in più routing. Questi archi non sono vincolitemporali (hard-constraints), ma nascondono un problema decisionale: ognuno diquesti archi rappresenta una decisione da prendere riguardo l’orientamento.

⇒ 2k decisioni!b. Si inseriscono un nodo origine O ed un nodo destinazione D e si collegano,

rispettivamente, a tutti i primi nodi dei routing ed a tutti gli ultimi nodi dei routing (inquesto caso mettendo direttamente archi orientati verso D);

c. Definita la variabile fi = tempo di fine dell’operazione i, allora si può dire che sulla rete

ci sono 2 tipi di vincoli:

i. 𝑓𝑖

≤ 𝑓𝑖

− 𝑑𝑖'

+ 𝑀(1 − 𝑧𝑖,𝑖'

) ∀ (𝑖, 𝑖') ∈ 𝑎𝑟𝑐ℎ𝑖 𝑛𝑜𝑛 𝑜𝑟𝑖𝑒𝑛𝑡𝑎𝑡𝑖

ii. 𝑓𝑖

≤ 𝑓𝑖

− 𝑑𝑖'

+ 𝑀𝑧𝑖,𝑖'

(𝑐𝑜𝑛 𝑀 = ∞)

Con 𝑧𝑖,𝑖'

= {1 𝑠𝑒 𝑖 𝑝𝑟𝑒𝑐𝑒𝑑𝑒 𝑖'; 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖}

d. La funzione obiettivo sarà quindi ovvero minimizzare il tempo per il𝑚𝑖𝑛 𝑓𝐷

raggiungimento di D da O, che quindi corrisponderà al minimo tempo dicompletamento.⇒ si nota che il problema risultate è un Problema 0-1 , che sappiamo essereNP-COMPLETO.

3. Dal grafo disgiuntivo, per un numero ragionevolmente piccolo di archi non orientati davalutare, si trova il sequenziamento migliore tramite l’uso del Problema del minimo LongestPath sul grafo dei percorsi ad ostacoli:

a. Si genera il grafo dei percorsi ad ostacoli, che corrisponde al grafo delle possibiliscelte: si crea cioè una biforcazione (o più) ad ogni scelta da dover valutare nel grafodisgiuntivo (dei routing).

b. Si valutano i costi dei vari percorsi che si possono creare orientando in un verso onell’altro gli archi non ancora orientati. Si devono valutare TUTTE le opzioni possibili; perquesto si può fare in modo semplice solo per un numero ridotto di archi.

c. Si inserisce il costo del percorso sull’arco valutato, quindi dopo aver valutato tutti ipossibili cammini da O a D si sceglie il percorso più conveniente (di costo minimo)trovando quindi il Min Longest Path.


Capitolo 4 - Group Technology (Sistemi Ibridi):

IMPORTANTE: l’ibridizzazione del sistema si fa ESCLUSIVAMENTE a partire da un sistema orientato alprocesso, MAI a partire da un sistema orientato al prodotto.I sistemi ibridi infatti si basano fondamentalmente sugli studi di Charles Burbage e sulla sua definizione diGroup Technology (GT).

Group Technology:Le group technology sono tutte quelle tecnologie in grado di creare sinergie tra reparti o lavorazionidiverse ma SIMILI tra loro. La definizione di “SIMILE” è particolarmente rilevante in questo ambito: sonosimili dei sottoinsiemi di prodotti o di macchine (Famiglie o Families di macchine) che si possonoclusterizzare, ovvero assegnare ad un’area specifica (CELLA PRODUTTIVA) che è diversa da una WS oda un reparto. In questa cella produttiva i prodotti entrano senza dover, prima o dopo, subire altrelavorazioni e passare per altre celle.

Cluster - Insieme di almeno 2 macchine o reparti che lavorano insieme.

Indice di Similarità:L’indice di similarità è fondamentale per valutare quanto due operazioni o macchine sono simili, equindi compatibili per essere in una stessa cella produttiva. Presa una qualsiasi coppia di operazioni omacchine, si valuta su alcuni parametri quanto queste sono simili tra loro e si assegna loro un indice disimilarità. Riportando questi valori in una matrice si ottiene la Matrice di Similarità.

Indice di Similarità di Seiffodini-Wolfe:Si definisce l’indice di similarità come:

𝑠𝑖𝑗

= 𝑚𝑎𝑥{𝑛

𝑖𝑗

𝑛𝑖

;𝑛

𝑖𝑗

𝑛𝑗

}

Dove

ni = # parti/prodotti che richiedono l’operazione i;

nj = # parti/prodotti che richiedono l’operazione j;

nij = # parti/prodotti che richiedono contemporaneamente l’operazione i e j.

Meccanismo di Formazione delle Celle (per similarità):1. Dagli indici di similarità si genera la matrice di similarità.2. Si sceglie una soglia di similarità, sopra la quale le macchine o operazioni possono essere

clusterizzate.3. Si prendono tutte le coppie sopra la soglia e si “accorpano”.


Modello colorazione:Se si ipotizza di rappresentare, tramite un grafo, la compatibilità o incompatibilità delle operazioni oreparti in un sistema produttivo, si può modellizzare il problema della formazione delle celle come unproblema di colorazione.

Variabili:

𝑥𝑖𝑘

= {1 𝑠𝑒 𝑙'𝑜𝑝𝑒𝑟𝑎𝑧𝑖𝑜𝑛𝑒 (𝑜 𝑟𝑒𝑝𝑎𝑟𝑡𝑜) 𝑖 è 𝑎𝑠𝑠𝑒𝑔𝑛𝑎𝑡𝑜 𝑎𝑙𝑙𝑎 𝑐𝑒𝑙𝑙𝑎 𝑘; 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖}

Con k = 1….m (caso peggiore in cui assegno 1 operazione ad 1 cella)

𝑦𝑘

= {1 𝑠𝑒 𝑙𝑎 𝑐𝑒𝑙𝑙𝑎 𝑘 è 𝑢𝑡𝑖𝑙𝑖𝑧𝑧𝑎𝑡𝑎; 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖}

Funzione Obiettivo:

𝑚𝑖𝑛𝑘=1

𝑚

∑ 𝑦𝑘

Ovvero minimizzare il numero di celle utilizzate.

Vincoli:

(vincolo di assegnamento)𝑘=1

𝑚

∑ 𝑥𝑖𝑘

= 1 ∀ 𝑖 = 1... 𝑚

(insieme archi del grafo delle𝑥𝑖𝑘

+ 𝑥𝑗𝑘

≤ 1 ∀ (𝑖, 𝑗) ∈ 𝐴

incompatibilità)

⇒ ma sappiamo che il problema della colorazione è NP-COMPLETO→ formare le celle diventa quindi complicato.

Modello di assegnamento ad eterogeneità controllata:Anziché minimizzare il numero complessivo di celle da utilizzare, minimizzeremo lo sbilanciamento tra lecelle.

Variabili:

𝑥𝑖𝑘

= {1 𝑠𝑒 𝑙'𝑜𝑝𝑒𝑟𝑎𝑧𝑖𝑜𝑛𝑒 (𝑜 𝑟𝑒𝑝𝑎𝑟𝑡𝑜) 𝑖 è 𝑎𝑠𝑠𝑒𝑔𝑛𝑎𝑡𝑜 𝑎𝑙𝑙𝑎 𝑐𝑒𝑙𝑙𝑎 𝑘; 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖}

Con k = 1….m (caso peggiore in cui assegno 1 operazione ad 1 cella)

µ = 𝐶𝑎𝑟𝑖𝑐𝑜 𝑖𝑑𝑒𝑎𝑙𝑒 𝑑𝑒𝑙𝑙𝑒 𝑐𝑒𝑙𝑙𝑒

Funzione Obiettivo:

𝑚𝑖𝑛𝑘=1

𝑚

∑ |µ − 𝐶𝑘|

Ovvero minimizzare la somma degli sbilanciamenti delle celle.

Vincoli:

(vincolo di assegnamento)𝑘=1

𝑚

∑ 𝑥𝑖𝑘

= 1 ∀ 𝑖 = 1... 𝑚


(insieme archi del grafo delle𝑥𝑖𝑘

+ 𝑥𝑗𝑘

≤ 1 ∀ (𝑖, 𝑗) ∈ 𝐴

incompatibilità)

(vincolo di bilancio)𝑘=1

𝑚

∑ 𝑑𝑖

· 𝑥𝑖𝑘

= 𝐶𝑘 ∀ 𝑖 = 1... 𝑚


CL MSP Review - lcolleluori.altervista.org

Documents

Transcript of CL MSP Review - lcolleluori.altervista.org