В практически урок ще разгледаме този път и ще сравним резултатите от симулацията с теоретично решение. Примери за решаване на проблеми на системи за масово обслужване

Математически (абстрактен) обект, чиито елементи са (фиг. 2.1):

• входен (входящ) поток от заявки (изисквания) за услуга;
• сервизни устройства (канали);
• опашка от приложения, чакащи обслужване;
• изходящ (изходящ) поток от обслужени заявки;
• потокът от заявки за последващи грижи след прекъсване на услугата;
• поток от необслужени заявки.

Заявка(заявка, изискване, обаждане, клиент, съобщение, пакет) - обект, влизащ в QS и изискващ обслужване в устройството. Набор от последователни приложения, разпределени във времева форма входен поток от приложения.

Ориз. 2.1.

сервизно устройство(устройство, устройство, канал, линия, инструмент, кола, рутер и др.) - QS елемент, чиято цел е да обслужва приложения.

Обслужване- забавяне на заявката в сервизното устройство за известно време.

Продължителност на услугата- време на забавяне (обслужване) на приложението в устройството.

Устройство за съхранение(buffer, input buffer, output buffer) - набор от места за изчакване на приложения пред обслужващото устройство. Брой места за чакане - капацитет за съхранение.

Заявление, получено от CMO, може да бъде в две състояния:

• 1) обслужване(в устройството);
• 2) очаквания(в акумулатора), ако всички устройства са заети да обслужват други заявки.

Рекламациите във формуляра за акумулаторна и чакаща услуга завойприложения. Броят на приложенията в акумулаторната чакаща услуга - дължина на опашката.

Буферираща дисциплина(дисциплина на опашка) - правилото за въвеждане на входящи приложения в устройството (буфер).

Сервизна дисциплина- правилото за избор на заявки от опашката за обслужване в устройството.

Приоритет- преференциалното право (за улавяне на ресурси) за влизане в акумулатора или избор от опашката за обслужване в приложенията на устройството от един клас по отношение на приложенията от други класове.

Има много системи за масово обслужване, които се различават по структурна и функционална организация. В същото време разработването на аналитични методи за изчисляване на показателите за ефективност на QS в много случаи включва редица ограничения и предположения, които стесняват набора от изследвани QS. Ето защо няма общ аналитичен модел за произволна сложна структура QS.

QS аналитичният модел е набор от уравнения или формули, които позволяват да се определят вероятностите от състояния на системата по време на нейната работа и показатели за ефективност въз основа на известните параметри на входящия поток и каналите за обслужване, буфериране и дисциплини на обслужване.

Аналитичното моделиране на QS е значително улеснено, ако процесите, протичащи в QS, са марковски (потоците от приложения са най-прости, времето за обслужване се разпределя експоненциално). В този случай всички процеси в QS могат да бъдат описани чрез обикновени диференциални уравнения, а в граничния случай - за стационарни състояния - чрез линейни алгебрични уравнения и, след като са решени с всякакви методи, налични в математическите софтуерни пакети, определят избраните показатели за ефективност .

В IM системите, когато внедряват QS, се приемат следните ограничения и предположения:

• приложение, въведено в системата моменталновлиза в услуга, ако няма заявки в опашката и устройството е свободно;
• в устройството за поддръжка по всяко време може да бъде само единискане;
• след приключване на обслужването на която и да е заявка в устройството, моментално се избира следващата заявка от опашката за обслужване, т.е. не работи на празен ходако има поне едно приложение в опашката;
• получаването на заявления в QS и продължителността на тяхното обслужване не зависят от броя на приложенията, които вече са в системата, или от други фактори;
• продължителността на обслужващите заявки не зависи от интензивността на заявките, постъпващи в системата.

Нека се спрем по-подробно на някои елементи на QS.

Входящ (входящ) поток от приложения. Потокът от събитиясе нарича поредица от хомогенни събития, следващи едно след друго и възникващи в някои, най-общо казано, случаенточки във времето. Ако събитието се състои в появата на искове, имаме поток на приложението.За да се опише потокът от приложения в общия случай, е необходимо да се зададат времевите интервали t = t k - t k-1между съседни моменти t k _ kи t kполучаване на заявления с поредни номера да се - 1 и да сесъответно (да се - 1, 2, ...; t 0 - 0 - начален момент от време).

Основната характеристика на потока на приложението е неговата X интензивност- среден брой приложения, пристигащи на входа на QS за единица време. Стойност t = 1/Xопределя средният интервал от време между две последователни поръчки.

Потокът се нарича детерминистиченако интервали от време t домежду съседни приложения приемат определени предварително известни стойности. Ако интервалите са еднакви (x до= t за всички k = 1, 2, ...), тогава потокът се извиква редовен.За пълно описание на редовния поток от заявки е достатъчно да зададете интензитета на потока хили стойността на интервала t = 1/X.

Поток, в който интервали от време x kмежду съседни приложения са случайни величини, т.нар случаен.За пълно описание на произволен поток от приложения в общия случай е необходимо да се зададат законите на разпределение F fc (x fc) за всеки от интервалите от време x k, k = 1,2,....

Произволен поток, в който всички времеви интервали x b x 2,... между съседни последователни клиенти са независими случайни променливи, описани от функции на разпределение FjCij), F 2 (x 2), ... съответно, се нарича поток с ограничено последействие.

Извиква се произволен поток повтарящ се,ако всички времеви интервали xb t 2 , ... разпределени между приложенията по същия закон F(t). Има много повтарящи се потоци. Всеки закон за разпределение генерира свой собствен повтарящ се поток. Повтарящите се потоци иначе са известни като Palm потоци.

Ако интензивността хи законът за разпределение F(t) на интервалите между последователни заявки не се променя с времето, тогава потокът от заявки се нарича стационаренВ противен случай потокът на приложението е нестационарни.

Ако във всеки момент от времето t kна входа на QS може да се появи само един клиент, тогава се извиква потокът от клиенти обикновени.Ако повече от едно приложение може да се появи по всяко време, тогава потокът от приложения е такъв извънредно,или група.

Потокът от заявки се нарича поток без последействие,ако бъдат получени заявления независимо от товаедин от друг, т.е. моментът на получаване на следващото заявление не зависи от това кога и колко заявления са получени преди този момент.

Нарича се стационарен обикновен поток без последействие най-простият.

Времевите интервали t между заявките в най-простия поток се разпределят според експоненциален (примерен) закон:с функция на разпределение F(t) = 1 - e~ m;плътност на разпределение/(f) = хех~"аз,където X > 0 - параметър на разпределение - интензивността на потока от приложения.

Най-простият поток често се нарича Поасон.Името идва от факта, че за този поток вероятността P fc (At) за точно възникване да сезаявки за определен времеви интервал At се определя Закон на Поасон:

Трябва да се отбележи, че потокът на Поасон, за разлика от най-простия, може да бъде:

• стационарен,ако интензивността хне се променя с времето;
• нестационарни,ако дебитът зависи от времето: х= >.(t).

В същото време най-простият поток по дефиниция винаги е неподвижен.

Аналитичните изследвания на моделите на опашката често се извършват при предположението за най-простия поток от заявки, което се дължи на редица забележителни характеристики, присъщи на него.

1. Сумиране (обединяване) на потоци. Най-простият поток в теорията на QS е подобен на нормалния закон за разпределение в теорията на вероятностите: преходът към границата за поток, който е сумата от потоци с произволни характеристики с безкрайно увеличаване на броя на членовете и намаляване на техния интензитет, води до към най-простия поток.

Сума ннезависими стационарни обикновени потоци с интензитети x x x 2 ,..., X Nобразува най-простия поток с интензитет

X=Y,^iпри условие, че добавените потоци имат повече или

по-малко еднакво малко въздействие върху общия поток. На практика общият поток е близък до най-простия при N > 5. И така когато се сумират независими най-прости потоци, общият поток ще бъде най-простиятза всяка стойност Н.

• 2. Вероятностно разреждане на потока. вероятностен(но недетерминиран) разреждане най-простият потокприложения, в които всяко приложение произволно с известна вероятност Рсе изключва от потока, независимо дали други приложения са изключени или не, води до образуването най-простият потокс интензивност Х* = pX,където х- интензивност на първоначалния поток. Потокът от изключени приложения с интензивност X** = (1 - p) X- също протозойнипоток.
• 3. Ефективност. Ако обслужващите канали (устройства) са проектирани за най-простия поток от заявки с интензитет х,тогава обслужването на други видове потоци (със същата интензивност) ще бъде осигурено с не по-малка ефективност.
• 4. Простота. Допускането на най-простия поток от приложения позволява на много математически модели да получат в ясна форма зависимостта на QS индикаторите от параметрите. Най-голям брой аналитични резултати са получени за най-простия поток от заявки.

Анализът на модели с потоци на приложение, различни от най-простите, обикновено усложнява математическите изчисления и не винаги позволява получаването на ясно аналитично решение. „Най-простият“ поток получи името си именно поради тази функция.

Приложенията може да имат различни права за стартиране на услугата. В този случай се казва, че приложенията са разнородни.Предимствата на някои потоци от приложения пред други в началото на услугата се определят от приоритети.

Важна характеристика на входния поток е коефициентът на вариация

където t int - математическо очакване на дължината на интервала; относно- стандартно отклонение на дължината на интервала x int (случайна променлива) .

За най-простия поток (a = -, m = -) имаме v = 1. За повечето

реални потоци 0

Сервизни канали (устройства). Основната характеристика на канала е продължителността на услугата.

Продължителност на услугата- времето, прекарано от приложението в устройството - в общия случай стойността е произволна. В случай на неравномерно натоварване на QS, времето за обслужване на заявки от различни класове може да се различава по законите на разпределение или само по средни стойности. В този случай обикновено се приема, че времето за обслужване за заявки от всеки клас е независимо.

Често практиците приемат, че продължителността на заявките за обслужване е разпределена експоненциален законкоето значително опростява аналитичните изчисления. Това се дължи на факта, че процесите, протичащи в системи с експоненциално разпределение на времевите интервали, са Марковпроцеси:

където c - интензивност на услугата,тук p = _--; t 0 bsl - математика-

време на изчакване за обслужване.

В допълнение към експоненциалното разпределение има Erlang /c-разпределения, хиперекспоненциални разпределения, триъгълни разпределения и някои други. Това не трябва да ни обърква, тъй като е показано, че стойността на критериите за ефективност на QS зависи малко от формата на закона за разпределение на времето за обслужване.

При изследването на QS същността на услугата, качеството на услугата, отпада от внимание.

Каналите могат да бъдат абсолютно надеждентези. не се провалят. По-скоро може да се приеме в изследването. Каналите може да имат крайна надеждност.В този случай QS моделът е много по-сложен.

Ефективността на QS зависи не само от параметрите на входните потоци и каналите за обслужване, но и от последователността, в която се обслужват входящите заявки, т.е. от начините за управление на потока от приложения, когато влизат в системата и се изпращат за обслужване.

Начините за управление на потока от приложения се определят от дисциплините:

• буфериране;
• обслужване.

Дисциплините за буфериране и поддръжка могат да бъдат класифицирани според следните критерии:

• наличие на приоритети между приложения от различни класове;
• метод за изтласкване на приложения извън опашката (за буфериране на дисциплини) и присвояване на заявки за обслужване (за сервизни дисциплини);
• правило за изпреварване или избиране на заявки за услуги;
• способност за промяна на приоритетите.

Вариант на класификацията на буферните дисциплини (очакване) в съответствие с изброените характеристики е показан на фиг. 2.2.

Зависи от наличностили липса на приоритетимежду приложения от различни класове, всички буфериращи дисциплини могат да бъдат разделени на две групи: неприоритетни и приоритетни.

от метод за изтласкване на приложения от хранилищетомогат да се разграничат следните класове буферни дисциплини:

• без изтласкване на заявки - заявките, които са влезли в системата и са установили, че устройството е напълно запълнено, се губят;
• с изместването на приложението на този клас, т.е. същия клас като полученото заявление;
• с изместване на приложението от класа с най-нисък приоритет;
• с изместване на приложението от групата на класовете с нисък приоритет.

Ориз. 2.2.

Буфериращите дисциплини могат да използват следното правила за изхвърляне на заявки от акумулатора:

• случайно изместване;
• изключване на последния ред, т.е. влезе в системата по-късно от всички;
• изтласкване на "дълъг" ред, т.е. намиращи се в акумулатора по-дълго от всички получени преди това приложения.

На фиг. 2.3 показва класификацията на дисциплините за обслужване на приложения в съответствие със същите характеристики като за дисциплините буфериране.

Понякога капацитетът за съхранение в моделите се счита за неограничен, въпреки че в реална система е ограничен. Такова предположение е оправдано, когато вероятността от загуба на поръчка в реална система поради препълване на капацитета за съхранение е по-малка от 10 _3. В този случай дисциплината практически няма ефект върху изпълнението на заявките.

Зависи от наличностили липса на приоритетимежду заявките от различни класове, всички дисциплини на обслужване, както и дисциплините за буфериране, могат да бъдат разделени на две групи: неприоритетни и приоритетни.

от как се присвояват служебните билетидисциплините за обслужване могат да бъдат разделени на дисциплини:

• единичен режим;
• групов режим;
• комбиниран режим.

Ориз. 2.3.

В сервизните дисциплини единичен режимуслуга всеки път само един назначензаявка, за която опашките се сканират след приключване на обслужването на предходната заявка.

В сервизните дисциплини групов режимуслуга всеки път се присвоява група заявкиедна опашка, за която опашките се сканират едва след като бъдат обслужени всички заявки от предварително зададената група. Новоприсвоената група билети може да включва всички билети от дадената опашка. Присвоени групови заявки последователно избрани от опашкатаи се обслужват от устройството, след което се назначава за обслужване следващата група заявки от друга опашка в съответствие с определената сервизна дисциплина.

Комбиниран режим- комбинация от единичен и групов режим, когато част от опашките на заявките се обработват в единичен режим, а другата част - в групов режим.

Дисциплините за обслужване могат да използват следните правила за избор на заявка за обслужване.

Неприоритетни(приложенията нямат ранни привилегии за обслужване - улавяне на ресурси):

• първи дошъл първи обслужен услуга FIFO (първи в - първи навън,първи влязъл - първи излязъл)
• обратна услуга- приложението се избира от опашката в режим LIFO (последно в - първи излязъл,последен влязъл, пръв излязъл)
• произволна услуга- приложението се избира от опашката в режим РАНД (случаен- на случаен принцип);
• циклично обслужване- приложенията се избират в процеса на циклично запитване на устройства в последователност 1, 2, зОТ з- броя на задвижванията), след което зададената последователност се повтаря;

Приоритет(приложенията имат привилегии за ранно обслужване - улавяне на ресурси):

• с относителни приоритети- ако в хода на текущото обслужване на заявка в системата постъпят заявки с по-висок приоритет, то обслужването на текущата заявка, дори без приоритет, не се прекъсва, а получените заявки се изпращат на опашката; относителните приоритети играят роля само в края на текущата услуга на приложението, когато е избрана нова заявка за услуга от опашката.
• с абсолютни приоритети- при постъпване на заявка с висок приоритет, обслужването на заявка с нисък приоритет се прекъсва и получената заявка се изпраща за обслужване; прекъснато приложение може да бъде върнато на опашката или премахнато от системата; ако заявлението се върне на опашката, тогава по-нататъшното му обслужване може да се извърши от прекъснатото място или отново;
• ко смесени приоритети- строгите ограничения на времето за изчакване на опашката за обслужване на отделни заявки изискват определянето на абсолютни приоритети за тях; в резултат на това времето за изчакване за приложения с нисък приоритет може да се окаже неприемливо голямо, въпреки че отделните приложения имат запас от време за изчакване; за изпълнение на ограничения за всички видове заявки, заедно с абсолютни приоритети, на някои заявки могат да бъдат присвоени относителни приоритети, а останалите могат да бъдат обслужвани в неприоритетен режим;
• с редуващи се приоритети- аналог на относителните приоритети, приоритетът се взема предвид само в моментите на завършване на текущото обслужване на група заявки от една опашка и назначаването на нова група за обслужване;
• планирано обслужване- заявки от различни класове (намиращи се в различни хранилища) се избират за обслужване съгласно определен график, който определя последователността на запитване на опашки от приложения, например, в случай на три класа приложения (магазини), графикът може да изглежда така (2, 1, 3, 3, 1, 2) или (1, 2, 3, 3, 2, 1).

В компютърните IM системи, като правило, дисциплината се прилага по подразбиране FIFO.Те обаче разполагат с инструменти, които предоставят на потребителя възможност да организира нужните му дисциплини на обслужване, включително и по график.

Заявленията, получени от CMO, се разделят на класове. В QS, който е абстрактен математически модел, приложенията принадлежат към различни класовев случай че се различават в симулираната реална система поне по една от следните характеристики:

• продължителност на услугата;
• приоритети.

Ако приложенията не се различават по продължителност на услугата и приоритети, те могат да бъдат представени от приложения от същия клас, включително когато идват от различни източници.

За математическо описание на обслужващи дисциплини със смесени приоритети използваме приоритетна матрица,което е квадратна матрица Q = (q, ;), аз, j - 1,..., I, I - броят класове приложения, влизащи в системата.

елемент q(j matrix задава приоритета на заявките за клас азвъв връзка с приложения за клас; и може да приема следните стойности:

• 0 - без приоритет;
• 1 - относителен приоритет;
• 2 - абсолютен приоритет.

Елементите на приоритетната матрица трябва да удовлетворяват следното изисквания:

• q n= 0, тъй като не могат да се задават приоритети между заявки от един и същи клас;
• ако q (j = 1 или 2 тогава р^ = 0, тъй като if клас приложения азимат предимство пред заявките за клас j,тогава последните не могат да имат предимство пред класовите претенции аз (i,j = 1, ..., I).

Зависи от възможности за промяна на приоритетитеПо време на работа на системата приоритетните дисциплини на буфериране и обслужване са разделени на два класа:

• 1) с статични приоритети,които не се променят с времето;
• 2) с динамични приоритети,което може да се променя по време на работа на системата в зависимост от различни фактори, например при достигане на определена критична стойност за дължината на опашката от приложения на клас, който няма приоритет или е с нисък приоритет, може да бъде с по-висок приоритет.

В IM компютърните системи задължително има един елемент (обект), чрез който и само чрез него се въвеждат заявки в модела. По подразбиране всички въведени приложения са неприоритетни. Но има възможности за задаване на приоритети в последователността 1, 2, ..., включително и по време на изпълнение на модела, т.е. в динамика.

Изходящ потоке потокът от обслужвани заявки, напускащи QS. В реални системи приложенията преминават през няколко QS: транзитна комуникация, производствен тръбопровод и др. В този случай изходящият поток е входящият поток за следващия QS.

Входящият поток на първата QS, преминавайки през следващите QS, се изкривява и това усложнява аналитичното моделиране. Трябва обаче да се има предвид, че с най-прост входен поток и експоненциална услуга(тези. в системите на Марков) изходящият поток също е най-простият.Ако времето за обслужване има неекспоненциално разпределение, тогава изходящият поток не само не е прост, но и не се повтаря.

Имайте предвид, че интервалите от време между изходящите заявки не са същите като сервизните интервали. В крайна сметка може да се окаже, че след края на следващата услуга QS не работи известно време поради липса на приложения. В този случай интервалът на изходящия поток се състои от времето на престой на QS и интервала на обслужване на първата заявка, пристигнала след престоя.

В QS, в допълнение към изходящия поток от обслужвани заявки, може да има поток от необслужени заявки.Ако такъв QS получава повтарящ се поток и услугата е експоненциална, тогава потокът от необслужени клиенти също е повтарящ се.

Безплатни опашки за канали. При многоканален QS могат да се формират опашки от свободни канали. Броят на безплатните канали е произволна стойност. Изследователите може да се интересуват от различни характеристики на тази случайна променлива. Обикновено това е средният брой канали, заети от услуга за интервал на проучване и техните коефициенти на натоварване.

Както отбелязахме по-рано, в реални обекти заявките се обслужват последователно в няколко QS.

Извиква се краен набор от последователно взаимосвързани QS, които обработват циркулиращи в тях приложения мрежа за опашка (Семо) (фиг. 2.4, а).

Ориз. 2.4.

SEMO се нарича още многофазен QS.

По-късно ще разгледаме пример за конструиране на QEMO IM.

Основните елементи на QS са възли (U) и източници (генератори) на заявки (G).

Възелмрежите са система за опашка.

Източник- генератор на приложения, влизащи в мрежата и изискващи определени етапи на обслужване в мрежовите възли.

Използва се графика за опростено изображение на QEMO.

Граф Семо- насочен граф (диграф), чиито върхове съответстват на възлите на QEM, а дъгите представляват преходите на приложенията между възлите (фиг. 2.4, b).

И така, ние разгледахме основните концепции на QS. Но при разработването на компютърни системи за IM и тяхното усъвършенстване е необходимо да се използва и огромният творчески потенциал, който в момента се съдържа в аналитичното моделиране на QS.

За по-добро възприемане на този творчески потенциал, като първо приближение, нека се спрем на класификацията на QS моделите.

Снимка 0 - 2 Потоци от събития (a) и най-простият поток (b)

10.5.2.1. стационарност

Потокът се нарича стационарен , ако вероятността за постигане на един или друг брой събития за елементарен период от време дължина τ (

Фигура 0-2 , а)зависи само от дължината на сечението и не зависи къде точно по оста T тази област се намира.

Стационарността на потока означава неговата равномерност във времето; вероятностните характеристики на такъв поток не се променят с времето. По-специално, така нареченият интензитет (или „плътност“) на потока от събития, средният брой събития за единица време за стационарен поток, трябва да остане постоянен. Това, разбира се, не означава, че действителният брой събития, появяващи се за единица време, е постоянен; потокът може да има локални концентрации и разреждане. Важно е, че при стационарен поток тези концентрации и разреждане не са регулярни и средният брой събития, попадащи в един интервал от време, остава постоянен за целия разглеждан период.

На практика често има потоци от събития, които (поне за ограничен период от време) могат да се считат за стационарни. Например, потокът от обаждания, пристигащи на телефонната централа, да речем, в интервала от 12 до 13 часа, може да се счита за стационарен. Същият поток вече няма да бъде неподвижен цял ден (през нощта интензивността на потока от обаждания е много по-малка, отколкото през деня). Имайте предвид, че същият е случаят с повечето физически процеси, които наричаме "стационарни", всъщност те са неподвижни само за ограничен период от време и удължаването на този период до безкрайност е просто удобен трик, използван за опростяване .

10.5.2.2. Без последействие

Потокът от събития се нарича поток без последействие , ако за всякакви неприпокриващи се интервали от време броят на събитията, попадащи на един от тях, не зависи от това колко събития са паднали на другия (или други, ако се разглеждат повече от два раздела).

В такива потоци събитията, които образуват потока, се появяват в последователни точки във времето независимо едно от друго. Например, потокът от пътници, влизащи в метростанция, може да се счита за поток без последствия, тъй като причините, които са причинили пристигането на отделен пътник в този конкретен момент, а не в друг, като правило, не са свързани с подобни причини за други пътници. При поява на такава зависимост се нарушава условието за липса на последействие.

Помислете например за потока от товарни влакове, движещи се по железопътна линия. Ако от съображения за безопасност те не могат да следват един след друг по-често от интервали от време t0 , тогава има зависимост между събитията в потока и е нарушено условието за липса на последействие. Въпреки това, ако интервалът t0 е малък спрямо средния интервал между влаковете, то такова нарушение е незначително.

Снимка 0 - 3 Поасоново разпределение

Помислете по оста T най-простият поток от събития с интензитет λ. (Фигура 0-2 b) . Ще се интересуваме от случаен интервал от време T между съседни събития в този поток; намерете неговия закон за разпределение. Първо, нека намерим функцията за разпределение:

F(t) = P(T ( 0-2)

вероятността стойността на T ще има стойност по-малка отT. Отделете от началото на интервала T (точки t0) сегмент t и намерете вероятността интервалът T ще бъде по-малко T . За да направите това, е необходимо, че за участък от дължина T , съседен на точка t0 , поне едно попадение на събитие в нишка. Нека изчислим вероятността за това F(t) чрез вероятността от противоположното събитие (на сегмент T никакви поточни събития няма да бъдат засегнати):

F (t) \u003d 1 - P 0

Вероятност P 0намираме по формула (1), като приемемм = 0:

откъдето функцията на разпределение на стойността T ще бъде:

(0-3)

Да се ​​намери плътността на разпределение f(t) случайна величина T,необходимо е да се разграничи изразът (0-1) сT:

0-4)

Законът за разпределение с плътност (0-4) се нарича експоненциален (или експоненциален ). Стойността λ се нарича параметър примерен закон.

Фигура 0 - 4 Експоненциално разпределение

Намерете числени характеристики на случайна променлива T- математическо очакване (средна стойност) M[t]=mt , и дисперсия D t . Ние имаме

( 0-5)

(интегриране по части).

Дисперсията на стойността на T е:

(0-6)

Извличайки корен квадратен от дисперсията, намираме стандартното отклонение на случайната променлива T.

И така, за експоненциално разпределение математическото очакване и стандартното отклонение са равни едно на друго и са обратни на параметъра λ, където λ. интензитет на потока.

По този начин външният вид м събития в даден интервал от време съответства на разпределението на Поасон, а вероятността интервалите от време между събитията да бъдат по-малки от някакво предварително определено число съответства на експоненциалното разпределение. Всичко това са просто различни описания на един и същ стохастичен процес.

QS Пример-1 .

Като пример, помислете за банкова система в реално време, обслужваща голям брой клиенти. В пиковите часове заявките от банковите касиери, които работят с клиенти, образуват Поасонов поток и пристигат средно две за 1 s (λ = 2).Потокът се състои от заявки, пристигащи със скорост 2 заявки в секунда.

Изчислете вероятността P ( m) събития m съобщения за 1 сек. Тъй като λ = 2, от предишната формула имаме

Заместване на m = 0, 1, 2, 3, получаваме следните стойности (до четиридесетични знаци):

Фигура 0 - 5 Най-прост пример за поток

Възможни са и повече от 9 съобщения за 1 s, но вероятността за това е много малка (около 0,000046).

Полученото разпределение може да бъде представено като хистограма (показана на фигурата).

Пример за CMO-2.

Устройство (сървър), което обработва три съобщения за 1s.

Нека има оборудване, което може да обработи три съобщения за 1 s (µ=3). Средно две съобщения се получават за 1s и в съответствие° С Поасоново разпределение. Каква част от тези съобщения ще бъдат обработени веднага след получаване?

Вероятността скоростта на пристигане да бъде по-малка или равна на 3 s се дава от

Ако системата може да обработи максимум 3 съобщения за 1 s, тогава вероятността тя да не бъде претоварена е

С други думи, 85,71% от съобщенията ще бъдат обслужени незабавно, а 14,29% с известно закъснение. Както можете да видите, рядко ще се случи забавяне на обработката на едно съобщение за време, по-голямо от времето за обработка на 3 съобщения. Времето за обработка на 1 съобщение е средно 1/3 s. Следователно, забавяне от повече от 1 s ще бъде рядко, което е напълно приемливо за повечето системи.

Пример за CMO 3

· Ако банков касиер е зает през 80% от работното си време, а останалото време прекарва в чакане на клиенти, тогава той може да се счита за устройство с коефициент на използване 0,8.

· Ако комуникационният канал се използва за предаване на 8-битови символи със скорост 2400 bps, т.е. максимум 2400/8 символа се предават за 1 s и ние изграждаме система, в която общото количество данни е 12000 изпратени символа от различни устройства през канал за натоварена минута (включително синхронизация, знаци за край на съобщението, контролни знаци и т.н.), тогава степента на използване на оборудването на комуникационния канал през тази минута е равна на

· Ако механизмът за достъп до файлове в натоварени часове прави 9000 достъпа до файлове и времето за достъп е средно 300 ms, тогава използването на хардуера на механизма за достъп в натоварени часове е

Концепцията за използване на оборудването ще се използва доста често. Колкото по-близо е използването на оборудването до 100%, толкова по-голямо е забавянето и толкова по-дълга е опашката.

Използвайки предишната формула, можете да съставите таблици със стойности на функцията на Поасон, от които можете да определите вероятността да получитем или повече съобщения за даден период от време. Например, ако средно 3,1 съобщения в секунда [т.е. д. λ = 3.1], тогава вероятността за получаване на 5 или повече съобщения за дадена секунда е 0,2018 (зам = 5 в таблицата). Или в аналитична форма

Използвайки този израз, системният анализатор може да изчисли вероятността системата да не отговаря на даден критерий за натоварване.

Често първоначалните изчисления могат да бъдат направени за стойностите на натоварването на оборудването.

p ≤ 0,9

Тези стойности могат да бъдат получени с помощта на таблици на Поасон.

Нека отново средната скорост на пристигане на съобщения λ = 3,1 съобщения/s. От таблиците следва, че вероятността за получаване на 6 или повече съобщения за 1 s е 0,0943. Следователно това число може да се приеме като критерий за натоварване за първоначалните изчисления.

10.6.2. Дизайнерски предизвикателства

С произволния характер на пристигането на съобщения в устройството, последното прекарва част от времето за обработка или обслужване на всяко съобщение, което води до образуването на опашки. Опашката в банката чака освобождаването на касата и неговия компютър (терминал). Опашката от съобщения във входния буфер на компютъра чака да бъде обработена от процесора. Опашката от заявки за масиви от данни чака освобождаване на канали и т.н. Опашки могат да се образуват във всички тесни места на системата.

Колкото по-висока е степента на използване на оборудването, толкова по-дълги са произтичащите опашки. Както ще бъде показано по-долу, възможно е да се проектира система, която работи задоволително с коефициент на използване ρ = 0,7, но коефициент по-голям от ρ > 0,9 може да доведе до лошо качество на услугата. С други думи, ако връзката за групови данни има 20% натоварване, е малко вероятно да има опашка върху нея. Ако се зарежда; е 0,9, тогава по правило ще се образуват опашки, понякога много големи.

Коефициентът на използване на оборудването е равен на съотношението на натоварването на оборудването към максималното натоварване, което това оборудване може да издържи, или е равно на съотношението на времето, през което оборудването е заето, към общото време на неговата работа.

При проектирането на система е обичайно да се оценява коефициентът на използване за различни видове оборудване; съответните примери ще бъдат дадени в следващите глави. Познаването на тези коефициенти ви позволява да изчислите опашките за съответното оборудване.

· Каква е дължината на опашката?

· Колко време ще отнеме?

На въпроси от този тип може да се отговори с помощта на теорията на опашките.

10.6.3. Системи за масово обслужване, техните класове и основни характеристики

За QS потоците от събития са потоци от заявки, потоци от "обслужващи" заявки и т.н. Ако тези потоци не са Поасон (процес на Марков), математическото описание на процесите, протичащи в QS, става несравнимо по-сложно и изисква по-тромав апарат, привеждането му в аналитични формули е възможно само в най-простите случаи.

Въпреки това, апаратът на „Марковската“ теория на опашката може да бъде полезен и в случай, че процесът, протичащ в QS, е различен от този на Марков; с негова помощ могат да се оценят приблизително характеристиките на ефективността на QS. Трябва да се отбележи, че колкото по-сложна е QS, колкото повече обслужващи канали съдържа, толкова по-точни са приблизителните формули, получени с помощта на теорията на Марков. Освен това, в редица случаи, за да се вземат информирани решения за управление на работата на QS, изобщо не е необходимо да имате точни познания за всичките му характеристики, често доста приблизителни, ориентировъчни.

QS се класифицират в системи с:

неуспехи (със загуби). В такива системи заявка, която пристига в момента, когато всички канали са заети, получава "отказ", напуска QS и не участва в по-нататъшния процес на обслужване.

очакване (с опашка). В такива системи заявка, която пристига, когато всички канали са заети, се поставя на опашка и чака, докато един от каналите стане свободен. Когато каналът е свободен, едно от приложенията в опашката се приема за обслужване.

Обслужването (дисциплината на опашката) в система за чакане може да бъде

подреден (заявленията се подават по реда на постъпването им),

· разстроен(приложенията се сервират в произволен ред) или

стек (първо от опашката се избира последното приложение).

Приоритет

о със статичен приоритет

о с динамичен приоритет

(в последния случай априори tet може например да се увеличи с времето за изчакване на заявката).

Системите с опашка са разделени на системи

· с неограничено чакане и

· с ограничени очакване.

В системите с неограничено изчакване всяка заявка, пристигнала в момента, когато няма свободни канали, попада в опашката и "търпеливо" чака освобождаването на канала, който ще я приеме за обслужване. Всяко заявление, получено от CMO, рано или късно ще бъде връчено.

В системи с ограничено изчакване се налагат определени ограничения върху престоя на приложението в опашката. Възможно е да се прилагат тези ограничения

· дължина на опашката (броят на приложенията едновременно в системата на опашката с ограничена дължина на опашката),

· времето, през което приложението остава в опашката (след определен период на престой в опашката, приложението напуска опашката и системата излиза с ограничено време на изчакване),

· общо време, прекарано от приложението в QS

и т.н.

В зависимост от вида на QS, когато се оценява неговата ефективност, могат да се използват определени стойности (показатели за ефективност). Например за QS с откази една от най-важните характеристики на нейната производителност е т.нар абсолютна честотна лентасредният брой заявки, които системата може да обслужи за единица време.

Наред с абсолюта често се разглежда относителна производителност CMO е средният дял на входящите заявки, обслужени от системата (отношението на средния брой заявки, обслужени от системата за единица време, към средния брой заявки, получени през това време).

В допълнение към абсолютната и относителната пропускателна способност при анализа на QS с неуспехи, ние можем, в зависимост от задачата на изследването, да се интересуваме от други характеристики, например:

· среден брой заети канали;

· средно относително време на престой на системата като цяло и на отделен канал

и т.н.

Очакваните QS имат малко по-различни характеристики. Очевидно за QS с неограничено време на изчакване както абсолютната, така и относителната пропускателна способност губят значението си, тъй като всяко искане пристига рано.или по-късно ще бъдат сервирани. За такъв QS важните характеристики са:

· среден брой заявления в опашката;

· среден брой приложения в системата (на опашката и в процес на обслужване);

· средно време за изчакване на заявка на опашката;

· средно време, прекарано от приложение в системата (на опашка и в услуга);

както и други характеристики на очакването.

За QS с ограничено изчакване и двете групи характеристики представляват интерес: както абсолютна, така и относителна пропускателна способност, и характеристики на изчакване.

За да се анализира процесът, протичащ в QS, е важно да се знаят основните параметри на системата: броят на каналите П,интензитет на потока на приложениеλ , производителността на всеки канал (средния брой заявки μ, обслужвани от канала за единица време), условията за формиране на опашката (ограничения, ако има такива).

В зависимост от стойностите на тези параметри се изразяват характеристиките на ефективността на работа на QS.

10.6.4. Формули за изчисляване на QS характеристики за случай на обслужване с едно устройство

Фигура 0 - 6 Модел на система за масово обслужване с опашка

Такива опашки могат да бъдат създадени от съобщения на входа на процесора, чакащи да бъдат обработени. Те могат да възникнат по време на работа на абонатни станции, свързани към многоточков комуникационен канал. По същия начин се образуват опашки от автомобили на бензиностанциите. Ако обаче има повече от един вход към услугата, имаме опашка с много устройства и анализът става по-сложен.

Разгледайте случая на най-простия поток от заявки за услуги.

Целта на теорията за опашката, представена тук, е да се приближи средният размер на опашката, както и средното време, прекарано от съобщения, чакащи в опашка. Също така е желателно да се оцени колко често опашката надвишава определена дължина. Тази информация ще ни позволи да изчислим, например, необходимото количество буферна памет за съхраняване на опашки от съобщения и свързаните с тях програми, необходимия брой комуникационни линии, необходимите размери на буфера за хъбове и т.н. Ще бъде възможно да се оцени времето за реакция.

Всяка от характеристиките варира в зависимост от използваните средства.

Помислете за опашка с един сървър. При проектирането на изчислителна система повечето опашки от този тип се изчисляват с помощта на горните формули.коефициент на вариация на времето за обслужване

Формулата на Хинчин-Полачек се използва за изчисляване на дължините на опашките при проектирането на информационни системи. Използва се в случай на експоненциално разпределение на времето за пристигане за всяко разпределение на времето за обслужване и всяка контролна дисциплина, стига изборът на следващото съобщение за обслужване да не зависи от времето за обслужване.

При проектирането на системи има такива ситуации, когато възникват опашки, когато контролната дисциплина несъмнено зависи от времето за обслужване. Например, в някои случаи може да изберем да използваме първо по-кратки съобщения за обслужване, за да получим по-бързо средно време за обслужване. При управление на комуникационна линия е възможно да се даде по-висок приоритет на входните съобщения, отколкото на изходните, тъй като първите са по-кратки. В такива случаи вече не е необходимо да се използва уравнението на Хинчин

Повечето времена за обслужване в информационните системи се намират някъде между тези два случая. Времената на обслужване, които са постоянни, са редки. Дори времето за достъп до твърдия диск не е постоянно поради различната позиция на масивите от данни на повърхността. Един пример, илюстриращ случая на постоянно време на обслужване, е заемането на комуникационната линия за предаване на съобщения с фиксирана дължина.

От друга страна, разпространението на времето за обслужване не е толкова голямо, колкото в случай на произволно или експоненциално разпределение, т.е.σs рядко достига стойностиt s. Този случай понякога се счита за "най-лошия случай и затова се използват формули, които се отнасят до експоненциалното разпределение на времената за обслужване. Такова изчисление може да даде донякъде надценени размери на опашките и времето за чакане в тях, но тази грешка поне не е опасна.

Експоненциалното разпределение на времето за обслужване със сигурност не е най-лошият случай, с който човек трябва да се сблъска в действителност. Въпреки това, ако времената за обслужване, получени от изчисляването на опашките, се окажат по-лошо разпределени от експоненциално разпределените времена, това често е предупредителен сигнал за разработчика. Ако стандартното отклонение е по-голямо от средната стойност, тогава обикновено има нужда от коригиране на изчисленията.

Помислете за следния пример. Има шест вида съобщения с времена на обслужване 15, 20, 25, 30, 35 и 300. Броят на съобщенията за всеки тип е еднакъв. Стандартното отклонение на тези времена е малко по-високо от средната им стойност. Последната стойност на времето за обслужване е много по-голяма от останалите. Това ще накара съобщенията да бъдат в опашката много по-дълго, отколкото ако времето за обслужване е от същия ред. В този случай при проектирането е препоръчително да се вземат мерки за намаляване на дължината на опашката. Например, ако тези числа са свързани с дължините на съобщенията, тогава може би много дългите съобщения трябва да бъдат разделени на части.

10.6.6. Пример за изчисление

При проектирането на банкова система е желателно да се знае броят на клиентите, които ще трябва да чакат на опашка за един касиер в пиковите часове.

Времето за реакция на системата и нейното стандартно отклонение се изчисляват, като се вземе предвид времето за въвеждане на данни от работната станция, печат и обработка на документи.

Действията на касиерката били премерени. Времето за обслужване ts е равно на общото време, прекарано от касиера на клиента. Коефициентът на използване на касата ρ е пропорционален на времето на неговата работа. Ако λ е броят на клиентите в пиковите часове, тогава ρ за касата е

Да кажем, че има 30 клиенти на час в пиковите часове. Средно един касиер отделя 1,5 минути на клиент. Тогава

ρ = (1,5 * 30) / 60 = 0,75

т.е. касата се използва на 75%.

Броят на хората на опашката може бързо да се оцени с помощта на графики. От тях следва, че ако ρ = 0,75, тогава средният брой хора nqна линия на касата е между 1,88 и 3,0 в зависимост от стандартното отклонение за t s .

Да приемем, че измерването на стандартното отклонение за tс даде стойност от 0,5 min. Тогава

σ s = 0,33 t s

От графиката на първата фигура намираме, че nq = 2,0, т.е. средно двама клиенти ще чакат на касата.

Общото време, прекарано от клиента на касата, може да се намери като

t ∑ = t q + t s = 2,5 минути + 1,5 минути = 4 минути

където t s се изчислява по формулата на Хинчин-Полачек.

10.6.7. коефициент на усилване

Анализирайки кривите на фигурите, виждаме, че когато оборудването, обслужващо опашката, се използва повече от 80%, кривите започват да растат с тревожна скорост. Този факт е много важен при проектирането на системи за предаване на данни. Ако проектираме система с повече от 80% използване на хардуера, тогава леко увеличение на трафика може да доведе до драстичен спад в производителността на системата или дори да причини срив.

Увеличение на входящия трафик с малък брой x%. води до увеличаване на размера на опашката с приблизително

Ако степента на използване на оборудването е 50%, тогава това увеличение е равно на 4ts% за експоненциалното разпределение на времето за обслужване. Но ако използването на оборудването е 90%, тогава увеличението на размера на опашката е 100ts%, което е 25 пъти повече. Леко увеличение на натоварването при 90% използване на оборудването води до 25-кратно увеличение на размера на опашката в сравнение със случая на 50% използване на оборудването.

По същия начин времето на опашката се увеличава с

При експоненциално разпределено време на обслужване тази стойност има стойност 4 t s2 за натоварване на оборудването равно на 50% и 100 т s2 за коефициент 90%, т.е. отново 25 пъти по-зле.

В допълнение, за малки коефициенти на използване на оборудването, ефектът от промените в σs върху размера на опашката е незначителен. Въпреки това, за големи коефициенти, промяната σс значително влияе върху размера на опашката. Следователно, когато се проектират системи с високо използване на оборудването, е желателно да се получи точна информация за параметъраσ с. Неточност на предположението относно експоненциалността на разпределението на tсе най-забележимо при големи стойности на ρ. Освен това, ако времето за обслужване внезапно се увеличи, което е възможно в комуникационните канали при предаване на дълги съобщения, тогава в случай на голямо ρ се образува значителна опашка.

Доста често, когато се анализират икономическите системи, се налага да се решават така наречените проблеми с опашката, които възникват в следната ситуация. Нека се анализира системата за поддръжка на автомобили, състояща се от определен брой станции с различен капацитет. На всяка станция (системен елемент) могат да възникнат поне две типични ситуации:

1. броят на приложенията е твърде голям за тази станция, има опашки и трябва да плащате за забавяне на услугата;
2. станцията получава твърде малко заявки и сега вече е необходимо да се вземат предвид загубите, причинени от престой на станцията.

Ясно е, че целта на системния анализ в този случай е да се определи някаква връзка между загубите на приходи поради опашкии загуби поради само азстанции.

Теория на опашките– специален раздел от теорията на системите е раздел от теорията на вероятностите, в който системите за масово обслужване се изучават с помощта на математически модели.

Система за опашка (QS)- това е модел, който включва: 1) произволен поток от изисквания, обаждания или клиенти, нуждаещи се от услуга; 2) алгоритъма за изпълнение на тази услуга; 3) канали (устройства) за поддръжка.

Примери за CMO са каси, бензиностанции, летища, търговци, фризьори, лекари, телефонни централи и други съоръжения, които обслужват определени приложения.

Проблем с теорията на опашкатасе състои в разработване на препоръки за рационално изграждане на QS и рационална организация на тяхната работа, за да се осигури висока ефективност на обслужването при оптимални разходи.

Основната характеристика на проблемите от този клас е очевидната зависимост на резултатите от анализа и получените препоръки от два външни фактора: честотата на получаване и сложността на поръчките (и следователно времето на тяхното изпълнение).

Предметът на теорията на опашките е да установи връзката между характера на потока от заявки, производителността на отделен обслужващ канал, броя на каналите и ефективността на обслужването.

Като QS характеристикиразглеждан:

• средният процент заявления, които са отхвърлени и оставят системата необслужена;
• средно време на престой на отделни канали и системата като цяло;
• средно време на чакане на опашка;
• вероятността полученото заявление да бъде незабавно обслужено;
• закон за разпределение на дължината на опашката и други.

Добавяме, че заявките (изискванията) влизат в QS произволно (в произволни моменти), с точки на кондензация и разреждане. Времето за обслужване за всяка заявка също е произволно, след което каналът за обслужване се освобождава и е готов да изпълни следващата заявка. Всеки QS, в зависимост от броя на каналите и тяхната производителност, има определен капацитет. SMO пропускателна способностможе би абсолютен(среден брой заявления, обслужени за единица време) и роднина(средно отношение на броя обслужени заявления към броя на подадените).

3.1 Модели на системи за масово обслужване.

Всяка QS може да се характеризира с израза: (а б В Г Д Е) , където

а - разпределение на входния поток от приложения;

b - разпределение на изходящия поток от приложения;

° С – конфигурация на сервизния механизъм;

д – дисциплина на опашката;

д – чакащ блок;

f е капацитетът на източника.

Сега нека разгледаме по-отблизо всяка функция.

Входящ поток от приложения- броя на заявления, получени от системата. Характеризира се с интензивността на входящия поток л.

Изходен поток от приложения– броя на приложенията, обслужвани от системата. Характеризира се с интензивността на изходящия поток м.

системна конфигурацияпредполага общия брой канали и обслужващи възли. SMO може да съдържа:

1. един каналуслуги (една писта, един доставчик);
2. един канал за обслужване, включително множество серийни възли(столова, клиника, конвейер);
3. няколко подобни каналауслуги, свързани паралелно (бензиностанции, информационно бюро, ж.п. гара).

По този начин могат да се разграничат едно- и многоканални QS.

От друга страна, ако всички обслужващи канали в QS са заети, тогава приближеното приложение може да остане в опашката или да напусне системата (например спестовна банка и телефонна централа). В този случай говорим за системи с опашка (изчакване) и системи с откази.

Завъртетее набор от приложения, които са влезли в системата за обслужване и очакват обслужване. Опашката се характеризира с дължината на опашката и нейната дисциплина.

Дисциплина на опашкатае правилото за обслужване на заявки от опашката. Основните видове опашки включват следното:

1. PERPPO (първи дошъл, първи обслужен) е най-често срещаният тип;
2. POSPPO (дошъл последен - първи обслужен);
3. SOP (произволен избор на приложения) - от базата данни.
4. PR - приоритетно обслужване.

Дължина на опашкатаможе би

• неограничен - тогава се говори за система с чисто очакване;
• равно на нула - тогава се говори за система с повреди;
• ограничена по дължина (система от смесен тип).

чакащ блок– "капацитет" на системата - общият брой заявки в системата (на опашка и на обслужване). По този начин, e=c+д.

Капацитет на източникакойто генерира заявки за услуги, е максималният брой заявки, които могат да влязат в QS. Например на летище капацитетът на източника е ограничен от броя на всички съществуващи самолети, а капацитетът на източника на телефонна централа е равен на броя на жителите на Земята, т.е. може да се счита за неограничен.

Броят на QS моделите съответства на броя на възможните комбинации от тези компоненти.

3.2 Входящ поток от изисквания.

С всеки отрязък от време а, а+ T ], нека асоциираме случайна променлива х, равен на броя заявки, получени от системата за времето T.

Потокът от заявки се извиква стационарен, ако законът за разпределение не зависи от началната точка на интервала а, но зависи само от дължината на дадения интервал T. Например потокът от приложения към телефонната централа през деня ( T\u003d 24 часа) не може да се счита за неподвижен, но от 13 до 14 часа ( T\u003d 60 минути) - можете.

Потокът се нарича няма последействие, ако историята на потока не влияе върху получаването на изисквания в бъдеще, т.е. изискванията са независими едно от друго.

Потокът се нарича обикновени, ако не повече от една заявка може да влезе в системата за много кратък период от време. Например потокът към фризьора е обикновен, но не и към службата по вписванията. Но ако като случайна променлива хпомислете за двойки приложения, пристигащи в службата по вписванията, тогава такъв поток ще бъде обикновен (т.е. понякога извънреден поток може да бъде намален до обикновен).

Потокът се нарича най-простият, ако е стационарен, без последействие и обикновен.

Основна теорема.Ако потокът е най-простият, тогава r.v. X [ a . а + T] се разпределя по закона на Поасон, т.е. .

Следствие 1. Най-простият поток се нарича още поток на Поасон.

Следствие 2. М(х)= М(Х [ а , а + T ] )= лT, т.е. по време на T лTприложения. Следователно за една единица време системата получава средно лприложения. Тази стойност се нарича интензивноствходен поток.

Помислете за ПРИМЕР .

Студиото получава средно по 3 заявки на ден. Ако приемем, че потокът е най-простият, намерете вероятността броят на заявките да бъде поне 5 през следващите два дни.

Решение.

Според задачата, л=3, T=2 дни, входен поток на Поасон, н ³5. при решаването е удобно да се въведе обратното събитие, което се състои в това, че през времето Tще бъдат получени по-малко от 5 заявления. Следователно, според формулата на Поасон, получаваме

^

3.3 Състояние на системата. Матрица и графика на преходите.

В случаен момент QS преминава от едно състояние в друго: променя се броят на заетите канали, броят на заявките и опашките и т.н.. Така QS с нканали и дължина на опашката, равна на м, може да бъде в едно от следните състояния:

д 0 – всички канали са безплатни;

д 1 – един канал е зает;

д н– всички канали са заети;

д н +1 – всички канали са заети и една заявка е на опашката;

д н + м– всички канали и всички места в опашката са заети.

Подобна система с повреди може да бъде в държави д 0 – д н .

За QS с чисто очакване има безкраен набор от състояния. По този начин, състояние д н QS по време T е количеството н приложения (изисквания), които са в системата в даден момент, т.е. н= н(T) - произволна стойност, д н (T) са резултатите от тази случайна променлива и П н (T) е вероятността системата да е в състояние д н .

Вече сме запознати със състоянието на системата. Имайте предвид, че не всички състояния на системата са еквивалентни. Състоянието на системата се нарича източникако системата може да излезе от това състояние, но не може да се върне към него. Състоянието на системата се нарича изолиран,ако системата не може да излезе или да влезе в това състояние.

За визуализиране на изображенията на състоянията на системата се използват диаграми (така наречените графики на прехода), в които стрелките показват възможните преходи на системата от едно състояние в друго, както и вероятностите за такива преходи.

Фигура 3.1 - графика на прехода

Comp.	E 0	Е 1	Е 2
E 0	Р 0,0	Р 0,1	Р 0,2
Е 1	P 1.0	R 1.1	R 1.2
Е 2	R 2.0	R 2.2	R 2.2

Също така понякога е удобно да се използва преходната матрица. В този случай първата колона означава началните състояния на системата (текущи), а след това са дадени вероятностите за преход от тези състояния към други.

Тъй като системата задължително ще премине от един

състояние към друго, тогава сумата от вероятностите във всеки ред винаги е равна на единица.

3.4 Едноканален QS.

3.4.1 Едноканална QS с повреди.

Ще разгледаме системи, които отговарят на изискванията:

(P/E/1):(–/1/¥) . Нека приемем също, че времето за обслужване на клиент не зависи от броя на клиентите, влизащи в системата. Тук и по-долу "P" означава, че входният поток е разпределен съгласно закона на Поасон, т.е. най-простият, "E" означава, че изходящият поток се разпределя експоненциално. Също така тук и по-долу основните формули са дадени без доказателство.

За такава система са възможни две състояния: д 0 - системата е безплатна и д 1 – системата е заета. Нека създадем матрица на прехода. Да вземем дTе безкрайно малко време. Нека събитието А се състои в това, че в системата през времето дTполучи една заявка. Събитие Б се състои в това, че през времето дTе обслужена една заявка. Събитие НО аз , к- по време на дTсистемата ще премине от състояние д азв състояние д к. защото ле интензитетът на входния поток, след това през времето дTвлиза в системата средно l*DTизисквания. Тоест вероятността за получаване на едно вземане P(A)=л* дT, и вероятността от обратното събитие Р(А)=1-l*DT.P(B)=Е(дT)= П(b< д T)=1- д - м д T = м дT- вероятността за обслужване на заявката в срок дT. След това A 00 - заявлението няма да бъде получено или ще бъде получено, но ще бъде връчено. A 00 \u003d Ā + A * V. R 00 \u003d 1 - l*DT. (взехме предвид това (дT) 2 е безкрайно малка стойност)

A 01 - заявлението ще бъде получено, но няма да бъде връчено. A 01 = A * . R 01 = l*DT.

И 10 - заявлението ще бъде обслужено и няма да има ново. A 10 \u003d B * а. R 10 = м*ДT.

И 11 - заявлението няма да бъде връчено или ще пристигне ново, което все още не е връчено. A 11 = +V * A. R 01 = 1- м*ДT.

Така получаваме матрицата на прехода:

Comp.	E 0	Е 1
E 0	1-л * Dt	л * Dt
Е 1	м * Dt	1-м * Dt

Вероятност за прекъсване и повреда на системата.

Нека сега намерим вероятността системата да е в състояние д 0 по всяко време T(тези. Р 0 ( T) ). Функционална графика
показано на фигура 3.2.

Асимптотата на графиката е права линия
.

Очевидно от някакъв момент T,

1

Фигура 3.2

Най-накрая разбираме това
и
, където Р 1 (T) е вероятността, че в даден момент T системата е заета (т.е. е в състояние д 1 ).

Очевидно в началото на работата на QS протичащият процес няма да бъде стационарен: това ще бъде „преходен“, нестационарен режим. След известно време (което зависи от интензивността на входните и изходните потоци) този процес ще изчезне и системата ще премине в стационарно стабилно състояние на работа, а вероятностните характеристики вече няма да зависят от времето.

Стационарен режим на работа и фактор на натоварване на системата.

Ако вероятността системата да е в състояние д к, т.е. Р к (T), не зависи от времето T, тогава казват, че QS е установил стационарен режимработа. В същото време стойността
Наречен фактор на натоварване на системата(или намалената плътност на потока от приложения). След това за вероятностите Р 0 (T) и Р 1 (T) получаваме следните формули:
,
. Можете също да заключите: колкото по-голям е коефициентът на натоварване на системата, толкова по-вероятно е системата да се повреди (т.е. вероятността системата да е заета).

Автомивката разполага с едно звено за поддръжка. Автомобилите пристигат в разпределение на Поасон със скорост 5 автомобила/час. Средното време за обслужване на един автомобил е 10 минути. Намерете вероятността приближаващата кола да намери системата заета, ако QS е в стационарен режим.

Решение.Според задачата, л=5, м г =5/6. Трябва да намерим вероятността Р 1 е вероятността от повреда на системата.
.

3.4.2 Едноканален QS с неограничена дължина на опашката.

Ще разгледаме системи, които отговарят на изискванията: (Р/Е/1):(d/¥/¥). Системата може да бъде в едно от състоянията д 0 , …, д к, … Анализът показва, че след известно време такава система започва да работи в стационарен режим, ако интензитетът на изходящия поток надвишава интензитета на входния поток (т.е. коефициентът на натоварване на системата е по-малък от единица). Като вземем предвид това условие, получаваме системата от уравнения

решавайки което откриваме, че . По този начин, при условие че г<1, получим
накрая
и
е вероятността QS да бъде в състоянието д кв произволен момент от време.

Средни характеристики на системата.

Поради неравномерно постъпване на заявки в системата и колебания във времето за обслужване, в системата се образува опашка. За такава система можете да проучите:

• н – броя на изискванията в QS (на опашката и в услуга);
• v – дължина на опашката;
• w – време на изчакване за начало на услугата;
• w 0 е общото време, прекарано в системата.

Ще ни е интересно средни характеристики(т.е. вземаме математическото очакване на разглежданите случайни променливи и помним, че г<1).

е средният брой приложения в системата.

е средната дължина на опашката.

е средното време на изчакване за стартиране на услугата, т.е. време за чакане на опашка.

- средното време, което приложението прекарва в системата - на опашка и за обслужване.

На автомивката има един сервизен блок и има място за опашка. Автомобилите пристигат в разпределение на Поасон със скорост 5 автомобила/час. Средното време за обслужване на един автомобил е 10 минути. Намерете всички средни QS характеристики.

Решение. л=5, м=60min/10min = 6. Фактор на натоварване г =5/6. След това средният брой коли в системата
, средна дължина на опашката
, средното време на изчакване за стартиране на услугата
часа = 50 минути и накрая средното време, прекарано в системата
час.

3.4.3 Едноканална QS от смесен тип.

Да предположим, че дължината на опашката е мизисквания. След това, за всеки с£ м, вероятността за намиране на QS в състоянието д 1+ с, се изчислява по формулата
, т.е. едно приложение се обслужва и друго сприложенията са на опашката.

Вероятността от прекъсване на системата е
,

и вероятността от повреда на системата е
.

Дадени са три едноканални системи за всяка л=5, м =6. Но първата система е с откази, втората е с чисто изчакване, а третата е с ограничена дължина на опашката, м=2. Намерете и сравнете вероятностите за прекъсване на тези три системи.

Решение.Коефициент на натоварване на всички системи г=5/6. За система с повреди
. За система с чисто очакване
. За система с ограничена дължина на опашката
. Изводът е очевиден: колкото повече приложения са в опашката, толкова по-малка е вероятността от прекъсване на системата.

3.5 Многоканален QS.

3.5.1 Многоканален QS с повреди.

Ще разгледаме системите (Р/Е/s):(-/s/¥) при предположението, че времето за обслужване не зависи от входния поток и всички линии работят независимо. Многоканалните системи, в допълнение към коефициента на натоварване, могат да се характеризират и с коефициента
, където с– брой канали за обслужване. Изследвайки многоканален QS, получаваме следните формули (формули на Erlang) за вероятността системата да бъде в състояние д кв случаен момент:

, k=0, 1, …

функция на разходите.

Както при едноканалните системи, увеличаването на коефициента на натоварване води до увеличаване на вероятността от повреда на системата. От друга страна, увеличаването на броя на обслужващите линии води до увеличаване на вероятността от прекъсване на системата или отделни канали. Следователно е необходимо да се намери оптималният брой обслужващи канали за тази QS. Средният брой безплатни обслужващи линии може да се намери по формулата
. Нека въведем C( с) – функция на разходите QS в зависимост от с 1 – цената на един отказ (неустойка за неизпълнена заявка) и от с 2 - разходите за престой на една линия за единица време.

За да намерите оптималната опция, трябва да намерите (и това може да се направи) минималната стойност на функцията на разходите: ОТ(с) = с 1* л * стр с +c 2*, чиято графика е показана на фигура 3.3:

Фигура 3.3

Търсенето на минималната стойност на функцията на разходите е, че първо намираме нейните стойности с =1, след това за с =2, след това за с =3 и т.н. докато на дадена стъпка стойността на функцията С( с) няма да бъде по-голям от предишния. Това означава, че функцията е достигнала своя минимум и е започнала да расте. Отговорът е броят на каналите за обслужване (стойност с), за които функцията на разходите е минимална.

ПРИМЕР .

Колко сервизни линии трябва да съдържат QS с повреди, ако л\u003d 2reb / ​​​​час, м\u003d 1reb / ​​​​час, наказанието за всеки отказ е 7 хиляди рубли, цената на престой за една линия е 2 хиляди рубли. след час?

Решение. г = 2/1=2. с 1 =7, с 2 =2.

Да приемем, че QS има два обслужващи канала, т.е. с =2. Тогава
. Следователно, C(2) = c 1 *л*стр 2 +c 2 *(2- y*(1-р 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Нека се преструваме, че с =3. Тогава
, C(3) = c 1 *л*стр 3 +c 2 *
=5.79.

Да приемем, че има четири канала, т.е. с =4. Тогава
,
, C(4) = c 1 *л*стр 4 +c 2 *
=5.71.

Да приемем, че QS има пет обслужващи канала, т.е. с =5. Тогава
, C(5) = 6,7 - повече от предишната стойност. Следователно оптималният брой канали за обслужване е четири.

3.5.2 Многоканален QS с опашка.

Ще разгледаме системите (Р/Е/s):(d/d+s/¥) при предположението, че времето за обслужване не зависи от входния поток и всички линии работят независимо. Ще кажем, че системата е инсталирана стационарна работа, ако средният брой входящи рекламации е по-малък от средния брой обслужени рекламации по всички линии на системата, т.е. л

P(w>0) е вероятността да изчакате услугата да започне,
.

Последната характеристика позволява решаването на проблема за определяне на оптималния брой канали за обслужване по такъв начин, че вероятността да се изчака началото на услугата е по-малка от даден брой. За да направите това, достатъчно е да изчислите последователно очакваната вероятност за с =1, с =2, с=3 и т.н.

ПРИМЕР .

SMO - станция за линейка на малък микрорайон. л=3 обаждания на час и м= 4 разговора на час за един екип. Колко екипажа трябва да има на станцията, така че вероятността да изчакате изход да е по-малка от 0,01?

Решение.Коефициент на натоварване на системата г =0,75. Да приемем, че има два налични отбора. Нека намерим вероятността да изчакаме услугата да започне в с =2.
,
.

Да предположим, че има три бригади, т.е. с=3. Според формулите получаваме това Р 0 =8/17, P(w>0)=0.04>0.01 .

Да приемем, че на станцията има четири екипажа, т.е. с=4. Тогава разбираме това Р 0 =416/881, P(w>0)=0.0077<0.01 . Следователно на гарата трябва да има четири бригади.

3.6 Въпроси за самоконтрол

1. Предмет и задачи на теорията на масовото обслужване.
2. QS, техните модели и обозначения.
3. Поток за въвеждане на изисквания. Интензитетът на входящия поток.
4. Състояние на системата. Матрица и графика на преходите.
5. Едноканален QS с повреди.
6. Едноканален QS с опашка. Характеристики.
7. Стационарен режим на работа. Коефициент на натоварване на системата.
8. Многоканален QS с повреди.
9. Оптимизиране на функцията на разходите.
10. Многоканален QS с опашка. Характеристики.

3.7 Упражнения за самостоятелна работа

1. Снек барът на бензиностанцията разполага с един гише. Автомобилите пристигат според разпределението на Поасон, със средно 2 автомобила на 5 минути. Средно 1,5 минути са достатъчни за изпълнение на поръчка, въпреки че продължителността на услугата се разпределя по експоненциален закон. Намерете: а) вероятността сергията да не работи; б) средно представяне; в) вероятността броят на пристигащите автомобили да бъде поне 10.
2. Рентгеновата машина ви позволява да изследвате средно 7 души на час. Интензивността на посетителите е 5 човека на час. При стационарна работа, определете средните характеристики.
3. Времето за обслужване в QS се подчинява на експоненциален закон,
   м = 7 изисквания на час. Намерете вероятността а) времето за обслужване да е между 3 и 30 минути; б) рекламацията ще бъде връчена в рамките на един час. Използвайте таблицата със стойности на функцията д х .
4. В речното пристанище има една котвена стоянка, интензивността на входящия поток е 5 кораба на ден. Интензивността на товаро-разтоварните операции е 6 кораба на ден. Имайки предвид стационарния режим на работа, определете всички средни характеристики на системата.
5. л=3, м=2, наказанието за всеки отказ е 5, а разходите за престой на линия са 2?
6. Какъв е оптималният брой канали за обслужване, които QS трябва да има, ако л=3, м =1, наказанието за всеки отказ е 7, а разходите за престой на линия са 3?
7. Какъв е оптималният брой канали за обслужване, които QS трябва да има, ако л=4, м=2, наказанието за всеки отказ е 5, а разходите за престой на линия са 1?
8. Определете броя на пистите за самолети, при спазване на изискването вероятността за изчакване да бъде по-малка от 0,05. В същото време интензивността на входния поток е 27 самолета на ден, а интензивността на тяхното обслужване е 30 самолета на ден.
9. Колко еквивалентни независими конвейерни линии трябва да има един цех, за да осигури ритъма на работа, при който вероятността за изчакване на обработката на продуктите трябва да бъде по-малка от 0,03 (всеки продукт се произвежда от една линия). Известно е, че интензивността на получаване на поръчки е 30 продукта на час, а интензивността на обработка на продукт в една линия е 36 продукта на час.
10. Непрекъсната случайна величина X е разпределена по експоненциален закон с параметър l=5. Намерете функцията на разпределение, характеристиките и вероятността за попадение в r.v. X в диапазона от 0,17 до 0,28.
11. Средният брой повиквания, пристигащи в телефонната централа за една минута, е 3. Ако приемем, че потокът е Поасон, намерете вероятността след 2 минути да има: а) две повиквания; б) по-малко от две обаждания; в) поне две обаждания.
12. В кутия има 17 части, 4 от които са дефектни. Монтажникът тегли 5 части на случаен принцип. Намерете вероятността а) всички извлечени части да са с високо качество; б) сред извлечените части 3 дефектни.
13. Колко канала трябва да има QS с повреди, ако л\u003d 2reb / ​​​​час, м\u003d 1reb / ​​​​час, наказанието за всеки отказ е 8 хиляди рубли, цената на престой за една линия е 2 хиляди рубли. след час?

1. Едноканален QS с повреди.

Пример.Нека едноканална QS с повреди представлява една дневна сервизна станция (OD) за измиване на автомобили. Приложението - кола, пристигнала в момент, когато постът е зает - е отказан сервиз.

Дебит на превозното средство = 1,0 (превозно средство на час).

Средното време за обслужване е 1,8 часа.

Автомобилният поток и сервизният поток са най-простите.

Задължително за дефиниранев стационарни гранични стойности:

Относителна честотна лента р;

Абсолютна честотна лента НО ;

Вероятности за провал P отворено.

Трябва да се сравни действителен QS пропускателна способност с номинален, което би било, ако всяка кола беше обслужена точно 1,8 часа и колите следваха една след друга без почивка.

2. Едноканален QS с изчакване

Характеристика на системата

Ø SMO има един канал.

Ø Входящият поток от заявки за услуга е най-простият поток с интензивност.

Ø Интензитетът на обслужвания поток е равен на m (т.е. средно непрекъснато зает канал ще издаде m обслужени заявки).

Ø Продължителността на услугата е случайна променлива, предмет на експоненциален закон за разпределение.

Ø Сервизният поток е най-простият Поасонов поток от събития.

Ø Заявката, получена в момента, когато каналът е зает, попада в опашката и чака обслужване.

Графика на състоянието

QS състоянията имат следното тълкуване:

С 0 - "каналът е безплатен";

С 1 - "каналът е зает" (няма опашка);

С 2 - "каналът е зает" (едно приложение е в опашката);

…………………………………………………….

сн- "каналът е зает" ( н-1 заявки са на опашка);

SN- "каналът е зает" ( н- 1 заявки са на опашката).

Стационарният процес в тази система се описва със следната система от алгебрични уравнения:

Решението на системата от уравнения е:

3. Едноканален QS с ограничена опашка.

Дължина на опашката :( н - 1)

Характеристики на системата:

1. Вероятност за отказ на обслужване на системата:

2. Относителна производителност на системата:

3. Абсолютна производителност на системата:

4. Среден брой приложения в системата:

5. Средно време на престой на приложение в системата:

6. Средна продължителност на престоя на клиента (заявлението) на опашката:

7. Среден брой заявки (клиенти) на опашката (дължина на опашката):

Пример.

Специализиран диагностичен пост е едноканален QS.

Броят на паркингите за чакащи за диагностика автомобили е ограничен и равен на 3 [( н- 1) = 3]. Ако всички паркоместа са заети, т.е. вече има три коли на опашката, тогава следващата кола, пристигнала за диагностика, не попада в сервизната опашка.

Потокът от автомобили, пристигащи за диагностика, се разпределя по закона на Поасон и е с интензитет 0,85 (автомобили на час).

Времето за диагностика на автомобила е разпределено по експоненциалния закон и е средно 1,05 часа.

4. Едноканален QS с изчакване

без ограничение на дължината на опашката

Условията за функциониране на QS остават непроменени, като се има предвид, че N .

Стационарният режим на работа на такава QS съществува:

за всеки н= 0, 1, 2, ... и кога λ < μ .

Системата от уравнения, описваща работата на QS:

Решението на системата от уравнения има формата:

2. Средна продължителност на престой на клиент в системата:

3. Среден брой клиенти в опашката за обслужване:

4. Средна продължителност на престоя на клиента на опашката:

Пример.

Специализиран диагностичен пост е едноканален QS. Броят на паркингите за чакащи за диагностика автомобили не е ограничен. Потокът от автомобили, пристигащи за диагностика, се разпределя по закона на Поасон и е с интензитет λ = 0,85 (автомобили на час). Времето за диагностика на автомобила е разпределено по експоненциалния закон и е средно 1,05 часа.

Необходимо е да се определят вероятностните характеристики на диагностичен пост, работещ в стационарен режим.

В резултат на решаването на проблема е необходимо да се определят крайните стойности на следните вероятностни характеристики:

ü вероятности за състояния на системата (диагностичен пост);

ü среден брой автомобили в системата (в услуга и на опашка);

ü средната продължителност на престоя на автомобила в системата (в сервиз и на опашка);

ü среден брой автомобили в сервизната опашка;

средната продължителност на времето, което една кола прекарва на опашка.

1. Параметър на сервизния поток и намалената интензивност на автомобилния поток:

μ = 0,952; ψ = 0,893.

2. Ограничаващи вероятности за състоянието на системата:

П 0 (T) определя частта от времето, през което диагностичният пост е принуден да бъде неактивен (неактивен). В примера този дял е 10,7%, тъй като П 0 (T) = 0,107.

3. Среден брой автомобили в системата

(в експлоатация и на линия):

4. Средна продължителност на престой на клиент в системата

5. Среден брой автомобили в сервизната опашка:

6. Средна продължителност на престоя на автомобила на опашката:

7. Относителна производителност на системата:

р= 1, т.е. всяка заявка, която влезе в системата, ще бъде обслужена.

8. Абсолютна честотна лента:

Презентационният дизайн на материала е представен във файла "TMO"

Въпроси и задачи

(според Афанасиев М.Ю.)

Въпрос 1.Един работник поддържа тридесет стана, като гарантира, че те започват след скъсване на конеца. Моделът на такава система за масово обслужване може да се характеризира като:

1) многоканален еднофазен с ограничена популация;

2) едноканален еднофазен с неограничено население;

3) едноканален многофазен с ограничена популация;

4) едноканален еднофазен с ограничена популация;

5) многоканален еднофазен с неограничено население.

Въпрос 2.В теорията на опашката, за да се опише най-простият поток от заявки, пристигащи на входа на системата, се използва вероятностното разпределение:

1) нормално;

2) експоненциален;

3) Поасон;

4) бином;

Въпрос 3.В теорията на опашките се приема, че броят на клиентите в популацията е:

1) фиксирани или променливи;

2) ограничено или неограничено;

3) известни или неизвестни;

4) случаен или детерминиран;

5) нищо от горното не е вярно.

Въпрос 4.Двата основни параметъра, които определят конфигурацията на системата за масово обслужване са:

1) процент на получаване и процент на обслужване;

2) дължина на опашката и правило за обслужване;

3) разпределение на времето между приложенията и разпределение на времето за обслужване;

4) броя на каналите и броя на фазите на обслужване;

5) нищо от горното не е вярно.

Въпрос 5.В теорията на опашките обикновено се използва вероятностно разпределение, за да се опише времето, изразходвано за обслужване на заявки:

1) нормално;

2) експоненциален;

3) Поасон;

4) бином;

5) нищо от горното не е вярно.

Въпрос 6.Ремонт на повредени компютри в Стопански факултет се извършва от трима специалисти, работещи едновременно и независимо един от друг. Моделът на такава система за масово обслужване може да се характеризира като:

1) многоканален с ограничено население;

2) едноканален с неограничено население;

3) едноканален с ограничена популация;

4) едноканален с ограничена опашка;

5) многоканален с неограничено население.

Отговори на въпроси: 1 -4, 2 - 3, 3 -2, 4 -4, 5 -2, 6 -1.

МРЕЖОВО ПЛАНИРАНЕ И УПРАВЛЕНИЕ

Системите за мрежово планиране и управление (SPU) са специален вид организирани системи за управление, предназначени да регулират производствените дейности на екипи. Както и в други системи от този клас, „обектът на управление” в STC системите е екип от изпълнители, които разполагат с определени ресурси: човешки, материални, финансови. Тези системи обаче имат редица характеристики, тъй като тяхната методологична основа са методите за изследване на операциите, теорията на насочените графи и някои раздели на теорията на вероятностите и математическата статистика. Необходимо свойство на системата за планиране и управление е и способността да се оцени текущото състояние, да се предвиди по-нататъшното протичане на работата и по този начин да се повлияе на хода на подготовката и производството, така че цялата гама работа да бъде завършена навреме и с най-ниски разходи .

Понастоящем моделите и методите на STC се използват широко при планиране и изпълнение на строително-монтажни работи, планиране на търговски дейности, съставяне на счетоводни отчети, разработване на търговски и финансов план и др.

Обхватът на приложение на SPM е много широк: от задачи, свързани с дейността на отделни хора, до проекти, включващи стотици организации и десетки хиляди хора (например развитието и създаването на голям териториално-промишлен комплекс).

За да се състави работен план за изпълнението на големи и сложни проекти, състоящи се от хиляди отделни изследвания и операции, е необходимо той да бъде описан с помощта на някакъв математически модел. Такъв инструмент за описание на проекти (комплекси) е мрежов модел.