Kursarbeid

"Simuleringsmodellering av et køsystem"

i kurset "Operasjonsforskning"

Introduksjon

Når man forsker på operasjoner, møter man ofte systemer designet for gjenbruk når man løser lignende problemer. Prosessene som oppstår kalles tjenesteprosesser, og systemene kalles køsystemer (QS). Hver QS består av et visst antall serviceenheter (instrumenter, enheter, punkter, stasjoner), som kalles servicekanaler. Kanaler kan være kommunikasjonslinjer, arbeidspunkter, datamaskiner, selgere osv. Basert på antall kanaler deles QS-systemer inn i enkanal og flerkanal.

Søknader mottas vanligvis av QS ikke regelmessig, men tilfeldig, og danner en såkalt tilfeldig flyt av søknader (krav). Service av søknader fortsetter også i noen tilfeldig tid. Den tilfeldige karakteren av applikasjonsflyten og tjenestetiden fører til at QS-en er ujevnt lastet: i noen perioder akkumuleres et veldig stort antall applikasjoner (enten står de i kø eller lar QS-en stå ubetjent), mens i andre perioder QS fungerer med underlast eller er inaktiv.

Emnet for køteori er konstruksjonen av matematiske modeller som kobler de gitte driftsforholdene til QS (antall kanaler, deres produktivitet, arten av flyten av forespørsler, etc.) med ytelsesindikatorer for QS, som beskriver dens evne å takle strømmen av forespørsler. Følgende brukes som indikatorer på effektiviteten til QS:

– Absolutt systemgjennomstrømning ( EN

Q

– sannsynlighet for å nekte å betjene forespørselen ();

k);

– gjennomsnittlig antall søknader i køen ();

QS er delt inn i 2 hovedtyper: QS med feil og QS med venting (kø). I en QS med avslag mottar en søknad som mottas på et tidspunkt da alle kanaler er opptatt, et avslag, forlater QS og deltar ikke i den videre tjenesteprosessen (for eksempel en søknad om telefonsamtale på et tidspunkt da alle kanaler er opptatt, mottar et avslag og lar QS-en ikke vises). I en ventende QS forlater ikke en forespørsel som kommer på et tidspunkt når alle kanaler er opptatt, men står i kø for service.

En av metodene for å beregne QS-effektivitetsindikatorer er simuleringsmetoden. Den praktiske bruken av datasimulering innebærer konstruksjon av en passende matematisk modell som tar hensyn til usikkerhetsfaktorer, dynamiske egenskaper og hele komplekset av sammenhenger mellom elementene i systemet som studeres. Simuleringsmodellering av systemdrift begynner med en bestemt starttilstand. På grunn av implementeringen av forskjellige hendelser av tilfeldig karakter, går systemmodellen ved påfølgende tidspunkter over til andre mulige tilstander. Denne evolusjonsprosessen fortsetter til siste øyeblikk av planperioden, dvs. til siste punkt av simuleringen.

1. Hovedkjennetegn ved CMO og indikatorer på deres effektivitet

1.1 Konseptet med en tilfeldig Markov-prosess

La det være et system som endrer tilstanden tilfeldig over tid. I dette tilfellet sier de at det skjer en tilfeldig prosess i systemet.

En prosess kalles en prosess med diskrete tilstander hvis dens tilstander kan listes på forhånd og overgangen til systemet fra en tilstand til en annen skjer brått. En prosess kalles en kontinuerlig tidsprosess hvis systemet går fra tilstand til tilstand umiddelbart.

QS-operasjonsprosessen er en tilfeldig prosess med diskrete tilstander og kontinuerlig tid.

En tilfeldig prosess kalles en Markov eller tilfeldig prosess uten ettervirkning hvis, for ethvert øyeblikk i tid, de sannsynlige egenskapene til prosessen i fremtiden bare avhenger av dens tilstand i øyeblikket og ikke avhenger av når og hvordan systemet kom til dette stat.

Når du analyserer operasjonsprosessene til en QS, er det praktisk å bruke et geometrisk diagram - tilstandsgraf. Vanligvis er systemtilstander avbildet av rektangler, og mulige overganger fra tilstand til tilstand er avbildet med piler. Et eksempel på en tilstandsgraf er vist i fig. 1.

En strøm av hendelser er en sekvens av homogene hendelser som følger etter hverandre på tilfeldige tidspunkter.

Strømmen er preget av intensitet λ - frekvensen av forekomst av hendelser eller gjennomsnittlig antall hendelser som kommer inn i QS per tidsenhet.

Flyten av hendelser kalles regelmessig hvis hendelser følger hverandre med visse like tidsintervaller.

En flyt av hendelser kalles stasjonær hvis dens sannsynlige egenskaper ikke avhenger av tid. Spesielt er intensiteten til en stasjonær strømning en konstant verdi: .

En flyt av hendelser kalles ordinær hvis sannsynligheten for at to eller flere hendelser inntreffer i løpet av en kort periode er liten sammenlignet med sannsynligheten for at en hendelse inntreffer, det vil si hvis hendelser dukker opp i den en etter en og ikke i grupper.

En flyt av hendelser kalles en flyt uten ettervirkning hvis antallet hendelser som faller på en av dem, for to ikke-overlappende tidsperioder, ikke er avhengig av antallet hendelser som faller på de andre.

En flyt av hendelser kalles enkleste (eller stasjonære Poisson) hvis den både er stasjonær, ordinær og ikke har noen ettervirkning.

1.2 Kolmogorov-ligninger

Alle overganger i systemet fra stat til stat skjer under en viss flyt av hendelser. La systemet være i en viss tilstand hvorfra en overgang til tilstanden er mulig, så kan vi anta at systemet påvirkes av en enkel flyt med intensitet som overfører det fra tilstand til. Så snart den første trådhendelsen inntreffer, skjer overgangen. For klarhetens skyld er intensiteten til hver pil som tilsvarer en overgang angitt på tilstandsgrafen. En slik merket tilstandsgraf gjør det mulig å konstruere en matematisk modell av prosessen, dvs. finn sannsynlighetene for alle tilstander som en funksjon av tid. For dem er differensialligninger kompilert, kalt Kolmogorov-ligninger.

Regel for å kompilere Kolmogorov-ligninger: På venstre side av hver ligning er den tidsderiverte av sannsynligheten for en gitt tilstand. På høyre side er summen av produktene av alle tilstander hvorfra en overgang til en gitt tilstand er mulig med intensiteten til de tilsvarende strømmene av hendelser minus den totale intensiteten til alle strømmer som fører systemet ut av en gitt tilstand, multiplisert etter sannsynligheten for en gitt tilstand.

For eksempel, for tilstandsgrafen vist i fig. 1, Kolmogorovs ligninger har formen:

Fordi på høyre side av systemet vises hvert ledd 1 gang med et fortegn og 1 gang med et tegn, så, ved å legge til alle ligningene, får vi det

,

,

Følgelig kan en av likningene til systemet forkastes og erstattes med likning (1.2.1).

For å få en spesifikk løsning må du kjenne til startbetingelsene, dvs. sannsynlighetsverdier på det første tidspunktet.

1.3 Endelige sannsynligheter og QS-tilstandsgraf

Hvis tiden for prosesser i systemet er tilstrekkelig lang (kl ), kan det etableres sannsynligheter for tilstander som ikke er avhengig av tid, som kalles endelige sannsynligheter, dvs. systemet er satt til stasjonær modus. Hvis antallet tilstander i systemet er begrenset, og fra hver av dem i et begrenset antall trinn er det mulig å gå til en hvilken som helst annen tilstand, så eksisterer de endelige sannsynlighetene, dvs.

Betydningen av de endelige sannsynlighetene er at de er lik den gjennomsnittlige relative tiden systemet er i en gitt tilstand.

Fordi i en stasjonær tilstand er tidsderivertene lik null, deretter oppnås ligningene for de endelige sannsynlighetene fra Kolmogorov-ligningene ved å likestille deres høyre side med null.

Tilstandsgrafene som brukes i køsystemmodeller kalles dø-og-reproduser-mønstre. Dette navnet skyldes det faktum at denne ordningen brukes i biologiske problemer knyttet til studiet av populasjonsstørrelse. Dens særegenhet er at alle tilstander i systemet kan representeres som en kjede der hver tilstand er forbundet med de forrige og etterfølgende (fig. 2).

Ris. 2. Angi graf i QS-modeller

La oss anta at alle strømmer som overfører systemet fra en tilstand til en annen er enklest. I følge grafen presentert i fig. 2, la oss lage ligninger for de endelige sannsynlighetene til systemet. De ser ut som:

Resultatet er et system fra ( n +1) likning, som løses ved eliminering. Denne metoden består i at sekvensielt alle sannsynlighetene til systemet uttrykkes gjennom sannsynlighet.

,

.

Ved å erstatte disse uttrykkene i den siste ligningen i systemet finner vi , så finner vi de gjenværende sannsynlighetene for QS-tilstandene.

1.4 Ytelsesindikatorer for QS

Hensikten med QS-modellering er å beregne systemytelsesindikatorer gjennom dens egenskaper. Følgende brukes som indikatorer på effektiviteten til QS:

– absolutt systemkapasitet ( EN), dvs. gjennomsnittlig antall søknader per tidsenhet;

- relativ gjennomstrømning ( Q), dvs. gjennomsnittlig andel av mottatte søknader som betjenes av systemet;

– sannsynlighet for feil (), dvs. sannsynligheten for at applikasjonen vil la QS ikke vises;

– gjennomsnittlig antall okkuperte kanaler ( k);

– gjennomsnittlig antall søknader i QS ();

– gjennomsnittlig oppholdstid for applikasjonen i systemet ();

– gjennomsnittlig antall søknader i køen () – kølengde;

– gjennomsnittlig antall applikasjoner i systemet ();

– gjennomsnittlig tid en applikasjon forblir i køen ();

– gjennomsnittlig tid en applikasjon forblir i systemet ()

– grad av kanalbelastning (), dvs. sannsynligheten for at kanalen er opptatt;

– gjennomsnittlig antall forespørsler behandlet per tidsenhet;

– gjennomsnittlig ventetid for tjeneste;

– sannsynligheten for at antall søknader i køen overskrider en viss verdi osv.

Det er bevist at for alle typer applikasjonsflyt, for enhver fordeling av tjenestetid, for enhver tjenestedisiplin, er den gjennomsnittlige tiden en forespørsel forblir i systemet (kø) lik gjennomsnittlig antall applikasjoner i systemet ( kø) delt på intensiteten til strømmen av søknader, dvs.

(1.4.1)

Formler (1.4.1) og (1.4.2) kalles Littles formler. De følger av det faktum at i den begrensende stasjonære modusen er gjennomsnittlig antall applikasjoner som kommer inn i systemet lik det gjennomsnittlige antall applikasjoner som forlater det, dvs. begge strømmene av forespørsler har samme intensitet.

Formler for beregning av effektivitetsindikatorer er gitt i tabell. 1.

Tabell 1.

Indikatorer	Enkanals QS med begrenset kø	Flerkanals QS med begrenset kø
Endelig sannsynligheter
Sannsynlighet
Absolutt gjennomstrømming evnen
Relativ båndbredde evnen
Gjennomsnittlig antall søknader pr
Gjennomsnittlig antall søknader pr service
Gjennomsnittlig antall søknader i systemet

1.5 Grunnleggende konsepter for simuleringsmodellering

Hovedmålet med simulering er å reprodusere oppførselen til systemet som studeres basert på analysen av de viktigste relasjonene til elementene.

Datasimulering bør betraktes som et statisk eksperiment.

Fra teorien om funksjoner til tilfeldige variabler er det kjent at for å modellere en tilfeldig variabel med en hvilken som helst kontinuerlig og monotont økende distribusjonsfunksjon, er det nok å kunne modellere en tilfeldig variabel jevnt fordelt på segmentet. Etter å ha mottatt implementeringen av en tilfeldig variabel, kan du finne den tilsvarende implementeringen av den tilfeldige variabelen, siden de er relatert av likheten

La oss anta at i et eller annet køsystem er tjenestetiden til en forespørsel fordelt i henhold til en eksponentiell lov med parameteren , hvor er intensiteten til tjenesteflyten. Da har formen

La være realiseringen av en tilfeldig variabel jevnt fordelt på segmentet, og la være den tilsvarende realiseringen av den tilfeldige tiden for å betjene en forespørsel. Deretter, ifølge (1.5.1)

1.6 Konstruksjon av simuleringsmodeller

Den første fasen av å lage en simuleringsmodell er fasen for å beskrive et virkelige system i form av egenskapene til hovedhendelsene. Disse hendelsene er vanligvis assosiert med overganger av systemet som studeres fra en mulig tilstand til en annen og er utpekt som punkter på tidsaksen. For å oppnå hovedmålet med modellering er det nok å observere systemet i øyeblikkene når hovedhendelsene inntreffer.

La oss vurdere et eksempel på et enkeltkanals køsystem. Hensikten med simuleringsmodellering av et slikt system er å bestemme estimater av dets hovedegenskaper, slik som gjennomsnittlig tid en applikasjon forblir i køen, gjennomsnittlig lengde på køen og prosentandelen av nedetid i systemet.

Egenskapene til selve køprosessen kan endre verdiene enten når en ny forespørsel om tjeneste mottas, eller når en annen forespørsel er fullført. QS kan begynne å betjene neste forespørsel umiddelbart (tjenestekanalen er ledig), men det kan være nødvendig å vente til forespørselen må ta plass i køen (QS med kø, tjenestekanalen er opptatt). Etter å ha fullført service av neste forespørsel, kan QS umiddelbart begynne å betjene neste forespørsel, hvis det er en, men kan også være inaktiv hvis det ikke er noen. Nødvendig informasjon kan fås ved å observere ulike situasjoner som oppstår under gjennomføringen av hovedhendelser. Således, når en forespørsel kommer til en QS med en kø og tjenestekanalen er opptatt, øker kølengden med 1. På samme måte reduseres kølengden med 1 hvis service av neste forespørsel er fullført og settet med forespørsler i køen er ikke tom.

For å betjene en simuleringsmodell er det nødvendig å velge en tidsenhet. Avhengig av typen av systemet som modelleres, kan en slik enhet være et mikrosekund, en time, et år osv.

Siden datasimulering i kjernen er et beregningseksperiment, må de observerte resultatene i aggregatet ha egenskapene til et tilfeldig utvalg. Bare i dette tilfellet vil en korrekt statistisk tolkning av det simulerte systemet sikres.

I datasimuleringsmodellering er hovedinteressen i observasjoner oppnådd etter at systemet som studeres når en stasjonær driftsmodus, siden prøvevariansen i dette tilfellet avtar kraftig.

Tiden som kreves for systemet for å oppnå en stasjonær driftsmodus, bestemmes av verdiene til parametrene og starttilstanden.

Siden hovedmålet er å skaffe observasjonsdata med den minste feilen mulig, kan du for å oppnå dette målet:

1) øke varigheten av simulering av funksjonsprosessen til systemet som studeres. I dette tilfellet øker ikke bare sannsynligheten for at systemet oppnår en stasjonær driftsmodus, men også antallet pseudorandom-tall som brukes øker, noe som også har en positiv effekt på kvaliteten på de oppnådde resultatene.

2) for en bestemt varighet T utføre simuleringsmodellering N beregningseksperimenter, også kalt modellkjøringer, med forskjellige sett med pseudorandomtall, som hver produserer én observasjon. Alle kjøringer starter med den samme starttilstanden til det simulerte systemet, men bruker forskjellige sett med pseudorandom-tall. Fordelen med denne metoden er uavhengigheten til observasjonene som er oppnådd, indikatorer på systemeffektivitet. Hvis nummeret N modellen er stor nok, så bestemmes grensene for det symmetriske konfidensintervallet for parameteren som følger:

, , dvs. , Hvor

Varians korrigert, ,

N– antall programkjøringer, – pålitelighet, .

2. Analytisk modellering av QS

2.1 Systemtilstandsgraf og Kolmogorov-ligninger

Tenk på et to-kanals køsystem (n = 2) med en begrenset kø på seks (m = 4). QS mottar den enkleste strømmen av søknader med en gjennomsnittlig intensitet λ = 4,8 og en eksponentiell lov om tidsfordeling mellom mottak av søknader. Strømmen av forespørsler servert i systemet er den enkleste med en gjennomsnittlig intensitet μ = 2 og en eksponentiell distribusjonslov for tjenestetid.

Dette systemet har 7 tilstander, la oss betegne dem:

S 0 – gratis system, ingen forespørsler;

S 1 – 1 forespørsel om service, køen er tom;

S 2 – 2 forespørsler om service, køen er tom;

S 3 – 2 forespørsler om service, 1 forespørsel i kø;

S 4 – 2 forespørsler om service, 2 forespørsler i kø;

S 5 – 2 forespørsler om service, 3 forespørsler i kø;

S 6 – 2 forespørsler om service, 4 forespørsler i kø;

Sannsynlighetene for at systemet ankommer i tilstander S 0 , S 1 , S 2 , …, S 6 er henholdsvis lik P 0 , P 1 , P 2 , …, P 6 .

Tilstandsgrafen til et køsystem er et mønster av død og reproduksjon. Alle tilstander i systemet kan representeres som en kjede der hver tilstand er koblet til de forrige og etterfølgende.

Ris. 3. Oppgi graf for en to-kanals QS

For den konstruerte grafen skriver vi Kolmogorov-ligningene:

For å løse dette systemet setter vi startbetingelsene:

Vi vil løse Kolmogorov-ligningssystemet (system av differensialligninger) ved å bruke Eulers numeriske metode ved å bruke programvarepakken Maple 11 (se vedlegg 1).

Euler-metoden

Hvor - i vårt tilfelle er dette høyresiden av Kolmogorov-ligningene, n=6.

La oss velge et tidstrinn. La oss anta hvor T– dette er tiden systemet når en stasjonær modus. Herfra får vi antall trinn . Konsekvent N Når det er beregnet ved hjelp av formel (1), får vi avhengigheten av sannsynlighetene for systemtilstander på tid, vist i fig. 4.

Verdiene til QS-sannsynlighetene ved er lik:

Ris. 4. Avhengighet av sannsynlighetene for systemtilstander på tid

P0

P5

P 4

P 3

P2

P 1

2.2 Endelige systemsannsynligheter

Dersom prosesstiden i systemet () er lang nok, kan det etableres tidsuavhengige tilstandssannsynligheter, som kalles sluttsannsynligheter, dvs. systemet er satt til stasjonær modus. Hvis antallet tilstander i systemet er endelig, og fra hver av dem i et begrenset antall trinn kan du gå til en hvilken som helst annen tilstand, så eksisterer de endelige sannsynlighetene, dvs.

Fordi i stasjonær tilstand er tidsderivertene lik 0, så fås ligningene for de endelige sannsynlighetene fra Kolmogorov-ligningene ved å likestille høyresidene til 0. La oss skrive ligningene for de endelige sannsynlighetene for QSen vår.

La oss løse dette systemet med lineære ligninger ved å bruke programvarepakken Maple 11 (se vedlegg 1).

Vi får de endelige sannsynlighetene for systemet:

Sammenligning av sannsynlighetene hentet fra Kolmogorov-likningssystemet for , med de endelige sannsynlighetene viser at feilene er like:

De. ganske liten. Dette bekrefter riktigheten av de oppnådde resultatene.

2.3 Beregning av systemeffektivitetsindikatorer etter endelige sannsynligheter

La oss finne effektivitetsindikatorene til køsystemet.

Først beregner vi den reduserte intensiteten til strømmen av applikasjoner:

1) Sannsynlighet for å nekte å betjene søknaden, dvs. sannsynligheten for at forespørselen forlater systemet ubetjent I vårt tilfelle blir forespørselen nektet tjeneste dersom alle 2 kanaler er opptatt og køen er maksimalt full (dvs. 4 personer i køen), dette tilsvarer systemtilstanden S 6 . Fordi sannsynligheten for at systemet ankommer i tilstand S 6 er lik P 6, da

4) Gjennomsnittlig kølengde, dvs. gjennomsnittlig antall applikasjoner i køen er lik summen av produktene av antall applikasjoner i køen og sannsynligheten for den tilsvarende tilstanden.

5) Den gjennomsnittlige tiden en applikasjon forblir i køen bestemmes av Littles formel:

3. Simuleringsmodellering av QS

3.1 Algoritme for QS-simuleringsmetoden (trinn for steg tilnærming)

Tenk på et to-kanals køsystem (n = 2) med en maksimal kølengde på seks (m = 4). QS mottar den enkleste strømmen av søknader med en gjennomsnittlig intensitet λ = 4,8 og en eksponentiell lov om tidsfordeling mellom mottak av søknader. Strømmen av forespørsler servert i systemet er den enkleste med en gjennomsnittlig intensitet μ = 2 og en eksponentiell distribusjonslov for tjenestetid.

For å simulere en QS vil vi bruke en av metodene for statistisk modellering – simuleringsmodellering. Vi vil bruke en steg-for-steg tilnærming. Essensen av denne tilnærmingen er at tilstandene til systemet vurderes ved påfølgende tidspunkter, hvor trinnet mellom disse er lite nok til at ikke mer enn én hendelse inntreffer i løpet av dens tid.

La oss velge et tidstrinn (). Det bør være mye mindre enn den gjennomsnittlige tiden for mottak av en søknad () og den gjennomsnittlige tiden for service (), dvs.

Hvor (3.1.1)

Basert på betingelse (3.1.1) bestemmer vi tidstrinnet .

Tidspunktet for mottak av en søknad av QS og tidspunktet for dens service er tilfeldige variabler. Derfor, når QS-systemer simuleres, beregnes de ved hjelp av tilfeldige tall.

La oss vurdere å sende inn en søknad til CMO. Sannsynligheten for at en forespørsel vil bli mottatt av QS i løpet av intervallet er lik: . La oss generere et tilfeldig tall, og hvis , så vil vi anta at søknaden på dette trinnet er mottatt av systemet if , da kom jeg ikke.

Programmet gjør dette er forespurt () . La oss ta tidsintervallet til å være konstant og lik 0,0001, da vil forholdet være lik 10000. Hvis søknaden mottas, tar den verdien "true", ellers er verdien "false".

bool isRequested()

dobbel r = R. NextDouble();

hvis (r< (timeStep * lambda))

La oss nå vurdere å betjene en applikasjon i QS. Tidspunktet for å betjene en forespørsel i systemet bestemmes av uttrykket , hvor er et tilfeldig tall. I programmet bestemmes servicetiden ved hjelp av funksjonen GetServiceTime () .

dobbel GetServiceTime()

dobbel r = R. NextDouble();

return (-1/mu*Math. Log (1-r, Math. E));

Algoritmen til simuleringsmetoden kan formuleres som følger. SMO åpningstider ( T) er delt inn i tidstrinn dt, hver av dem utfører en rekke handlinger. Først bestemmes systemtilstandene (kanalbelegg, kølengde), deretter ved å bruke funksjonen er forespurt () , avgjøres det om søknaden ble mottatt på dette trinnet eller ikke.

Hvis mottatt, og det er gratis kanaler, bruk funksjonen GetServiceTime () Vi genererer søknadsbehandlingstiden og setter den på service. Hvis alle kanaler er opptatt og kølengden er mindre enn 4, plasserer vi forespørselen i køen, men hvis kølengden er 4, vil forespørselen bli nektet tjeneste.

I tilfellet når søknaden på dette trinnet ikke ble mottatt og tjenestekanalen er gratis, sjekker vi om det er kø. Hvis det er det, legger vi forespørselen fra køen for service i en gratis kanal. Etter fullførte operasjoner reduseres tjenestetiden for opptatte kanaler med en trinnverdi dt .

Etter at tiden har gått T, dvs. etter modellering av driften av QS, beregnes systemytelsesindikatorer og resultatene vises på skjermen.

3.2 Programflytskjema

Blokkskjemaet til programmet som implementerer den beskrevne algoritmen er vist i fig. 5.

Ris. 5. Programblokkskjema

La oss beskrive noen blokker mer detaljert.

Blokk 1. Innstilling av initiale parameterverdier.

Tilfeldig R; // Tilfeldig tallgenerator

offentlig uint maxQueueLength; // Maksimal kølengde

public unit channelCount; // Antall kanaler i systemet

offentlig dobbel lambda; // Intensiteten i strømmen av mottatte forespørsler

offentlig dobbel mu; // Intensiteten til forespørselsserviceflyten

offentlig dobbel timeStep; // Tidstrinn

offentlig dobbel timeOfFinishProcessingReq; // Slutttidspunkt for forespørselsservice i alle kanaler

offentlig dobbel timeInQueue; // Tid brukt av QS i stater med kø

offentlig dobbel behandlingstid; // Systemdriftstid

offentlig dobbel totalBehandlingstid; // Total tid for serviceforespørsler

offentlig uint requestEntryCount; // Antall mottatte søknader

offentlig uint declinedRequestCount; // Antall avslåtte søknader

offentlig uint acceptedRequestCount; // Antall forespørsler levert

uint køLengde; // Kølengde //

Type som beskriver QS-tilstander

enum SysCondition(S0, S1, S2, S3, S4, S5, S6);

SysCondition gjeldendeSystemCondition; // Gjeldende systemtilstand

Stille inn systemtilstander. La oss skille 7 forskjellige tilstander for dette 2-kanals systemet: S 0, S 1. S 6. QS er i S0-tilstand når systemet er ledig; S 1 – minst én kanal er gratis; i S 2-tilstand, når alle kanaler er opptatt og det er en plass i køen; i tilstand S 6 – alle kanaler er opptatt og køen har nådd sin maksimale lengde (kølengde = 4).

Vi bestemmer den nåværende tilstanden til systemet ved hjelp av funksjonen GetCondition()

SysCondition GetCondition()

SysCondition p_currentCondit = SysCondition.S0;

int busyChannelCount = 0;

for (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

busyChannelCount++;

p_currentCondit += k * (i + 1);

if (busyChannelCount > 1)

(p_currentCondit++;)

return p_currentCondit + (int) QueueLength;

Endring i tiden QS bruker i stater med kølengder 1, 2,3,4. Dette implementeres av følgende programkode:

if (kølengde > 0)

timeInQueue += timeStep;

if (kølengde > 1)

(timeInQueue += timeStep;)

Det er en slik operasjon som å plassere en tjenesteforespørsel i en gratis kanal. Alle kanaler skannes fra den første når betingelsen timeOfFinishProcessingReq er oppfylt [ Jeg ] <= 0 (kanalen er gratis), sendes en søknad til den, dvs. Sluttiden for å betjene forespørselen genereres.

for (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq [i]<= 0)

timeOfFinishProcessingReq [i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq [i];

Service av forespørsler i kanaler er modellert av koden:

for (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq [i] > 0)

timeOfFinishProcessingReq [i] -= timeStep;

Simuleringsmetodealgoritmen er implementert i programmeringsspråket C#.

3.3 Beregning ytelsesindikatorer for QS basert på resultater av simuleringsmodelleringen

De viktigste indikatorene er:

1) Sannsynligheten for å nekte å betjene en søknad, dvs. sannsynligheten for at forespørselen forlater systemet ubetjent I vårt tilfelle blir forespørselen nektet tjeneste hvis alle 2 kanaler er opptatt og køen er maksimalt full (dvs. 4 personer i køen). For å finne sannsynligheten for feil deler vi tiden QS er i tilstanden med kø 4 med den totale driftstiden til systemet.

2) Relativ gjennomstrømning er den gjennomsnittlige andelen av innkommende forespørsler som betjenes av systemet.

3) Absolutt gjennomstrømning er gjennomsnittlig antall forespørsler som leveres per tidsenhet.

4) Kølengde, dvs. gjennomsnittlig antall søknader i køen. Lengden på køen er lik summen av produktene av antall personer i køen og sannsynligheten for den tilsvarende tilstanden. Vi vil finne sannsynlighetene for tilstander som forholdet mellom tiden QS er i denne tilstanden og den totale driftstiden til systemet.

5) Den gjennomsnittlige tiden en applikasjon forblir i køen bestemmes av Littles formel

6) Gjennomsnittlig antall okkuperte kanaler bestemmes som følger:

7) Prosentandelen av søknader som ble nektet tjeneste er funnet ved hjelp av formelen

8) Prosentandelen av søknader som leveres, bestemmes av formelen

3.4 Statistisk behandling av resultater og deres sammenligning med resultatene av analytisk modellering

Fordi effektivitetsindikatorer oppnås som et resultat av simulering av QS over en begrenset tid; de inneholder en tilfeldig komponent. Derfor, for å oppnå mer pålitelige resultater, må de behandles statistisk. For dette formålet vil vi estimere konfidensintervallet for dem basert på resultatene av 20 kjøringer av programmet.

Verdien faller innenfor konfidensintervallet dersom ulikheten er tilfredsstilt

, Hvor

matematisk forventning (gjennomsnittsverdi), funnet av formelen

Varians korrigert,

,

N =20 – antall løp,

– pålitelighet. Når og N =20 .

Resultatet av programmet er vist i fig. 6.

Ris. 6. Type program

For å gjøre det lettere å sammenligne resultatene oppnådd ved forskjellige modelleringsmetoder, presenterer vi dem i form av en tabell.

Tabell 2.

Indikatorer effektiviteten til QS	resultater analytisk modellering	resultater simuleringsmodellering (siste trinn)	Simuleringsresultater
			Bunnlinjen tillitsfulle intervall	Øvre grense tillitsfulle intervall
Sannsynlighet for feil		0,174698253017626	0,158495148639101	0,246483801571923
Relativ båndbredde		0,825301746982374	0,753516198428077	0,841504851360899
Absolutt gjennomstrømming		3,96144838551539	3,61687775245477	4,03922328653232
Gjennomsnittlig kølengde		1,68655313447018	1,62655862750852	2,10148609204869
Gjennomsnittlig tid en applikasjon tilbringer i kø	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
Gjennomsnittlig antall opptatte kanaler		1,9807241927577	1,80843887622738	2,01961164326616

Fra bordet 2 viser at resultatene oppnådd fra analytisk modellering av QS faller innenfor konfidensintervallet oppnådd fra resultatene av simuleringsmodellering. Det vil si at resultatene oppnådd ved forskjellige metoder er konsistente.

Konklusjon

Denne artikkelen diskuterer hovedmetodene for å modellere QS og beregne deres ytelsesindikatorer.

Et to-kanals QS-system med en maksimal kølengde på 4 ble modellert ved å bruke Kolmogorovs ligninger, og de endelige sannsynlighetene for systemtilstander ble funnet. Indikatorer for effektiviteten er beregnet.

Simuleringsmodellering av driften av en slik QS ble utført. Et program ble laget i programmeringsspråket C# som simulerer driften. En serie beregninger ble utført, basert på resultatene av hvilke verdiene av systemeffektivitetsindikatorer ble funnet og deres statistiske behandling ble utført.

Resultatene oppnådd fra simuleringsmodellering stemmer overens med resultatene av analytisk modellering.

Litteratur

1. Ventzel E.S. Driftsforskning. – M.: Bustard, 2004. – 208 s.

2. Volkov I.K., Zagoruiko E.A. Driftsforskning. – M.: Forlaget til MSTU oppkalt etter. N.E. Bauman, 2002. – 435 s.

3. Volkov I.K., Zuev S.M., Tsvetkova G.M. Tilfeldige prosesser. – M.: Forlaget til MSTU oppkalt etter. N.E. Bauman, 2000. – 447 s.

4. Gmurman V.E. En guide til å løse problemer i sannsynlighetsteori og matematisk statistikk. – M.: Høyere skole, 1979. – 400 s.

5. Ivnitsky V.L. Teori om kønettverk. – M.: Fizmatlit, 2004. – 772 s.

6. Forskning av operasjoner i økonomi / red. N.Sh. Kremer. – M.: Unity, 2004. – 407 s.

7. Taha H.A. Introduksjon til operasjonsforskning. – M.: Publishing House “Williams”, 2005. – 902 s.

8. Kharin Yu.S., Malyugin V.I., Kirlitsa V.P. og andre Grunnleggende om simulering og statistisk modellering. – Minsk: Design PRO, 1997. – 288 s.

Markov tilfeldig prosess med diskrete tilstander og kontinuerlig tid, diskutert i forrige forelesning, foregår i køsystemer (QS).

Køsystemer – dette er systemer som mottar forespørsler om tjeneste på tilfeldige tidspunkter, og de mottatte forespørslene betjenes ved hjelp av tjenestekanalene som er tilgjengelige for systemet.

Eksempler på køsystemer inkluderer:

• kontantoppgjørsenheter i banker og foretak;
• personlige datamaskiner som betjener innkommende applikasjoner eller krav for å løse visse problemer;
• bil bensinstasjoner; bensinstasjon;
• revisjonsfirmaer;
• skatteinspeksjonsavdelinger som er ansvarlige for å akseptere og verifisere gjeldende rapportering av foretak;
• telefonsentraler etc.

	Noder	Krav
Sykehus	Ordnere	Pasienter
Produksjon
flyplassen	Utganger til rullebaner Registreringspunkter	Passasjerer

La oss vurdere operasjonsdiagrammet til QS (fig. 1). Systemet består av en forespørselsgenerator, en dispatcher og en serviceenhet, en feilregnskapsenhet (terminator, ordredestruerer). Generelt kan en tjenestenode ha flere tjenestekanaler.

Ris. 1

1. Applikasjonsgenerator – objektgenererende forespørsler: gate, verksted med installerte enheter. Innspillet er flyt av søknader(strøm av kunder til butikken, strøm av ødelagte enheter (maskiner, maskiner) for reparasjoner, strøm av besøkende til garderoben, strøm av biler til bensinstasjonen, etc.).
2. Avsender – en person eller enhet som vet hva de skal gjøre med applikasjonen. En node som regulerer og dirigerer forespørsler til tjenestekanaler. Avsender:

• godtar søknader;
• danner en kø hvis alle kanaler er opptatt;
• leder dem til tjenestekanaler hvis det er ledige;
• avslår søknader (av ulike grunner);
• mottar informasjon fra tjenestenoden om gratis kanaler;
• overvåker driftstiden til systemet.

1. Kø – applikasjonsakkumulator. Det er kanskje ingen kø.
2. Service Senter består av et begrenset antall tjenestekanaler. Hver kanal har 3 tilstander: ledig, opptatt, fungerer ikke. Hvis alle kanaler er opptatt, så kan du komme med en strategi for hvem du skal overføre forespørselen til.
3. Avslag fra tjeneste oppstår hvis alle kanaler er opptatt (noen av dem fungerer kanskje ikke).

I tillegg til disse grunnleggende elementene i QS, fremhever noen kilder også følgende komponenter:

terminator – ødelegger av transaksjoner;

lager – lagring av ressurser og ferdige produkter;

regnskapskonto - for å utføre transaksjoner av typen "kontering";

leder – ressursforvalter;

Klassifisering av SMO

Første divisjon (basert på tilstedeværelsen av køer):

• QS med feil;
• SMO med kø.

I QS med feil en søknad mottatt på et tidspunkt da alle kanaler er opptatt avvises, forlater QS og blir ikke betjent i fremtiden.

I Kø med kø en applikasjon som kommer på et tidspunkt hvor alle kanaler er opptatt går ikke, men setter seg i kø og venter på at muligheten skal bli servert.

QS med køer er delt inn i ulike typer avhengig av hvordan køen er organisert - begrenset eller ubegrenset. Begrensninger kan gjelde både lengden på køen og ventetiden, «servicedisiplin».

Så for eksempel vurderes følgende QSer:

• CMO med utålmodige forespørsler (kølengde og tjenestetid er begrenset);
• QS med prioritert service, det vil si at noen forespørsler blir betjent utenom tur osv.

Typer kørestriksjoner kan kombineres.

En annen klassifisering deler CMO i henhold til kilden til søknader. Applikasjoner (krav) kan genereres av selve systemet eller av et eksternt miljø som eksisterer uavhengig av systemet.

Naturligvis vil flyten av forespørsler som genereres av systemet selv avhenge av systemet og dets tilstand.

I tillegg er SMO delt inn i åpen CMO og lukket SMO.

I en åpen QS avhenger ikke egenskapene til flyten av applikasjoner av tilstanden til QS selv (hvor mange kanaler som er opptatt). I en lukket QS - de er avhengige. For eksempel, hvis en arbeider betjener en gruppe maskiner som krever justering fra tid til annen, avhenger intensiteten av strømmen av "krav" fra maskinene av hvor mange av dem som allerede er i drift og venter på justering.

Et eksempel på et lukket system: en kasserer som utsteder lønn i en bedrift.

Basert på antall kanaler er QSer delt inn i:

• enkelt-kanal;
• multikanal.

Kjennetegn ved et køsystem

Hovedkarakteristikkene til enhver type køsystem er:

• inputstrøm av innkommende krav eller forespørsler om tjeneste;
• kø disiplin;
• servicemekanisme.

Inndatakrav Stream

For å beskrive inngangsstrømmen må du spesifisere en sannsynlighetslov som bestemmer rekkefølgen av øyeblikkene når forespørsler om tjeneste mottas, og angi antall slike krav i hver påfølgende kvittering. I dette tilfellet opererer de som regel med konseptet "sannsynlig fordeling av øyeblikkene for mottak av krav." Her kan de gjøre følgende: individuelle og gruppekrav (antall slike krav i hver vanlig kvittering). I sistnevnte tilfelle snakker vi vanligvis om et køsystem med parallellgruppeservice.

A i– ankomsttid mellom krav – uavhengige identisk fordelte tilfeldige variabler;

E(A)– gjennomsnittlig (MO) ankomsttid;

λ=1/E(A)– intensiteten av mottak av krav;

Inndatastrømegenskaper:

1. En sannsynlighetslov som bestemmer rekkefølgen av øyeblikk når forespørsler om tjeneste mottas.
2. Antall forespørsler ved hver neste ankomst for gruppeflyt.

Kødisiplin

Kø – et sett med krav som venter på tjeneste.

Køen har et navn.

Kødisiplin definerer prinsippet etter hvilke krav som kommer til inngangen til serveringssystemet kobles fra køen til serviceprosedyren. De mest brukte kødisiplinene er definert av følgende regler:

• førstemann til mølla;

først inn først ut (FIFO)

den vanligste typen kø.

Hvilken datastruktur er egnet for å beskrive en slik kø? Matrisen er dårlig (begrenset). Du kan bruke en LIST-struktur.

Listen har en begynnelse og en slutt. Listen består av oppføringer. En post er en listecelle. Applikasjonen kommer på slutten av listen, og velges for service fra begynnelsen av listen. Posten består av kjennetegn ved applikasjonen og en lenke (indikator på hvem som står bak). I tillegg, hvis køen har en ventetidsbegrensning, så skal også maksimal ventetid angis.

Som programmerere bør du kunne lage toveis enveislister.

Liste handlinger:

• sett inn i halen;
• ta fra begynnelsen;
• fjerne fra listen etter at tidsavbruddet utløper.
• Sist ankommer - først til å bli servert LIFO (patronklemme, blindvei på en togstasjon, gikk inn i en overfylt bil).

En struktur kjent som en STACK. Kan beskrives med en matrise eller listestruktur;

• tilfeldig utvalg av applikasjoner;
• valg av søknader basert på prioriteringskriterier.

Hver søknad kjennetegnes blant annet av sitt prioritetsnivå og plasseres ved mottak ikke i bakkanten av køen, men på slutten av sin prioriterte gruppe. Ekspeditøren sorterer etter prioritet.

Køegenskaper

• begrensningventetid tjenesteøyeblikket (det er en kø med begrenset ventetid på tjeneste, som er knyttet til konseptet "tillatt kølengde");
• kølengde.

Servicemekanisme

Servicemekanisme bestemt av egenskapene til selve tjenesteprosedyren og strukturen til tjenestesystemet. Vedlikeholdsprosedyrens egenskaper inkluderer:

• antall tjenestekanaler ( N);
• varighet av serviceprosedyren (sannsynlighetsfordeling av tid for servicekrav);
• antall krav som er oppfylt som et resultat av hver slik prosedyre (for gruppesøknader);
• sannsynlighet for feil i tjenestekanalen;
• strukturen til tjenestesystemet.

For å analytisk beskrive egenskapene til en tjenesteprosedyre, brukes begrepet "sannsynlighetsfordeling av tid for servicekrav".

S i– tjenestetid Jeg-te kravet;

E(S)– gjennomsnittlig tjenestetid;

μ=1/E(S)– hastighet på serviceforespørsler.

Det skal bemerkes at tiden som kreves for å betjene en applikasjon, avhenger av selve applikasjonens art eller kundens krav og av tilstanden og egenskapene til servicesystemet. I noen tilfeller er det også nødvendig å ta hensyn til sannsynlighet for feil i tjenestekanalen etter en viss begrenset tidsperiode. Denne egenskapen kan modelleres som en strøm av feil som kommer inn i QS og har prioritet over alle andre forespørsler.

QS utnyttelsesgrad

N·μ – servicehastighet i systemet når alle serviceenheter er opptatt.

ρ=λ/( Nμ) – kalt utnyttelseskoeffisient av QS , viser hvor mye systemressurser som brukes.

Tjenestesystemstruktur

Strukturen til servicesystemet bestemmes av antall og relative plassering av servicekanaler (mekanismer, enheter, etc.). Først og fremst bør det understrekes at et tjenestesystem kan ha mer enn én tjenestekanal, men flere; Denne typen system er i stand til å betjene flere krav samtidig. I dette tilfellet tilbyr alle tjenestekanaler de samme tjenestene, og derfor kan det hevdes at parallell tjeneste .

Eksempel. Kasseapparater i butikken.

Tjenestesystemet kan bestå av flere forskjellige typer tjenestekanaler som hvert betjent krav må passere, dvs. i tjenestesystemet prosedyrer for kravservice implementeres konsekvent . Servicemekanismen bestemmer egenskapene til den utgående (serverte) strømmen av forespørsler.

Eksempel. Medisinsk kommisjon.

Kombinert tjeneste – betjene innskudd i sparebanken: først kontrolløren, deretter kassereren. Som regel 2 kontrollører per kasserer.

Så, funksjonaliteten til ethvert køsystem bestemmes av følgende hovedfaktorer :

• sannsynlig fordeling av øyeblikkene for mottak av forespørsler om tjeneste (enkelt eller gruppe);
• kraften til kilden til krav;
• sannsynlig fordeling av tjenestens varighetstid;
• konfigurasjon av serveringssystemet (parallell, sekvensiell eller parallell-sekvensiell tjeneste);
• antall og produktivitet av tjenestekanaler;
• kødisiplin.

Hovedkriteriene for effektiviteten av funksjonen til QS

Som hovedkriterier for effektiviteten til køsystemer Avhengig av typen av problemet som skal løses, kan følgende vises:

• sannsynlighet for umiddelbar service av en innkommende applikasjon (P obsl = K obs / K post);
• sannsynlighet for å nekte å betjene en innkommende søknad (P åpen = K åpen / K-post);

Åpenbart er P obsl + P åpen =1.

Strømmer, forsinkelser, vedlikehold. Pollacheck – Khinchin formel

Forsinkelse – et av kriteriene for å betjene QS er tiden søknaden bruker på å vente på service.

D i– forsinkelse i forespørselskø Jeg;

W i =D i +Si– tid som kreves i systemet Jeg.

(med sannsynlighet 1) – den etablerte gjennomsnittlige forsinkelsen for en forespørsel i køen;

(med sannsynlighet 1) – den etablerte gjennomsnittlige tiden kravet er i QS (venter).

Q(t) – antall forespørsler i kø om gangen t;

L(t)– antall krav i systemet om gangen t(Q(t) pluss antall krav som blir betjent om gangen t.

Deretter indikatorene (hvis de finnes)

(med sannsynlighet 1) – steady-state gjennomsnittlig antall forespørsler i køen over tid;

(med sannsynlighet 1) – steady-state gjennomsnittlig antall krav i systemet over tid.

Merk at ρ<1 – обязательное условие существования d, w, Q Og L i et køsystem.

Hvis vi husker at ρ= λ/( Nμ), så er det klart at hvis intensiteten på mottak av søknader er større enn Nμ, så ρ>1 og det er naturlig at systemet ikke vil være i stand til å takle en slik strøm av søknader, og derfor kan vi ikke snakke om mengdene d, w, Q Og L.

De mest generelle og nødvendige resultatene for køsystemer inkluderer konserveringsligninger

Det skal bemerkes at kriteriene ovenfor for vurdering av systemytelse kan beregnes analytisk for køsystemer M/M/N(N>1), dvs. systemer med Markov-strømmer av forespørsler og tjenester. Til M/G/ l for enhver distribusjon G og for noen andre systemer. Generelt må tidsfordelingen mellom ankomst, tjenestetidsfordelingen eller begge være eksponentiell (eller en slags eksponentiell Erlang-fordeling av kth-orden) for at en analytisk løsning skal være mulig.

I tillegg kan vi også snakke om egenskaper som:

• absolutt systemkapasitet – А=Р obsl *λ;
• relativ systemkapasitet –

Nok et interessant (og illustrerende) eksempel på en analytisk løsning – beregning av steady-state gjennomsnittlig forsinkelse i en kø for et køsystem M/G/ 1 i henhold til formelen:

.

I Russland er denne formelen kjent som Pollacek-formelen – Khinchin, i utlandet er denne formelen assosiert med navnet Ross.

Således, hvis E(S) er større, så overbelastningen (i dette tilfellet målt som d) vil være større; som er å forvente. Formelen avslører også et mindre åpenbart faktum: Overbelastning øker også når variasjonen i tjenestetidsfordelingen øker, selv om den gjennomsnittlige tjenestetiden forblir den samme. Intuitivt kan dette forklares som følger: variansen til den tilfeldige variabelen for tjenestetid kan få en stor verdi (siden den må være positiv), dvs. den eneste tjenesteenheten vil være opptatt i lang tid, noe som vil føre til en økning i køen.

Emnet køteori er å etablere en sammenheng mellom faktorene som bestemmer funksjonaliteten til køsystemet og effektiviteten av driften. I de fleste tilfeller er alle parametere som beskriver køsystemer tilfeldige variabler eller funksjoner, derfor tilhører disse systemene stokastiske systemer.

Den tilfeldige karakteren av strømmen av søknader (krav), så vel som, i det generelle tilfellet, varigheten av tjenesten fører til det faktum at en tilfeldig prosess skjer i køsystemet. Av den tilfeldige prosessens natur , som forekommer i køsystemet (QS), skilles ut Markovske og ikke-markovske systemer . I Markov-systemer er den innkommende strømmen av krav og den utgående strømmen av betjente krav (applikasjoner) Poisson. Poisson-strømmer gjør det enkelt å beskrive og konstruere en matematisk modell av et køsystem. Disse modellene har ganske enkle løsninger, så de fleste av de velkjente anvendelsene av køteori bruker Markov-ordningen. Når det gjelder ikke-Markov-prosesser, blir problemene med å studere køsystemer betydelig mer kompliserte og krever bruk av statistisk modellering og numeriske metoder ved bruk av en datamaskin.

1.1. Struktur og parametere for effektiviteten og kvaliteten på funksjonen til QS

Mange økonomiske problemer er knyttet til køsystemer, d.v.s. slike systemer der det på den ene siden oppstår massive forespørsler (krav) for utførelse av noen tjenester, og på den andre siden blir disse forespørslene tilfredsstilt. QS inkluderer følgende elementer: kilde til krav, innkommende flyt av krav, kø, serveringsenheter (tjenestekanaler), utgående flyt av krav. Køteori studerer slike systemer.

Fasilitetene som betjener krav kalles servicerer eller servicekanaler. Disse inkluderer for eksempel drivstoffinnretninger på bensinstasjoner, telefonkommunikasjonskanaler, landingsbaner, reparatører, billettkasserer, laste- og lossepunkter på baser og varehus.

Ved å bruke metodene for køteori kan mange problemer med å studere prosesser som forekommer i økonomien løses. Ved organisering av handel gjør disse metodene det derfor mulig å bestemme det optimale antallet utsalgssteder for en gitt profil, antall selgere, leveringsfrekvensen av varer og andre parametere. Et annet typisk eksempel på køsystemer kan være bensinstasjoner, og oppgavene med køteori handler i dette tilfellet om å etablere det optimale forholdet mellom antall serviceforespørsler som kommer til en bensinstasjon og antall serviceenheter, hvor de totale kostnadene av service og tap fra nedetid ville være minimal. Teorien om kø kan også brukes ved beregning av arealet til lagerlokaler, mens lagerområdet betraktes som en serviceenhet, og ankomst av kjøretøy for lossing anses som et krav. Modeller av teorien om kø brukes også for å løse en rekke problemer med organisering og rasjonering av arbeidskraft, og andre sosioøkonomiske problemer.

Hver QS inkluderer i sin struktur et visst antall tjenesteenheter, kalt tjenestekanaler (disse kan inkludere personer som utfører visse operasjoner - kasserere, operatører, ledere, etc.) som betjener en viss strøm av applikasjoner (krav), som kommer til innspillet tilfeldig ganger. Service av applikasjoner skjer på et ukjent, vanligvis tilfeldig tidspunkt og avhenger av mange forskjellige faktorer. Etter å ha utført forespørselen, er kanalen frigjort og klar til å motta neste forespørsel. Den tilfeldige karakteren av strømmen av applikasjoner og tidspunktet for deres service fører til ujevn belastning av QS - overbelastning med dannelse av køer av applikasjoner eller underbelastning - med tomgang i kanalene. Tilfeldigheten i strømmen av forespørsler og varigheten av tjenesten deres gir opphav til en tilfeldig prosess i QS, hvis studie krever konstruksjon og analyse av dens matematiske modell. Studiet av funksjonen til QS er forenklet hvis den tilfeldige prosessen er Markovian (en prosess uten ettervirkninger, eller uten minne), når driften av QS enkelt beskrives ved bruk av endelige systemer med vanlige lineære differensialligninger av første orden, og i begrensende modus (med en tilstrekkelig lang drift av QS) ved hjelp av endelige systemer lineære algebraiske ligninger. Som et resultat uttrykkes indikatorer for effektiviteten av funksjonen til QS gjennom parametrene til QS, flyten av applikasjoner og disiplin.

Det er kjent fra teorien at for at en tilfeldig prosess skal være markovsk, er det nødvendig og tilstrekkelig at alle strømmer av hendelser (strømmer av applikasjoner, strømmer av serviceapplikasjoner, etc.), under påvirkning av hvilke overganger av systemet fra stat til stat til tilstand oppstår, er Poisson, dvs. hadde egenskapene konsekvens (for alle to ikke-overlappende tidsintervaller avhenger ikke antall hendelser som inntreffer under den ene av antall hendelser som skjer etter den andre) og ordinæritet (sannsynligheten for at mer enn én hendelse inntreffer i løpet av en elementær, eller liten, tidsperiode er ubetydelig sammenlignet med sannsynligheten for at en hendelse inntreffer i løpet av denne tidsperioden). For den enkleste Poisson-strømmen er den tilfeldige variabelen T (tidsintervallet mellom to nabohendelser) fordelt i henhold til en eksponentiell lov, som representerer dens fordelingstetthet eller differensialfordelingsfunksjon.

Hvis arten av strømmer i en QS er forskjellig fra Poisson, kan dens effektivitetsegenskaper bestemmes omtrentlig ved å bruke Markov-teorien om kø, og jo mer nøyaktig, jo mer kompleks er QS, og jo flere tjenestekanaler har den. I de fleste tilfeller krever ikke gyldige anbefalinger for praktisk styring av en QS kunnskap om dens eksakte egenskaper; det er nok å ha deres omtrentlige verdier.

Hver QS, avhengig av parameterne, har en viss driftseffektivitet.

Effektiviteten av funksjonen til QS er preget av tre hovedgrupper av indikatorer:

1. Effektivitet ved bruk av QS - absolutt eller relativ gjennomstrømning, gjennomsnittlig varighet av QS-opptatt periode, QS-utnyttelsesgrad, QS-ikke-bruksforhold;

2. Kvalitet på betjening av applikasjoner - gjennomsnittlig tid (gjennomsnittlig antall applikasjoner, distribusjonslov) for å vente på en applikasjon i en kø eller opphold av en applikasjon i QS; sannsynligheten for at den mottatte søknaden umiddelbart vil bli akseptert for utførelse;

3. Effektiviteten av funksjonen til et par CMO-forbruker, og forbrukeren er forstått som et sett med applikasjoner eller en kilde til dem (for eksempel den gjennomsnittlige inntekten brakt av CMO per enhet driftstid, etc.) .

1.2 Klassifisering av QS og deres hovedelementer

QS klassifiseres i ulike grupper avhengig av sammensetningen og tiden brukt i køen før tjenestestart, og disiplinen til serviceforespørsler.

I henhold til sammensetningen av QS er det enkeltkanal (med en serveringsenhet) og multikanal (med et stort antall serveringsenheter). Flerkanalssystemer kan bestå av tjenesteenheter med både samme og ulik ytelse.

Basert på tidskravene som gjenstår i køen før service starter, er systemene delt inn i tre grupper:

1) med ubegrenset ventetid (med venting),

2) med avslag;

3) blandet type.

I en QS med ubegrenset ventetid, kommer neste forespørsel, som finner alle enhetene opptatt, i en kø og venter på service til en av enhetene er ledig.

I systemer med feil forlater en innkommende forespørsel, som finner alle enheter opptatt, systemet. Et klassisk eksempel på et system med feil er driften av en automatisk telefonsentral.

I systemer med blandet type finner en innkommende forespørsel alle enheter opptatt, står i kø og venter på service i en begrenset tid. Uten å vente på service på det angitte tidspunktet forlater forespørselen systemet.

La oss kort vurdere funksjonene til noen av disse systemene.

1. En QS med venting kjennetegnes ved at i et system med n (n>=1) kommer enhver forespørsel som ankommer QS i det øyeblikket alle kanaler er opptatt i en kø og venter på tjeneste, og enhver innkommende forespørsel er betjent. Et slikt system kan være i en av et uendelig antall tilstander: s n +к (r=1,2...) – alle kanaler er opptatt og det er r applikasjoner i køen.

2. En QS med venting og en begrensning på kølengde skiller seg fra ovenstående ved at dette systemet kan være i en av n+m+1 tilstander. I tilstander s 0 , s 1 ,…, s n er det ingen kø, siden det enten ikke er noen applikasjoner i systemet eller ingen i det hele tatt og kanalene er ledige (s 0), eller det er flere I (I = 1,n ) applikasjoner i systemet, som betjenes av det tilsvarende (n+1, n+2,...n+r,...,n+m) antall applikasjoner og (1,2,...r,...,m) applikasjoner som står i køen. En søknad som kommer til QS-inngangen på et tidspunkt der det allerede er m søknader i køen, avvises og lar systemet være ubetjent.

Dermed fungerer en flerkanals QS i hovedsak som en enkeltkanal, når alle n kanaler fungerer som én med en gjensidig assistansedisiplin kalt alle som én, men med en høyere tjenesteintensitet. Tilstandsgrafen til et slikt lignende system inneholder bare to tilstander: s 0 (s 1) - alle n kanalene er ledige (opptatte).

En analyse av ulike typer QS med gjensidig assistanse av alt-i-ett-typen viser at slik gjensidig assistanse reduserer den gjennomsnittlige tiden en applikasjon oppholder seg i systemet, men forverrer en rekke andre egenskaper som sannsynlighet for feil, gjennomstrømning, gjennomsnittlig antall søknader i køen og ventetiden for utførelse av dem. Derfor, for å forbedre disse indikatorene, brukes en endring i disiplinen for serviceforespørsler med enhetlig gjensidig assistanse mellom kanaler som følger:

· Hvis en forespørsel kommer til QS på et tidspunkt da alle kanaler er ledige, begynner alle n kanalene å betjene den;

· Hvis neste forespørsel kommer på dette tidspunktet, bytter noen av kanalene til å betjene den

· Hvis, mens de betjener disse to forespørslene, kommer en tredje forespørsel, så byttes noen av kanalene til å betjene denne tredje forespørselen, inntil hver forespørsel som ligger i QS-en betjenes av kun én kanal. I dette tilfellet kan en søknad mottatt i det øyeblikket alle kanaler er opptatt, i QS med avslag og enhetlig gjensidig bistand mellom kanaler, bli avvist og vil bli tvunget til å la systemet stå ubetjent.

Metoder og modeller brukt i køteori kan deles inn i analytisk og simulering.

Analytiske metoder for køteori gjør det mulig å oppnå egenskapene til systemet som noen funksjoner av driftsparametrene. Takket være dette blir det mulig å gjennomføre en kvalitativ analyse av påvirkningen av individuelle faktorer på effektiviteten til QS. Simuleringsmetoder er basert på datamodellering av køprosesser og brukes dersom det er umulig å bruke analytiske modeller.

For tiden er de mest teoretisk utviklet og praktiske i praktiske applikasjoner metoder for å løse køproblemer der den innkommende strømmen av krav er den enkleste (Poisson).

For den enkleste flyten følger frekvensen av forespørsler som kommer inn i systemet Poisson-loven, dvs. sannsynligheten for ankomst i løpet av tiden t med nøyaktig k krav er gitt av formelen:

En viktig egenskap ved en QS er tiden det tar å betjene krav i systemet. Tjenestetiden for en forespørsel er som regel en tilfeldig variabel og kan derfor beskrives av en distribusjonslov. Den eksponentielle loven om tjenestetidsfordeling er mest brukt i teori og spesielt i praktiske applikasjoner. Fordelingsfunksjonen for denne loven har formen:

De. sannsynligheten for at tjenestetiden ikke overskrider en viss verdi t bestemmes av denne formelen, der µ er parameteren for eksponentiell service av krav i systemet, dvs. det gjensidige av tjenestetiden t rev:

La oss vurdere analytiske modeller av de vanligste QSene med forventning, dvs. slike QS der forespørsler mottatt på et tidspunkt når alle serveringskanaler er opptatt, settes i kø og betjenes etter hvert som kanalene blir ledige.

Den generelle formuleringen av problemet er som følger. Systemet har n serveringskanaler, som hver kan betjene kun én forespørsel om gangen.

Systemet mottar en enkel (paussonsk) flyt av forespørsler med parameter . Hvis det, på det tidspunktet neste forespørsel kommer, allerede er minst n forespørsler i systemet for service (dvs. alle kanaler er opptatt), så blir denne forespørselen i kø og venter på at service skal begynne.

I systemer med en bestemt tjenestedisiplin blir en innkommende forespørsel, å finne alle enheter opptatt, avhengig av prioritet, enten betjent ute av sving eller plassert i kø.

Hovedelementene i QS er: innkommende flyt av krav, kø av krav, serveringsenheter (kanaler) og utgående flyt av krav.

Studiet av QS begynner med analysen av den innkommende strømmen av krav. Den innkommende kravflyten er samlingen av krav som kommer inn i systemet og må betjenes. Den innkommende strømmen av krav studeres for å etablere mønstrene for denne strømmen og ytterligere forbedre kvaliteten på tjenesten.

I de fleste tilfeller er den innkommende strømmen ukontrollerbar og avhenger av en rekke tilfeldige faktorer. Antallet forespørsler som kommer per tidsenhet er en tilfeldig variabel. En tilfeldig variabel er også tidsintervallet mellom tilstøtende innkommende forespørsler. Gjennomsnittlig antall forespørsler mottatt per tidsenhet og gjennomsnittlig tidsintervall mellom tilstøtende innkommende forespørsler antas imidlertid å være gitt.

Gjennomsnittlig antall krav som kommer inn i tjenestesystemet per tidsenhet kalles ankomsthastigheten for etterspørsel og bestemmes av følgende relasjon:

hvor T er gjennomsnittsverdien av intervallet mellom ankomsten av påfølgende forespørsler.

For mange reelle prosesser er flyten av krav ganske godt beskrevet av Poissons distribusjonslov. En slik flyt kalles den enkleste.

Den enkleste strømmen har følgende viktige egenskaper:

1) Egenskapen til stasjonaritet, som uttrykker invariansen til det sannsynlige strømningsregimet over tid. Dette betyr at antall forespørsler som kommer inn i systemet med like tidsintervaller i gjennomsnitt bør være konstant. For eksempel bør antall biler som ankommer for lasting i gjennomsnitt per dag være det samme for ulike tidsperioder, for eksempel ved begynnelsen og slutten av et tiår.

2) Fravær av ettervirkning, som bestemmer den gjensidige uavhengigheten av mottak av ett eller annet antall forespørsler om tjeneste i ikke-overlappende tidsperioder. Dette betyr at antall forespørsler som kommer i løpet av en gitt tidsperiode ikke er avhengig av antall forespørsler som blir behandlet i forrige tidsperiode. For eksempel er antall kjøretøyer som kommer for materialer den tiende dagen i måneden uavhengig av antall kjøretøy som blir utført på den fjerde eller en hvilken som helst annen foregående dag i måneden.

3) Egenskapen til vanlighet, som uttrykker den praktiske umuligheten av samtidig mottak av to eller flere krav (sannsynligheten for en slik hendelse er umåtelig liten i forhold til tidsperioden som vurderes, når sistnevnte har en tendens til null).

Med den enkleste flyten av krav, følger fordelingen av krav som kommer inn i systemet Poissons distribusjonslov:

sannsynligheten for at nøyaktig k forespørsler kommer til servicesystemet i løpet av tiden t:

Hvor. - gjennomsnittlig antall forespørsler mottatt for tjeneste per tidsenhet.

I praksis er betingelsene for den enkleste flyten ikke alltid strengt oppfylt. Prosessen er ofte ikke-stasjonær (på forskjellige tidspunkter på dagen og forskjellige dager i måneden kan strømmen av krav endres; den kan være mer intens om morgenen eller de siste dagene i måneden). Det er også en ettervirkning, når antall krav for frigjøring av varer i slutten av måneden avhenger av deres tilfredshet i begynnelsen av måneden. Fenomenet heterogenitet observeres også når flere kunder samtidig ankommer lageret for materialer. Generelt gjenspeiler imidlertid Poisson-fordelingsloven mange køprosesser med en ganske høy tilnærming.

I tillegg kan tilstedeværelsen av en Poisson-strøm av krav bestemmes ved statistisk behandling av data ved mottak av forespørsler om service. Et av trekkene ved Poisson-fordelingsloven er likheten mellom den matematiske forventningen til en tilfeldig variabel og variansen til den samme variabelen, dvs.

En av de viktigste egenskapene til serviceenheter, som bestemmer gjennomstrømningen til hele systemet, er servicetid.

Tjenestetiden for én forespørsel () er en tilfeldig variabel som kan endres over et bredt område. Det avhenger av stabiliteten til driften av selve serviceenhetene, så vel som av ulike parametere som kommer inn i systemet, krav (for eksempel ulik bærekapasitet til kjøretøyer som ankommer for lasting eller lossing.

En stokastisk variabel er fullstendig preget av en fordelingslov, som bestemmes på grunnlag av statistiske tester.

I praksis blir hypotesen om den eksponentielle fordelingsloven om tjenestetid oftest akseptert.

Den eksponentielle distribusjonsloven for tjenestetid oppstår når distribusjonstettheten avtar kraftig med økende tid t. For eksempel når hoveddelen av kravene betjenes raskt, og langsiktig service er sjelden. Tilstedeværelsen av en eksponentiell distribusjonslov for tjenestetid er etablert på grunnlag av statistiske observasjoner.

Med den eksponentielle distribusjonsloven for tjenestetid, er sannsynligheten for en hendelse for at tjenestetiden ikke varer mer enn t lik:

der v er intensiteten av å betjene ett behov av en serviceenhet, som bestemmes ut fra forholdet:

hvor er gjennomsnittstiden for å betjene én forespørsel av én tjenesteenhet.

Det skal bemerkes at hvis loven om distribusjon av tjenestetid er veiledende, vil loven om distribusjon av tjenestetid for flere enheter også være veiledende i nærvær av flere serviceenheter med samme kraft:

hvor n er antall serveringsenheter.

En viktig parameter for QS er belastningsfaktoren, som er definert som forholdet mellom intensiteten av mottak av krav og intensiteten av tjenesten v.

hvor a er belastningsfaktoren; - intensiteten av kravene som kommer inn i systemet; v er intensiteten av å betjene én forespørsel fra én tjenesteenhet.

Fra (1) og (2) får vi det

Tatt i betraktning at det er intensiteten på forespørsler som kommer inn i systemet per tidsenhet, viser produktet antall forespørsler som kommer inn i servicesystemet i løpet av den gjennomsnittlige tiden for å betjene én forespørsel av én enhet.

For en QS med venting må antallet betjente enheter n være strengt tatt større enn belastningsfaktoren (krav for en stabil eller stasjonær driftsmodus for QS):

Ellers vil antallet innkommende forespørsler være større enn den totale produktiviteten til alle serveringsenheter, og køen vil vokse ubegrenset.

For QS med feil og blandede typer kan denne tilstanden svekkes; for effektiv drift av disse QS-typene er det tilstrekkelig å kreve at minimumsantallet betjente enheter n ikke er mindre enn belastningsfaktoren:

1.3 Simuleringsprosess

Som nevnt tidligere, begynner prosessen med iterativ utvikling av en simuleringsmodell med å lage en enkel modell, som deretter gradvis blir mer kompleks i samsvar med kravene til problemet som skal løses. Følgende hovedstadier kan skilles i simuleringsprosessen:

1. Dannelse av problemet: beskrivelse av problemet som studeres og fastsettelse av målene for studien.

2. Modellutvikling: logisk og matematisk beskrivelse av det modellerte systemet i samsvar med problemformuleringen.

3. Dataforberedelse: identifikasjon, spesifikasjon og innsamling av data.

4. Modelloversettelse: oversettelse av modellen til et språk som er akseptabelt for datamaskinen som brukes.

5. Verifikasjon: fastslå riktigheten av maskinprogrammer.

6. Validering: vurdering av nødvendig nøyaktighet og samsvar av simuleringsmodellen med det virkelige systemet.

7. Strategisk og taktisk planlegging: fastsettelse av betingelsene for å gjennomføre et maskineksperiment med en simuleringsmodell.

8. Eksperimentering: kjører en simuleringsmodell på en datamaskin for å få den nødvendige informasjonen.

9. Analyse av resultater: studere resultatene av et simuleringseksperiment for å utarbeide konklusjoner og anbefalinger for å løse problemet.

10. Implementering og dokumentasjon: implementering av anbefalinger hentet fra simuleringen, utarbeidelse av dokumentasjon på modellen og bruken av den.

La oss vurdere hovedstadiene i simuleringsmodellering. Den første oppgaven til en simuleringsstudie er å presist definere problemet og i detalj formulere målene for studien. Vanligvis er problemdefinisjon en pågående prosess som vanligvis skjer gjennom hele studiet. Den er revidert som en dypere forståelse av problemet som studeres og fremveksten av nye aspekter ved det.

Når den første definisjonen av problemet er formulert, begynner stadiet med å bygge en modell av systemet som studeres. Modellen inkluderer en statistisk og dynamisk beskrivelse av systemet. I den statistiske beskrivelsen bestemmes elementene i systemet og deres egenskaper, og i den dynamiske beskrivelsen, samspillet mellom elementene i systemet, som et resultat av at det oppstår en endring i dets tilstand over tid.

Prosessen med å danne en modell er på mange måter en kunst. Modellutvikleren må forstå strukturen til systemet, identifisere reglene for dets funksjon og være i stand til å fremheve det viktigste i dem, og eliminere unødvendige detaljer. Modellen må være lett å forstå og samtidig kompleks nok til å realistisk representere egenskapene til et reelt system. De viktigste avgjørelsene tas av prosjekterende om de vedtatte forenklingene og forutsetningene er riktige, hvilke elementer og samspillet mellom dem som skal inkluderes i modellen. Detaljnivået i modellen avhenger av formålet med opprettelsen. Det er nødvendig å vurdere bare de elementene som er avgjørende for å løse problemet som studeres. Både på problemdannelsesstadiet og på modelleringsstadiet er det nødvendig med et nært samspill mellom modellutvikleren og dens brukere. I tillegg gir tett samhandling på stadier av problemformulering og modellutvikling brukeren tillit til riktigheten av modellen, og bidrar derfor til å sikre en vellykket implementering av resultatene fra simuleringsstudien.

På modellutviklingsstadiet fastsettes kravene til inngangsdata. Noen av disse dataene kan allerede være tilgjengelige for modellbyggeren, mens andre vil kreve tid og krefter å samle inn. Vanligvis settes verdien av slike inputdata basert på noen hypoteser eller foreløpig analyse. I noen tilfeller har de nøyaktige verdiene til én (eller flere) inngangsparametere liten innvirkning på resultatene av modellkjøringer. Følsomheten til de oppnådde resultatene for endringer i inngangsdataene kan vurderes ved å utføre en serie simuleringskjøringer for forskjellige verdier av inngangsparameterne. Simuleringsmodellen kan derfor brukes til å redusere tiden og kostnadene som kreves for å foredle inndata. Når modellen er utviklet og de første inndataene er samlet inn, er neste oppgave å oversette modellen til en datamaskintilgjengelig form.

På verifikasjons- og valideringsstadiene blir simuleringsmodellens funksjon vurdert. På verifiseringsstadiet bestemmes det om modellen som er programmert for datamaskinen samsvarer med utviklerens intensjon. Dette gjøres vanligvis ved å kontrollere beregningen manuelt, men en rekke statistiske metoder kan også brukes.

Etablering av tilstrekkeligheten til simuleringsmodellen til systemet som studeres, utføres på valideringsstadiet. Modellvalidering utføres vanligvis på ulike nivåer. Spesifikke valideringsmetoder inkluderer å etablere tilstrekkelighet ved å bruke konstante verdier for alle parametere i simuleringsmodellen eller ved å vurdere følsomheten til utdata for endringer i inngangsdataverdier. Under valideringsprosessen bør det gjøres sammenligninger basert på analyse av både reelle og eksperimentelle data om hvordan systemet fungerer.

Betingelsene for å utføre maskinkjøringer av modellen bestemmes på stadiene av strategisk og taktisk planlegging. Oppgaven med strategisk planlegging er å utvikle en effektiv eksperimentell plan, som et resultat av at forholdet mellom kontrollerte variabler blir avklart, eller funnet en kombinasjon av verdier av kontrollerte variabler, minimering eller maksimering av simuleringsmodellen. Taktisk planlegging, i motsetning til strategisk planlegging, tar opp spørsmålet om hvordan man utfører hver simulering som kjøres innenfor den eksperimentelle planen for å få størst mulig informasjon fra utdataene. En viktig plass i taktisk planlegging er definisjonen av betingelser for simuleringskjøringer og metoder for å redusere variansen av gjennomsnittsverdien av modellresponsen.

De neste stadiene i prosessen med simuleringsforskning - å gjennomføre et dataeksperiment og analysere resultatene - inkluderer å kjøre simuleringsmodellen på en datamaskin og tolke de resulterende utdataene. Den siste fasen av en simuleringsstudie er å implementere de resulterende løsningene og dokumentere simuleringsmodellen og dens bruk. Ingen simuleringsprosjekt skal anses som fullført før resultatene er brukt i beslutningsprosessen. Suksessen til implementeringen avhenger i stor grad av hvor riktig modellutvikleren fullførte alle de tidligere stadiene av simuleringsforskningsprosessene. Hvis utvikleren og brukeren jobbet tett og oppnådde en gjensidig forståelse for å utvikle modellen og utforske den, vil resultatet av prosjektet sannsynligvis bli vellykket implementert. Hvis det ikke var noe nært forhold mellom dem, vil det, til tross for elegansen og tilstrekkeligheten til simuleringsmodellering, være vanskelig å utvikle effektive anbefalinger.

Trinnene ovenfor utføres sjelden i en strengt definert sekvens, fra problemdefinisjon til dokumentasjon. Under simulering kan det oppstå svikt i modellkjøringer, feilaktige antakelser som senere må forlates, refokusering av forskningsmål, re-estimeringer og ombygging av modellen. Denne prosessen tillater utvikling av en simuleringsmodell som gir en valid vurdering av alternativer og letter beslutningsprosessen.

Kapittel 2. Distribusjoner og pseudorandomtallgeneratorer

Følgende notasjoner vil bli brukt nedenfor:

X er en tilfeldig variabel; f(x) - sannsynlighetstetthetsfunksjon X; F(x) - sannsynlighetsfunksjon X;

a - minimumsverdi;

b - maksimal verdi;

μ - matematisk forventning M[X]; σ2 - varians M[(X-μ)2];

σ - standardavvik; α-parameter for;

En kø med lengde k forblir i den med sannsynlighet Pk og slutter seg ikke til køen med sannsynlighet gk=1 - Pk." Det er akkurat slik folk vanligvis oppfører seg i køer. I køsystemer, som er matematiske modeller av produksjonsprosesser, kan ev. kølengden er begrenset av en konstant størrelse (for eksempel bunkerskapasitet). Dette er selvsagt et spesielt tilfelle av den generelle innstillingen. Noen...

Ytelsesindikatorer for QS

• absolutt og relativ systemkapasitet;
• belastning og tomgang;
• gjennomsnittlig tid for å fulllaste systemet;
• gjennomsnittlig tid en applikasjon forblir i systemet.

Indikatorer som karakteriserer systemet fra forbrukernes synspunkt:

• P obs – sannsynlighet for forespørsel om service,
• t syst – applikasjonens oppholdstid i systemet.

Indikatorer som karakteriserer systemet med tanke på dets operasjonelle egenskaper:

• λ b– absolutt systemgjennomstrømning (gjennomsnittlig antall forespørsler levert per tidsenhet),
• P obs – relativ systemkapasitet,
• k z – systembelastningsfaktor.

se også Parametre for økonomisk effektivitet av QS

Oppgave . Et delt datasenter med tre datamaskiner mottar bestillinger fra bedrifter om dataarbeid. Hvis alle tre datamaskinene fungerer, blir den nylig mottatte bestillingen ikke akseptert, og bedriften blir tvunget til å kontakte et annet datasenter. Gjennomsnittlig arbeidstid med én bestilling er 3 timer.Intensiteten på strømmen av søknader er 0,25 (1/time). Finn de begrensende sannsynlighetene for tilstander og ytelsesindikatorer for datasenteret.
Løsning. I henhold til betingelsen n=3, λ=0,25(1/h), t vol. =3 (h). Tjenestestrømningsintensitet μ=1/t vol. =1/3=0,33. Datamaskinbelastningsintensitet i henhold til formel (24) ρ=0,25/0,33=0,75. La oss finne de begrensende sannsynlighetene for tilstander:
ifølge formel (25) p 0 =(1+0,75+0,75 2/2!+0,75 3/3!) -1 =0,476;
ifølge formel (26) p1 =0,75∙0,476=0,357; p 2 =(0,75 2/2!)∙0,476=0,134; p 3 =(0,75 3 /3!)∙0,476=0,033 dvs. i den stasjonære driftsmodusen til datasenteret er det i gjennomsnitt 47,6% av tiden ingen forespørsel, 35,7% - det er en forespørsel (en datamaskin er opptatt), 13,4% - to forespørsler (to datamaskiner), 3,3% av tiden - tre forespørsler (tre datamaskiner er opptatt).
Sannsynligheten for feil (når alle tre datamaskinene er opptatt), og dermed P åpen. =p3 =0,033.
I følge formel (28) er den relative kapasiteten til senteret Q = 1-0,033 = 0,967, dvs. I gjennomsnitt, av hver 100 forespørsler, betjener datasenteret 96,7 forespørsler.
I følge formel (29) er senterets absolutte kapasitet A = 0,25∙0,967 = 0,242, dvs. I gjennomsnitt blir det servert 0,242 søknader per time.
I følge formel (30) er gjennomsnittlig antall okkuperte datamaskiner k = 0,242/0,33 = 0,725, dvs. hver av de tre datamaskinene vil være opptatt med å betjene forespørsler i gjennomsnitt bare 72,5/3 = 24,2 %.
Når du vurderer effektiviteten til et datasenter, er det nødvendig å sammenligne inntektene fra utførelsen av forespørsler med tapene fra nedetiden til dyre datamaskiner (på den ene siden har vi høy gjennomstrømming av QS, og på den andre siden , er det betydelig nedetid for tjenestekanaler) og velg en kompromissløsning.

Oppgave . Havnen har én kai for lossing av skip. Fartøyets strømningshastighet er 0,4 (kar per dag). Gjennomsnittlig lossetid for ett fartøy er 2 dager. Det forutsettes at køen kan være av ubegrenset lengde. Finn ytelsesindikatorene til køya, samt sannsynligheten for at ikke mer enn 2 fartøy venter på å losse.
Løsning. Vi har ρ = λ/μ = μt vol. =0,4∙2=0,8. Siden ρ = 0,8 < 1, så kan ikke køen for lossing øke i det uendelige og det finnes begrensende sannsynligheter. La oss finne dem.
Sannsynligheten for at køya er ledig, i henhold til (33) p 0 = 1 - 0,8 = 0,2, og sannsynligheten for at den er opptatt, P belegg. = 1-0,2 = 0,8. I henhold til formel (34) er sannsynligheten for at det er 1, 2, 3 fartøy ved kaien (dvs. 0, 1, 2 fartøy venter på å losse) lik p 1 = 0,8(1-0,8) = 0, 16; p 2 = 0,8 2 ∙(1-0,8) = 0,128; p 3 = 0,8 3 ∙(1-0,8) = 0,1024.
Sannsynligheten for at ikke mer enn 2 fartøy venter på å losse er lik
P=p 1 + p 2 + p 3 = 0,16 + 0,128 + 0,1024 = 0,3904
I henhold til formel (40), gjennomsnittlig antall skip som venter på lossing
L jh = 0,82 /(1-0,8) = 3,2
og gjennomsnittlig ventetid for lossing i henhold til formelen (15.42)
Tp = 3,2/0,8 = 4 dager.
I henhold til formel (36) er gjennomsnittlig antall fartøyer plassert ved kai, L syst. = 0,8/(1-0,8) = 4 (dager) (eller enklere i henhold til (37) L syst. = 3,2+0,8 = 4 (dager), og gjennomsnittlig tid fartøyet ligger ved kai i henhold til formelen (41) ) T syst = 4/0,8 = 5 (dager).
Det er åpenbart at effektiviteten ved lossing av skip er lav. For å øke den, er det nødvendig å redusere gjennomsnittstiden for lossing av fartøyet t om eller øke antall køyer n.

Oppgave . I et supermarked kommer en strøm av kunder til betalingssenteret med en intensitet på λ = 81 personer. Klokken ett. Gjennomsnittlig varighet av service av en kassekontrollør til én kunde t rev = 2 min. Definere:
EN. Minimum antall kasserere n min, hvor køen ikke vil vokse til uendelig, og de tilsvarende tjenestekarakteristikkene for n=n min .
b. Optimal mengde n opt. kontroller-kasserer, hvor den relative verdien av kostnadene C rel., knyttet til kostnadene ved vedlikehold av servicekanaler og med å holde seg i kundekøen, gitt for eksempel som , vil være minimal, og sammenligne tjenestekarakteristikkene med n= n min og n=n opt .
V. Sannsynligheten for at det ikke er mer enn tre kunder i køen.
Løsning.
EN. Etter tilstand l = 81(1/t) = 81/60 = 1,35 (1/min.). I henhold til formel (24) r = l/ m = lt rev = 1,35×2 = 2,7. Køen vil ikke vokse i det uendelige forutsatt r/n< 1, т.е. при n >r = 2,7. Dermed er minimum antall kassererkontrollører n min = 3.
La oss finne tjenesteegenskapene til QS på P= 3.
Sannsynligheten for at det ikke er kjøpere i oppgjørsnoden, i henhold til formel (45) p 0 = (1+2,7+2,7 2 /2!+2,7 3 /3!+2,7 4 /3!(3 -2,7)) - 1 = 0,025, dvs. i gjennomsnitt 2,5 % kontrollører og kasser vil være inaktive en stund.
Sannsynligheten for at det blir kø ved beregningsnoden, ifølge (48) P very. = (2,7 4 /3!(3-2,7))0,025 = 0,735
Gjennomsnittlig antall kunder i køen for (50) L och. = (2,7 4 /3∙3!(1-2,7/3) 2)0,025 = 7,35.
Gjennomsnittlig ventetid i kø for (42) T veldig. = 7,35/1,35 = 5,44 (min).
Gjennomsnittlig antall kjøpere i oppgjørsnoden etter (51) L-system. = 7,35+2,7 = 10,05.
Gjennomsnittlig tid brukt av kjøpere i oppgjørsnoden i henhold til (41) T syst. = 10,05/1,35 = 7,44 (min).
Tabell 1

Tjenesteegenskaper	Antall kasserere
	3	4	5	6	7
Sannsynlighet for nedetid for kasserere p 0	0,025	0,057	0,065	0,067	0,067
Gjennomsnittlig antall kunder i køen T veldig.	5,44	0,60	0,15	0,03	0,01
Relativ verdi av kostnader C rel.	18,54	4,77	4,14	4,53	5,22

Gjennomsnittlig antall kasserere involvert i å betjene kunder, ifølge (49) k = 2,7.
Koeffisient (andel) av kasserere ansatt i service
= ρ/n = 2,7/3 = 0,9.
Absolutt gjennomstrømning av beregningsnoden A = 1,35 (1/min), eller 81 (1/t), dvs. 81 kunder i timen.
Analyse av tjenestekarakteristikker indikerer en betydelig overbelastning av betalingssenteret i nærvær av tre kasserere.
b. Relativ kostnadsverdi for n = 3
C rel. = = 3/1,35+3∙5,44 = 18,54.
La oss beregne den relative verdien av kostnadene for andre verdier P(Tabell 1).
Som det fremgår av tabellen. 2 oppnås minimumskostnadene ved n = n opt. = 5 kontroller-kasserere.
La oss bestemme tjenestekarakteristikkene til beregningsnoden for n = n opt. =5. Vi får P veldig bra. = 0,091; L veldig = 0,198; T og. = 0,146 (min); L syst. = 2,90; T snst. = 2,15 (min); k = 2,7; k3 = 0,54.
Som vi kan se, med n = 5 sammenlignet med n = 3, sank sannsynligheten for forekomst av en kø P veldig betydelig. , kølengde L veldig og gjennomsnittlig tid brukt i kø T veldig. og følgelig gjennomsnittlig antall kjøpere L system. og gjennomsnittlig tid brukt i betalingsnoden T-systemet, samt andelen kontrollører som er engasjert i å betjene k 3. Men gjennomsnittlig antall kassekontrollører som er engasjert i å betjene k og den absolutte gjennomstrømningen til betalingsnoden A endret seg naturligvis ikke.
V. Sannsynligheten for at det ikke er mer enn 3 kunder i køen er gitt av
= 1- P veldig bra + p 5+1 + p 5+2 + p 5+3 , hvor hvert ledd er funnet ved hjelp av formler (45) – (48). Vi får for n=5:

Legg merke til at når det gjelder n=3 kasserere, er den samme sannsynligheten betydelig lavere: P(r ≤ 3) =0,464.

1. Indikatorer for effektiviteten av å bruke QS:

Den absolutte kapasiteten til QS er det gjennomsnittlige antallet forespørsler som kan være

kan betjene QS per tidsenhet.

Relativ kapasitet til QS - forholdet mellom gjennomsnittlig antall forespørsler,

antall tjenesteleverandører som betjenes per tidsenhet, til gjennomsnittlig antall ankomster for samme

søknadstid.

Gjennomsnittlig varighet av ansettelsesperioden til CMO.

QS-utnyttelsesgrad er den gjennomsnittlige andelen av tiden

CMO er opptatt med å betjene forespørsler osv.

2. Kvalitetsindikatorer for serviceapplikasjoner:

Gjennomsnittlig ventetid på søknad i køen.

Gjennomsnittlig tid en søknad forblir i CMO.

Sannsynligheten for at en forespørsel blir nektet tjeneste uten å vente.

Sannsynligheten for at en nylig mottatt søknad umiddelbart vil bli akseptert for tjeneste.

Lov om fordeling av ventetid på søknad i kø.

Loven om fordeling av tiden en søknad forblir i QS.

Gjennomsnittlig antall søknader i køen.

Gjennomsnittlig antall søknader i CMO mv.

3. Indikatorer for effektiviteten av funksjonen til "SMO - klient"-paret, der "klient" forstås som hele settet med forespørsler eller en viss kilde til dem. Slike indikatorer inkluderer for eksempel gjennomsnittlig inntekt generert av CMO per tidsenhet

Klassifisering av køsystemer

Etter antall QS-kanaler:

enkeltkanal(når det er én tjenestekanal)

multikanal, mer presist n-kanal (når antall kanaler n≥ 2).

Etter tjenestedisiplin:

1. SMO med feil, der søknaden mottatt ved inngangen til QS i det øyeblikket da alle

kanalene er opptatt, mottar et "avslag" og forlater QS ("forsvinner"). Slik at denne applikasjonen er fortsatt

er betjent, må den igjen inn i QS-inngangen og betraktes som en søknad mottatt for første gang. Et eksempel på en QS med avslag er driften av en automatisk telefonsentral: hvis det oppringte telefonnummeret (en søknad mottatt ved inngangen) er opptatt, mottar søknaden et avslag, og for å nå dette nummeret må det være ringte igjen.

2. SMO med forventning(ubegrenset venting eller kø). I slike systemer

en forespørsel som kommer når alle kanaler er opptatt, står i kø og venter på at kanalen blir tilgjengelig og godtar den for service. Hver søknad som mottas ved inngangen vil etter hvert bli behandlet. Slike selvbetjeningssystemer finnes ofte i handel, innen forbruker- og medisinske tjenester, og i bedrifter (for eksempel service av maskiner av et team av justeringsarbeidere).

3. SMO blandet type(med begrenset forventning). Dette er systemer der det er pålagt noen begrensninger for applikasjonens opphold i køen.

Disse begrensningene kan gjelde for kølengde, dvs. maksimalt mulig

antall søknader som kan stå i køen samtidig. Et eksempel på et slikt system er et bilverksted som har en begrenset parkeringsplass for defekte biler som venter på reparasjon.

Ventebegrensninger kan bekymre tiden applikasjonen tilbrakte i køen, ifølge historien

på hvilket tidspunkt den går ut av køen og forlater systemet).

I QS med venting og i QS av blandet type benyttes ulike kommunikasjonsskjemaer.

serviceforespørsler fra køen. Service kan være bestilt, når forespørsler fra køen betjenes i den rekkefølgen de kommer inn i systemet, og uordnet, der applikasjoner fra køen betjenes i tilfeldig rekkefølge. Noen ganger brukt prioritert tjeneste, når noen forespørsler fra køen anses som prioritert og derfor serveres først.

Slik begrenser du strømmen av søknader:

lukket Og åpen.

Hvis strømmen av applikasjoner er begrenset og applikasjoner som har forlatt systemet kan returneres til det,

xia, så er QS lukket, ellers - åpen.

Etter antall servicestadier:

enkel fase Og flerfase

Hvis QS-kanalene er homogene, dvs. utføre samme vedlikeholdsoperasjon

nei, så kalles slike QS enkel fase. Hvis tjenestekanaler er lokalisert sekvensielt og de er heterogene, siden de utfører forskjellige tjenesteoperasjoner (dvs. tjenesten består av flere påfølgende stadier eller faser), kalles QS-en flerfase. Et eksempel på driften av en flerfase QS er bilservice på en bensinstasjon (vasking, diagnostisering osv.).