Markovs tilfeldige prosess med diskrete tilstander og kontinuerlig tid som ble vurdert i forrige forelesning foregår i køsystemer (QS).

Køsystemer - dette er systemer der tjenesteforespørsler kommer til tilfeldige tider, og de mottatte forespørslene blir betjent ved hjelp av tjenestekanalene som er tilgjengelige for systemet.

Eksempler på køsystemer er:

• avregnings- og kontantnoder i banker, i bedrifter;
• personlige datamaskiner som serverer innkommende applikasjoner eller krav for å løse visse problemer;
• bilstasjoner; Bensinstasjon;
• revisjonsselskaper;
• avdelinger for skatteinspeksjoner som er engasjert i aksept og verifisering av gjeldende rapportering av virksomheter;
• telefonsentraler osv.

La oss vurdere arbeidsplanen til QS (figur 1). Systemet består av en forespørselsgenerator, en avsender og en serviceenhet, en feilregnskapsenhet (terminator, ordensdestruer). Generelt kan en tjenesteknute ha flere tjenestekanaler.

Figur: 1

1. Søknadsgenerator - et objekt som genererer applikasjoner: en gate, et verksted med installerte enheter. Inngangen mottar strøm av applikasjoner (strømmen av kunder til butikken, strømmen av ødelagte enheter (maskiner, maskinverktøy) for reparasjoner, strømmen av besøkende til garderoben, strømmen 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 tilgjengelig;
• avviser søknader (av forskjellige grunner);
• mottar informasjon fra tjenesteknuten om gratis kanaler;
• overvåker systemets oppetid.

1. Kø - akkumulator av applikasjoner. Det kan være ingen kø.
2. Tjenesteknute består av et begrenset antall tjenestekanaler. Hver kanal har tre tilstander: ledig, opptatt, fungerer ikke. Hvis alle kanaler er opptatt, kan du komme med en strategi som du vil overføre forespørselen til.
3. Avskjed fra tjenesten oppstår hvis alle kanaler er opptatt (noen av dem fungerer kanskje ikke).

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

terminator - ødeleggeren av transaksjoner;

lager - akkumulering av ressurser og ferdige produkter;

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

leder - ressurssjef;

CMO-klassifisering

Første divisjon (ved tilstedeværelse av køer):

• CMO med feil
• CMO med kø.

PÅ CMO med avslag en forespørsel som ankommer på et tidspunkt hvor alle kanaler er opptatt mottar et avslag, forlater QS og blir ikke betjent i fremtiden.

PÅ CMO med kø en forespørsel som ankommer i det øyeblikket alle kanaler er opptatt, går ikke, men går inn i køen og venter på at muligheten skal bli servert.

CMO med køer er delt inn i forskjellige typer, avhengig av hvordan køen er organisert - begrenset eller ikke begrenset... Begrensninger kan være relatert til både kølengde og ventetid, "servicedisiplin".

Så, for eksempel, blir følgende QSer vurdert:

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

Købegrensningstyper kan kombineres.

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

Naturligvis vil strømmen av applikasjoner som genereres av selve systemet, avhenge av systemet og dets tilstand.

I tillegg er CMO-er delt inn i åpenCMO og lukket CMO.

I en åpen QS avhenger ikke egenskapene til applikasjonsflyten av tilstanden til selve QS (hvor mange kanaler som er opptatt). I en lukket QS er de avhengige. For eksempel, hvis en arbeider betjener en gruppe maskiner som noen ganger krever justering, avhenger intensiteten av strømmen av "krav" fra maskinene av hvor mange av dem som allerede fungerer som de skal og venter på justering.

Et eksempel på et lukket system: utbetaling av lønn fra en kasser i et foretak.

Etter antall kanaler er CMO delt inn i:

• enkeltkanal;
• flerkanals.

Kø-systemegenskaper

Hovedegenskapene til et køsystem av noe slag er:

• inngangsstrømmen av innkommende forespørsler eller tjenesteforespørsler;
• kødisiplin;
• servicemekanisme.

Krav til inngangsstrøm

For å beskrive inngangsstrømmen, må du stille en sannsynlov som bestemmer rekkefølgen av tidspunkter når tjenesteforespørsler kommer, og angi antall slike krav i hver vanlig kvittering. I dette tilfellet opererer de som regel med begrepet “sannsynlig fordeling av øyeblikkene for mottak av krav”. Her kan de gjøre som enkelt- og gruppekrav (antall slike krav i hver vanlig opptak). I sistnevnte tilfelle snakker vi vanligvis om et servicesystem med parallell gruppetjeneste.

En i- ankomsttid mellom kravene - uavhengige identisk fordelte tilfeldige variabler;

E (A) - gjennomsnittlig (MO) opptakstid;

λ \u003d 1 / E (A) - intensiteten til mottak av forespørsler;

Input stream egenskaper:

1. En sannsynlighetslov som bestemmer rekkefølgen av tidspunkter når tjenesteforespørsler kommer.
2. Antall forespørsler i hver påfølgende ankomst for gruppestrømmer.

Kødisiplin

Kø - et sett med krav som venter på service.

Køen har et navn.

Kødisiplin definerer prinsippet ifølge hvilket forespørslene som kommer til inngangen til serveringssystemet er koblet fra køen til serviceprosedyren. De mest brukte køfagene er definert av følgende regler:

• førstemann til mølla;

først inn først ut (FIFO)

den vanligste typen kø.

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

Listen har en begynnelse og en slutt. Listen består av oppføringer. En post er en celle i en liste. Forespørselen kommer på slutten av listen, og velges for tjeneste fra begynnelsen av listen. Posten består av en beskrivelse av søknaden og en lenke (en indikator på hvem som står bak) I tillegg, hvis køen har en tidsavbruddsgrense, må også tidsavgrensningen spesifiseres.

Som programmerere skal du kunne lage tosidige, ensidige lister.

Liste handlinger:

• sett inn i halen;
• ta fra begynnelsen;
• fjern fra listen etter tidsavbrudd.
• kom sist - servert førstLIFO (klips for kassetter, blindvei på jernbanestasjonen, gikk inn i en pakket vogn).

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

• tilfeldig utvalg av applikasjoner;
• valg av søknader etter prioritetskriterium.

Hver forespørsel er blant annet preget av prioritetsnivå og plasseres ikke ved halen i køen, men på slutten av prioritetsgruppen. Senderen sorterer etter prioritet.

Køegenskaper

• begrensningventetid øyeblikket av tjenestetilgang (det er en kø med en begrenset ventetid på tjenesten, som er forbundet med begrepet "tillatt kølengde");
• kø lengde.

Servicemekanisme

Servicemekanisme bestemmes av egenskapene til selve serviceprosedyren og strukturen til servicesystemet. Kjennetegnene ved vedlikeholdsprosedyren inkluderer:

• antall tjenestekanaler ( N);
• varigheten av serviceprosedyren (sannsynlig fordeling av servicetiden for krav);
• antall krav oppfylt som et resultat av hver slik prosedyre (for gruppesøknader);
• sannsynligheten for svikt i serveringskanalen;
• strukturen til servicesystemet.

For en analytisk beskrivelse av egenskapene til serviceprosedyren, brukes begrepet "sannsynlig fordeling av servicetiden til kunder".

S i - tjenestetid jegth krav;

E (S) - gjennomsnittlig servicetid

μ \u003d 1 / E (S)- hastigheten på serviceforespørsler.

Det skal bemerkes at tjenestetiden til en forespørsel avhenger av selve forespørselens art eller klientens krav og av tilstanden og funksjonene til serveringssystemet. I noen tilfeller må man også ta hensyn til sannsynlighet for feil på tjenestekanal etter et bestemt begrenset tidsintervall. Denne karakteristikken kan modelleres som en strøm av feil som kommer inn i QS og har prioritet over alle andre applikasjoner.

Utnyttelsesgrad for CMO

N· Μ er tjenesteprisen i systemet når alle tjenesteenhetene er opptatt.

ρ=λ/( Nμ) kalles koeffisient for bruk av systemet , viser hvor mye systemressursene er involvert.

Tjenestesystemstruktur

Strukturen til servicesystemet bestemmes av antall og gjensidig ordning av tjenestekanaler (mekanismer, enheter osv.). Først og fremst bør det understrekes at et servicesystem ikke kan ha en tjenestekanal, men flere; et system av denne typen er i stand til å betjene flere krav samtidig. I dette tilfellet tilbyr alle tjenestekanaler de samme tjenestene, og det kan derfor argumenteres for at det er parallell tjeneste .

Eksempel. Kassedisker i butikken.

Tjenestesystemet kan bestå av flere forskjellige typer tjenestekanaler som hvert tjenestekrav må passere gjennom, dvs. i tjenestesystemet kundeserviceprosedyrer implementeres sekvensielt ... Servicemekanismen definerer egenskapene til den utgående (servert) strømmen av forespørsler.

Eksempel. Medisinsk kommisjon.

Kombinert service - betjening av innskudd i sparebanken: først kontrolleren, deretter kassereren. Som regel er det to kontrollere for en kasserer.

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

• sannsynlig fordeling av tidspunktene for mottak av tjenesteforespørsler (enkelt eller gruppe);
• kraften til kilden til krav;
• sannsynlig fordeling av tjenestens varighet;
• konfigurasjonen av servicesystemet (parallell, seriell eller parallell seriell tjeneste);
• antall og ytelse av serveringskanaler;
• køens disiplin.

Hovedkriteriene for effektiviteten av QSs funksjon

Som hovedkriterier for effektiviteten til å fungere i køsystemer avhengig av arten av problemet som løses, kan det være:

• sannsynligheten for øyeblikkelig forkynnelse av den mottatte forespørselen (P obsl \u003d K obs / K post);
• sannsynligheten for å nekte å motta den mottatte forespørselen (P åpen \u003d K åpen / K-post);

Åpenbart er P obsl + P åpen \u003d 1.

Strømmer, forsinkelser, vedlikehold. Pollachek-Khinchin-formel

Forsinkelse - et av kriteriene for å betjene QS, den tiden applikasjonen venter på service.

D i - forsinkelse i forespørselskøen jeg;

W i \u003d D i + S i- tid brukt i systemet med kravet jeg.

(med sannsynlighet 1) er steady-state gjennomsnittsforsinkelse for en forespørsel i køen;

(med sannsynlighet 1) - steady-state gjennomsnittlig tid brukt av forespørselen i CMO (venter).

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

L (t)– antall forespørsler i systemet om gangen t(Q (t) pluss antall forespørsler som er i bruk om gangen t.

Så indikatorene (hvis de eksisterer)

(med sannsynlighet 1) - steady-state tidsgjennomsnittlig antall forespørsler i køen;

(med sannsynlighet 1) er det gjennomsnittlige antall forespørsler i systemet i steady-state.

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

Husker at ρ \u003d λ / ( Nμ), så blir det sett at hvis intensiteten av ankomsten av forespørsler er større enn Nμ, deretter ρ\u003e 1, og det er naturlig at systemet ikke vil takle en slik strøm av forespørsler, og derfor kan vi ikke snakke om verdiene d, w, Qog L.

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

Det skal bemerkes at kriteriene ovenfor for å evaluere ytelsen til systemet kan beregnes analytisk for køsystemer M / M / N(N\u003e 1), dvs. systemer med Markov-strømmer av krav og tjenester. Til M / G /l for enhver distribusjon G og for noen andre systemer. Generelt må fordelingen av tid mellom ankomster, fordelingen av tjenestetid eller begge disse mengdene være eksponentiell (eller en slags eksponentiell k-ordre Erlang-distribusjon) for at en analytisk løsning skal være mulig.

I tillegg kan du også snakke om slike egenskaper som:

• absolutt gjennomstrømning av systemet - A \u003d P obsl * λ;
• relativ systemgjennomstrømning -

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

.

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

Så hvis E (S) er viktigere, så er 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 gjennomsnittlig tjenestetid forblir den samme. Intuitivt kan dette forklares som følger: variansen til den tilfeldige variabelen for tjenestetiden kan få en stor verdi (siden den må være positiv), dvs. den eneste serviceenheten vil være opptatt i lang tid, noe som vil føre til en økning i køen.

Temaet for køteori er etablering av et forhold mellom faktorene som bestemmer funksjonaliteten til køsystemet, og effektiviteten av dets funksjon. I de fleste tilfeller er alle parametere som beskriver køsystemer tilfeldige variabler eller funksjoner, derfor blir disse systemene referert til som stokastiske systemer.

Den tilfeldige karakteren av strømmen av krav (krav), så vel som generelt sett varigheten av tjenesten fører til at det skjer en tilfeldig prosess i køsystemet. Av karakteren til den tilfeldige prosessen forekommer i køsystemet (QS), skille markov og ikke-Markov-systemer ... I Markov-systemer er den innkommende strømmen av forespørsler og den utgående strømmen av betjente forespørsler (krav) Poisson. Poisson-strømmer gjør det enkelt å beskrive og bygge en matematisk modell av et køsystem. Disse modellene har ganske enkle løsninger; derfor bruker de fleste av de kjente anvendelsene av køteori Markov-ordningen. Når det gjelder ikke-Markov-prosesser, blir problemene med å studere køsystemer mye mer kompliserte og krever bruk av statistisk modellering, numeriske metoder ved bruk av datamaskiner.

4. MASSETJENESTE TEORI

4.1. Klassifisering av køsystemer og ytelsesindikatorer

Systemer der tjenestekrav oppstår på tilfeldige tider og det er enheter for å betjene disse påstandene, kalles køsystemer (CMO).

CMO-er kan klassifiseres av serviceorganisasjonen som følger:

Mislykkede systemer har ingen køer.

Ventesystemer har køer.

Forespørsel mottatt når alle tjenestekanaler er opptatt:

Etterlater systemet med feil;

Går inn i køen for service i systemer med ventetid med ubegrenset kø eller ledig plass med begrenset kø;

La systemet vente i en begrenset kø hvis det ikke er ledig plass i den køen.

Mengden tapt tid betraktes som et mål på effektiviteten av den økonomiske QS:

Vente i kø;

Nedetid for tjenestekanaler.

For alle typer QS brukes følgende ytelsesindikatorer :

- relativ båndbredde - dette er den gjennomsnittlige andelen av innkommende applikasjoner som serveres av systemet;

- absolutt gjennomstrømning - dette er gjennomsnittlig antall forespørsler som serveres av systemet per tidsenhet;

- sannsynlighet for svikt - det er sannsynligheten for at forespørselen etterlater systemet uten service;

- gjennomsnittlig antall travle kanaler - for flerkanals QS.

Indikatorene for CMOs effektivitet beregnes ved hjelp av formler fra spesielle referansebøker (tabeller). De første dataene for slike beregninger er resultatene av QS-modellering.

4.2. Modellering av køsystem:

grunnleggende parametere, tilstandsgraf

Med alle de forskjellige CMO-ene har de det vanlige trekk som tillater å forene deres modellering for å finne de mest effektive alternativene for å organisere slike systemer .

For å simulere QS, må du ha følgende innledende data:

Hovedinnstillinger;

Statlig graf.

Resultatene av QS-modellering er sannsynlighetene for dets tilstander, der alle indikatorer for effektiviteten uttrykkes.

Hovedparametrene for modellering av QS inkluderer:

Kjennetegn ved innkommende strøm av tjenesteforespørsler;

Servicemekanismeegenskaper.

Ta i betraktning x flytegenskaper .

Søknadsflyt - rekkefølgen av forespørsler som kommer inn for service.

Intensiteten i applikasjonsflyten - gjennomsnittlig antall søknader mottatt av QS per tidsenhet.

Strømmer av applikasjoner er enkle og forskjellige fra de enkleste.

For de enkleste strømningene av applikasjoner brukes QS-modeller.

Det enkleste , eller poisson kalt en strøm som er stasjonær, enkelt og i den ingen ettervirkninger.

Stationaritet betyr uforanderligheten av intensiteten til mottak av søknader over tid.

Enkelt flyten av forespørsler er i tilfelle når sannsynligheten for ankomst av mer enn en forespørsel er nær null på kort tid.

Ingen ettereffekt ligger i det faktum at antall søknader mottatt av QS i ett tidsintervall ikke påvirker antall søknader som mottas i et annet tidsintervall.

Simuleringsmodeller brukes til andre bestillinger enn de enkleste.

Ta i betraktning tjenestemekanismens egenskaper .

Servicemekanismen er preget av:

- nummer tjenestekanaler ;

Kanalytelse, eller serviceintensitet - det gjennomsnittlige antall krav som betjenes av en kanal per tidsenhet;

Køens disiplin (for eksempel køvolum , rekkefølgen på valget fra køen til servicemekanismen osv.).

Statlig graf beskriver tjenestesystemets funksjon som overganger fra en stat til en annen under påvirkning av strømmen av krav og deres service.

For å bygge en graf med tilstander for QS, må du:

Lag en liste over alle mulige tilstander i QS;

Presentere de oppførte tilstandene grafisk og vise mulige overganger mellom dem med piler;

Vei de viste pilene, det vil si tildele dem de numeriske verdiene til overgangsintensitetene bestemt av intensiteten i strømmen av krav og intensiteten i tjenesten.

4.3. Beregner sannsynlighetene for stater

køsystemer

Angi graf for QS med ordning for død og fødsel er en lineær kjede, der hver av middelstatene har direkte og tilbakemeldingsforbindelse med hver av nabolandene, og de ekstreme tilstandene med bare en nabo:

Antall stater i grafen med en mer enn det totale antallet tjenestekanaler og plasser i køen.

QS kan være i en hvilken som helst av sine mulige tilstander, derfor er den forventede utgangshastigheten fra en hvilken som helst tilstand lik den forventede inngangshastigheten til systemet i denne tilstanden. Derfor vil ligningssystemet for å bestemme sannsynligheten for tilstander for de enkleste flytene ha formen:

hvor er sannsynligheten for at systemet er i staten

- intensiteten til overgangen, eller gjennomsnittlig antall systemoverganger per tidsenhet fra stat til stat.

Ved hjelp av dette ligningssystemet, samt ligningen

sannsynligheten for en hvilken som helst stat kan beregnes ut fra følgende generell regel :

sannsynligheten for en nulltilstand beregnes som

og deretter tas en brøkdel, i telleren der det er produktet av alle intensitetene i strømningene langs pilene som fører fra venstre mot høyre fra staten til staten, og i nevneren er produktet av alle intensitetene langs pilene som går fra høyre til venstre fra staten til staten, og denne brøk multipliseres med den beregnede sannsynligheten

Konklusjoner om fjerde avsnitt

Køsystemer har en eller flere servicekanaler og kan ha en begrenset eller ubegrenset kø (systemer med ventetid) for tjenesteforespørsler, ikke ha kø (systemer med feil). Tjenesteforespørsler skjer tilfeldig. Køsystemer er preget av følgende ytelsesindikatorer: relativ gjennomstrømning, absolutt gjennomstrømning, feilsannsynlighet, gjennomsnittlig antall opptatt kanaler.

Modellering av køsystemer utføres for å finne de mest effektive alternativene for deres organisasjon og forutsetter følgende innledende data for dette: grunnleggende parametere, tilstandsgraf. Slike data inkluderer følgende: strømningshastigheten til applikasjoner, antall tjenestekanaler, tjenestetakten og køstørrelsen. Antall tilstander i grafen er en mer enn summen av antall servicekanaler og steder i køen.

Beregningen av sannsynlighetene for statene i køsystemet med ordningen "død og fødsel" utføres i henhold til hovedregelen.

Selvtest spørsmål

Hvilke systemer kalles køsystemer?

Hvordan klassifiseres køsystemer i henhold til organisasjonen?

Hvilke køsystemer kalles feilsystemer og hvilke kalles ventesystemer?

Hva skjer med et krav som kommer på et tidspunkt da alle tjenestekanalene er opptatt?

Hva blir sett på som et mål på effektiviteten til det økonomiske køsystemet?

Hva er ytelsesindikatorene for køsystemet?

Hva er de første dataene for beregning av ytelsesindikatorene til køsystemer?

Hvilke innledende data trengs for å modellere køsystemer?

Gjennom hvilke resultater av modellering av køsystemet uttrykker alle indikatorene for effektiviteten?

Hva er de viktigste parametrene for modellering av køsystemer?

Hvordan kjennetegnes tjenesteforespørselsflyter?

Hvordan karakteriseres tjenestemekanismer?

Hva tilstandsgrafen til et køsystem beskriver

Hva er nødvendig for å bygge en tilstandsgraf for et køsystem?

Hva er tilstandsgrafen til et køsystem med en "død og fødsel" -ordning?

Hva er antall tilstander i køsystemets tilstandsgraf?

Hva er formen på ligningssystemet for å bestemme sannsynligheten for tilstandene til køsystemet?

Hva er den generelle regelen for å beregne sannsynligheten for en hvilken som helst tilstand i køsystemet?

Eksempler på problemløsning

1. Bygg et tilstandsgraf over køsystemet og gi hovedavhengighetene til ytelsesindikatorene.

og) n-kanal QS med feil (Erlang-problem)

Hovedinnstillinger:

Kanaler,

Flytintensitet,

Serviceintensitet.

Mulige systemtilstander:

Alle kanaler er opptatt (forespørsler i systemet).

Tilstandsgraf:

Relativ båndbredde,

Sannsynlighet for svikt,

Gjennomsnittlig antall travle kanaler.

b) n-kanal QS med m-begrenset kø

Mulige systemtilstander:

Alle kanaler er gratis (null ordrer i systemet);

En kanal er opptatt, resten er gratis (en forespørsel i systemet);

To kanaler er opptatt, resten er gratis (to kunder i systemet);

...................................................................................

Alle kanaler er opptatt, to applikasjoner står i køen;

Alle kanaler er opptatt, applikasjoner står i køen.

Tilstandsgraf:

c) Enkanals QS med ubegrenset kø

Mulige systemtilstander:

Alle kanaler er gratis (null ordrer i systemet);

Kanalen er opptatt, null forespørsler i køen;

Kanalen er opptatt, en forespørsel står i køen;

...................................................................................

Kanalen er opptatt, applikasjonen står i køen;

....................................................................................

Tilstandsgraf:

Systemeffektivitetsindikatorer:

,

Gjennomsnittlig tid brukt av en forespørsel i systemet ,

,

,

Absolutt båndbredde,

Relativ båndbredde.

d) n-kanal QS med ubegrenset kø

Mulige systemtilstander:

Alle kanaler er gratis (null ordrer i systemet);

En kanal er opptatt, resten er gratis (en forespørsel i systemet);

To kanaler er opptatt, resten er gratis (to kunder i systemet);

...................................................................................

Alle kanaler er opptatt (forespørsler i systemet), null forespørsler i køen;

Alle kanaler er opptatt, en forespørsel står i køen;

....................................................................................

Alle kanaler er opptatt, applikasjoner står i køen;

....................................................................................

Tilstandsgraf:

Systemeffektivitetsindikatorer:

Gjennomsnittlig antall opptatt kanaler,

Gjennomsnittlig antall forespørsler i systemet ,

Gjennomsnittlig antall søknader i køen ,

Gjennomsnittlig tid brukt av et program i køen .

2. Datasenteret har tre datamaskiner. Senteret får i gjennomsnitt fire oppgaver i timen å løse. Gjennomsnittstiden for å løse ett problem er en halv time. Datasenteret aksepterer og stiller i kø opptil tre oppgaver som skal løses. Det er nødvendig å vurdere effektiviteten til senteret.

BESLUTNING. Fra tilstanden er det klart at vi har en flerkanals QS med begrenset kø:

Antall kanaler;

Intensitet i flyten av forespørsler (oppgave / time);

Servicetid for en forespørsel (time / oppgave), serviceintensitet (oppgave / time);

Kølengde.

Liste over mulige tilstander:

Ingen applikasjoner, alle kanaler er gratis;

En kanal er opptatt, to er gratis;

To kanaler er opptatt, den ene er gratis;

Tre kanaler er opptatt;

Tre kanaler er opptatt, en forespørsel står i køen;

Tre kanaler er opptatt, to applikasjoner står i køen;

Tre kanaler er opptatt, tre applikasjoner står i køen.

Statlig graf:

La oss beregne sannsynligheten for staten:

Ytelsesindikatorer:

Sannsynlighet for feil (alle tre datamaskiner er opptatt og tre applikasjoner står i køen)

Relativ båndbredde

Absolutt båndbredde

Gjennomsnittlig antall sysselsatte datamaskiner

3. (Problemet med bruk av QS med feil.) Det er tre veiledere i avdelingens kvalitetskontrollavdeling. Hvis en del kommer til kvalitetskontrollavdelingen, når alle inspektører er opptatt med å betjene tidligere mottatte deler, blir den ukontrollert. Gjennomsnittlig antall deler som leveres til kvalitetskontrollavdelingen per time er 24, gjennomsnittlig tid som en inspektør bruker på å utføre service på en del er 5 minutter. Bestem sannsynligheten for at delen vil passere kvalitetskontrollavdelingen uten tilsyn, hvor opptatt inspektørene er og hvor mange som må leveres for å (* - den angitte verdien).

BESLUTNING. Av tilstandens tilstand, da.

1) Sannsynlighet for nedetid for tjenestekanaler:

,

3) Tjenestesannsynlighet:

4) Gjennomsnittlig antall opptatt kanaler:

.

5) Andelen kanaler okkupert av tjenesten:

6) Absolutt båndbredde:

Når. Å gjøre lignende beregninger for, får vi

Siden, etter å ha gjort beregninger for, får vi

SVAR. Sannsynligheten for at en del vil passere QC-avdelingen uten tilsyn er 21%, og inspektørene vil være opptatt med å betjene med 53%.

For å sikre en tjenestesannsynlighet på mer enn 95%, kreves minst fem veiledere.

4. (Problemet med å bruke QS med ubegrenset ventetid.) Sparebanken har tre kasserere () for å betjene innskytere. Strømmen av innskytere kommer inn i sparebanken med en hastighet på person / time. Gjennomsnittlig varighet for betjening av en innskyter av kontroller-kassereren min

Bestem egenskapene til sparebanken som et objekt for CMO.

BESLUTNING. Servicestrømintensitet, lastintensitet.

1) Sannsynligheten for nedetid for kontrollere-kasserere i løpet av arbeidsdagen (se forrige oppgave nr. 3):

.

2) Sannsynligheten for å finne alle kasserekontrollere opptatt:

.

3) Køsannsynlighet:

.

4) Gjennomsnittlig antall søknader i køen:

.

5) Gjennomsnittlig ventetid for en forespørsel i køen:

min.

6) Gjennomsnittlig tid brukt av en applikasjon i CMO:

7) Gjennomsnittlig antall gratis kanaler:

.

8) Beleggningsgrad for servicekanaler:

.

9) Gjennomsnittlig antall besøkende i sparebanken:

SVAR. Sannsynligheten for nedetid for kasserere er 21% av arbeidstiden, sannsynligheten for at en besøkende er i køen er 11,8%, gjennomsnittlig antall besøkende i køen er 0,236 personer, den gjennomsnittlige ventetiden for besøkende til service er 0,472 minutter.

5. (Problem med bruk av QS med venting og med en begrenset kølengde.) Butikken mottar tidlige grønnsaker fra forstads drivhus. Lastede biler ankommer til forskjellige tider med intensiteten av bilene per dag. Bryterom og utstyr for tilberedning av grønnsaker til salgs lar deg behandle og oppbevare varer medført av to biler (). Butikken har tre pakker (), som hver i gjennomsnitt kan behandle varer fra en maskin innen en time. Varigheten av arbeidsdagen for skiftarbeid er 12 timer.

Bestem hva kapasiteten til vaskeromene skal være for at sannsynligheten for fullstendig behandling av varer skal være.

BESLUTNING. La oss definere belastningsintensiteten til pakkerne:

Auto / dag

1) Finn sannsynligheten for nedetid for pakker i fravær av maskiner (ordrer):

og 0! \u003d 1.0.

2) Sannsynlighet for tjenestenekt:

.

3) Tjenestesannsynlighet:

Fordi , vi vil gjøre lignende beregninger for, vi får), mens sannsynligheten for fullstendig behandling av varene vil være.

Selvstudieoppgaver

For hver av følgende situasjoner, bestem deg:

a) hvilken klasse objektet til CMO tilhører;

b) antall kanaler;

c) kølengde;

d) intensiteten av strømmen av applikasjoner;

e) tjenestetakst for én kanal;

f) antall alle tilstander til QS-objektet.

I svarene angir du verdiene for hvert element ved hjelp av følgende forkortelser og dimensjoner:

a) TOE - enkeltkanal med feil; MO - flerkanals med feil; ОЖО - enkeltkanal med begrenset kø ventetid; ОЖН - enkeltkanal med ventetid med ubegrenset kø; МЖО - flerkanals med ventetid med begrenset kø; МЖН - flerkanals med ventetid med ubegrenset kø;

b) =… (enheter);

c) =… (enheter);

d) \u003d xxx / xxx(enheter / min);

e) \u003d xxx / xxx(enheter / min);

f) (enheter).

1. Vakthavende ved byadministrasjonen har fem telefoner. Telefonsamtaler mottas med en intensitet på 90 forespørsler per time, og den gjennomsnittlige varigheten er 2 minutter.

2. Det er 3 steder på parkeringsplassen i nærheten av butikken, som hver er reservert for en bil. Biler ankommer parkeringsplassen med en intensitet på 20 biler i timen. Varigheten av oppholdet til biler på parkeringsplassen er i gjennomsnitt 15 minutter. Parkering på kjørebanen er ikke tillatt.

3. ATS fra virksomheten gir ikke mer enn 5 forhandlinger samtidig. Gjennomsnittlig varighet av samtalen er 1 minutt. Stasjonen mottar i gjennomsnitt 10 samtaler per sekund.

4. Lastelvahavnen mottar i gjennomsnitt 6 tørrlastskip per dag. Det er 3 kraner i havnen, som hver i gjennomsnitt betjener 1 tørrlastskip i 8 timer. Kranene opererer døgnet rundt. Tørlasteskip som venter på service er ved veikanten.

5. I ambulansetjenesten i landsbyen er det 3 utsendere på vakt døgnet rundt og betjener 3 telefoner. Hvis en forespørsel om å ringe en lege mottas av en pasient når avsenderne er opptatt, avvises abonnenten. Flyten av forespørsler er 4 samtaler per minutt. Registrering av en søknad tar i gjennomsnitt 1,5 minutter.

6. Frisørsalongen har 4 mestere. Den innkommende flyten av besøkende har en intensitet på 5 personer per time. Gjennomsnittlig servicetid for en klient er 40 minutter. Lengden på tjenestekøen anses som ubegrenset.

7. Bensinstasjonen har to dispensere for utlevering av bensin. I nærheten av stasjonen er det en plattform for to biler for å vente på drivstoff. I gjennomsnitt ankommer en bil til stasjonen på 3 minutter. Gjennomsnittlig servicetid for en maskin er 2 minutter.

8. På stasjonen i verkstedet for forbrukertjenester er det tre formenn. Hvis en klient kommer inn på et verksted når alle håndverkere er opptatt, forlater han verkstedet uten å vente på service. Gjennomsnittlig antall klienter som kontakter et verksted på 1 time er 20. Gjennomsnittlig tid det tar for en workshop å betjene en klient er 6 minutter.

9. ATS i landsbyen gir ikke mer enn 5 forhandlinger om gangen. Gjennomsnittlig forhandlingstid er ca 3 minutter. Samtaler til stasjonen ankommer i gjennomsnitt på 2 minutter.

10. Det er 3 dispensere på en bensinstasjon (bensinstasjon). Området på stasjonen, der bilene venter på å fylle drivstoff, har ikke plass til mer enn en bil, og hvis den er opptatt, vil ikke neste bil som ankommer stasjonen stå i kø, men kjører til neste stasjon. I gjennomsnitt ankommer biler stasjonen hvert 2. minutt. Prosessen med å fylle drivstoff på en bil tar i gjennomsnitt 2,5 minutter.

11. I en liten butikk betjenes kundene av to selgere. Gjennomsnittlig servicetid for en kunde er 4 minutter. Intensiteten i strømmen av kjøpere er 3 personer per minutt. Butikkens kapasitet er slik at ikke mer enn 5 personer kan stå i kø samtidig. En shopper som går inn i en overfylt butikk når det allerede er 5 personer i køen, venter ikke utenfor og drar.

12. Jernbanestasjonen i dacha-landsbyen betjenes av et billettkontor med to vinduer. I helgene, når befolkningen aktivt bruker jernbanen, er passasjerstrømningshastigheten 0,9 person / min. Kassereren bruker i gjennomsnitt 2 minutter på å betjene passasjeren.

For hvert av QS-alternativene som er angitt i alternativene, er strømningshastigheten på forespørsler lik tjenestens hastighet av en kanal. Påkrevd:

Lag en liste over mulige tilstander;

Konstruer en tilstandsgraf i henhold til "død og reproduksjon" -skjemaet.

I svaret angir du for hver oppgave:

Antall systemtilstander;

Intensiteten i overgangen fra den siste staten til den nest siste.

Alternativ nummer 1

1.Single-channel QS med en kø på 1 forespørsel

2. 2-kanals QS med feil (Erlang-problem)

3.31-kanals QS med 1-begrenset kø

5.31-kanals CMO med ubegrenset kø

Alternativ nummer 2

1.Single-channel QS med en kø på 2 ordrer

2,3-kanals QS med feil (Erlang-problem)

3.30-kanals SMO med 2-begrenset kø

4. Enkanals CMO med ubegrenset kø

5.30-kanals CMO med ubegrenset kø

Alternativ nummer 3

1.Single-channel QS med en kø på 3 ordrer

2,4-kanals QS med feil (Erlang-problem)

3,29-kanals SMO med 3-begrenset kø

4. Enkanals CMO med ubegrenset kø

5,29-kanals CMO med ubegrenset kø

Alternativ nummer 4

1. enkanals QS med en kø på 4 forespørsler

2,5-kanals CMO med feil (Erlang-problem)

3,28-kanals QS med 4-begrenset kø

4. Enkanals CMO med ubegrenset kø

5,28-kanals CMO med ubegrenset kø

Alternativ nummer 5

1.Single-channel QS med en kø på 5 applikasjoner

2,6-kanals CMO med feil (Erlang-problem)

3,27-kanals CMO med 5-begrenset kø

4. Enkanals CMO med ubegrenset kø

5,27-kanals CMO med ubegrenset kø

Alternativ nummer 6

1.Single-channel QS med en kø på 6 applikasjoner

2,7-kanals QS med feil (Erlang-problem)

3,26-kanals CMO med 6-begrenset kø

4. Enkanals CMO med ubegrenset kø

5,26-kanals CMO med ubegrenset kø

Alternativ nummer 7

1. enkanals QS med en kø på 7 applikasjoner

2.8-kanals QS med feil (Erlang-problem)

3,25-kanals CMO med 7-begrenset kø

4. Enkanals CMO med ubegrenset kø

5,25-kanals CMO med ubegrenset kø

Alternativ nummer 8

1.Single-channel QS med en kø på 8 applikasjoner

2.9-kanals QS med feil (Erlang-problem)

3,24-kanals QS med 8-begrenset kø

4. Enkanals CMO med ubegrenset kø

5,24-kanals CMO med ubegrenset kø

Alternativ nr. 9

1.Single-channel QS med en kø på 9 applikasjoner

2.10-kanals CMO med feil (Erlang-problem)

3,23-kanals SMO med 9-begrenset kø

4. Enkanals CMO med ubegrenset kø

5,23-kanals CMO med ubegrenset kø

Alternativ nr. 10

1.Single-channel QS med en kø på 10 applikasjoner

2,11-kanals QS med feil (Erlang-problem)

3,22-kanals SMO med 10-begrenset kø

4. Enkanals CMO med ubegrenset kø

5.22-kanals CMO med ubegrenset kø

• absolutt og relativ systemkapasitet;
• belastnings- og nedetidsfaktorer;
• gjennomsnittlig tid for full systembelastning;
• gjennomsnittlig oppholdstid for en forespørsel i systemet.

• P ob er sannsynligheten for å betjene forespørselen,
• t-systemet er tiden forespørselen er i systemet.

• λ b- systemets absolutte gjennomstrømning (gjennomsnittlig antall forespørsler som blir servert per tidsenhet),
• P obs - systemets relative gjennomstrømning,
• k s - systembelastningsfaktor.

Oppgave. Datasenteret for kollektiv bruk med tre datamaskiner mottar bestillinger fra bedrifter for databehandling. Hvis alle tre datamaskinene fungerer, aksepteres ikke den nye ordren, og bedriften blir tvunget til å henvende seg til et annet datasenter. Gjennomsnittlig arbeidstid med en bestilling er 3 timer. Intensiteten i applikasjonsflyten er 0,25 (1 / t). Finn de begrensende sannsynlighetene for tilstander og ytelsesindikatorer til datasenteret.
Beslutning. Ved tilstand n \u003d 3, λ \u003d 0,25 (1 / t), t vol. \u003d 3 (h). Servicestrømningsintensitet μ \u003d 1 / t vol. \u003d 1/3 \u003d 0,33. Intensiteten til datamaskinbelastningen i henhold til formelen (24) ρ \u003d 0,25 / 0,33 \u003d 0,75. La oss finne de begrensende sannsynlighetene for stater:
i henhold til formelen (25) p0 \u003d (1 + 0,75 + 0,75 2/2! +0,75 3/3!) -1 \u003d 0,476;
i henhold til formelen (26) p 1 \u003d 0,75 ∙ 0,476 \u003d 0,357; p 2 \u003d (0,75 2/2!) ∙ 0,476 \u003d 0,134; p 3 \u003d (0,75 3/3!) ∙ 0,476 \u003d 0,033 dvs. i den stasjonære driftsmåten til datasenteret er det i gjennomsnitt 47,6% av tiden ikke en eneste 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 applikasjoner (tre datamaskiner er opptatt).
Sannsynligheten for feil (når alle tre datamaskinene er opptatt), dermed åpner P. \u003d p 3 \u003d 0,033.
I henhold til formel (28) er den relative gjennomstrømningen til sentrum Q \u003d 1-0,033 \u003d 0,967, dvs. i gjennomsnitt betjener datasenteret 96,7 applikasjoner av hver 100 applikasjoner.
I følge formel (29) er senterets absolutte gjennomstrømning A \u003d 0,25 ∙ 0,967 \u003d 0,242, dvs. 0.242 forespørsler serveres i gjennomsnitt per time.
I henhold til formel (30) er gjennomsnittlig antall sysselsatte datamaskiner k \u003d 0,242 / 0,33 \u003d 0,725, dvs. hver av de tre datamaskinene vil være opptatt med å betjene applikasjoner i gjennomsnitt med bare 72,5 / 3 \u003d 24,2%.
Når vi vurderer effektiviteten til et datasenter, er det nødvendig å sammenligne inntektene fra kjøringen av applikasjoner med tapene fra nedetid for dyre datamaskiner (på den ene siden har vi en høy gjennomstrømning av QS, og på den annen side en betydelig nedetid for tjenestekanaler) og velg en kompromissløsning.

Oppgave. Havnen har en båtplass for lossing av skip. Strømningshastigheten til fartøyene er 0,4 (fartøyer per dag). Gjennomsnittlig tid for lossing av ett fartøy er 2 dager. Det antas at køen kan ha ubegrenset lengde. Finn ytelsesindikatorene for båtplassen, samt sannsynligheten for at ikke mer enn 2 fartøyer venter på lossing.
Beslutning. Vi har ρ \u003d λ / μ \u003d μt vol. \u003d 0,4 ∙ 2 \u003d 0,8. Siden ρ \u003d 0,8 < 1 kan ikke køen for lossing vokse uendelig og begrense sannsynligheten. La oss finne dem.
Sannsynligheten for at køya er ledig, ifølge (33), p 0 \u003d 1 - 0,8 \u003d 0,2, og sannsynligheten for at den er opptatt, P er opptatt. \u003d 1-0,2 \u003d 0,8. I følge formelen (34) er sannsynligheten for at det er 1, 2, 3 skip ved køya (dvs. 0, 1, 2 skip venter på lossing) er p 1 \u003d 0,8 (1-0,8) \u003d 0, seksten; p 2 \u003d 0,8 2 ∙ (1-0,8) \u003d 0,128; p 3 \u003d 0,8 3 ∙ (1-0,8) \u003d 0,1024.
Sannsynligheten for at ikke mer enn 2 skip venter på lossing er
P \u003d p 1 + p 2 + p 3 \u003d 0,16 + 0,128 + 0,1024 \u003d 0,3904
I henhold til formel (40), gjennomsnittlig antall skip som venter på lossing
L jh \u003d 0,8 2 / (1-0,8) \u003d 3,2
og gjennomsnittlig ventetid for lossing i henhold til formelen (15.42)
T och \u003d 3,2 / 0,8 \u003d 4 dager.
I henhold til formelen (36), gjennomsnittlig antall skip ved køya, L-systemet. \u003d 0,8 / (1-0,8) \u003d 4 (dager) (eller enklere i henhold til (37) L-systemet. \u003d 3,2 + 0,8 \u003d 4 (dager), og gjennomsnittlig tid for et skips opphold ved køye i henhold til formelen (41) T syst \u003d 4 / 0,8 \u003d 5 (dag).
Det er åpenbart at effektiviteten ved lossing av skip er lav. For å øke den, er det nødvendig å redusere gjennomsnittlig tid for lossing av fartøyet omtrent eller å øke antall køyer n.

Oppgave. I supermarkedet ankommer en strøm av kjøpere til bosetningssenteret med en intensitet λ \u003d 81 personer. i timen. Gjennomsnittlig varighet for betjening av en kunde av kontrolleren er t rev \u003d 2 minutter. Definere:
og. Minimum antall kasserere n min,hvor køen ikke vil vokse til uendelig, og de tilsvarende tjenestekarakteristikkene for n \u003d n min.
b. Det optimale tallet n opt. kontrollere-kasserere, der den relative verdien av kostnadene C rel., assosiert med kostnadene for å opprettholde servicekanaler og holde seg i køen til kunder, angir for eksempel hvordan, vil være minimal, og sammenligne egenskapene til tjenesten for n \u003d n min og n \u003d n opt ...
på. Sannsynligheten for at det ikke vil være flere enn tre kunder i køen.
Beslutning.
og. Etter tilstand l \u003d81 (1 / t) \u003d 81/60 \u003d 1,35 (1 / min.). I henhold til formelen (24) er r \u003d l / m \u003d lt omtrent \u003d 1,35 × 2 \u003d 2,7. Køen vil ikke vokse til uendelig hvis r / n< 1, т.е. при n > r \u003d 2,7. Dermed er minimum antall kassereregulatorer n min \u003d 3.
La oss finne serviceegenskapene til QS for p= 3.
Sannsynligheten for at det ikke er noen kjøpere i avregningsnoden, i henhold til formelen (45) p 0 \u003d (1 + 2,7 + 2,7 2/2! + 2,7 3/3! + 2,7 4/3! (3 -2,7)) -1 \u003d 0,025, dvs. i gjennomsnitt 2,5% kasserekontrollere vil være inaktive.
Sannsynligheten for at det vil være kø i beregningsnoden, ifølge (48) P och. \u003d (2,7 4/3! (3-2,7)) 0,025 \u003d 0,735
Gjennomsnittlig antall kunder i køen, av (50) L och. \u003d (2,7 4/3 ∙ 3! (1-2,7 / 3) 2) 0,025 \u003d 7,35.
Gjennomsnittlig ventetid i køen av (42) T och. \u003d 7,35 / 1,35 \u003d 5,44 (min).
Gjennomsnittlig antall kjøpere i avregningsnoden for (51) L-systemet. \u003d 7,35 + 2,7 \u003d 10,05.
Gjennomsnittlig tid brukt av kjøpere i avregningsnoden i henhold til (41) T-systemet. \u003d 10,05 / 1,35 \u003d 7,44 (min).
Tabell 1

1. Intensiteten i tjenestestrømmen

2. Koeffisient for lasting av CMO

3. Sannsynligheten for kø

4. Sannsynlighet for systemfeil

5. Båndbredde

6. Gjennomsnittlig antall søknader i køen

7. Gjennomsnittlig antall søknader som leveres av QS

8. Gjennomsnittlig antall søknader i CMO

9. Gjennomsnittlig søknadstid i CMO

10. Gjennomsnittlig tid brukt av et program i køen

11. Gjennomsnittlig antall travle kanaler.

Det er nødvendig å vurdere kvaliteten på det resulterende systemet etter kombinasjonen av verdiene til indikatorene. Når du analyserer simuleringsresultater, er det viktig å ta hensyn til interessene til klienten og eieren av systemet. Spesielt skal min eller maks være en eller annen indikator.

26. Enkanals CMO

27. Enkanals QS med feil

28. Flerkanals QS med begrenset kø

CMO-parametere:

o Intensitet av strømmen av applikasjoner.

o Intensitet i tjenestestrømmen.

o Gjennomsnittlig tjeneste for forespørselen.

o Antall servicekanaler.

o Tjenestedisiplin.

< СМО на примере работы АЗС. Несколько одинак. колонок, произв-ть кот.известна. Если колонки заняты, то обслуживание в очереди м. ждать не > 3 biler samtidig. Køen regnes som vanlig. Hvis alle setene i køen er opptatt, nektes maskinen tjeneste.

29. Transportoppgave

- et bredt spekter av oppgaver, ikke bare transportkarakter, ressurstildeling, er flere. leverandører, d / annet vilkårlig antall forbrukere. D / transportører er oftest knyttet til transport:

1. Koble forbrukere til produsentens ressurser.

2. Binding til destinasjonene for avgangspunkter

3. Sammenkobling av godstrafikk i retning fremover og bakover.

4. Optimal fordeling av V-utgang fra industri. produkter m / u produserer.

< модель привязки к пункту назначения. Известны: пункты отправления и назначения, объемы отправления по к-му пункту, потребность в грузе, стоимость доставки по каждому варианту. Н. оптимальный план перевозок с min транспортными издержками.

30. Tr. lukket oppgave - sSend. last \u003d ∑V forbruk i denne lasten, dvs. ∑ai \u003d ∑bj (m er antall leverandører, n er antall forbrukere).

31 ... Hvis denne tilstanden ikke er mulig - åpen st. oppgave... Da må den reduseres til lukket:

1. Hvis etterspørselen etter destinasjonene overstiger lageret til avreisepunktene, introduseres en fiktiv leverandør med den manglende forsendelsen V.

2. Hele tilførselen av leverandører\u003e trenger, deretter inngangssikker. forbruker.

32. Algoritme for å løse problemet ved hjelp av potensialmetoden (trinn):

1. Utvikling av den opprinnelige planen (referanseløsning).

2. Beregning av potensialer.

3. Kontrollere planen for optimalitet.

4. Søk etter den maksimale lenken for ikke-optimalitet (hvis element 3 ikke blir utført)

5. Å tegne en kontur av omfordeling av ressurser.

6. Bestemmelse av min e-ta i kretsen for omfordeling og omfordeling. ressurser langs konturen.

7. Få en ny plan.

Denne prosedyren gjentas flere ganger til en optimal løsning er funnet. Algoritmen forblir uendret. Metoder for å finne den opprinnelige planen:

1. S-Z vinkelmetode

2. Metode for min kostnad

3. Metode med dobbel preferanse

Den potensielle metoden gjør det mulig å finne den optimale for et begrenset antall planer. (Vogels metode) Potensialmetoden ble utviklet av d / classic. transportoppgaver, men disse er sjeldne, du må innføre en rekke begrensninger.

33. I økonomien med å organisere møter, normen for oppgaver, kat. redusert til en transportoppgave:

1. Avd. levering fra obj. noen leverandører. forbrukere d. ekskludert på grunn av mangel på nødvendig konv. lagring, overbelastning av kommunikasjon, etc.

2. Arrangør. kreves def. min ∑ kostnader for produksjon og transport av produkter. M. viser seg å være økonomisk. mer lønnsomt å levere råvarer fra fjernere punkter, men<себест-ти. Критерий оптимальности принимает ∑ затрат на пр-во и тран-ку.

3. En rekke transporter. ruter har båndbreddebegrensninger.

4. Leveranser per definisjon. ruter er obligatoriske og obligatoriske. d. angi optim. plan.

5. Det økonomiske problemet er ikke et transportproblem. (Eks. - distribusjon av produserte produkter av bedrifter).

6. Behovet for en maksimal målfunksjon for transporttypeoppgaven.

7. Behovet for en og samme t for å distribuere last av forskjellige slag blant forbrukerne - Fleroppgave transportoppgave.

8. Levering av varer på kort tid. (Potensialmetoden er ikke egnet, den løses ved hjelp av en spesiell algoritme).

34. Transportoppgave i nettverkserstatning

Hvis tilstanden til transportoppgaven er satt i form av et diagram, hvor leverandører, forbrukere og forbindelser vises. deres veier, verdiene til lastelagrene og behovene for det og indikatorene for optimalitetskriteriet (tariffer, avstander) er angitt. På noder (noder) i nettverket er leverandører og forbrukere avbildet. Lastebeholdninger anses som positive, og kravene er negative tall. Nettverkskanter (buer) - veier. Transportløsning. problemet i nettverksinnstillingen er basert på den potensielle metoden og begynner med konstruksjonen av en innledende referanseplan, som må tilfredsstille kravene:

1. Alle aksjer må distribueres og kundene er fornøyde.

2. For hvert toppunkt må levering av last angis (+ eller -)

3. Totalt antall leveranser må være 1 mindre enn antall hjørner.

4. Pilene, som indikerer leveranser, trenger ikke å danne en krets. krets.

Deretter blir planen sjekket for optimalitet, som potensialene beregnes for. Få en ny plan og undersøke på nytt for optimalitet. Bestem verdien av objektivfunksjonen.

Når det gjelder en åpen modell, introduseres en fiktiv kunde eller leverandør.

35. D / løser vitenskapelige og praktiske problemer innen logistikk ca. hovedmetoder:

1. Metoder for systemanalyse

2. Metoder for teorien om operasjonsforskning

3. Cybernetiske metoder

4. Prognosemetode

5. Metoder for sakkyndig vurdering

6. Simuleringsmetoder

36. Det meste av logistikken er brukte imitasjoner. modellering, der mønstrene som bestemmer det kvantitative forholdet forblir ukjent, og selve logistikkprosessen forblir en "svart boks" eller "grå boks".

Til de viktigste prosessene med imitasjoner. modellering rel-Xia:

1. Konstruksjon av en modell av et reelt system.

2. Sette opp eksperimenter på denne modellen.

Modelleringsmål:

o Bestemmelse av oppførselen til logistikksystemet.

o Velge en strategi for å tilby. naib.eff-th fungerende logistikk. systemer.

Etterligning. det anbefales å utføre modellering når forholdene er:

1. Ikke substantiv. fullstendig formulering av problemer eller analysemetoder for løsning er ikke utviklet. matte. modeller.

2. Analytisk. modellen er tilgjengelig, men prosedyrene er komplekse og tidkrevende, sl. imitere. simulering gir en enklere måte å løse problemet på.

3. Analytisk. løsninger n., men implementeringen av dem er umulig på grunn av utilstrekkelig matematisk opplæring av personell.

37. Fant bred anvendelse innen logistikk ekspertsystemer - spesiell dataprogrammer, kat. hjelpe spesialister med å ta beslutninger, kommunikasjon. med materialflytstyring.

Ekspert-systemet tillater:

1. Ta raske og kvalitetsbeslutninger innen materialadministrasjon.

2. å trene erfarne spesialister på relativt kort tid.

4. Bruk erfaring og kunnskap fra høyt kvalifiserte spesialister på forskjellige arbeidsplasser.

Ulemper med ekspertsystemet:

1. Begrenset bruk av sunn fornuft.

2. Det er umulig å ta hensyn til alle funksjonene i programmet til ekspertsystemet.

Beregning av effektivitetsindikatorer for en åpen enkeltkanals QS med feil. Beregning av effektivitetsindikatorer for en åpen flerkanals QS med feil. Beregning av effektivitetsindikatorer for en flerkanals QS med en begrensning på køens lengde. Beregning av effektivitetsindikatorer for flerkanals QS ved å vente.

1. Søknadsflyter i CMO

2. Servicelovgivning

3. Kvalitetskriterier for arbeidet med QS

4.

5. Parametere for kømodeller. Når man analyserer massesystemer

6. I. Modell A - en modell av et enkeltkanals køsystem med Poisson-inngangsstrøm av krav og eksponentiell tjenestetid.

7. II. Modell B er et flerkanals servicesystem.

8. III. Modell C - Modell med konstant servicetid.

9. IV. Modell D er en begrenset populasjonsmodell.

Søknadsflyter i CMO

Det er inngangs- og utgangsstrømmer av applikasjoner.
Inngangsstrømmen av krav er en tidssekvens av hendelser ved inngangen til QS, for hvilken forekomsten av en hendelse (krav) overholder sannsynlige (eller deterministiske) lover. Hvis kravene til service er i tråd med en hvilken som helst tidsplan (for eksempel biler ankommer bensinstasjonen hvert 3. minutt), overholder en slik strømning deterministiske (visse) lover. Men som regel er mottak av søknader underlagt tilfeldige lover.
For å beskrive tilfeldige lover i køteorien introduseres en modell av hendelsesflyter. En strøm av hendelser er en sekvens av hendelser som følger etter hverandre på tilfeldige tider.
Som hendelser kan ankomsten av krav til QS-inngangen (ved inngangen til køblokken), utseendet til kravene ved inngangen til tjenesteenheten (ved utgangen fra køblokken) og utseendet til betjente krav ved utgangen fra QS vises.

Hendelsesstrømmer har forskjellige egenskaper som lar deg skille mellom forskjellige typer strømmer. Først av alt kan strømninger være homogene og ikke-homogene.
Homogene strømmer er strømmer der forespørselsflyten har de samme egenskapene: de har først til mølla-prioritet, de behandlede forespørslene har de samme fysiske egenskapene.
Heterogene tråder er tråder der kravene har forskjellige egenskaper: kravene er oppfylt i henhold til prioritetsprinsippet (for eksempel et avbruddskart i en datamaskin), de behandlede kravene har forskjellige fysiske egenskaper.
En ikke-enhetlig strøm av hendelser kan skjematisk vises som følger

Følgelig er det mulig å bruke flere QS-modeller for å betjene heterogene strømmer: en enkeltkanals QS med en kødisiplin som tar hensyn til prioriteringene til inhomogene krav, og en flerkanals QS med en individuell kanal for hver type krav.
En regelmessig flyt er en flyt der hendelser følger hverandre med jevne mellomrom. Hvis vi betegner med - øyeblikkene av forekomst av hendelser, dessuten og med intervaller mellom hendelser, så for en regelmessig flyt

En tilbakevendende strøm defineres følgelig som en strøm som alle fordelingsfunksjoner fungerer for intervaller mellom forespørsler

sammenfaller, altså

Fysisk er en tilbakevendende strøm en sekvens av hendelser som alle intervaller mellom hendelser ser ut til å "oppføre seg" på samme måte; overholder den samme distribusjonsloven. Dermed er det mulig å undersøke bare et hvilket som helst intervall og oppnå statistiske egenskaper som vil være gyldige for alle andre intervaller.
For å karakterisere strømmer blir sannsynligheten for fordelingen av antall hendelser i et gitt tidsintervall ofte introdusert i betraktning, som bestemmes som følger:

hvor er antall hendelser som vises i intervallet.
En strømning uten ettereffekt er preget av egenskapen at for to usammenhengende tidsintervaller, og hvor ,,, sannsynligheten for forekomst av antall hendelser i det andre intervallet ikke avhenger av antall hendelser i det første intervallet.

Fraværet av ettervirkning betyr fraværet av en sannsynlig avhengighet av den påfølgende prosessen av den forrige. Hvis det er en enkeltkanals QS med servicetid, og med en strøm av krav uten ettereffekt ved inngangen til systemet, vil utgangsstrømmen være med ettereffekt, siden krav på utgangen av QS ikke vises oftere enn intervallet. I en vanlig strøm, der hendelser følger hverandre med jevne mellomrom, er det den alvorligste ettervirkningen.
En flyt med begrenset ettereffekt er en strøm som intervallene mellom hendelsene er uavhengige for.
En strøm kalles stasjonær hvis sannsynligheten for forekomst av et visst antall hendelser i et tidsintervall bare avhenger av lengden på dette intervallet og ikke avhenger av plasseringen på tidsaksen. For en stasjonær strøm av hendelser er gjennomsnittlig antall hendelser per tidsenhet konstant.
En vanlig strømning er en strømning der sannsynligheten for at to eller flere forespørsler faller på et gitt lite tidsintervall dt er ubetydelig sammenlignet med sannsynligheten for at en forespørsel faller.
En flyt som har egenskapene til stasjonaritet, fravær av ettereffekt og ordinærhet kalles Poisson (enkleste). Denne strømmen har en sentral plass blant alle variasjonene i strømmer, akkurat som tilfeldige variabler eller prosesser med normalfordeling i den anvendte teorien om sannsynlighet.
Poisson-strømning er beskrevet med følgende formel:
,
hvor er sannsynligheten for forekomst av hendelser i tid, er strømningsintensiteten.
Strømningshastigheten er gjennomsnittlig antall hendelser som skjer per tidsenhet.
For en Poisson-strøm fordeles tidsintervallene mellom krav eksponentielt

En strøm med begrenset ettereffekt, for hvilken tidsintervallene mellom krav fordelt i henhold til normal lov, kalles en normal flyt.

Servicelovgivning

Servicemodus (tjenestetid), så vel som modus for ankomstkrav, kan være enten konstant eller tilfeldig. I mange tilfeller overholder tjenestetiden en eksponentiell fordeling.
Sannsynligheten for at tjenesten avsluttes før tid t er:

hvor er strømningstettheten til applikasjoner
Derfra distribusjonstettheten til tjenestetid

En ytterligere generalisering av loven om eksponentiell tjeneste kan være Erlang-distribusjonsloven, når hvert tjenesteintervall overholder loven:

hvor er intensiteten til den opprinnelige Poisson-strømmen, k er rekkefølgen på Erlang-strømmen.

Kvalitetskriterier for arbeidet med QS

Effektiviteten til QS-operasjonen blir vurdert av forskjellige indikatorer, avhengig av kjeden og typen av QS. Det mest utbredte er følgende:

Den absolutte gjennomstrømningen av QS med feil (systemytelse) er gjennomsnittlig antall forespørsler som systemet kan behandle.

Den relative gjennomstrømningen av QS er forholdet mellom gjennomsnittlig antall forespørsler behandlet av systemet og gjennomsnittlig antall forespørsler mottatt ved inngangen til QS.

Gjennomsnittlig nedetid på systemet.

For et køsystem legges følgende egenskaper til:
Lengden på køen, som avhenger av en rekke faktorer: på når og hvor mange forespørsler som kom inn i systemet, hvor mye tid det ble brukt på å betjene forespørslene som kom. Køen er en tilfeldig variabel. Effektiviteten til køsystemet avhenger av lengden på køen.

For QS med begrenset ventetid i køen er alle karakteristikkene ovenfor viktige, og for systemer med ubegrenset venting er den absolutte og relative gjennomstrømningen til QS meningsløs.

I fig. 1 viser servicesystemer av forskjellige konfigurasjoner.

Kømodellparametere. Når man analyserer massesystemer tjenesten bruker tekniske og økonomiske egenskaper.

De mest brukte spesifikasjonene er:

1) gjennomsnittlig tid som klienten bruker i kø;

2) gjennomsnittlig kø lengde;

3) gjennomsnittlig tid som klienten bruker i servicesystemet (ventetid pluss servicetid);

4) gjennomsnittlig antall kunder i servicesystemet;

5) sannsynligheten for at tjenestesystemet vil være ledig;

6) sannsynligheten for et visst antall klienter i systemet.

Blant de økonomiske egenskapene er følgende av største interesse:

1) kostnadene ved å vente i køen;

2) ventekostnader i systemet;

3) vedlikeholdskostnader.

Køsystemmodeller... Avhengig av kombinasjonen av de ovennevnte egenskapene, kan forskjellige modeller av køsystemer vurderes.

Her ser vi på noen av de mest berømte modellene. De har alle følgende egenskaper til felles:

A) Poisson-fordeling av sannsynligheten for skadesmottak;

B) standard kundeatferd;

C) FIFO-serviceregel (først til mølla);

D) enkelt vedlikeholdsfase.

I. Modell A - en modell av et enkeltkanals køsystem M / M / 1 med Poisson-inngangsstrøm av krav og eksponentiell tjenestetid.

De vanligste køproblemene med en enkelt kanal. I dette tilfellet danner kunder en kø til et enkelt servicepunkt. Anta at for slike systemer er følgende vilkår oppfylt:

1. Bestillinger serveres etter først til mølla-prinsippet (FIFO), hvor hver klient venter på sin tur til slutten, uavhengig av lengden på køen.

2. Utseende av ordrer er uavhengige hendelser, men gjennomsnittlig antall ordrer som ankommer per tidsenhet er uendret.

3. Prosessen med ankomstankomst er beskrevet av en Poisson-fordeling, og krav kommer fra et ubegrenset sett.

4. Tjenestetid er beskrevet av en eksponentiell sannsynlighetsfordeling.

5. Tjenesteprisen er høyere enn frekvensen for mottak av søknader.

La λ være antall forespørsler per tidsenhet;

μ er antall klienter som serveres per tidsenhet;

n er antall forespørsler i systemet.

Deretter er køsystemet beskrevet av ligningene nedenfor.

Formler for beskrivelse av M / M / 1-systemet:

Gjennomsnittlig servicetid for en klient i systemet (ventetid pluss servicetid);

Gjennomsnittlig antall kunder i køen;

Gjennomsnittlig ventetid for en klient i køen;

Karakteristisk for systembelastningen (hvor lang tid systemet er opptatt med service);

Sannsynligheten for fravær av applikasjoner i systemet;

Sannsynligheten for at det er mer enn K-ordrer i systemet.

II. Modell B - flerkanals servicesystem M / M / S. I et flerkanalsystem er to eller flere kanaler åpne for service. Kundene antas å vente i en delt kø og få tilgang til den første gratis servicekanalen.

Et eksempel på et slikt flerkanals enfasesystem kan sees i mange banker: fra den generelle køen vender kundene seg til det første ledige vinduet for service.

I et flerkanalsystem overholder strømmen av krav Poisson-loven, og tjenestetiden overholder det eksponentielle. Førstkommende servert først, og alle tjenestekanalene fungerer i samme hastighet. Formlene for modell B er komplekse nok til å bruke. For å beregne parametrene til et flerkanals tjenestesystem er det praktisk å bruke riktig programvare.

Den gang søknaden sto i køen;

Tid bestillingen var i systemet.

III. Modell C - modell med konstant brukstid M / D / 1.

Noen systemer har konstant snarere enn eksponentielt distribuert tjenestetid. I slike systemer betjenes kundene i en bestemt periode, for eksempel i en automatisk bilvask. For modell C med konstant tjenestetakt er verdiene til mengdene Lq og Wq to ganger mindre enn de tilsvarende verdiene i modell A med en variabel servicetakt.

Modell C formler:

Gjennomsnittlig kø lengde;

Gjennomsnittlig ventetid i kø;

Gjennomsnittlig antall kunder i systemet;

Gjennomsnittlig ventetid i systemet.

IV. Modell D er en begrenset populasjonsmodell.

Hvis antallet potensielle kunder i servicesystemet er begrenset, har vi å gjøre med en spesiell modell. Et slikt problem kan oppstå for eksempel når det gjelder service på utstyret til en fabrikk med fem maskiner.

Det særegne ved denne modellen i forhold til de tre som ble vurdert tidligere, er at det er en gjensidig avhengighet mellom lengden på køen og frekvensen for mottak av søknader.

V. Model E - Begrenset linjemodell. Modellen skiller seg fra de forrige ved at antall seter i køen er begrenset. I dette tilfellet etterlater en kunde som ankommer systemet når alle kanaler og steder i køen er opptatt, systemet ubetjent, dvs. det blir avvist.

Som et spesielt tilfelle av modellen med begrenset kø, kan vi vurdere modellen med avslag hvis antall plasser i køen reduseres til null.