Modelli di sistemi di code. Modelli matematici dei più semplici sistemi di accodamento

Chetverikov S. Yu., Popov MA

Russia, Istituto di Economia e Imprenditorialità (Mosca)

La teoria dei sistemi di code è una disciplina matematica applicata che indaga caratteristiche numeriche fenomeni che si verificano nell'economia. Questi includono il funzionamento di una centrale telefonica, centri di assistenza ai consumatori, registratori di cassa in un supermercato, ecc.

I modelli matematici di tali oggetti sono sistemi di accodamento (QS) descritti come segue: le richieste (domande di servizio) entrano nel sistema, ognuna delle quali viene servita per un certo tempo e poi esce dal sistema. Tuttavia, a causa dei vincoli di risorse (numero di registratori di cassa in servizio, velocità del servizio, ecc.), il sistema è in grado di servire solo un certo numero di sinistri contemporaneamente. I modelli matematici in questo caso sono progettati per risolvere il problema del calcolo degli indicatori numerici della qualità di funzionamento del QS.

Quando si costruiscono modelli QS, si distinguono fondamentalmente due sistemi: deterministico e stocastico, che determinano effettivamente il tipo di modello matematico.

Consideriamo il più semplice sistema deterministico costituito da P dispositivi identici, in cui i requisiti arrivano a intervalli di tempo deterministici (costanti) e anche il tempo per soddisfare ogni requisito è costante. È ovvio che se le richieste arrivano a intervalli

e il tempo di servizio per ogni esigenza è

allora la condizione necessaria e sufficiente per il normale funzionamento del sistema è il compimento della disuguaglianza

Altrimenti, nel tempo, i requisiti si accumuleranno nel sistema.

Opzioni X e q hanno un semplice significato fisico:

X- il numero medio di richieste pervenute per unità di tempo o l'intensità del flusso in entrata;

q è il numero medio di requisiti che ciascun dispositivo è in grado di soddisfare per unità di tempo o l'intensità dei requisiti di manutenzione da parte di un dispositivo;

/ 7ts - il numero medio di requisiti che sono in grado di soddisfare P apparecchi o il requisito di intensità di manutenzione dell'intero sistema.

Pertanto, la condizione (1) significa che l'intensità del flusso in entrata non deve superare l'intensità dei requisiti di servizio dell'intero sistema. Considera la quantità

Il cosiddetto avvio di sistema.

Allora la disuguaglianza (1) può essere riscritta come:

In questo caso, il carico può essere interpretato come la frazione media di tempo durante la quale i dispositivi sono impegnati a soddisfare i requisiti e il valore di 1 - p - come la frazione media del tempo durante la quale i dispositivi sono inattivi.

Infine, una nota in più sul funzionamento di un sistema con caratteristiche deterministiche:

se al momento iniziale l'impianto è libero e la condizione (2) è soddisfatta, allora ogni domanda che entra nell'impianto diventa immediatamente il dispositivo di servizio;

nel caso pag

infine, se p > 1, allora per unità di tempo la coda aumenta in media di Mr-1).

Nei sistemi di coda reali, gli elementi di casualità giocano un ruolo significativo:

in primo luogo, i tempi tra gli arrivi dei sinistri non sono deterministici;

in secondo luogo, i tempi di servizio delle richieste non sono deterministici.

Inoltre, possono comparire elementi di casualità a causa di altri motivi, ad esempio guasti di elementi di sistemi di accodamento.

Si scopre che gli elementi di casualità influiscono in modo significativo sulla qualità del funzionamento dei sistemi di servizio. Quindi, se il carico p = 1, allora, contrariamente ai sistemi deterministici, nei sistemi stocastici la coda tende in media all'infinito nel tempo. Le code nei sistemi stocastici si formano anche nel caso p

Si consideri una descrizione formalizzata di QS. I parametri principali del QS sono:

flusso di requisiti in entrata;

struttura del sistema;

caratteristiche temporali dei requisiti di servizio;

disciplina del servizio.

Diamo un'occhiata a queste opzioni.

Flusso in entrataè caratterizzato da momenti casuali di ricezione dei requisiti in un sistema semplice e, per i sistemi complessi, dai tipi di requisiti che arrivano in questi momenti.

Quando si specifica un flusso casuale, di solito si presume che il flusso di input sia ricorrente e, molto spesso, Poisson.

Facciamo alcune osservazioni sulla correttezza della descrizione dei flussi di domanda che entrano nei sistemi reali di Poisson e di quelli ricorrenti. Ovviamente, la proprietà dell'assenza di effetto collaterale nei sistemi reali è estremamente rara, poiché un flusso con tale proprietà può ricevere un numero arbitrariamente grande di requisiti con una probabilità diversa da zero (sebbene estremamente piccola) in qualsiasi periodo di tempo arbitrariamente piccolo. Tuttavia, la pratica mostra che la descrizione del flusso in entrata da parte di Poisson è legittima nella maggior parte dei casi con un grado di accuratezza sufficiente. Un'ulteriore conferma matematica di questo fatto è il teorema di Khinchin, che dice che l'unione di un gran numero di flussi "rari" sotto vincoli molto deboli dà un flusso di Poisson.

Anche la seconda proprietà del flusso di Poisson, la stazionarietà, non suscita critiche. Infatti, l'intensità del flusso in entrata, di regola, dipende dall'ora del giorno, dall'anno e così via. Se vengono preservate le proprietà di assenza di effetti collaterali e ordinarietà, si ottiene un flusso di Poisson non stazionario. In alcuni casi è possibile sviluppare modelli matematici per il calcolo sistemi economici con un tale flusso in entrata, ma le formule risultanti sono molto ingombranti e difficili da realizzare applicazione pratica. Per questo motivo i calcoli sono limitati ad un certo intervallo di tempo in cui l'intensità del flusso in ingresso cambia poco.

Se si abbandona solo la proprietà di ordinarietà, si ottiene un flusso di Poisson non ordinario, in cui i momenti di arrivo dei requisiti formano un flusso di Poisson ordinario, ma in ogni momento arriva un numero casuale di requisiti. La maggior parte dei risultati validi per i sistemi con un flusso di Poisson si trasferiscono praticamente invariati ai sistemi con un flusso di Poisson non ordinario.

Per impostare la struttura QSè necessario elencare tutti gli elementi disponibili nel sistema, e indicare quali tipi di esigenze o anche in quali fasi del servizio ogni elemento può servire. In questo caso, un singolo elemento può servire richieste di più tipi e, viceversa, richieste dello stesso tipo possono essere servite su più elementi. In quanto segue, assumeremo che il QS abbia uno o più elementi identici e ogni requisito può essere soddisfatto su uno qualsiasi di essi. Si chiamano sistemi di questo tipo linea singola(un elemento) o multilinea(più elementi).

I sistemi di servizio possono avere elementi per le richieste in attesa dell'inizio del servizio. Se ci sono infiniti di tali elementi, allora parlano di sistemi con attesa, se il loro numero è finito - di sistemi con un numero finito di posti di attesa, se sono del tutto assenti (il requisito che ha reso tutti gli elementi occupati in quel momento di ingresso nel sistema è perso; un esempio sono i normali sistemi telefonici) - sui sistemi con perdite.

Tempi i requisiti di servizio sono anche un oggetto complesso per una descrizione formalizzata. Di solito si presume che i tempi di servizio di tutti i clienti siano indipendenti l'uno dall'altro e siano variabili casuali equamente distribuite. Se il QS riceve richieste di vario tipo, la distribuzione del tempo di servizio può dipendere dal tipo di richiesta.

Disciplina del servizio consiste nella regola dell'accodamento dei requisiti e dell'ordine in cui vengono selezionati dalla coda per il servizio, nella distribuzione degli elementi tra i requisiti e nei sistemi multifase - tra le fasi del servizio. Assumeremo che la disciplina più semplice sia implementata nel sistema: soddisfare il requisito nell'ordine di arrivo (FIFO). Nei sistemi multilinea, viene formata una coda comune per tutti gli elementi e la prima richiesta nella coda va a qualsiasi elemento liberato.

Tuttavia, QS utilizza anche discipline di servizio più complesse. Gli esempi più semplici di tali discipline sono l'ordine di servizio di inversione (inverso) (LIFO), in cui viene soddisfatto l'ultimo requisito entrato nel sistema.

La disciplina della separazione uniforme degli elementi del sistema, in cui ciascuno di P i requisiti nel sistema sono serviti alla stessa tariffa 1/pag. A volte, nel momento in cui un'esigenza entra nel sistema, si conosce l'ora del suo servizio (il lavoro da svolgere). Quindi è possibile utilizzare discipline che dipendono dai tempi di servizio residui delle richieste. In particolare, la disciplina di servire il primo requisito con il tempo di servizio minimo residuo consente di ottenere in qualsiasi momento la lunghezza minima della coda. L'utilizzo di complesse discipline di servizio consente molto spesso, senza alcun costo aggiuntivo, di migliorare sensibilmente la qualità del funzionamento del QS.

Una classe speciale di QS è costituita dai sistemi prioritari che ricevono flussi di richieste con priorità diverse e le richieste con priorità più elevate hanno la precedenza sulle richieste con priorità più basse, ad es. servito in precedenza. Le priorità possono essere relative, quando le richieste con priorità più alta non interrompono i servizi con le richieste con priorità più bassa sugli elementi, e assolute, quando si verifica tale interruzione.

Nel caso di priorità assolute, sono possibili anche varie modifiche: i clienti sottoserviti con servizio interrotto lasciano gli impianti (sistemi con dropout), continuano a essere assistiti dopo che tutti i clienti con priorità più alta hanno lasciato il sistema (sistemi con assistenza post-vendita) e vengono nuovamente assistiti.

Le discipline di servizio dovrebbero includere anche fattori come la fase preparatoria prima dell'inizio della manutenzione del requisito successivo o dopo che un requisito è arrivato in un sistema libero, la fase di passaggio di un elemento a requisiti di servizio di tipo diverso, i requisiti di manutenzione da parte di elementi inaffidabili di il sistema, ecc. Infine, la quantità di tempo che una richiesta trascorre nel sistema o il tempo necessario per attendere l'inizio del servizio può essere limitato.

Descriviamo ora quelle caratteristiche QS che interessano all'utente. A volte in pratica vengono chiamate caratteristiche probabilistico-temporali. I più importanti sono lunghezza della coda(ovvero il numero di richieste in attesa di essere evase) e tempo di attesa per l'inizio della pubblicazione della richiesta. Poiché sia ​​la lunghezza della coda che il tempo di attesa per l'inizio del servizio sono variabili casuali, allora, naturalmente, sono descritte dalle proprie distribuzioni. Inoltre, le distribuzioni della lunghezza della coda e del tempo di attesa dipendono dall'ora corrente.

Nei sistemi con perdite o un numero finito di posti di attesa, le caratteristiche più importanti includono anche la probabilità di perdere il credito. A volte, insieme alla lunghezza della coda, prendono in considerazione il numero totale di richieste nel sistema, e insieme al servizio inizia il tempo di attesa - tempo di permanenza del requisito nel sistema.

Negli impianti con perdite oa numero finito di posti di attesa, nonché negli impianti con attesa e carico p

La maggior parte dei lavori sulla teoria delle code sono dedicati alla ricerca di caratteristiche stazionarie, sebbene le caratteristiche non stazionarie siano state studiate in modo sufficientemente dettagliato.

Letteratura

• 1. Gnedenko B.V. Corso di probabilità. Mosca: Fizmatgiz, 1961.
• 2. Feller W. Introduzione alla teoria della probabilità e sue applicazioni.T.I. M.: Signor,
• 1984.
• 3. Gnedenko B.V., Kovalenko I.N. Introduzione alla teoria delle code. Mosca: Nauka, 1966.
• 4. Saaty TL Elementi di teoria delle code e sue applicazioni. M.: Sov. radiofonico, 1965.

Considerato nella lezione precedente, un processo casuale di Markov con stati discreti e tempo continuo si svolge nei sistemi di coda (QS).

Sistemi di coda - si tratta di sistemi in cui le richieste di servizio vengono ricevute in tempi casuali, mentre le richieste ricevute vengono evase utilizzando i canali di servizio a disposizione del sistema.

Esempi di sistemi di accodamento sono:

• nodi di regolamento e di cassa in banche, imprese;
• computer personale, al servizio delle applicazioni in arrivo o dei requisiti per la risoluzione di determinati problemi;
• stazioni di servizio auto; stazione di servizio;
• società di revisione;
• dipartimenti di ispezioni fiscali coinvolti nell'accettazione e nella verifica della rendicontazione corrente delle imprese;
• centralini telefonici, ecc.

	Nodi	Requisiti
Ospedale	Inservienti	Pazienti
Produzione
L'aeroporto	Uscite di pista Punti di registrazione	Passeggeri

Considera lo schema del funzionamento QS (Fig. 1). Il sistema è costituito da un generatore di richieste, un dispatcher e un nodo di servizio, un nodo di contabilità guasti (terminatore, distruttore di richieste). Nodo di servizio in caso generale può avere più canali di servizio.

Riso. uno

1. Generatore di applicazioni – un oggetto che genera applicazioni: una strada, un'officina con unità installate. L'input è flusso di applicazione(il flusso di clienti al negozio, il flusso di unità rotte (automobili, macchine utensili) per le riparazioni, il flusso di visitatori al guardaroba, il flusso di auto ai distributori di benzina, ecc.).
2. Spedizioniere – una persona o un dispositivo che sa cosa fare con il biglietto. Un nodo che regola e indirizza le richieste ai canali di servizio. Spedizioniere:

• accetta le domande;
• forma una coda se tutti i canali sono occupati;
• li indirizza ai canali di servizio, se presenti;
• rifiuta le domande (per vari motivi);
• riceve informazioni dal nodo di servizio sui canali gratuiti;
• tiene traccia dell'ora del sistema.

1. Giro - richiesta accumulatore. La coda potrebbe non esistere.
2. Nodo di servizio consiste in un numero finito di canali di servizio. Ogni canale ha 3 stati: libero, occupato, inattivo. Se tutti i canali sono occupati, puoi elaborare una strategia a cui trasferire l'applicazione.
3. Rifiuto dal servizio si verifica se tutti i canali sono occupati (alcuni di essi potrebbero non funzionare).

Oltre a questi elementi di base in QS, alcune fonti distinguono anche i seguenti componenti:

terminatore - distruttore di transazioni;

magazzino - stoccaggio di risorse e prodotti finiti;

conto contabile - per l'esecuzione di operazioni del tipo "registrazione";

manager - manager delle risorse;

Classificazione OCM

La prima divisione (dalla presenza di code):

• CMO con errori;
• CMO con una coda.

A CMO con errori una richiesta che arriva nel momento in cui tutti i canali sono occupati viene rifiutata, lascia il QS e non viene ulteriormente servita.

A CMO con una coda un'applicazione che arriva in un momento in cui tutti i canali sono occupati non esce, ma fa la coda e attende un'opportunità per essere servita.

QS con code suddiviso in tipi diversi a seconda di come è organizzata la coda - limitato o non limitato. Le restrizioni possono riguardare sia la lunghezza della coda che il tempo di attesa, "disciplina del servizio".

Quindi, ad esempio, si considerano i seguenti QS:

• QS con richieste impazienti (la lunghezza della coda e il tempo di servizio sono limitati);
• QS con servizio prioritario, ovvero alcune applicazioni vengono servite a turno, ecc.

I tipi di restrizione della coda possono essere combinati.

Un'altra classificazione divide l'OCM in base alla fonte delle applicazioni. Il sistema stesso o un ambiente esterno che esiste indipendentemente dal sistema può generare applicazioni (requisiti).

Naturalmente, il flusso di richieste generato dal sistema stesso dipenderà dal sistema e dal suo stato.

Inoltre, le SMO sono suddivise in aprire OCM e Chiuso SMO.

In un QS aperto, le caratteristiche del flusso di applicazioni non dipendono dallo stato del QS stesso (quanti canali sono occupati). In un QS chiuso, dipendono. Ad esempio, se un lavoratore serve un gruppo di macchine che richiedono aggiustamenti di volta in volta, l'intensità del flusso di "fabbisogni" dalle macchine dipende da quante di esse sono già in buono stato e in attesa di aggiustamento.

Un esempio di sistema chiuso: l'emissione di uno stipendio da parte di un cassiere presso un'impresa.

Per il numero di canali, i QS sono divisi in:

• canale singolo;
• multicanale.

Caratteristiche del sistema di code

Le caratteristiche principali di un sistema di code di qualsiasi tipo sono:

• il flusso di input dei requisiti in entrata o delle richieste di servizio;
• disciplina della coda;
• meccanismo di servizio.

Flusso di input dei requisiti

Per descrivere il flusso di input, è necessario impostare una legge probabilistica che determina la sequenza dei momenti di ricezione dei fabbisogni di servizio, e indicare il numero di tali richieste in ciascuna regolare ricevuta. In questo caso, di regola, operano con il concetto di "distribuzione probabilistica dei momenti di ricezione dei requisiti". Qui puoi comportarti come requisiti singoli e di gruppo (il numero di tali reclami in ogni ricevuta successiva). In quest'ultimo caso, di solito noi stiamo parlando su un sistema di code con servizio a gruppi paralleli.

un io– tempo di arrivo tra i requisiti – variabili casuali indipendenti distribuite in modo identico;

E(A)è l'ora media (MO) di arrivo;

λ=1/E(A)- l'intensità della ricezione dei requisiti;

Caratteristiche del flusso di input:

1. Una legge probabilistica che determina la sequenza dei momenti di ricezione dei fabbisogni di servizio.
2. Il numero di richieste in ogni arrivo successivo per i flussi multicast.

Disciplina della coda

Giro - una serie di requisiti in attesa di essere assistiti.

La coda ha un nome.

Disciplina della coda determina il principio secondo il quale le richieste che pervengono all'ingresso del sistema di servizio sono collegate dalla coda alla procedura di servizio. Le discipline di coda più comunemente utilizzate sono definite dalle seguenti regole:

• primo arrivato, primo servito;

first in first out (FIFO)

il tipo più comune di coda.

Quale struttura dati è adatta per descrivere una tale coda? L'array è danneggiato (limitato). È possibile utilizzare una struttura LIST.

L'elenco ha un inizio e una fine. L'elenco è composto da voci. Una voce è una cella di elenco. L'applicazione arriva alla fine dell'elenco e viene selezionata per il servizio dall'inizio dell'elenco. La voce consiste in una descrizione dell'applicazione e un collegamento (un indice di chi c'è dietro). Inoltre, se la coda ha un limite di tempo, è necessario specificare anche il limite di tempo.

Tu, come programmatori, dovresti essere in grado di creare elenchi a due lati, a un lato.

Elenca le azioni:

• inserire nella coda;
• prendere dall'inizio;
• rimuovere dall'elenco dopo il timeout.
• ultimo arrivato, primo servito LIFO (clip di cartuccia, vicolo cieco alla stazione ferroviaria, entrato in un'auto piena).

Una struttura nota come STACK. Può essere descritto da una struttura a matrice o elenco;

• selezione casuale delle applicazioni;
• selezione delle domande per criterio di priorità.

Ogni applicazione è caratterizzata, tra l'altro, da un livello di priorità e, all'arrivo, viene posta non in coda alla coda, ma alla fine del suo gruppo di priorità. Il dispatcher ordina per priorità.

Caratteristiche della coda

• limitazionetempo di attesa momento del servizio (c'è una coda con tempo limitato attese del servizio, che è associato al concetto di "lunghezza della coda ammissibile");
• lunghezza della coda.

Meccanismo di servizio

Meccanismo di servizio è determinato dalle caratteristiche della procedura di servizio stessa e dalla struttura del sistema dei servizi. Le procedure di servizio includono:

• numero di canali di servizio ( N);
• la durata della procedura di servizio (distribuzione probabilistica del tempo di servizio dei fabbisogni);
• il numero di requisiti soddisfatti a seguito dell'attuazione di ciascuna di tali procedure (per le domande di gruppo);
• la probabilità di fallimento del canale di servizio;
• struttura del sistema dei servizi.

Per una descrizione analitica delle caratteristiche della procedura di servizio si utilizza il concetto di “distribuzione probabilistica del tempo di servizio dei fabbisogni”.

si– tempo di servizio io esimo requisito;

E(S)– tempo medio di servizio;

μ=1/E(S)- la velocità dei requisiti di servizio.

Va notato che il tempo per la manutenzione di un'applicazione dipende dalla natura dell'applicazione stessa o dai requisiti del client e dallo stato e dalle capacità del sistema di manutenzione. In alcuni casi è anche necessario tenerne conto probabilità di guasto del canale di servizio dopo un certo intervallo di tempo limitato. Questa caratteristica può essere modellata come un flusso di guasti che entrano nel QS e hanno la priorità su tutte le altre applicazioni.

Fattore di utilizzo QS

Nμ – velocità di servizio nel sistema quando tutti i dispositivi di servizio sono occupati.

ρ=λ/( Nμ) viene chiamato Fattore di utilizzo QS , mostra quante risorse di sistema vengono utilizzate.

Struttura del sistema dei servizi

La struttura del sistema di servizio è determinata dal numero e disposizione reciproca canali di servizio (meccanismi, dispositivi, ecc.). Innanzitutto va sottolineato che un sistema di servizi può avere non un canale di servizio, ma diversi; un sistema di questo tipo è in grado di soddisfare più esigenze contemporaneamente. In questo caso, tutti i canali di servizio offrono gli stessi servizi e, quindi, si può affermare che esiste servizio parallelo .

Esempio. Registratori di cassa in negozio.

Il sistema di servizio può essere costituito da diversi tipi di canali di servizio attraverso i quali deve passare ogni requisito servito, ovvero nel sistema di servizio le procedure di manutenzione dei requisiti sono implementate in sequenza . Il meccanismo di servizio definisce le caratteristiche del flusso di richieste in uscita (servito).

Esempio. Commissione medica.

Servizio combinato - servizio di deposito presso la cassa di risparmio: prima il controllore, poi il cassiere. Di norma, 2 controllori per cassiere.

Così, la funzionalità di qualsiasi sistema di accodamento è determinata dai seguenti fattori principali :

• distribuzione probabilistica dei momenti di ricezione delle richieste di servizio (singola o di gruppo);
• requisiti di capacità della fonte;
• distribuzione probabilistica del tempo di durata del servizio;
• configurazione del sistema di servizio (servizio parallelo, seriale o parallelo-seriale);
• il numero e le prestazioni dei canali di servizio;
• disciplina della coda.

I criteri principali per l'efficacia del funzionamento del QS

Come i criteri principali per l'efficacia del funzionamento dei sistemi di code A seconda della natura del problema da risolvere, potrebbero esserci:

• la probabilità di servizio immediato dell'applicazione ricevuta (servizio P =K obs /K post);
• la probabilità di rifiuto del servizio della domanda ricevuta (P otk =K otk /K post);

È ovvio che R obl + P otk =1.

Flussi, ritardi, servizio. Formula Pollacek-Khinchin

Ritardo – uno dei criteri del servizio QS, il tempo impiegato dalla richiesta in previsione del servizio.

D i– ritardo nella coda delle richieste io;

W io \u003d D io + S io– tempo trascorso nel sistema del requisito io.

(con probabilità 1) è il ritardo medio stabilito di una richiesta in coda;

(con probabilità 1) è il tempo medio stazionario che il requisito trascorre nel QS (attesa).

Q(t) - il numero di richieste in coda alla volta t;

L(t)– numero di clienti nel sistema alla volta t(Q(t) più il numero di requisiti che sono in servizio in quel momento t.

Quindi esponenti (se presenti)

(con probabilità 1) è il numero medio di richieste in coda in regime stazionario;

(con probabilità 1) è il numero medio di richieste nel sistema in regime stazionario.

Si noti che ρ<1 – обязательное условие существования d, w, Q e l nel sistema di coda.

Se ricordiamo che ρ= λ/( Nμ), allora è chiaro che se l'intensità di ricezione delle richieste è maggiore di Nμ, quindi ρ>1, ed è naturale che il sistema non sarà in grado di far fronte a un tale flusso di applicazioni, e quindi non si può parlare di d, w, Q e l.

I risultati più generali e necessari per i sistemi di accodamento includono le equazioni di conservazione

Si precisa che i suddetti criteri di valutazione delle prestazioni del sistema possono essere analiticamente calcolati per i sistemi di coda M/M/N(N>1), ovvero sistemi con flussi di clienti e servizi Markov. Per M/G/ l per qualsiasi distribuzione G e per alcuni altri sistemi. In generale, la distribuzione del tempo tra gli arrivi, la distribuzione del tempo di servizio, o entrambi devono essere esponenziali (o una sorta di distribuzione Erlang esponenziale del k-esimo ordine) affinché sia ​​possibile una soluzione analitica.

Inoltre, puoi anche parlare di caratteristiche come:

• throughput assoluto del sistema – А=Р servizio *λ;
• throughput relativo del sistema -

Un altro interessante (e illustrativo) esempio di soluzione analitica – calcolo del ritardo di coda medio in regime stazionario per un sistema di code M/G/ 1 secondo la formula:

.

In Russia, questa formula è nota come formula di Pollacek. – Khinchin, all'estero questa formula è associata al nome di Ross.

Quindi, se E(S) Esso ha maggior valore, quindi il sovraccarico (in questo caso misurato come d) sarà più grande; che è prevedibile. La formula rivela anche un fatto meno ovvio: la congestione aumenta anche all'aumentare della variabilità nella distribuzione dei tempi di servizio, anche se il tempo medio di servizio rimane lo stesso. Intuitivamente, questo può essere spiegato come segue: la varianza della variabile casuale del tempo di servizio può richiedere Grande importanza(perché deve essere positivo), cioè l'unico dispositivo di servizio sarà occupato a lungo, che aumenterà la coda.

Il tema della teoria delle code consiste nello stabilire la relazione tra i fattori che determinano la funzionalità del sistema di code e l'efficienza del suo funzionamento. Nella maggior parte dei casi, tutti i parametri che descrivono i sistemi di accodamento sono variabili o funzioni casuali, quindi questi sistemi sono indicati come sistemi stocastici.

La natura casuale del flusso delle domande (requisiti), così come, in generale, la durata del servizio porta al fatto che nel sistema di accodamento si verifica un processo casuale. Per la natura del processo casuale che si verificano in un sistema di code (QS) sono distinti Sistemi Markov e non Markov . Nei sistemi Markov, il flusso in entrata delle richieste e il flusso in uscita delle richieste servite (reclami) sono di Poisson. I flussi di Poisson semplificano la descrizione e la creazione di un modello matematico di un sistema di code. Questi modelli ne hanno abbastanza soluzioni semplici, quindi le applicazioni più note della teoria delle code utilizzano uno schema markoviano. Nel caso dei processi non markoviani, i problemi di studio dei sistemi di accodamento diventano molto più complicati e richiedono l'uso di modelli statistici, metodi numerici che utilizzano un computer.

Nella pratica dell'attività umana, un grande posto è occupato dai processi di accodamento che si verificano in sistemi progettati per essere utilizzati riutilizzabili per risolvere lo stesso tipo di problemi. Tali sistemi sono chiamati sistemi di accodamento (QS). Esempi di tali sistemi sono sistemi telefonici, sistemi informatici, automobilistici, aeronautici, sistemi di manutenzione, negozi, biglietterie e simili.

Ogni sistema è costituito da un certo numero di unità di servizio (strumenti, dispositivi, dispositivi "punti, stazioni), che sono detti canali di servizio. In base al numero di canali, il QS è suddiviso in monocanale e multicanale. Il diagramma di un sistema di code a canale singolo è mostrato in Fig. 6.2.

Le applicazioni di solito non entrano nel sistema regolarmente, ma in modo casuale, formando un flusso casuale di applicazioni (requisiti). Il servizio di ogni esigenza in sé può richiedere un certo tempo o, più spesso, un tempo indefinito. La natura casuale porta al fatto che il QS viene caricato in modo non uniforme: in alcuni periodi di tempo si accumula molto un gran numero di applicazioni (o si mettono in fila o lasciano il QS non servito), mentre negli altri periodi il QS funziona con un carico insufficiente o è inattivo.

Riso. 6.2.

Lo scopo dello studio dei sistemi di accodamento è quello di analizzare la qualità del loro funzionamento e identificare le opportunità per il suo miglioramento. Allo stesso tempo, il concetto di "qualità di funzionamento" avrà il suo in ogni singolo caso significato specifico ed espresso in diversi termini quantitativi. Ad esempio, indicatori quantitativi come la dimensione della coda per il servizio, il tempo medio di servizio, l'attesa del servizio o la ricerca di un requisito nel sistema di servizio, il tempo di inattività dei dispositivi di servizio; fiducia che tutte le richieste ricevute dal sistema saranno soddisfatte.

Pertanto, la qualità del funzionamento del sistema di code è intesa non come la qualità dell'esecuzione di un determinato lavoro, la cui richiesta è stata ricevuta, ma il grado di soddisfazione del bisogno di servizio.

L'oggetto della teoria delle code è la costruzione di modelli matematici che mettono in relazione le condizioni operative date del QS (il numero di canali, le loro prestazioni, la natura del flusso di applicazioni, ecc.) con gli indicatori di prestazione del QS, che descrivono la sua capacità di far fronte al flusso di applicazioni.

Classificazione dei sistemi di coda

La prima caratteristica che permette di classificare i compiti in coda è il comportamento delle richieste ricevute dal sistema di servizio nel momento in cui tutte le macchine sono occupate.

In alcuni casi, un reclamo che entra nel sistema in un momento in cui tutte le macchine sono occupate non può attendere il loro rilascio e lascia il sistema non servito, ad es. la richiesta è persa per il sistema di servizio fornito. Tali sistemi di servizio sono chiamati sistemi con perdite e i problemi formulati sulla base di essi sono chiamati problemi di servizio per sistemi con perdite.

Se, invece, una domanda, entrata nel sistema, entra in coda e attende il rilascio del dispositivo, allora tali sistemi sono chiamati sistemi con attesa e le attività corrispondenti sono chiamate attività di servizio nei sistemi con attesa. QS con attesa si divide in diverse tipologie a seconda di come è organizzata la coda: con una lunghezza della coda limitata o illimitata, con un tempo di attesa limitato, ecc.

I QS differiscono anche per il numero di requisiti che possono essere contemporaneamente nel sistema di servizio. Assegna:

• 1) sistemi con flusso limitato di requisiti;
• 2) impianti con flusso illimitato di fabbisogni.

A seconda delle forme organizzazione interna servizi nel sistema sono:

• 1) impianti con servizio ordinato;
• 2) impianti con servizio disordinato.

Un passo importante nello studio del QS è la scelta dei criteri che caratterizzano il processo in esame. La scelta dipende dal tipo di problemi oggetto di studio, dall'obiettivo perseguito dalla soluzione.

Molto spesso in pratica ci sono sistemi in cui il flusso dei requisiti è vicino al più semplice e il tempo di servizio obbedisce a una legge di distribuzione esponenziale. Questi sistemi sono più completamente sviluppati nella teoria delle code.

Nelle condizioni di un'impresa, sono tipiche attività con attesa, con un numero finito di dispositivi di servizio, con un flusso limitato di requisiti e con manutenzione disordinata.

Negli ultimi decenni, in vari campi economia nazionale c'era la necessità di risolvere problemi probabilistici relativi al funzionamento dei sistemi di code. Esempi di tali sistemi sono centrali telefoniche, officine di riparazione, punti vendita al dettaglio, biglietterie e così via. il lavoro di qualsiasi sistema di accodamento consiste nel soddisfare il flusso in entrata dei requisiti (chiamate degli abbonati, flusso dei clienti al negozio, requisiti per il lavoro in officina, ecc.).
La disciplina matematica che studia i modelli di sistemi di code reali è chiamata teoria delle code. Il compito della teoria delle code è stabilire la dipendenza degli indicatori di prestazione risultanti del sistema di code (la probabilità che il requisito venga soddisfatto; l'aspettativa matematica del numero di requisiti serviti, ecc.) dagli indicatori di input (il numero di dispositivi nel sistema, i parametri del flusso in entrata dei requisiti, ecc.) .) è possibile stabilire tali dipendenze in forma di formula solo per semplici sistemi di accodamento. Lo studio dei sistemi reali viene effettuato imitando o modellando il loro lavoro su un computer utilizzando il metodo dei test statistici.
Il sistema di accodamento si considera fornito se sono definiti:
1) il flusso in ingresso dei fabbisogni, ovvero, in altre parole, la legge di distribuzione che caratterizza i momenti in cui i fabbisogni entrano nel sistema. La causa principale dei requisiti è chiamata sorgente. In quanto segue si intende assumere che la fonte abbia un numero illimitato di requisiti e che i requisiti siano omogenei, cioè differiscano solo nei momenti della loro comparsa nel sistema;
2) un sistema di servizio costituito da un'unità e un nodo di servizio. Quest'ultimo è uno o più dispositivi di servizio, che verranno indicati come dispositivi. Ogni requisito deve andare a uno degli strumenti per essere sottoposto a manutenzione. Potrebbe risultare che i requisiti dovranno attendere fino a quando i dispositivi non saranno liberi. In questo caso, i requisiti sono nel negozio, formando una o più code. Assumiamo che il passaggio del fabbisogno dal nodo di memoria al nodo di servizio avvenga istantaneamente;
3) il tempo di servizio del fabbisogno di ciascun dispositivo, che è una variabile casuale ed è caratterizzato da una certa legge di distribuzione;
4) disciplina di attesa, ossia un insieme di regole che disciplinano il numero di requisiti che contemporaneamente sono presenti nel sistema. Un sistema in cui una domanda in entrata viene rifiutata quando tutti i dispositivi sono occupati viene chiamato sistema senza attesa. Se una richiesta che ha tenuto occupati tutti i dispositivi entra in coda e attende fino a
fino a quando uno dei dispositivi non diventa libero, un tale sistema viene chiamato puro sistema di attesa. Un sistema in cui un cliente che ha tenuto occupati tutti i server entra in coda solo se il numero di clienti nel sistema non supera un certo livello (altrimenti il ​​cliente è perso) è chiamato sistema di code miste;
5) disciplina del servizio, ovvero un insieme di regole in base alle quali il requisito viene selezionato dalla coda per il servizio. Le seguenti regole sono più spesso utilizzate nella pratica:
- le domande di servizio sono accettate in ordine di priorità;
- Le domande di servizio sono accettate in base al tempo minimo di ricezione del rifiuto;
- le domande di servizio sono accettate in ordine casuale secondo le probabilità date;
6) disciplina della coda, ovvero un insieme di regole in base alle quali il requisito dà la preferenza all'una o all'altra coda (se ce n'è più di una) e si trova nella coda selezionata. Ad esempio, un reclamo in entrata può prendere posto nella coda più corta; in questa coda, può essere posizionato per ultimo (tale coda è chiamata ordinata), oppure può andare in servizio fuori turno. Sono possibili anche altre opzioni.

Modellazione di simulazione di sistemi di code

Modello -è qualsiasi immagine, analogica, mentale o stabilita, immagine, descrizione, diagramma, disegno, ecc. di qualsiasi oggetto, processo o fenomeno, che nel processo di cognizione (studio) sostituisce l'originale, pur conservandone alcuni importanti per questo studio proprietà tipiche.
La modellazione è lo studio di qualsiasi oggetto o sistema di oggetti costruendo e studiando i loro modelli. E anche - questo è l'uso di modelli per determinare o perfezionare le caratteristiche e razionalizzare i modi di costruire oggetti di nuova costruzione.
Il modello è uno strumento per lo studio di sistemi complessi.
In generale un sistema complessoè presentato come una costruzione multilivello di elementi interagenti combinati in sottosistemi di diversi livelli. I sistemi complessi, inclusi, includono Sistemi di informazione. La progettazione di sistemi così complessi viene eseguita in due fasi.

1 Design esterno

In questa fase, la scelta della struttura del sistema, i suoi elementi principali, l'organizzazione dell'interazione tra gli elementi, la considerazione dell'impatto ambiente esterno, valutazione degli indicatori di performance del sistema.

2 Design interno - design dei singoli elementi
sistemi

Un metodo tipico per studiare i sistemi complessi nella prima fase è la loro simulazione su un computer.
Come risultato della modellazione, si ottengono dipendenze che caratterizzano l'influenza della struttura e dei parametri del sistema sulla sua efficienza, affidabilità e altre proprietà. Queste dipendenze vengono utilizzate per ottenere la struttura e i parametri ottimali del sistema.
Un modello formulato nel linguaggio della matematica utilizzando metodi matematici chiamato modello matematico.
La modellazione di simulazione è caratterizzata dalla riproduzione di fenomeni descritti da un modello matematico, con la conservazione della loro struttura logica, la sequenza di alternanza nel tempo. Le informazioni idonee che circolano nel modello possono essere utilizzate per stimare i valori desiderati, purché disponibili per la registrazione e la successiva elaborazione.
I valori desiderati nello studio dei processi mediante simulazione sono generalmente determinati come valori medi dai dati di un gran numero di implementazioni di processi. Se il numero di realizzazioni N utilizzato per stimare i valori ricercati è sufficientemente grande, allora, per la legge dei grandi numeri, le stime risultanti acquisiscono stabilità statistica e possono essere prese come valori approssimativi dei valori ricercati con precisione sufficiente per la pratica.
L'essenza del metodo di modellazione della simulazione applicato alle attività di accodamento è la seguente. Gli algoritmi sono costruiti
con l'aiuto del quale è possibile sviluppare realizzazioni casuali di determinati flussi di eventi omogenei, nonché modellare i processi di funzionamento dei sistemi di servizio. Questi algoritmi vengono utilizzati per riprodurre ripetutamente l'implementazione di un processo di servizio casuale in condizioni fisse del problema. Le informazioni risultanti sullo stato del processo sono sottoposte ad elaborazioni statistiche per valutare i valori che sono indicatori della qualità del servizio.

3 Formazione di implementazioni di un flusso casuale di richieste

Nello studio di sistemi complessi con il metodo della simulazione, viene prestata notevole attenzione alla presa in considerazione di fattori casuali.
Come schemi matematici utilizzati per formalizzare l'azione di questi fattori, usiamo eventi casuali, variabili casuali e processi casuali (funzioni). La formazione su un computer di realizzazioni di oggetti casuali di qualsiasi natura si riduce alla generazione e trasformazione di numeri casuali. Considera un metodo per ottenere possibili valori di variabili casuali con una data legge di distribuzione. Per formare i possibili valori di variabili casuali con una data legge di distribuzione, il materiale iniziale sono variabili casuali che hanno una distribuzione uniforme nell'intervallo (0, 1). In altre parole, i possibili valori xi della variabile aleatoria t, che ha distribuzione uniforme nell'intervallo (0, 1), possono essere trasformati in possibili valori yi della variabile aleatoria r), la cui legge di distribuzione è dato. Il metodo di trasformazione consiste nel selezionare numeri casuali da una popolazione distribuita uniformemente che soddisfa una determinata condizione in modo tale che i numeri selezionati obbediscano a una data legge di distribuzione.
Assumiamo che sia necessario ottenere una sequenza di numeri casuali yi con funzione di densità 1^(y). Se il dominio della funzione f^y) non è limitato su uno o entrambi i lati, è necessario passare alla corrispondente distribuzione troncata. Lascia che l'intervallo di valori possibili per la distribuzione troncata sia (a, b).
Dalla variabile casuale r) corrispondente alla funzione di densità f → y), si passa a f.
Valore casuale b, avrà un intervallo di valori possibili (0, 1) e una funzione di densità f ^ (z) data dall'espressione.
Sia il valore massimo di f^(z) uguale a f m . Impostiamo distribuzioni uniformi negli intervalli (0, 1) di numeri casuali x 2 i-1 e x 2 io. La procedura per ottenere una sequenza yi di numeri casuali con una funzione di densità ^(y) si riduce a quanto segue:
1) dalla popolazione iniziale vengono selezionate coppie di numeri casuali x2i-1,
2) per questi numeri si verifica la validità della disuguaglianza
x 21<-- ^[а + (Ъ-а)х 2М ] (3)
m
3) se la disuguaglianza (3) è soddisfatta, il numero successivo yi è determinato dalla relazione
yi \u003d a + (b-a) x 21 (4)
Quando si modellano i processi di servizio, diventa necessario realizzare realizzazioni di un flusso casuale di eventi omogenei (applicazioni). Ogni evento di flusso è caratterizzato dal tempo tj in cui si verifica. Per descrivere un flusso casuale di eventi omogenei come un processo casuale, è sufficiente specificare una legge di distribuzione che caratterizzi la sequenza di variabili casuali tj. Per ottenere la realizzazione di un flusso di eventi omogenei t1, t2..., tk, è necessario formare una realizzazione z b z 2 ,...,zk di un vettore casuale k-dimensionale ££2,... , Sk e calcola i valori ti secondo i seguenti rapporti:
t2 =
Sia dato un flusso ordinario stazionario con effetti collaterali limitati dalla funzione di densità f(z). In accordo con la formula di Palm (6), troviamo la funzione di densità f1(z1) per il primo intervallo z1.
1-Jf(u)du
Ora possiamo generare un numero casuale z b come mostrato sopra, corrispondente alla funzione di densità f1(z1), e ottenere il momento di comparsa della prima richiesta t1 = z1. Successivamente, formiamo una serie di numeri casuali corrispondenti alla funzione di densità f(z), e utilizzando la relazione (4) calcoliamo i valori delle quantità t2, t3 ,.., tk.
4 Elaborazione dei risultati della simulazione
Quando si implementano algoritmi di modellazione su un computer, vengono generate informazioni sugli stati del sistema in studio. Queste informazioni sono il materiale di partenza per determinare i valori approssimativi delle quantità ricercate o, come si suol dire, le stime per le quantità ricercate.
La stima della probabilità dell'evento A è calcolata dalla formula
p(A) = mN . (7)
Stima della media x di una variabile casuale b, calcolato da
formula
_ 1n
k=1
La stima S 2 per la varianza della variabile casuale ^ è calcolata dalla formula
1 N 1 ( NL 2
S2=1 YA xk 2-5> J (9)
Stima del momento di correlazione K^ per variabili casuali b, e c con possibili valori x k e y k, rispettivamente, è calcolato dalla formula
1 N 1 N
Y> [ oh!

5 Esempio di modellazione QS
Considera il seguente sistema:
1 Le richieste arrivano in orari casuali, mentre
l'intervallo di tempo Q tra due richieste successive ha una legge esponenziale con il parametro io, cioè, la funzione di distribuzione ha la forma
>0. (11) Il sistema di accodamento è costituito da server numerati identici.
3 Tempo T su bsl - una variabile casuale con una legge di distribuzione uniforme sul segmento.
4 Sistema senza attesa, ad es. il requisito che rendeva occupati tutti i dispositivi lascia il sistema.
5 La disciplina del servizio è la seguente: se al momento della ricezione del k -esimo requisito il primo server è libero, allora inizia a servire il requisito; se questo server è occupato e il secondo è libero, la richiesta viene soddisfatta dal secondo server e così via.
Necessità di valutare aspettative matematiche il numero di richieste servite dal sistema nel tempo T e rifiutate.
Per il momento iniziale di calcolo scegliamo il momento di arrivo del primo requisito Т1=0. Introduciamo la seguente notazione: Tk è il momento di ricezione del k-esimo requisito; ti - ora di fine servizio i-esimo requisito dispositivo, i=1, 2, 3, ...,s.
Si supponga che al tempo T 1 tutti i dispositivi siano liberi.
La prima richiesta arriva al server 1. Il tempo di servizio di questo server ha una distribuzione uniforme sul segmento. Pertanto, il valore specifico di t obl di questo tempo è trovato dalla formula
(12)
dove r è il valore di una variabile casuale R uniformemente distribuita sul segmento. Il dispositivo 1 sarà occupato durante il tempo di o bsl. Pertanto, l'istante t 1 della fine della manutenzione del requisito da parte del dispositivo 1 è da considerarsi uguale a: t 1 = T1+ t circa obsl.
Quindi aggiungine uno al contatore delle richieste servite e passa alla richiesta successiva.
Si supponga che k requisiti siano già stati considerati. Definiamo il momento Т k+1 di ricezione del (k+1)-esimo requisito. Per fare ciò, troviamo il valore t dell'intervallo di tempo tra requisiti successivi. Poiché questo intervallo ha una legge esponenziale, quindi
12
x \u003d - In r (13)
| Ll
dove r è il valore successivo della variabile casuale R . Quindi il momento di arrivo del (k + 1)esimo requisito: T k +1 = Tk + T.
Il primo dispositivo è gratuito in questo momento? Per rispondere a questa domanda è necessario verificare la condizione ti< Tk + i - Если это условие выполнено, то к моменту Т k +1 первый прибор освободился и может обслуживать требование. В этом случае t 1 заменяем на (Т k +1 + t обсл), добавляем единицу в счетчик об служенных требований и переходим к следующему требованию. Если t 1>T k +1, quindi il primo dispositivo all'istante T k +1 è occupato. In questo caso, controlliamo se il secondo dispositivo è gratuito. Se la condizione i 2< Tk + i выполнено, заменяем t2 на (Т k +1+ t о бсл), добавляем единицу в счетчик обслуженных требований и переходим к следующему требованию. Если t 2>Т k +1, quindi controlliamo la condizione 1з<Тк+1 и т. д. Eсли при всех i от 1 до s имеет ti >T k +1, quindi al momento T k +1 tutti i dispositivi sono occupati. In questo caso, ne aggiungiamo uno al contatore degli errori e passiamo al requisito successivo. Ogni volta, dopo aver calcolato Tk + 1, dobbiamo verificare anche la condizione per la cessazione dell'implementazione: Tk + i< T . Если это условие выполнено, то одна реализация процесса функционирования системы воспроизведена и испыта ние заканчивается. В счетчике обслуженных требований и в счетчике отказов находятся числа n обсл и n отк.
Dopo aver ripetuto tale test n volte (usando una r diversa) e aver mediato i risultati degli esperimenti, determiniamo le stime delle aspettative matematiche del numero di clienti serviti e del numero di clienti rifiutati:
(14)
(Ji
nj =1
dove (n obl) j e (n obl) j sono i valori di n obl e n obl nell'esperimento j-esimo.
13

Elenco delle fonti utilizzate
1 Emelyanov A.A. Modellazione di simulazione dei processi economici [Testo]: Proc. indennità per le università / A.A. Emelyanov, EA Vlasova, RV Pensiero. - M.: Finanza e statistica, 2002. - 368s.
2 Buslenko, NP Modellazione di sistemi complessi [Testo] / N.P. Buslenko.- M.: Nauka, 1978. - 399p.
3 sovietici B.Ya. Sistemi di modellazione [Testo]: Proc. per le università / B.Ya. Sove tov, SA Yakovlev. -M. : Più alto. scuola, 1985. - 271 p.
4 sovietici B.Ya. Sistemi di modellazione [Testo]: Laboratorio di laboratorio: Proc. indennità per le università nella specialità: "Sistema automatizzato per l'elaborazione delle informazioni e il controllo". / B.Ya. Sovetov, SA Yakovlev. -M. : Più alto. scuola, 1989. - 80 p.
5 Maximei IV Modellazione di simulazione su un computer [Testo] / Maksimey, I.V. -M: RADIO E COMUNICAZIONE, 1988. - 231s.
6 Wentzel E.S. Teoria della probabilità [Testo]: libro di testo. per università / E.S. Porta di sfiato - M. : Più in alto. scuola, 2001. - 575 p.
7 Gmurman, V.E. Teoria della probabilità e statistica matematica [Testo]: manuale. indennità / V.E. Gmurman - M.: Più in alto. scuola, 2001. - 479 p.
Annesso A
(obbligatorio)
Argomenti approssimativi di insediamento e opere grafiche
1 C'è un medico che lavora al pronto soccorso. La durata del trattamento del paziente
e gli intervalli di tempo tra i ricoveri dei pazienti sono variabili casuali distribuite secondo la legge di Poisson. In base alla gravità delle lesioni, i pazienti sono suddivisi in tre categorie, il ricovero di un paziente di qualsiasi categoria è un evento casuale con distribuzione equiprobabile. Il medico si occupa prima dei pazienti con le lesioni più gravi (nell'ordine in cui vengono ricevuti), quindi, se non ce ne sono, con pazienti di gravità moderata e solo successivamente con pazienti con lesioni lievi. Simula il processo e stima i tempi medi di attesa in coda dei pazienti di ciascuna categoria.
2 Nella flotta di city car sono presenti due zone di riparazione. Il primo serve riparazioni di corto e media durata, il secondo - medio e lungo. In caso di guasti, i veicoli vengono consegnati alla flotta; l'intervallo di tempo tra le consegne è una variabile di Poisson casuale. La durata della riparazione è una variabile casuale con una distribuzione normale. Modellare il sistema descritto. Stimare i tempi medi di attesa nella coda di trasporto, che richiedono riparazioni rispettivamente a breve, medio e lungo termine.
3 Un minimarket con un controller: un cassiere serve i clienti il ​​cui flusso in entrata obbedisce alla legge di Poisson con un parametro di 20 clienti / ora. Eseguire una simulazione del processo descritto e determinare la probabilità di fermo del controllore - cassiere lunghezza media code, il numero medio di clienti nel minimarket, il tempo medio di attesa per il servizio, il tempo medio trascorso dai clienti nel minimarket e valutarne l'operato.
4 ATS riceve domande per chiamate interurbane. Il flusso delle richieste è Poisson. In media, vengono ricevute 13 domande all'ora. Trova il numero medio di domande ricevute al giorno, il tempo medio tra la comparsa delle domande. Alla centrale telefonica compaiono malfunzionamenti se vengono ricevute più di 50 richieste in mezz'ora. Trova la probabilità di guasto della stazione.
5 La stazione di servizio riceve il più semplice
il flusso delle domande con un'intensità di 1 auto ogni 2 ore Non più di 3 auto possono essere in coda nel piazzale. Tempo medio di riparazione - 2 ore. Valutare il lavoro dell'OCM e sviluppare raccomandazioni per migliorare il servizio.
6 Un tessitore serve un gruppo di telai, effettuando, se necessario, interventi a breve termine, la cui durata è una variabile casuale. Simula la situazione descritta. Qual è la probabilità di fermo macchina di due macchine contemporaneamente. Quanto è lungo il tempo di fermo medio per macchina.
7 In una centrale telefonica a lunga distanza, due operatori telefonici servono una coda comune di ordini. L'ordine successivo è servito dall'operatore telefonico che è stato il primo ad essere rilasciato. Se entrambi sono occupati al momento della ricezione dell'ordine, la chiamata verrà annullata. Simula il processo assumendo che i flussi di input siano Poisson.
8 Ci sono due medici che lavorano al pronto soccorso. La durata del trattamento fa male
e gli intervalli di tempo tra i ricoveri dei pazienti sono variabili casuali distribuite secondo la legge di Poisson. In base alla gravità delle lesioni, i pazienti sono suddivisi in tre categorie, il ricovero di un paziente di qualsiasi categoria è un evento casuale con distribuzione equiprobabile. Il medico si occupa prima dei pazienti con le lesioni più gravi (nell'ordine in cui vengono ricevuti), quindi, se non ce ne sono, con pazienti di gravità moderata e solo successivamente con pazienti con lesioni lievi. Simula il processo e stima i tempi medi di attesa in coda dei pazienti di ciascuna categoria.
9 In una centrale telefonica interurbana servono due operatori telefonici
creare una coda comune di ordini. L'ordine successivo è servito da quell'operatore telefonico,
che è stato rilasciato per primo. Se entrambi sono occupati al momento della ricezione dell'ordine, si forma una coda. Simula il processo assumendo che i flussi di input siano Poisson.
10 In un sistema di trasmissione dati, i pacchetti di dati vengono scambiati tra i nodi A e B su un canale di comunicazione duplex. I pacchetti arrivano ai punti del sistema dagli abbonati con intervalli di tempo tra loro di 10 ± 3 ms. La trasmissione del pacchetto richiede 10 ms. I punti hanno registri buffer che possono memorizzare due pacchetti, incluso quello trasmesso. Se un pacchetto arriva nel momento in cui i registri sono occupati, i punti del sistema hanno accesso ad una linea di comunicazione satellitare half duplex, che trasmette pacchetti di dati in 10 ± 5 ms. Quando la linea satellitare è occupata, il pacchetto viene rifiutato. Simula lo scambio di informazioni nel sistema di trasmissione dati per 1 min. Determinare la frequenza delle chiamate alla linea satellitare e il suo carico. Se sono possibili guasti, determinare il volume dei registri del buffer necessari affinché il sistema funzioni senza guasti.
11 Si prenda in uso il sistema standard ad un centralino telefonico ad un ingresso: se l'abbonato è occupato non si forma la coda ed è necessario chiamare nuovamente. Simula la situazione: tre abbonati cercano di raggiungere lo stesso proprietario del numero e, in caso di successo, parlano con lui per un po' di tempo (casuale nella durata). Qual è la probabilità che qualcuno che cerca di passare attraverso il telefono non sia in grado di farlo in un certo tempo T.
12 Una società commerciale prevede di evadere gli ordini di acquisto di beni tramite telefono, per i quali è necessario installare un apposito centralino miniautomatico con più apparecchi telefonici. Se l'ordine arriva quando tutte le linee sono occupate, il cliente riceve un rifiuto. Se al momento della ricezione della richiesta almeno una riga è libera, si passa a questa riga e si effettua l'ordine. L'intensità del flusso di domande in entrata è di 30 ordini all'ora. La durata dell'applicazione è in media di 5 minuti. Determinare il numero ottimale di canali di servizio per garantire il funzionamento stazionario del QS.
13 In un negozio self-service ci sono 6 controllori - cassieri. Il flusso di acquirenti in entrata obbedisce alla legge di Poisson con un'intensità di 120 persone all'ora. Un cassiere può servire 40 persone all'ora. Determinare la probabilità di cassiere inattivo, il numero medio di clienti in coda, il tempo medio di attesa, il numero medio di cassieri occupati. Dare una valutazione del lavoro del QS.
14 Un flusso Poisson di 200 clienti all'ora entra in un negozio self-service. Durante il giorno sono serviti da 3 controllori cassieri con un'intensità di 90 clienti all'ora. L'intensità del flusso di input degli acquirenti durante le ore di punta aumenta fino a un valore di 400 acquirenti all'ora e durante le ore di recessione raggiunge i 100 acquirenti all'ora. Determinare la probabilità di formare una coda nel negozio e la lunghezza media della coda durante il giorno, nonché il numero richiesto di controllori cassieri durante le ore di punta e di recessione, fornendo la stessa lunghezza della coda e la probabilità della sua formazione di nella modalità nominale.
15 Il numero medio di clienti che arrivano al nodo di regolamento in un punto vendita self-service è di 100 persone all'ora. La cassa può servire 60 persone all'ora. Simula il processo e determina quanti cassieri sono necessari in modo che la probabilità di una coda non superi 0,6.
16 Simulare una coda in un negozio con un venditore con leggi equiprobabili di distribuzione di variabili casuali: l'arrivo dei clienti e la durata del servizio (con qualche set fisso di parametri). Ottenere caratteristiche stabili: i valori medi di attesa in coda da parte dell'acquirente e il tempo di inattività del venditore in previsione dell'arrivo degli acquirenti. Valuta la loro credibilità.
17 Simulare una coda in un negozio con un venditore con le leggi di Poisson di distribuzione di variabili casuali: l'arrivo dei clienti e la durata del servizio (con alcuni set di parametri fissi). Ottenere caratteristiche stabili: i valori medi di attesa in coda da parte dell'acquirente e il tempo di inattività del venditore in previsione dell'arrivo degli acquirenti. Valuta la loro credibilità.
18 Creare un modello di stazione di servizio. Trova indicatori della qualità delle richieste di servizio. Determinare il numero di rack in modo che la coda non cresca.
19 Numero medio di clienti che arrivano al nodo cassa di un negozio self-service, 60 persone all'ora. La cassa può servire 35 persone all'ora. Simula il processo e determina quanti cassieri sono necessari in modo che la probabilità di una coda non superi 0,6.
20 Costruisci un modello percorso dell'autobus con n fermate. Determinare gli indicatori di performance per l'uso di QS.

il funzionamento o l'efficienza del sistema di accodamento sono i seguenti.

Per CMO con errori:

Per CMO con attesa illimitata sia il throughput assoluto che quello relativo perdono il loro significato, poiché ogni richiesta in arrivo verrà servita prima o poi. Per un tale QS, indicatori importanti sono:

Per OCM tipo misto vengono utilizzati entrambi i gruppi di indicatori: relativi e larghezza di banda assoluta e caratteristiche di aspettativa.

A seconda dello scopo dell'operazione di accodamento, uno qualsiasi degli indicatori di cui sopra (o un insieme di indicatori) può essere selezionato come criterio di prestazione.

modello analitico QS è un insieme di equazioni o formule che consentono di determinare le probabilità degli stati del sistema nel processo del suo funzionamento e calcolare gli indicatori di prestazione in base a caratteristiche note flusso in entrata e canali di servizio.

Non esiste un modello analitico generale per un QS arbitrario. Sono stati sviluppati modelli analitici per un numero limitato di casi speciali di QS. I modelli analitici che rappresentano più o meno accuratamente i sistemi reali sono, di regola, complessi e difficili da vedere.

La modellazione analitica del QS è molto facilitata se i processi che si verificano nel QS sono markoviani (i flussi di richieste sono semplici, i tempi di servizio sono distribuiti in modo esponenziale). In questo caso, tutti i processi in QS possono essere descritti da ordinario equazioni differenziali, e nel caso limite, per stati stazionari- lineare equazioni algebriche e, dopo averli risolti, determinare gli indicatori di performance selezionati.

Consideriamo esempi di alcuni QS.

2.5.1. QS multicanale con errori

Esempio 2.5. Tre ispettori del traffico controllano le lettere di vettura dei camionisti. Se almeno un ispettore è libero, il camion in transito viene fermato. Se tutti gli ispettori sono occupati, il camion passa senza fermarsi. Il flusso dei camion è il più semplice, il tempo di controllo è casuale con distribuzione esponenziale.

Tale situazione può essere simulata da un QS a tre canali con guasti (senza coda). Il sistema è aperto, con applicazioni omogenee, monofase, con canali assolutamente affidabili.

Descrizione degli stati:

Tutti gli ispettori sono liberi;

Un ispettore è impegnato;

Due ispettori sono occupati;

Tre ispettori sono impegnati.

Il grafico degli stati del sistema è mostrato in fig. 2.11.

Riso. 2.11.

Nel grafico: - l'intensità del flusso dei camion; - l'intensità dei controlli documentali da parte di un ispettore del traffico.

La simulazione viene effettuata al fine di determinare la parte delle vetture che non verrà testata.

Soluzione

La parte desiderata della probabilità è la probabilità di impiego di tutti e tre gli ispettori. Poiché il grafico di stato rappresenta schema tipico"morte e riproduzione", quindi troveremo usando le dipendenze (2.2).

Il rendimento di questo posto di ispettori del traffico può essere caratterizzato rendimento relativo:

Esempio 2.6. Per ricevere ed elaborare i rapporti dal gruppo di ricognizione, un gruppo di tre ufficiali è stato assegnato al dipartimento di ricognizione dell'associazione. Il tasso previsto di segnalazione è di 15 rapporti all'ora. Il tempo medio di elaborazione di una segnalazione da parte di un funzionario è . Ogni ufficiale può ricevere rapporti da qualsiasi gruppo di ricognizione. L'ufficiale rilasciato elabora l'ultimo dei rapporti ricevuti. Le segnalazioni in arrivo devono essere elaborate con una probabilità di almeno il 95%.

Determinare se il gruppo di tre ufficiali assegnato è sufficiente per completare il compito assegnato.

Soluzione

Un gruppo di ufficiali lavora come CMO con fallimenti, composto da tre canali.

Il flusso di relazioni con intensità può essere considerato il più semplice, poiché è il totale di diversi gruppi di ricognizione. Intensità di manutenzione . La legge di distribuzione è sconosciuta, ma ciò non è essenziale, poiché è dimostrato che per i sistemi con guasti può essere arbitraria.

La descrizione degli stati e il grafico di stato del QS saranno simili a quelli forniti nell'Esempio 2.5.

Poiché il grafo di stato è uno schema di "morte e riproduzione", esistono espressioni già pronte per le sue probabilità di stato limite:

La relazione è chiamata la ridotta intensità del flusso di applicazioni. significato fisicoè il seguente: il valore è il numero medio di richieste pervenute al QS per il tempo medio di servizio di una richiesta.

Nell'esempio .

Nel Fallimento CMO si verifica quando tutti e tre i canali sono occupati, ovvero . Quindi:

Perché probabilità di fallimento nell'elaborazione delle segnalazioni è superiore al 34% (), quindi è necessario aumentare il personale del gruppo. Raddoppiamo la composizione del gruppo, cioè il QS avrà ora sei canali, e calcoliamo:

Pertanto, solo un gruppo di sei agenti sarà in grado di elaborare i rapporti in arrivo con una probabilità del 95%.

2.5.2. QS multicanale con attesa

Esempio 2.7. Ci sono 15 strutture di attraversamento dello stesso tipo nella sezione di forzatura del fiume. Il flusso di veicoli in arrivo all'incrocio è in media di 1 unità/min, il tempo medio di attraversamento di un'unità di equipaggiamento è di 10 minuti (tenendo conto del ritorno dell'impianto di attraversamento).

Valutare le caratteristiche principali dell'attraversamento, inclusa la probabilità di un incrocio immediato subito dopo l'arrivo di un'attrezzatura.

Soluzione

Larghezza di banda assoluta, ovvero tutto ciò che arriva all'incrocio viene quasi subito attraversato.

Numero medio di attraversamenti operativi:

Rapporti di utilizzo incrociato e tempi di fermo:

È stato inoltre sviluppato un programma per risolvere l'esempio. Gli intervalli di tempo per l'arrivo delle apparecchiature all'incrocio, il tempo dell'attraversamento sono presi da distribuire secondo una legge esponenziale.

I tassi di utilizzo del traghetto dopo 50 corse sono praticamente gli stessi: .