Аналитични модели на системи за масово обслужване. За малък?t може да се получи приблизителна формула, получена чрез заместване на функцията e-Xt само с два члена на разширение на степени на?t, тогава вероятността за постигане на малък период от време?t е поне едно

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

QS предполага, че има типични пътеки(обслужващи канали), през които те преминават в процеса на обработка приложения. Обикновено се казва, че приложенията обслуженканали. Каналите могат да бъдат различни по предназначение, характеристики, могат да се комбинират в различни комбинации; приложенията може да са в опашки, чакащи обслужване. Някои приложения може да се обслужват от канали, докато други може да откажат това. Важно е заявките от гледна точка на системата да са абстрактни: те са нещо, което иска да бъде обслужено, тоест да премине по определен път в системата. Каналите също са абстракция: те обслужват заявки.

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

Примери за ООП (вж. таблица 30.1) включват: автобусен маршрут и превоз на пътници; производствен конвейер за обработка на детайли; ескадрила от самолети, летящи на чужда територия, която се „обслужва“ от зенитни оръдия за противовъздушна отбрана; цевта и рога на картечницата, които "обслужват" патроните; електрически заряди, движещи се в някакво устройство и др.

Но всички тези системи са комбинирани в един клас QS, тъй като подходът към тяхното изследване е един и същ. Състои се във факта, че първо с помощта на генератор на произволни числа се теглят произволни числа, които симулират СЛУЧАЙНИТЕ моменти на появата на поръчките и времето на тяхното обслужване в каналите. Но взети заедно, тези произволни числа, разбира се, са подчинени статистическимодели.

Например, нека се каже: „средно приложенията пристигат в размер на 5 броя на час“. Това означава, че времената между пристигането на две съседни заявки са произволни, например: 0.1; 0,3; 0,1; 0,4; 0.2, както е показано на фиг. 30.1, но общо те дават средно 1 (обърнете внимание, че в примера това не е точно 1, а 1.1 - но в друг час тази сума например може да бъде равна на 0.9); но само за доста дълго времесредната стойност на тези числа ще стане близо до един час.

Резултатът (например пропускателна способност на системата), разбира се, също ще бъде случайна променлива на отделни интервали от време. Но измерена за дълъг период от време, тази стойност средно ще съответства на точното решение. Тоест, за да се характеризира QS, човек се интересува от отговори в статистически смисъл.

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

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

Нека изброим някои основни концепции на QS.

Каналите са това, което служи; Има горещ (те започват да обслужват заявка в момента, в който влезе в канала) и студен (каналът има нужда от време, за да се подготви, преди да започне обслужването). Източници на поръчки - генерирайте поръчки в произволни моменти, според статистически закон, зададен от потребителя. Приложенията, известни още като клиенти, влизат в системата (генерирани от източници на приложения), преминават през нейните елементи (обслужват се) и я оставят обслужена или незадоволена. Има нетърпеливи кандидати - такива, на които им е писнало да чакат или да са в системата и които напускат CMO по собствено желание. Приложенията формират потоци - поток от приложения на входа на системата, поток от обслужвани приложения, поток от отхвърлени приложения. Потокът се характеризира с броя приложения от определен тип, наблюдавани в определено място на QS за единица време (час, ден, месец), т.е. потокът е статистическа величина.

Опашките се характеризират с правилата за опашка (дисциплина на обслужване), броя на местата в опашката (максималния брой клиенти, които могат да бъдат в опашката) и структурата на опашката (отношението между местата в опашката). Има ограничени и неограничени опашки. Нека изброим най-важните дисциплини за поддръжка. FIFO (First In, First Out - първи влязъл, първи излязъл): ако заявката е първата, която пристига в опашката, тогава тя ще бъде първата, която отива за обслужване. LIFO (Last In, First Out - последно влязло, първо излязло): ако заявката е пристигнала последна в опашката, то тя първа ще отиде за обслужване (пример - патрони в клаксона на картечница). SF (Short Forward): тези заявки от опашката, които имат по-кратко време за обслужване, се обслужват първи.

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

Нека има два магазина. В магазин № 1 обслужването се извършва на принципа първи дошъл, първи обслужен, т.е. тук се прилага дисциплината за обслужване FIFO (виж Фиг. 30.3).

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

В магазин № 2 се прилага дисциплината SF (виж Фиг. 30.4), което означава, че стоките на парче могат да бъдат закупени извън ред, тъй като времето за обслужване Tобслужване такава покупка е малка.

Както се вижда от двете фигури, последният (пети) купувач ще закупи продукт на бройка, така че времето за обслужване е кратко - 0,5 минути. Ако този клиент дойде в магазин №1, ще бъде принуден да стои на опашка цели 8 минути, а в магазин №2 ще бъде обслужен веднага, извън опашката. Така средното време за обслужване на всеки клиент в магазин с дисциплина обслужване FIFO ще бъде 4 минути, а в магазин с дисциплина обслужване HF - само 2,8 минути. И социалната полза, спестяването на време ще бъде: (1 – 2,8/4) · 100% = 30 процента! И така, 30% от времето, спестено за обществото - и това се дължи само на правилния избор на дисциплина на обслужване.

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

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

За работата на QS може да се съди по показатели. Най-популярните от тях:

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

пропускателна способност на системата;

вероятността на клиент да бъде отказано обслужване;

вероятност за заетост на всеки канал и всички тях заедно;

средно време на заетост на всеки канал;

вероятност за заетост на всички канали;

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

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

вероятността от прекъсване на цялата система;

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

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

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

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

Качеството на получената система трябва да се съди по съвкупността от стойности на индикатора. Когато анализирате резултатите от моделирането (показателите), също е важно да обърнете внимание на интересите на клиента и интересите на собственика на системата, тоест един или друг индикатор трябва да бъде минимизиран или максимизиран, както и степента на тяхното изпълнение . Имайте предвид, че най-често интересите на клиента и собственика не съвпадат помежду си или не винаги съвпадат. По-долу ще обозначим индикаторите з = { ч 1 , ч 2 , …} .

Параметрите на QS могат да бъдат: интензивността на потока от заявки, интензивността на потока от услуги, средното време, през което една заявка е готова да чака услуга в опашката, броят на каналите за обслужване, дисциплината на обслужване и скоро. Параметрите са това, което влияе върху производителността на системата. Ще обозначим параметрите по-долу като Р = { r 1 , r 2 , …} .

Пример. Бензиностанция (бензиностанция).

1. Постановка на проблема. На фиг. Фигура 30.5 показва оформлението на бензиностанцията. Нека разгледаме метода за моделиране на QS, използвайки неговия пример и плана за неговото изследване. Шофьорите, минаващи покрай бензиностанции по пътя, може да искат да заредят автомобила си. Не всички шофьори искат да получат сервиз (да заредят колата си с бензин); Да приемем, че от целия поток автомобили на бензиностанцията идват средно 5 коли на час.

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

2. Метод на изследване SMO. В нашия пример ще приложим принципа на последователно осчетоводяване на поръчки (за подробности относно принципите на моделиране вж. лекция 32). Идеята му е, че едно приложение преминава през цялата система от влизане до излизане и едва след това се моделира следващото приложение.

За по-голяма яснота, нека изградим времева диаграма на QS операцията, отразяваща се на всеки ред (времевата ос T) състоянието на отделен елемент от системата. Има толкова времеви линии, колкото има различни места в QS и потоците. В нашия пример има 7 от тях (поток от заявки, поток, чакащ на първо място в опашката, чакащ поток на второ място в опашката, поток на услуга в канал 1, поток на услуга в канал 2 , поток от приложения, обслужвани от системата, поток от отхвърлени приложения).

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

В тази формула стойността на потока λ трябва да се посочи (преди това трябва да се определи експериментално в съоръжението като средностатистическо), r- произволно равномерно разпределено число от 0 до 1 от RNG или маси, в който трябва да се вземат произволни числа подред (без специална селекция).

Задача. Генерирайте поток от 10 случайни събития с честота на събития от 5 бр./час.

Решението на проблема. Нека вземем произволни числа, равномерно разпределени в диапазона от 0 до 1 (вижте. маса) и изчислете техните естествени логаритми (вижте таблица 30.2).

Формулата на потока на Поасон определя разстоянието между две случайни събития, както следва: T= –Ln(r рр)/ λ . Тогава, предвид това λ = 5, имаме разстояния между две произволни съседни събития: 0,68, 0,21, 0,31, 0,12 часа. Тоест събитията се случват: първо - в момента на времето T= 0, второто - в момента на времето T= 0,68, трето - в момента на времето T= 0,89, четвърто - в момента на времето T= 1.20, пети - в момента на времето T= 1,32 и така нататък. Събития - пристигането на поръчки ще бъде отразено на първия ред (виж Фиг. 30.7).

Първата заявка се приема и тъй като в този момент каналите са свободни, се настройва да обслужва първия канал. Приложение 1 се прехвърля в реда „1 канал“.

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

където ролята на интензивността се играе от размера на потока услуги μ 1 или μ 2, в зависимост от това кой канал обслужва заявката. Намираме на диаграмата момента на края на услугата, като отлагаме генерираното време за услуга от момента, в който услугата започне, и спускаме заявката до реда „Обслужено“.

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

Ако в даден момент се окаже, че и двата канала са заети, тогава заявката трябва да бъде поставена в опашка. На фиг. 30.7 е заявка с номер 3. Имайте предвид, че според условията на задачата, за разлика от каналите, заявките не са в опашката за произволно време, а чакат някой от каналите да се освободи. След освобождаване на канала заявката се издига на линията на съответния канал и там се организира обслужването му.

Ако всички места в опашката са заети към момента на пристигането на следващото заявление, тогава заявлението трябва да бъде изпратено до реда „Отказано“. На фиг. 30.7 е приложение номер 6.

Процедурата за симулиране на обслужване на приложения продължава известно време за наблюдение. Tн. Колкото по-дълго е това време, толкова по-точни ще бъдат резултатите от симулацията в бъдеще. В действителност те избират прости системи T n, равно на 50-100 или повече часа, въпреки че понякога е по-добре да се измери тази стойност чрез броя на прегледаните приложения.

През последните десетилетия в различни области на националната икономика възникна необходимостта от решаване на вероятностни проблеми, свързани с работата на системите за масово обслужване. Примери за такива системи са телефонни централи, сервизи, търговски обекти, билетни каси и др. Задачата на всяка система за масово обслужване е да обслужва потока от постъпващи в нея заявки (обаждания на абонати, клиенти, идващи в магазина, заявки за извършване на работа в цеха и др.).
Математическата дисциплина, която изучава модели на реални системи за масово обслужване, се нарича теория на масовото обслужване. Задачата на теорията на масовото обслужване е да установи зависимостта на получените показатели за ефективност на системата за масово обслужване (вероятността заявката да бъде обслужена; математическото очакване на броя обслужени заявки и т.н.) от входните индикатори (броя на устройства в системата, параметри на входящия поток от заявки и т.н.) е възможно да се установят такива зависимости под формата на формула само за прости системи за масово обслужване. Изследването на реални системи се извършва чрез имитация или моделиране на тяхната работа на компютър с помощта на метода на статистическо тестване.
Системата за опашка се счита за определена, ако:
1) входящият поток от изисквания или, с други думи, законът за разпределение, характеризиращ моментите във времето, когато изискванията влизат в системата. Основната причина за изискванията се нарича източник. По-нататък ще се съгласим да приемем, че източникът има неограничен брой изисквания и че изискванията са хомогенни, тоест се различават само в моментите на появата им в системата;
2) сервизна система, състояща се от устройство за съхранение и сервизна единица. Последният представлява едно или повече обслужващи устройства, които по-нататък ще наричаме устройства. Всяка заявка трябва да пристигне на едно от устройствата, за да бъде обслужена. Може да се окаже, че изискванията ще трябва да изчакат, докато устройствата станат налични. В този случай заявките се намират в изоставане, образувайки една или повече опашки. Да приемем, че прехвърлянето на заявка от единицата за съхранение към сервизния възел става незабавно;
3) времето за обслужване на заявка от всяко устройство, което е случайна величина и се характеризира с определен закон на разпределение;
4) дисциплина на изчакване, т.е. набор от правила, регулиращи броя на изискванията, разположени в една и съща точка от времето в системата. Система, в която заявка се отхвърля, когато всички сървъри са заети, се нарича система без изчакване. Ако дадена заявка установи, че всички устройства са заети, тя се поставя на опашка и изчаква, докато
докато едно от устройствата стане достъпно, такава система се нарича система за чисто изчакване. Система, в която заявка, която намира всички устройства за заети, се поставя на опашка само ако броят на заявките в системата не надвишава определено ниво (в противен случай заявката се губи), се нарича смесена система за опашка;
5) дисциплина на обслужване, т.е. набор от правила, според които се избира изискване от опашката за обслужване. В практиката най-често се използват следните правила:
- заявките се приемат за обслужване на принципа първи дошъл, първи обслужен;
- заявки се приемат за обслужване според минималния срок за получаване на отказ;
- заявките се приемат за обслужване в произволен ред в съответствие с определени вероятности;
6) дисциплина на опашката, т.е. набор от правила, според които дадена заявка дава предимство на една или друга опашка (ако има няколко от тях) и се намира в избраната опашка. Например, входяща заявка може да се проведе в най-късата опашка; в тази опашка той може да бъде разположен последен (такава опашка се нарича подредена) или може да отиде за обслужване извън ред. Възможни са и други варианти.

Симулационно моделиране на системи за масово обслужване

1 Външен дизайн

2 Вътрешен дизайн - проектиране на отделни елементи
системи

3 Формиране на реализации на произволен поток от заявки

5 Пример за QS моделиране
Помислете за следната система:
1 Изискванията пристигат на случаен принцип, с
интервалът от време Q между всеки две последователни искания има експоненциален закон с параметъра аз,т.е. функцията на разпределение има формата
>0. (11) Сервизната система се състои от s еднакви, номерирани устройства.
3 Време T около bsl - случайна променлива с равномерен закон на разпределение на сегмента.
4 Система без изчакване, т.е. заявка, която намира, че всички устройства са заети, напуска системата.
5 Дисциплината на обслужване е следната: ако в момента на пристигане на k-тата заявка първият сървър е свободен, то той започва да обслужва заявката; ако това устройство е заето, а второто е свободно, то заявката се обслужва от второто устройство и т.н.
Необходимо е да се оценят математическите очаквания на броя заявки, обслужени от системата по време на T и отхвърлени.
За начален момент на изчисление избираме момента на пристигане на първата заявка T1=0. Нека въведем следното обозначение: Tk е моментът на пристигане на k-то търсене; ti е моментът на приключване на обслужването на заявката от i-то устройство, i=1, 2, 3, ...,s.
Да приемем, че в момент T1 всички устройства са свободни.
Първото искане пристига на устройство 1. Времето за обслужване на това устройство има равномерно разпределение в сегмента. Следователно намираме специфичната стойност на tobsl за това време, използвайки формулата
(12)
където r е стойността на случайната променлива R, равномерно разпределена върху сегмента. Устройство 1 ще бъде заето за време t около bsl. Следователно моментът t 1 от края на обслужването на заявката от устройство 1 трябва да се счита за равен на: t 1 = T1+ t o bsl.
След това трябва да добавите една към брояча на обслужените заявки и да преминете към разглеждане на следващата заявка.
Да приемем, че k изисквания вече са разгледани. Нека определим момента T k+1 на пристигане на (k+1)-то търсене. За да направим това, намираме стойността t на интервала от време между последователните изисквания. Тъй като този интервал има експоненциален закон, тогава
12
x = - In r (13)
| Ll
където r е следващата стойност на случайната променлива R. Тогава моментът на пристигане на (k+1)-то търсене: T k +1 = Tk+ T.
Първото устройство безплатно ли е в момента? За да отговорите на този въпрос, трябва да проверите условието ti< Tk + i - Если это условие выполнено, то к моменту Т k +1 первый прибор освободился и может обслуживать требование. В этом случае t 1 заменяем на (Т k +1 + t обсл), добавляем единицу в счетчик об служенных требований и переходим к следующему требованию. Если t 1>T k +1, тогава първото устройство в момента T k +1 е заето. В този случай проверяваме дали второто устройство е свободно. Ако условие i 2< Tk + i выполнено, заменяем t2 на (Т k +1+ t о бсл), добавляем единицу в счетчик обслуженных требований и переходим к следующему требованию. Если t 2>Т k +1, след което проверяваме условие 1з<Тк+1 и т. д. Eсли при всех i от 1 до s имеет ti >T k +1, тогава в момента T k +1 всички устройства са заети. В този случай добавяме едно към брояча на неуспехите и преминаваме към следващото изискване. Всеки път, след като се изчисли T k +1, е необходимо да се провери условието за края на изпълнението: Tk + i< T . Если это условие выполнено, то одна реализация процесса функционирования системы воспроизведена и испыта ние заканчивается. В счетчике обслуженных требований и в счетчике отказов находятся числа n обсл и n отк.
Чрез повтаряне на такъв тест n пъти (с използване на различни r) и осредняване на експерименталните резултати, ние определяме оценки на математическите очаквания за броя на обслужените заявки и броя на отхвърлените заявки:
(14)
(Джи
n j =1
където (n obsl) j и (n otk) j са стойностите на n obsl и n otk в j-тия експеримент.
13

Списък на използваните източници
1 Емелянов А.А. Симулационно моделиране на икономически процеси [Текст]: Учебник. ръководство за университети / A.A. Емелянов, Е.А. Власова, Р.В. Мисъл. - М.: Финанси и статистика, 2002. - 368 с.
2 Бусленко, Н.П. Моделиране на сложни системи [Текст]/ Н.П. Бусленко, М.: Наука, 1978. - 399 с.
3 съветски B.Ya. Моделиране на системи [Текст]: Учебник. за университети / B.Ya. Советов, С.А. Яковлев. -М. : По-висок училище, 1985. - 271 с.
4 съветски B.Ya. Моделиране на системи [Текст]: Лабораторни упражнения: Учеб. ръководство за ВУЗ по специалността: „Системи за автоматизирана обработка на информация и управление“. / Б.Я. Советов, С.А. Яковлев. -М. : По-висок училище, 1989. - 80 с.
5 Максимей И.В. Симулационно моделиране на компютър [Текст]/ Максимей, И.В. -М: РАДИО И СЪОБЩЕНИЯ, 1988. - 231 с.
6 Ventzel E.S. Теория на вероятностите [Текст]: учебник. за университети / E.S. Вентилационна цел.- М.: По-високо. училище, 2001. - 575 с.
7 Гмурман, В.Е. Теория на вероятностите и математическа статистика [Текст]: учебник. надбавка / V.E. Гмурман.- М.: Висш. училище, 2001. - 479 с.
Приложение А
(задължително)
Приблизителни теми за изчислителна и графична работа
1 В спешното отделение работи само един лекар. Продължителност на лечението на пациента
и интервалите от време между приемите на пациентите са случайни променливи, разпределени съгласно закона на Поасон. Според тежестта на нараняванията пациентите се разделят на три категории; приемането на пациент от всяка категория е случайно събитие с еднакво вероятно разпределение. Лекарят се занимава първо с пациенти с най-тежки наранявания (по реда на приемането им), след това, ако няма такива, със средно тежки пациенти и едва след това с пациенти с леки наранявания. Моделирайте процеса и изчислете средното време на чакане на опашката за пациенти от всяка категория.
2 Градският автопарк има две ремонтни зони. Първият обслужва ремонти с кратка и средна продължителност, вторият - среден и дълъг. Когато възникнат повреди, превозните средства се доставят на автопарка; интервалът от време между доставките е случайна променлива на Поасон. Продължителността на ремонта е случайна величина с нормален закон на разпределение. Моделирайте описаната система. Оценете средното време на чакане на опашката за превозни средства, изискващи съответно краткосрочен, средносрочен и дългосрочен ремонт.
3 Минимаркет с един контрольор-касиер обслужва клиенти, чийто входящ поток се подчинява на закона на Поасон с параметър 20 клиента/час. Извършете симулация на описания процес и определете вероятността от прекъсване на контролера - касиер, дължината на опашката, средния брой клиенти в минимаркета, средното време на чакане за обслужване, средното време на клиентите в минипазара и оценете работата му.
4 ATS получава заявки за междуградски разговори. Клиентският поток е Поасон. Средно на час се получават по 13 молби. Намерете средния брой заявления, получени на ден, средното време между появата на заявления. Една телефонна централа получава неизправности, ако получи повече от 50 заявки за половин час. Намерете вероятността от повреда на станцията.
5 Сервизът получава най-простия
текущи заявки с интензивност 1 автомобил на 2 часа В двора не може да има повече от 3 автомобила. Средното време за ремонт е 2 часа. Оценете ефективността на CMO и разработете препоръки за подобряване на услугата.
6 Един тъкач обслужва група станове, като при необходимост извършва краткотрайна интервенция, чиято продължителност е случайна променлива. Симулирайте описаната ситуация. Каква е вероятността от прекъсване на две машини едновременно? Колко време е средният престой на една машина?
7 В междуградска телефонна централа двама телефонни оператори обслужват обща опашка от поръчки. Следващата поръчка се обслужва от телефонния оператор, който пръв се е освободил. Ако и двамата са заети в момента на получаване на поръчката, обаждането ще бъде отменено. Моделирайте процеса, като приемете входните потоци за Поасон.
8 В спешното отделение работят двама лекари. Продължителността на лечението е болезнена
а интервалите от време между приемите на пациентите са случайни променливи, разпределени съгласно закона на Поасон. Според тежестта на нараняванията пациентите се разделят на три категории; приемането на пациент от всяка категория е случайно събитие с еднакво вероятно разпределение. Лекарят се занимава първо с пациенти с най-тежки наранявания (по реда на приемането им), след това, ако няма такива, със средно тежки пациенти и едва след това с пациенти с леки наранявания. Моделирайте процеса и изчислете средното време на чакане на опашката за пациенти от всяка категория.
9 В междуградската телефонна централа обслужваха двама телефонисти
създайте обща опашка от поръчки. Следващата поръчка се обслужва от този телефонен оператор,
която първа се освободи. Ако и двамата са заети в момента на пристигане на поръчката, се образува опашка. Моделирайте процеса, като приемете входните потоци за Поасон.
10 В система за предаване на данни пакетите данни се обменят между възли A и B по дуплексен комуникационен канал. Пакетите пристигат в системните точки от абонати с времеви интервали между тях от 10 ± 3 ms. Предаването на пакет отнема 10 ms. Точките имат буферни регистри, които могат да съхраняват два пакета, включително този, който се предава. Ако пристигне пакет, когато регистрите са заети, системните точки получават достъп до сателитна полудуплексна комуникационна линия, която предава пакети данни за 10 ± 5 ms. Когато сателитната линия е заета, пакетът се отхвърля. Моделирайте обмена на информация в система за предаване на данни за 1 минута. Определете честотата на обажданията към сателитната линия и нейното натоварване. В случай на евентуални повреди, определете обема на буферните регистри, необходими за безотказна работа на системата.
11 Нека се използва обичайната система на телефонна централа с един вход: ако абонатът е зает, тогава опашката не се образува и трябва да се обадите отново. Симулирайте ситуацията: трима абонати се опитват да се обадят на собственика на един и същ номер и, ако успеят, говорят с него известно време (произволно по продължителност). Каква е вероятността някой, който се опитва да се обади, да не успее да го направи в рамките на определено време T.
12 Търговска фирма планира да изпълнява поръчки за закупуване на стоки по телефона, за което е необходимо да инсталира подходяща мини телефонна централа с няколко телефонни апарата. Ако пристигне поръчка, когато всички линии са заети, клиентът получава отказ. Ако в момента на получаване на явяване поне една линия е свободна, тогава се извършва превключване към тази линия и се прави поръчка. Интензивността на входящия поток от заявки е 30 поръчки на час. Средното време за обработка на заявката е 5 минути. Определете оптималния брой канали за обслужване, за да осигурите стационарна работа на QS.
13 Магазинът на самообслужване разполага с 6 контрольори – касиери. Входящият клиентски поток се подчинява на закона на Поасон с интензивност 120 души/час. Един касиер може да обслужи 40 души на час. Определете вероятността касиерът да не работи, средния брой клиенти на опашката, средното време на чакане, средния брой заети касиери. Оценете работата на QS.
14 Магазин на самообслужване получава Поасонов поток с интензитет от 200 клиенти на час. През деня се обслужват от 3 касиер-контрольори с интензивност 90 клиента на час. Интензитетът на входящия клиентски поток в пиковите часове нараства до 400 клиента на час, а в часовете на спад достига до 100 клиента на час. Определете вероятността за образуване на опашка в магазина и средната дължина на опашката през деня, както и необходимия брой касиери в пиковите и извън пиковите часове, осигурявайки същата дължина на опашката и вероятността за нейното формиране както в номинален режим.
15 Средният брой клиенти, пристигащи в центъра за плащане в магазин на самообслужване е 100 души/час. Един касиер може да обслужи 60 души на час. Моделирайте процеса и определете колко касиери са необходими, за да се гарантира, че вероятността за опашка не надвишава 0,6.
16 Симулирайте опашка в магазин с един продавач при равновероятни закони за разпределение на случайни променливи: пристигане на клиенти и продължителност на обслужване (с някакъв фиксиран набор от параметри). Получаване на стабилни характеристики: средни стойности на чакане на опашка от купувача и време на престой на продавача, докато чака пристигането на купувачите. Оценете тяхната надеждност.
17 Симулирайте опашка в магазин с един продавач съгласно законите на Поасон за разпределение на случайни променливи: пристигане на клиенти и продължителност на обслужване (с някакъв фиксиран набор от параметри). Получаване на стабилни характеристики: средни стойности на чакане на опашка от купувача и време на престой на продавача, докато чака пристигането на купувачите. Оценете тяхната надеждност.
18 Създайте модел на бензиностанция. Намерете показатели за качество на билетната услуга. Определете броя на броячите, така че опашката да не се увеличава.
19 Средният брой клиенти, пристигащи в разплащателния център на магазин на самообслужване, е 60 души на час. Един касиер може да обслужи 35 души на час. Моделирайте процеса и определете колко касиери са необходими, за да се гарантира, че вероятността за опашка не надвишава 0,6.
20 Разработете модел на автобусен маршрут с n спирки. Определете показателите за ефективност за използване на QS.

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

3.1.1 Обща информация за системите за масово обслужване

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

Фигура 3.1 показва QS диаграмата.

Основните елементи (характеристики) на системите за масово обслужване са:

Сервизна единица (блок),

Поток от приложения

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

Сервизна единицапредназначени да извършват действия според изискванията на влизащите в системата приложения.

Ориз. 3.1 Диаграма на системата за масово обслужване

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

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

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

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

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

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

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

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

Специална област на приложната математика теория на масатаподдръжка (TMO)– занимава се с анализ на процеси в системи за масово обслужване. Предмет на изучаване на теорията на масовото обслужване е QS.

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

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

Като характеристики на ефективността на QS системата обикновено се избират следните три основни групи (обикновено средни) показатели:

Индикатори за ефективност на използването на QS:

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

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

Средна продължителност на периода на заетост на ООП.

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

Индикатори за качество на заявките за обслужване:

Средно време за изчакване на приложение на опашката.

Средно време, през което едно приложение остава в CMO.

Вероятността заявката да бъде отказана услуга без изчакване.

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

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

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

Средният брой приложения в опашката.

Среден брой заявления в ООП и др.

Индикатори за ефективността на двойката „SMO - потребител“, където „потребител“ се разбира като целия набор от приложения или някои от тях

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

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

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

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

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

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

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

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

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

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

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

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

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

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

F (t) = 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 ] = m t , и дисперсия Dt. Ние имаме

( 0-5)

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

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

(0-6)

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

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

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

Пример SMO-1 .

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

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

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

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

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

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

Пример SMO-2.

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

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

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

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

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

Пример SMO- 3

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

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

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

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

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

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

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

ρ ≤ 0,9

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

Нека отново средната скорост на пристигане на съобщения λ = 3,1 съобщения/s. От таблиците следва, че вероятността за получаване на 6 или повече съобщения за 1 секунда е 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, рано или късно ще бъде обслужено.

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

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

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

· общо време на престой на приложението в CMO

и т.н.

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

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

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

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

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

и т.н.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

От друга страна, разпространението на времето за обслужване не е толкова голямо, колкото при произволното или експоненциалното му разпределение, т.е.σ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с даде стойност от 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 s 2 при коефициент на използване на оборудването 50% и 100 т s 2 за коефициент 90%, т.е. отново 25 пъти по-зле.

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

Squeak: Моделиране на системи за опашка

• програмиране,
• ООП,
• Паралелно програмиране

В Habré има много малко информация за такъв език за програмиране като Squeak. Ще се опитам да говоря за това в контекста на моделирането на системи за масово обслужване. Ще ви покажа как да напишете прост клас, да обясня структурата му и да го използвате в програма, която ще обслужва заявки през няколко канала.

Няколко думи за Squeak

<объект> <сообщение>

Системи за масово обслужване

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

Малко математика

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

Ранд клас

Float variableWordSubclass: #Rand "име на клас" instanceVariableNames: "" "променливи на екземпляр" classVariableNames: "R" "променливи на клас" poolDictionaries: "" "общи речници" категория: "Пример" "име на категория"
Методи:

"Инициализация" init R:= Time totalSeconds.next "Следващо псевдослучайно число" next R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
За да зададете първоначалното състояние на сензора, изпратете съобщение Rand инициал.
За да получите следващото произволно число, което изпращаме ранд следващ.

Програма за обработка на заявления

Код за Squeak

„Деклариране на временни променливи“ | proc1 proc2 t1 t2 s1 s2 sysPriority опашка продължи r | "Първоначални настройки на променлива" Rand инициал. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2:= -1. продължи:= вярно. sysPriority:= Приоритет на активния процес на процесора. Опашка "Текущ приоритет":= Семафор нов. „Модел на опашка за заявка“ „Създаване на процес – модел на канал 1“ (Процес за Контекст: [ proc1:= Процесор activeProcess. whileTrue: „Цикъл на обслужване“ [ чакане на опашка. „Изчакване на заявка“ t1:= SysTime + 2. „Следващо активиране време" s1:= s1 + 1. proc1 спиране. "Суспендиране на процеса, докато чака услугата да завърши" ] proc1:= нула. "Изтриване на препратката към процес 1" ] приоритет: (sysPriority + 1)) възобновяване. „Новият приоритет е по-голям от фона“ „Създаване на процес – модел на канал 2“ (Process forContext: [ proc2:= Processor activeProcess.. whileTrue: [ queue wait. t2:= SysTime + 7. s2:= s2 + 1 .proc2 suspend: proc2:= nil: (sysPriority + 1)) resume. „Продължение на описанието на основния процес и изходния модел“ whileTrue: [ r:= (Rand next * 10) закръглено. (r = 0) ifTrue: . ((SysTime rem: r) = 0) ifTrue: . „Изпращане на заявка“ „Превключване на процеса на обслужване“ (t1 = SysTime) ifTrue: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. „Времето на модела тиктака“ ]. „Показване на състоянието на брояча на поръчки“ Изскачащото меню информира: „proc1: „,(s1 printString),“, proc2: „,(s2 printString). продължи:= невярно.