La teoria delle code si concentra sulla comprensione di come funzionano le linee, o code, e come aumentarne l’efficienza. Utilizza la conoscenza della teoria della probabilità per calcolare le diverse fasi del processo.
Nella nostra vita, siamo stati tutti in coda per acquistare generi alimentari dal supermercato più vicino o per prelevare denaro da un bancomat. Se sei una persona razionale allora deve essere arrivata una domanda: come fanno queste organizzazioni a calcolare quanti sportelli bancomat/bancomat dovrebbero essere sufficienti per un’elaborazione efficiente dei clienti? La risposta viene dal famoso concetto matematico “The Queuing Theory”. In questo articolo discuteremo la formulazione matematica della teoria delle code con un funzionamento approfondito e l’applicazione di questo concetto nella vita reale. Insieme a questi, cercheremo di capire la sua applicabilità al machine learning . Di seguito sono riportati gli argomenti da trattare in questo articolo.
Sommario
Una delicata introduzione alla teoria delle code
Il funzionamento matematico della teoria delle code
Modelli in coda
Applicazioni della teoria delle code
Iniziamo con un’introduzione al concetto di teoria delle code che fornirà una panoramica di alto livello di questo concetto.
Una delicata introduzione alla teoria delle code
La teoria delle code si concentra sulla comprensione di come funzionano le linee, o code, e come aumentarne l’efficienza. Ci sono alcuni aspetti di questo studio, incluso il modo in cui le persone si comportano quando devono aspettare per effettuare un acquisto o ricevere un servizio, che tipo di organizzazione della coda sposta le persone in modo efficace attraverso le linee e anche determinare quante persone possono essere elaborate attraverso la coda all’interno un dato periodo.
Una teoria delle code è essenzialmente uno strumento per l’analisi dei costi. La maggior parte delle aziende non potrebbe operare in modo che nessuno dei suoi clienti abbia mai dovuto fare la fila, o perché sarebbe proibitivo o perché non hanno così tanti clienti.
( collegamento GIF )
La gif sopra è l’esempio perfetto di un errore del sistema. Di conseguenza, le aziende utilizzano la teoria delle code per impostare le proprie operazioni in modo da trovare un equilibrio tra il costo del servizio ai clienti e l’inconveniente di dover fare la fila. La teoria delle code ha quattro fattori principali che aiutano a derivare i risultati:
Il metodo con cui i clienti arrivano in coda.
La natura della coda indica in che modo sta operando la coda.
Il metodo di erogazione del servizio.
Il metodo di partenza dalla posizione della coda.
Capiamo la formulazione matematica necessaria per ottenere le risposte di cui sopra.
Stai cercando un repository completo di librerie Python utilizzate nella scienza dei dati, dai un’occhiata qui .
Il funzionamento matematico della teoria delle code
La teoria delle code utilizza la conoscenza della teoria della probabilità per calcolare le diverse fasi del processo. Utilizza principalmente la distribuzione di probabilità esponenziale e di Poisson. Diamo un’occhiata a come queste probabilità vengono utilizzate dalla teoria delle code.
Distribuzioni di probabilità esponenziale e di Poisson
Nella teoria delle code, la distribuzione esponenziale con un parametro rate e una variabile casuale esponenziale viene calcolata per un tempo di interarrivo in un processo a punti di Poisson . Questa distribuzione può essere utilizzata per modellare i tempi di arrivo dei clienti o i tempi di servizio per diversi motivi.
La funzione esponenziale è una funzione strettamente decrescente della variabile casuale, il che significa che è più probabile che il tempo tra gli arrivi sia piccolo che grande dopo che si è verificato un arrivo.
Esiste una proprietà nota come “nessuna memoria” nella distribuzione esponenziale, il che significa che il tempo fino al prossimo arrivo non dipende da quanto tempo è già trascorso. Poiché le azioni dei clienti sono indipendenti, questo ha senso intuitivo per un modello che misura gli arrivi dei clienti.
La distribuzione di Poisson si riferisce alla distribuzione esponenziale perché viene utilizzata per determinare la probabilità che un certo numero di arrivi si verifichi in un determinato intervallo di tempo.
Quando non ci sono arrivi, la distribuzione di Poisson fornisce un valore esponenziale che è uguale alla probabilità del tempo di interarrivo maggiore della variabile casuale della distribuzione esponenziale. Le probabilità di zero arrivi in un periodo sono correlate con le probabilità di un tempo di interarrivo di una certa lunghezza. Il tempo inter-arrivo si riferisce al periodo che intercorre tra l’arrivo dei clienti.
A volte le distribuzioni di probabilità esponenziale e di Poisson non spiegano chiaramente la distribuzione delle variabili in quel caso viene utilizzata la distribuzione di Erlang.
Quando la distribuzione esponenziale è generalizzata forma la distribuzione Erlang. Una variabile casuale, denominata variabile casuale Erlang, è una misura dell’intervallo di tempo tra un evento specifico e una variabile casuale esponenziale indipendente per l’evento successivo. Questa generalizzazione si ottiene introducendo due nuovi parametri nella distribuzione esponenziale.
Il parametro shape generalizza la forma della distribuzione indicata con ‘k’
Il parametro di scala è il reciproco del parametro di velocità della distribuzione esponenziale.
Ma dove useremo queste distribuzioni di probabilità? La risposta sta nel calcolo del processo di input e output per una coda.
Il processo di input
Il processo di input calcola l’arrivo dei clienti inizializzando l’ora per ogni cliente. Questo tempo viene quindi utilizzato per calcolare ulteriormente la variabile indipendente casuale per la funzione esponenziale. Si presume che non possa verificarsi più di un arrivo in un dato istante. Se possono verificarsi più arrivi in un dato istante, sono consentiti arrivi in blocco.
Un modello a sorgente finita trae i suoi arrivi dalla popolazione e un modello bulking è quello in cui i clienti arrivano ma non entrano. La funzione non di memoria della distribuzione esponenziale entra in gioco poiché l’azione di ciascun cliente è indipendente dall’altro.
Il processo di uscita
Il processo di servizio descrive il processo di output di un sistema di code. Per determinare il tempo di servizio di un cliente, specifichiamo una distribuzione di probabilità. Esistono due disposizioni di server, parallelo e serie .
Parallelamente, se tutti i server forniscono lo stesso tipo di servizio, un cliente deve passare solo attraverso un server per ricevere il servizio.
In serie, un cliente deve passare attraverso diversi server per ricevere il servizio.
In questo processo, la distribuzione esponenziale non spiega accuratamente i tempi di servizio in quanto un servizio che richiede molte fasi di servizio diverse, richiede una distribuzione di probabilità molto più flessibile, motivo per cui la distribuzione di Erlang viene utilizzata in questo processo.
Discipline in coda
La disciplina della coda descrive come gli arrivi vengono presi per il servizio. È normale che un nuovo arrivato venga messo alla fine della coda e non venga servito fino a quando tutti gli arrivi non sono stati gestiti. Esistono tre discipline di base per le code:
Disciplina First Come First Serve (FCFS).
Disciplina Last Come First Served (LCFS).
Disciplina del servizio in ordine casuale (SIRO).
A seconda della disciplina scelta, è probabile che i tempi di attesa dei clienti varino in modo significativo. Ad esempio, nessuno vuole arrivare in anticipo a una disciplina LCFS. In generale, la disciplina non ha alcun impatto sulla coda stessa, poiché gli arrivi ricevono costantemente il servizio indipendentemente dalla disciplina. La coda dipende da due fattori.
L’intensità del traffico è espressa come numero medio di arrivi per unità di tempo preso come tempo medio di servizio. Questo carico offerto è una misura di ciò che vogliono i clienti.
In base all’intensità del traffico, viene calcolato il numero di server per carico, chiamato fattore di utilizzo
Notazione Kendall-Lee
Poiché la descrizione di tutte le caratteristiche della coda diventa molto prolissa, viene utilizzata una notazione molto più semplice chiamata notazione Kendall-Lee.
La notazione Kendall-Lee fornisce un totale di sei abbreviazioni per caratteristiche scritte con una barra.
Sulla base delle distribuzioni di probabilità della prima e della seconda caratteristica, la prima e la seconda caratteristica descrivono i processi di arrivo e di servizio. Per la prima e la seconda caratteristica, M rappresenta una distribuzione esponenziale
E rappresenta una distribuzione Erlang
G rappresenta una distribuzione generale
La terza caratteristica specifica il numero di server che lavorano contemporaneamente, detti anche server paralleli.
Il quarto descrive la disciplina della coda secondo il suo acronimo dato.
Il quinto descrive il numero massimo di clienti che possono essere ospitati nel sistema.
Il sesto è il numero di clienti da cui il sistema può attingere.
Ad esempio, in una banca, il modello di accodamento è rappresentato come M/M/5/F CF S/20/, che può essere decodificato come tempi di arrivo esponenziali, tempi di servizio esponenziali, una disciplina di coda FCFS e una capacità totale di 20 clienti, e un bacino di popolazione infinita da cui attingere.
Parliamo di diversi modelli di coda che sono stati utilizzati.
Modelli in coda
Possiamo ora analizzare diversi modelli basati sulla conoscenza preliminare della funzionalità della teoria delle code.
Il sistema di accodamento M/M/1/GD/∞/∞
Un sistema M/M/1/GD/∞/∞ ha tempi di interarrivo esponenziali, tempi di servizio esponenziali e un server. Questo sistema può essere modellato come un processo di nascita-morte.
Un processo in cui lo stato del sistema in qualsiasi intervallo di tempo è un numero intero positivo. Ci sono due probabilità importanti in questo processo, la probabilità di nascita e la probabilità di morte .
La probabilità di nascita è la probabilità che un arrivo avvenga nel tempo
Allo stesso modo, la probabilità che il servizio avvenga in un periodo di tempo è la probabilità di morte.
Pertanto, nascite e morti hanno significati simili rispettivamente con l’arrivo e il completamento del servizio. Una nascita aumenta lo stato di uno, mentre una morte diminuisce lo stato di uno. Pertanto, queste due probabilità devono essere indipendenti l’una dall’altra.
Il sistema di accodamento M/M/1/GD/c/∞
Questo sistema di accodamento ha tempi di interarrivo e servizio esponenziali, con due diverse velocità esponenziali λ e µ rispettivamente. Il sistema funziona in modo molto simile al sistema nascita-morte, tranne per il fatto che quando un cliente “c” è presente nel sistema, gli arrivi aggiuntivi sono esclusi dall’ingresso e da allora in poi non vengono più conteggiati.
Ad esempio, un cliente tipico non si preoccuperebbe di aspettare in fila in un fast-food se le file sono troppo lunghe. Invece, il cliente visiterebbe un altro ristorante.
Il sistema di accodamento M/M/s/GD/∞/∞
Questo sistema di accodamento ha tempi di interarrivo e servizio esponenziali, con due diverse velocità esponenziali λ e µ rispettivamente. In questo sistema ci sono “server” disposti a servire un’unica linea di clienti, come forse si troverebbe in una banca. Se il numero di clienti presenti nel sistema è inferiore al numero di server, allora ogni cliente viene servito. Se il numero di clienti è maggiore del numero di server nel sistema, i clienti ‘s’ vengono serviti e gli altri clienti sono in fila.
I sistemi di accodamento M/G/∞/GD/∞/∞ e GI/G/∞/GD/∞/∞
Questi sistemi sono unici in quanto dispongono di un numero infinito di server, il che significa che un cliente non dovrà mai aspettare in coda per l’inizio del servizio. Pensa a questo come a un self-service, simile allo shopping online.
Il sistema di coda M/G/s/GD/s/∞
In questo sistema in cui un cliente arriva e vede che tutti i server sono occupati, di conseguenza, il cliente lascia completamente il sistema senza ricevere alcun servizio. In questo caso non viene creata alcuna coda e diciamo che i clienti bloccati sono stati cancellati.
Applicazioni della teoria delle code
La teoria delle code è utilizzata in vari settori di cui facciamo parte nella vita quotidiana. Diamo un’occhiata ad alcuni casi d’uso popolari attraverso i quali possiamo comprenderne l’applicabilità nell’apprendimento automatico.
A. Applicazioni della teoria delle code nella previsione del tempo di attesa
Teoria delle code nel servizio clienti
Nel servizio clienti viene utilizzato il modello di accodamento M/M/S. In questo modello ci sono tempi inter-arrivo, tempi di servizio esponenziali e server. Qui i clienti sono chiamati chiamanti, i server sono operatori telefonici. Queste code sono costituite da chiamanti in attesa che lo stato venga servito dalle risorse di sistema.
Teoria delle code all’ATM
In un ATM viene utilizzato il modello di accodamento M/M/1 in cui sono presenti tempi inter-arrivi, servizio esponenziale e un unico server per servire i clienti. Qui l’orario di servizio e l’orario di arrivo sono distribuiti in modo esponenziale. Qui nel modello vengono utilizzati la coda singola e il server singolo.
Teoria delle code nella gestione delle biblioteche
Lo scopo della fila nelle biblioteche è quello di facilitare la circolazione dei libri, i servizi di sportello e i servizi annessi. Le attività di base nella biblioteca sono la manutenzione dello stack, la gestione dei membri, la selezione dei materiali della biblioteca e la pianificazione dell’acquisizione dei materiali.
B. Applicazioni della teoria delle code nella schedulazione dinamica
Teoria delle code in Processors
Il processore pianifica l’attività in base alla loro priorità. Ad esempio, 10 diverse applicazioni sono in esecuzione sul tuo smartphone e sono tutte accodate di conseguenza, ma il processore deciderà quale app eseguire in background in modo che il tuo utilizzo della RAM non venga influenzato. In questo, il processore utilizza la disciplina dell’accodamento basato sulla priorità per accodare le applicazioni in background.
Teoria delle code nel sistema informatico
L’arrivo dei lavori in un sistema informatico si comporta come il processo di arrivo e il tempo di esecuzione è il processo di Poisson. I lavori vengono eseguiti nell’ordine in cui arrivano, quindi FCFS viene utilizzato come disciplina di arrivo in coda. Se il computer è occupato all’arrivo del lavoro, viene inserito in una coda.
Insieme ai casi d’uso sopra menzionati, questa teoria ha anche applicazioni nei seguenti compiti: –
Migliorare l’efficienza dei dipendenti
Miglioramento della qualità del servizio
Miglioramento delle vendite in tutto il negozio
Aumentare la fidelizzazione dei clienti
Semplificazione della comunicazione
Riduzione dei costi operativi
Programmazione negli ospedali
Nel dominio dell’apprendimento automatico, la teoria delle code è comunemente usata nella previsione del tempo di attesa. Le applicazioni di cui sopra possono anche essere considerate e modellate con i principi dell’apprendimento automatico al fine di ottenere risultati migliori.
Verdetto finale
C’è spesso una forma di coda ogni volta che la domanda corrente per un servizio supera la capacità corrente di quel servizio. Questo articolo fornisce alcuni concetti fondamentali della teoria delle code e delle sue applicazioni. Abbiamo anche trattato gli importanti casi d’uso della teoria delle code e ne abbiamo compreso l’applicabilità al dominio dell’apprendimento automatico.
DI SOURABH MEHTA da analyticsindiamag.com/
