Appunti di Sistemi integrati di produzione

C

Dinamica del processo: il cliente entra nel sistema all’istante n (n-1 clienti sono già entrati, alcuni sono stati

n C W

serviti e sono usciti, altri sono in servizio e altri sono in attesa), subisce un tempo di attesa dal

n n

momento in cui entra al momento in cui viene servito (nel mentre altri clienti vengono serviti e altri

C

entrano nel sistema), viene prelevato dalla coda secondo la regola di priorità in vigore e trascorre

n

t C S =W +t

un tempo in servizio, esce dal sistema dopo un tempo detto tempo di

n n n n n

attraversamento del sistema. τ =i -i

Distribuzione degli arrivi: tra due clienti successivi trascorre un intervallo di tempo che la teoria delle

n n n-1

code modella come una variabile aleatoria con distribuzione nota.

τ

Le distribuzioni più comunemente impiegate per modellare sono:

n

• f(τ)=δ(τ– τ )

Distribuzione costante: dove δ è la funzione di Dirac.

0

• -λτ -1 -1 -λτ

f(τ)= λe , E( λ e σ( λ , F(τ)= 1-e

Distribuzione esponenziale: τ)= τ)=

La distribuzione esponenziale per la modellazione dell’intervallo di tempo tra arrivi successivi riveste

particolare importanza ed è spesso impiegata perché: 1) c’è una buona accordanza con le

osservazioni sperimentali, 2) gode di un certo numero di proprietà per cui è possibile determinare

per via analitica senza approssimazione le principali caratteristiche di un sistema a coda,

3) la probabilità che si abbiano k arrivi nell’intervallo (0,T] segue una

distribuzione di Poisson.

4) gli interarrivi esponenziali e il numero di arrivi Poissoniani caratterizzano un processo di Poisson,

che gode della proprietà di mancanza di memoria: la probabilità che nel prossimo intervallo di tempo

→

Δτ si verifichi un arrivo non dipende dal tempo intercorso dall’ultimo arrivo la distribuzione

esponenziale è l’unica a godere della proprietà secondo cui la distribuzione del tempo residuo è

indipendente dal tempo già maturato. [DIMOSTRAZIONE SU NOTABILITY]

t

Distribuzione del tempo di servizio: anche è modellato come una variabile aleatoria e le distribuzioni più

n

comunemente impiegate sono:

• δ(t-t )

f(t)=

Distribuzione costante: dove δ è la funzione di Dirac.

0

UA 9

• -μτ -1 -1

f(t)= μe , E(t)= μ e σ(t)= μ

Distribuzione esponenziale: (tempo di servizio impossibile che

→

va a 0 non ottimale).

• Altre come Erlang, iper-esponenziale…

Discipline di priorità: regole che determinano come il servitore sceglie il prossimo cliente da servire. Tipi:

• Discipline basate sull’ordine di arrivo: First Come First Served (FCFS), Last Come First Served (LCFS),

random order.

• Discipline basate sulla classe dei clienti: Head Of Line (HOL), i clienti vengono assegnati ad una classe

e a ciascuna di queste viene associato un livello di priorità, nell’ambito della stessa classe la disciplina

è FCFS o LCFS ma i clienti di classi inferiori vengono serviti solo se non ci sono clienti di classi a

priorità maggiore.

• Discipline basate sulla durata del servizio richiesto : Shortest Processing Time (SPT) o Longest

Processing Time (LPT).

Classificazione delle code isolate: ciascuna coda viene caratterizzata con la notazione A/S/m/P/BL/Pr dove: A

indica la distribuzione degli arrivi, S indica la distribuzione dei tempi di servizio, m è il numero di

servitori, P è la numerosità della popolazione di clienti, BL è la capacità massima della coda e Pr

indica la disciplina di priorità. {D: costante, M: esponenziale, G: generale}.

ese: M/M/1: distribuzione arrivi e servizio esponenziali, coda Single Server, popolazione infinita

(omessa), spazio atteso infinito (omessa) e disciplina FCFS (omessa).

Prestazioni delle code isolate: 1

• = λ

Intensità di traffico: quantità di servizio richiesto nell’unità di tempo, .

μ

• Capacità del sistema: quantità del servizio che il sistema può produrre nell’unità di tempo C=m=num servitori

λ

• = min [ , 1] = [ , 1],

Fattore di utilizzo: rapporto tra intensità di traffico e capacità del sistema, μ∗m

si può interpretare anche come percentuale di servitori mediamente occupata.

• Flusso uscente (throughtput): quantità di clienti che escono dal sistema per UDT, nei casi più

ℎ = min (λ, mμ)

semplici (popolazioni infinita e spazio d’attesa infinito) si calcola come ovvero il

minimo tra il flusso entrante e la capacità massima del sistema.

• Dal punto di vista del cliente: tempo di attraversamento (s ), tempo di attesa in coda (w ) e tempo di

n n

servizio (t ).

n

• Dal punto di vista aggregato: numero di clienti nel sistema (n(t)), numero clienti in coda (q(t)),

numero clienti in servizio (n (t)), se il sistema ha capacità m, deve essere: q(t)=max(0, n(t)-m).

s

Teorema di Little: stabilisce una relazione tra flusso in entrata, tempo di attraversamento e numero di clienti

compresi tra due confini specificati di un sistema a coda.

λE(s) = E(n), λE(w) = E(q), λE(t) = E(n )

Il risultato non dipende dalla distribuzione degli arrivi e del tempo di servizio e rimane valido qualunque sia la

disciplina di servizio, purché conservativa (clienti in coda verranno prima o poi serviti, non abbandonati).

[Dimostrazione intuitiva che la prima relazione è valida almeno per le medie campionarie di n(t) e s su iPad].

n

()

1 1

̅ = λ̅ → ̅ = lim ∫ (), λ = lim , ̅ = lim ∑

→∞ →∞ →∞

0 =1

UA 10

̅

̅ = ̅ = =

Esempio prestazioni: -numero medio di clienti nel sistema: , -tempo di attraversamento:

1− λ

1 2

1 1

μ ̅̅

= ̅ = ̅ − = = = =

, -numero medio di clienti in coda: , -tempo medio di attesa:

1− λ 1− 1− λ 1− μ

Reti di code: si tratta di sistemi a coda con struttura a rete, in cui più sistemi a cosa isolata concorrono all’esecuzione

del servizio completo. Si prestano a modellare contesti applicativi che prevedono insiemi di moduli o

elementi tra loro interconnessi in modo che l’input di ciascuno sia una combinazione degli output degli altri.

Classificazione delle reti di code:

• Sistema chiuso/aperto: numero di clienti che circolano nel sistema è fisso/variabile.

• Blocking/non-blocking: i buffer sono finiti e, se il buffer a valle di un server è pieno, il server a monte si blocca

o i buffer sono infiniti e nessun server può mai bloccarsi.

• Distribuzione degli arrivi al sistema.

• Distribuzione dei tempi di servizio.

• Disciplina di servizio.

• Reliable/unreliable server: affidabilità dei server inferiore o pari a 1.

• Single/multi class: aggregazione dei parametri dei diversi tipi di cliente in un cliente rappresentativo o

modellazione esplicita dei diversi tipi di cliente del sistema.

• Routing dipendente/indipendente dallo stato del sistema: i clienti visitano i server seguendo un percorso che

dipende dallo stato del sistema o meno.

L’estensione della teoria delle code alle reti di code ha portato i seguenti risultati:

• Teoremi che consentono il calcolo esatto delle prestazioni delle reti caratterizzate da distribuzione

esponenziale dei tempi di servizio e interarrivo.

• Metodi approssimati che consentono di valutare con discreta precisione le prestazioni delle reti con

caratteristiche generali.

Prestazioni delle reti di code:

• Flusso uscente dalla coda i-esima e dal sistema.

• Utilizzo delle stazioni della rete.

• Dimensione della coda i-esima, numero medio di clienti in attesa o in servizio alla coda i-esima.

• Probabilità marginale: è la probabilità di trovare n clienti nella coda i-esima.

i

• Tempo di attraversamento della coda i-esima e della rete.

I risultati ottenuti estendendo la teoria delle code alle reti di code non sono in forma esplicita come nel caso delle

code isolate, occorre infatti modellizzare le transizioni dei clienti da una coda all’altra e, in generale, non è

possibile analizzare ciascuna coda indipendentemente dalle altre. Occorre pertanto implementare,

avvalendosi di un calcolatore, gli algoritmi utili alla valutazione di tali parametri di prestazione.

UA 11

Le stazioni di lavoro, carico/scarico e i trasportatori possono essere modellati come code SS, MS o IS, le parti da

produrre possono essere aggregate in classi seguendo i principi della Group Technology e rappresentate da una parte

→

standard per classe di aggregazione la variabilità dei tempi di servizio assume allora il significato di distribuzione dei

tempi di lavorazione, carico/scarico e trasporto specifici per ciascuna parte della classe considerata, il flusso uscente

dal sistema coincide con il flusso uscente dalle stazioni di scarico dei pallet.

Modello semplice FMS: rete di code chiusa (pallet in numero finito e costante), non-blocking, distribuzione degli arrivi

e dei tempi di servizio esponenziali, disciplina: FCFS, reliable server, single class e routing indipendente. È un modello

che semplifica le dinamiche del sistema ma permette di avere una valutazione molto più accurata di quella che si

ottiene con i metodi statici pur richiedendo livello di complicazione computazionale e di modellazione contenuto. La

qualità dei risultati è coerente con l’obiettivo di ridurre per stadi successivi, attraverso l’uso di strumenti via via più

complessi e precisi, l’insieme di alternative ammissibili fino a trovare l’alternativa migliore.

Mean Value Analysis: è un efficiente algoritmo per l’analisi delle reti di code chiuse e la determinazione dei valori

medi dei parametri di prestazione: lunghezza delle code, tempo di attraversamento e flusso uscente.

L’efficienza dell’algoritmo però si paga in quanto con la MVA non è possibile calcolare la distribuzione di

probabilità congiunta delle lunghezze delle code, ovvero la distribuzione di probabilità degli stati possibili

della rete. Si basa su tre equazioni:

−1 −1

̅() = μ + μ

̅ ( − 1)

1. , è il tempo medio di attraversamento della stazione i-esima.

() = ,

2. &eg