2.2 Многоканален QS с изчакване
Система с ограничена дължина на опашката. Нека разгледаме канал QS с чакане, който получава поток от заявки с интензитет ; интензивност на обслужване (за един канал); брой места в опашката.
Състоянията на системата са номерирани според броя на заявките, свързани със системата:
без опашка:
Всички канали са безплатни;
Един канал е зает, останалите са свободни;
-каналите са заети, останалите не са;
Всички канали са заети, няма свободни канали;
има опашка:
Всички n-канали са заети; едно приложение е на опашката;
Всички n-канали, r-заявки в опашката са заети;
Всички n-канали, r-заявки в опашката са заети.
GSP е показан на фиг. 17. Всяка стрелка е маркирана със съответните интензитети на потоците от събития. По стрелките отляво надясно системата винаги се прехвърля от един и същ поток от заявки с интензитет на
Ориз. 17. Многоканален QS с изчакване
Графиката е типична за процесите на размножаване и смърт, за които предварително е получено решение. Нека напишем изрази за граничните вероятности на състоянията, използвайки нотацията: (тук използваме израза за сумата геометрична прогресиясъс знаменател).
Така са намерени всички вероятности на състоянието.
Нека да определим характеристиките на работата на системата.
Вероятност за провал. Входяща заявка се отхвърля, ако всички n-канали и всички m-места в опашката са заети:
(18)
Относителната производителност допълва вероятността от повреда до едно:
Абсолютна производителност на QS:
(19)
Среден брой заети канали. За QS с откази съвпадна със средния брой заявления в системата. За QS с опашка средният брой заети канали не съвпада със средния брой приложения в системата: последната стойност се различава от първата със средния брой приложения в опашката.
Нека означим средния брой заети канали с . Всеки зает канал обслужва средно A-искания за единица време, а QS като цяло обслужва средно A-искания за единица време. Разделяйки едно на друго, получаваме:
Средният брой приложения в опашката може да се изчисли директно като математическо очакване на дискретно случайна величина:
(20)
Тук отново (изразът в скоби) се появява производната на сумата от геометричната прогресия (виж по-горе (11), (12) - (14)), използвайки връзката за нея, получаваме:
Среден брой приложения в системата:
Средно време за изчакване на приложение на опашката. Нека разгледаме редица ситуации, които се различават по състоянието, в което новопристигналата заявка ще намери системата и колко време ще трябва да чака за обслужване.
Ако дадена заявка не установи, че всички канали са заети, тя изобщо няма да трябва да чака (съответните членове в математическо очакванеса равни на нула). Ако заявка пристигне в момент, когато всички n-канали са заети и няма опашка, тя ще трябва да изчака средно време, равно на (защото „потокът на освобождаване“ на -каналите има интензитет ). Ако дадена заявка установи, че всички канали са заети и една заявка пред нея в опашката, тя ще трябва да изчака средно определен период от време (за всяка заявка отпред) и т.н. Ако заявката се окаже в опашка от - заявки, ще трябва да изчака средно време Ако новопристигнала заявка намери m-заявки вече в опашката, тогава тя изобщо няма да чака (но няма да бъде обслужена). Намираме средното време на изчакване, като умножим всяка от тези стойности по съответните вероятности:
(21)
Точно както в случая на едноканален QS с изчакване, отбелязваме, че този израз се различава от израза за средната дължина на опашката (20) само с фактора , т.е.
.
Средното време на престой на заявка в системата, както и за едноканален QS, се различава от средното време на изчакване със средното време за обслужване, умножено по относителната пропускателна способност:
.
Системи с неограничена дължина на опашка. Разгледахме QS на канал с изчакване, когато не повече от m-заявки могат да бъдат в опашката едновременно.
Както и преди, когато се анализират системи без ограничения, е необходимо да се вземат предвид получените отношения за .
Получаваме вероятностите за състояния от формулите чрез преминаване към границата (при ). Обърнете внимание, че сумата от съответната геометрична прогресия се събира при и се разминава при >1. Ако приемем, че<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Вероятност за отказ, относителна и абсолютна производителност. Тъй като всяка заявка рано или късно ще бъде обслужена, характеристиките на пропускателната способност на QS ще бъдат:
Средният брой заявления в опашката се получава от (20):
,
и средното време на изчакване е от (21):
.
Средният брой заети канали, както и преди, се определя чрез абсолютната пропускателна способност:
.
Средният брой приложения, свързани с QS, се определя като средния брой приложения в опашката плюс средния брой приложения в услуга (среден брой заети канали):
Пример 2. Бензиностанция с две помпи (n = 2) обслужва поток от автомобили с интензитет =0,8 (автомобили в минута). Средно време за обслужване на машина:
В района няма друга бензиностанция, така че опашката от автомобили пред бензиностанцията може да расте почти неограничено. Намерете характеристиките на QS.
Тъй като<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
и т.н.
Ще намерим средния брой заети канали, като разделим абсолютния капацитет на QS A = = 0,8 на интензитета на услугата = 0,5:
Вероятността да няма опашка на бензиностанция ще бъде:
Среден брой коли в опашката:
Среден брой автомобили на бензиностанциите:
Средно време на чакане на опашка:
Средно време, което една кола прекарва на бензиностанция:
QS с ограничено време за изчакване. Преди това разглеждахме системи с чакане, ограничено само от дължината на опашката (броя m-заявки едновременно в опашката). В такъв QS приложение, което е нараснало в опашката, не я напуска, докато не изчака услуга. На практика има и други видове QS, при които едно приложение, след като е изчакало известно време, може да излезе от опашката (т.нар. „нетърпеливи” приложения).
Нека разгледаме QS от този тип, като приемем, че ограничението на времето за изчакване е случайна променлива.
Да приемем, че има n-канален QS с чакане, в който броят на местата в опашката е неограничен, но времето, през което една заявка остава в опашката, е някаква случайна променлива със средна стойност, следователно всяка заявка в опашката опашката е подложена на един вид Поасонов "поток на грижа" с интензивност:
Ако този поток е Поасон, тогава процесът, протичащ в QS, ще бъде марковски. Нека намерим вероятностите на състоянието за това. Номерирането на системните състояния е свързано с броя на приложенията в системата - както обслужвани, така и стоящи на опашка:
без опашка:
Всички канали са безплатни;
Един канал е зает;
Два канала са заети;
Всички n-канали са заети;
има опашка:
Всички n-канала са заети, една заявка е в опашката;
Всички n-канали са заети, r-заявките са в опашка и т.н.
Графиката на състоянията и преходите на системата е показана на фиг. 23.
Ориз. 23. QS с ограничено време на изчакване
Нека маркираме тази графика както преди; всички стрелки, водещи отляво надясно, ще показват интензивността на потока от приложения. За състояния без опашка, стрелките, водещи от тях отдясно наляво, както и преди, ще показват общата интензивност на потока, обслужващ всички заети канали. Що се отнася до състояния с опашка, стрелките, водещи от тях отдясно наляво, ще имат общата интензивност на потока от услуги на всички n-канали плюс съответния интензитет на потока на отклонения от опашката. Ако в опашката има r-заявки, тогава общата интензивност на потока от заминаващи ще бъде равна на .
Както може да се види от графиката, има модел на размножаване и смърт; използвайки общи изрази за ограничаващите вероятности на състоянията в тази схема (използвайки съкратени обозначения, ние пишем:
(24)
Нека отбележим някои характеристики на QS с ограничено изчакване в сравнение с разгледаните по-рано QS със заявки за „пациенти“.
Ако дължината на опашката не е ограничена и заявките са „търпеливи“ (не напускат опашката), тогава стационарният граничен режим съществува само в случая (при , съответната безкрайна геометрична прогресия се отклонява, което физически съответства на неограничен растеж от опашката на ).
Напротив, в QS с „нетърпеливи“ заявки, напускащи опашката рано или късно, установеният режим на обслужване при винаги се постига, независимо от намалената интензивност на потока от заявки. Това следва от факта, че серията за в знаменателя на формула (24) се сближава за всякакви положителни стойности на и .
За QS с „нетърпеливи“ заявки, концепцията за „вероятност от повреда“ няма смисъл - всяка заявка идва на опашката, но може да не чака услуга, тръгвайки преди време.
Относителна производителност, среден брой заявки в опашката. Относителният капацитет q на такъв QS може да се изчисли, както следва. Очевидно всички заявления ще бъдат обслужени, с изключение на тези, които напускат опашката предсрочно. Нека изчислим средния брой заявления, които напускат опашката рано. За да направим това, изчисляваме средния брой приложения в опашката:
Всяко от тези приложения е обект на „поток от заминавания“ с интензивност . Това означава, че от средния брой -приложения в опашката средно -приложения ще напуснат, без да чакат обслужване, -приложения за единица време и общо за единица време, средно -приложения ще бъдат обслужени. Относителният капацитет на QS ще бъде:
Все още получаваме средния брой заети канали, като разделим абсолютната честотна лента A на:
(26)
Среден брой заявления в опашката. Връзката (26) ви позволява да изчислите средния брой приложения в опашката, без да сумирате безкрайните серии (25). От (26) получаваме:
и средният брой заети канали, включени в тази формула, могат да бъдат намерени като математическо очакване на случайна променлива Z, приемаща стойности 0, 1, 2,..., n с вероятности ,:
В заключение отбелязваме, че ако във формули (24) отидем до границата при (или, което е същото, при ), тогава при 
Опашка с дължина k остава в нея с вероятност Pk и не се присъединява към опашката с вероятност gk=1 - Pk." Точно така хората обикновено се държат на опашки. В системите за масово обслужване, които са математически модели на производствени процеси, възможните дължината на опашката е ограничена от постоянен размер (капацитет на бункера, например). Очевидно това е специален случай на общата настройка. Някои...
В този раздел ще разгледаме някои от най-простите QS и ще изведем изрази за техните характеристики (индикатори за ефективност). В същото време ще демонстрираме основните методологични похвати, характерни за елементарната, „марковска” теория на масовото обслужване. Няма да преследваме броя QS проби, за които ще бъдат получени окончателни изрази на характеристики; Тази книга не е справочник по теория на масовото обслужване (тази роля се изпълнява много по-добре от специални ръководства). Нашата цел е да запознаем читателя с някои „малки трикове“, които улесняват пътя през теорията на опашките, която в редица съществуващи (дори претендиращи за популярни) книги може да изглежда като несвързан набор от примери.
В този раздел ще разгледаме всички потоци от събития, които прехвърлят QS от състояние в състояние, като най-прости (без да уточняваме това всеки път). Сред тях ще бъде т. нар. „сервизен поток“. Отнася се за потока от заявки, обслужван от един непрекъснато зает канал.
В този поток интервалът между събитията, както винаги в най-простия поток, има експоненциално разпределение (в много ръководства вместо това се казва: „времето за обслужване е експоненциално“; ние самите ще използваме този термин в бъдеще). В този раздел експоненциалното разпределение на времето за обслужване ще се разбира от само себе си, както винаги за „най-простата“ система.
Ще представим характеристиките на ефективността на разглеждания QS, докато продължаваме.
1. n-канален QS с откази (проблем Erlang).
Тук ще разгледаме един от първите, „класически“ проблеми на теорията на масовото обслужване; този проблем възниква от практическите нужди на телефонията и е решен в началото на този век от датския математик Ерланг. Проблемът се формулира по следния начин: има канали (комуникационни линии), които получават поток от заявки с интензитет K. Потокът от услуги има интензитет (обратната стойност на средното време за обслужване). Намерете крайните вероятности за състоянията на QS, както и характеристиките на неговата ефективност:
A - абсолютна пропускателна способност, т.е. среден брой приложения, обслужвани за единица време;
Относителна производителност, т.е. средният дял на входящите приложения, обслужвани от системата;
Rotk е вероятността за отказ, т.е. приложението да остави QS необслужен;
k е средният брой заети канали.
Решение. Ще номерираме състоянията на системата S (SMO) според броя на заявките, намиращи се в системата (в този случай съвпада с броя на заетите канали):
В CMO няма нито едно приложение,
Има една заявка в QS (един канал е зает, останалите са свободни),
В системата QS заявките за канали са заети, останалите са свободни),
Има заявки в QS (всички канали са заети).
Графиката на състоянието на QS съответства на модела на смъртта и размножаването (фиг. 20.1). Нека маркираме тази графика - поставете интензитета на потоците от събития до стрелките Потокът от приложения с интензитет X се прехвърля от системата (щом пристигне заявление, системата скача от ).
Същият поток от заявки прехвърля системата от всяко ляво състояние в съседното дясно (вижте горните стрелки на фиг. 20.1).
Нека поставим интензитетите на долните стрелки. Нека системата е в състояние (един канал работи). Извършва поддръжка за единица време. Посочваме интензитета на стрелката.Сега нека си представим, че системата е в състояние (два канала работят). За да тръгне, трябва или първият канал, или вторият да приключи обслужването; общата интензивност на техните обслужващи потоци е равна на съответната стрелка. Общият поток от услуги, предоставяни от три канала, има интензитет, равен на каналите - Поставяме тези интензитети в долните стрелки на фиг. 20.1.
И сега, знаейки всички интензитети, ще използваме готови формули (19.7), (19.8) за крайните вероятности в схемата на смъртта и размножаването. Използвайки формула (19.8), получаваме:
Членовете на разширението ще бъдат коефициентите в изразите за
Забележете, че във формули (20.1), (20.2) интензитетите на яйцата са включени не поотделно, а само под формата на съотношение.
и ще наречем стойността „намален интензитет на потока от приложения“. Значението му е средният брой заявки, получени за средното време на обслужване на една заявка. Използвайки тази нотация, пренаписваме формулите (20.1), (20.2) във формата:
Формулите (20.4), (20.5) за крайните вероятности на състоянията се наричат формули на Ерланг - в чест на основателя на теорията на масовото обслужване. Повечето от другите формули на тази теория (днес ги има повече от гъби в гората) не носят специални имена.
Така окончателните вероятности са намерени. Използвайки ги, ще изчислим характеристиките на ефективността на QS. Първо, нека намерим вероятността входяща заявка да бъде отхвърлена (няма да бъде обслужена). За да направите това, всички канали трябва да са заети, което означава
От тук намираме относителната производителност - вероятността заявката да бъде обслужена:
Получаваме абсолютната пропускателна способност, като умножим интензивността на потока от приложения X по
Всичко, което остава, е да се намери средният брой заети канали k. Тази стойност може да бъде намерена „директно“, като математическо очакване на дискретна случайна променлива с възможни стойности и вероятности на тези стойности
Замествайки тук изрази (20.5) и извършвайки съответните трансформации, в крайна сметка ще получим правилната формула за k. Но ще я изведем много по-просто (ето го, един от „малките трикове“!) Всъщност знаем абсолютната производителност A. Това не е нищо повече от интензивността на потока от приложения, обслужвани от системата. Всеки зает канал обслужва средно заявки за единица време. Това означава, че средният брой заети канали е
И каква част от каналите ще бъдат неактивни?
Тук вече се вижда известен намек за оптимизация. Всъщност поддръжката на всеки канал за единица време струва определена сума. В същото време всяко обслужвано приложение генерира известен доход. Умножавайки този доход по средния брой обслужени приложения A за единица време, получаваме средния доход от QS за единица време. Естествено, с увеличаването на броя на каналите, този доход се увеличава, но се увеличават и разходите, свързани с поддръжката на каналите. Какво ще надделее - увеличение на приходите или разходите? Това зависи от условията на операцията, „таксата за обслужване на приложението“ и разходите за поддръжка на канала. Познавайки тези стойности, можете да намерите оптималния брой канали, най-рентабилните. Няма да решим такъв проблем, оставяйки на същия „не мързелив, любопитен читател“ да измисли пример и да го реши. Като цяло измислянето на проблеми развива повече от решаването на вече поставени от някого.
ML системите са част от по-широк клас динамични системи, които понякога се наричат поточни системи. Система с нишки е система, в която определени обекти се преместват през един или повече канали с ограничен капацитет с цел преместване от една точка в друга. Когато се анализират поточните системи, те се разделят на два основни класа:
регулярни системи, т.е. системи, в които потоците се държат по предвидим начин (големината на потока и времето на появата му в канала са известни). В случай, че има само един канал, изчислението на системата е тривиално. Очевидно е, че между интензитета на потока λ и скорост на обслужване сима съотношение λ < ° С;
неправилни системи, т.е. системи, в които нишките се държат по непредвидими начини.
По-интересен е случаят с редовен поток, който се разпределя в мрежа от канали. Очевидно е, че състоянието λ < ° Сзапазени за всеки канал. Това създава сложен комбинаторен проблем.
Има седем пътя:
A→B→D→E→F
A→C→B→ E→F
A→C→B→D→E→F
A→C→B→ D→F
Необходимо е превоз на товари от А V Е. Капацитетът на всеки канал е известен. Какъв е капацитетът на мрежата и по какъв път трябва да поеме потокът? Този проблем може да бъде решен с помощта на теоремата за максимален поток, която разгледахме по-рано (фиг. 6).
Вторият клас включва произволни вероятни потоци, при които времето на получаване на изискване не е определено и броят на изискванията е непредвидим. Теорията на опашките се занимава с решаването на такива проблеми.
Най-общо системата за масово обслужване може да бъде представена на фигура 7.
Ориз. 7.
Предмет на теорията на масовото обслужванее да се установи връзката между характера на потока от заявки, броя на каналите, производителността, правилната работа и ефективността.
Като експлоатационни характеристикиМогат да се използват следните количества и функции:
среден брой приложения, които QS може да обслужи за единица време;
средният брой заявления, които са отхвърлени и напускат ООП;
вероятността полученото заявление да бъде незабавно обслужено;
средно време на чакане на опашка;
среден брой приложения в опашката;
среден доход на СМО за единица време и други икономически показатели на СМО.
Анализът на QS се опростява, ако в системата протича процес на Марков, тогава системата може да се опише с обикновени диференциални уравнения, а граничните вероятности - с линейни алгебрични уравнения.
Процесът на Марков изисква всички потоци да бъдат поасонови (без последващи ефекти), но апаратът на процесите на Марков се използва и когато процесът е различен от процеса на Марков. В този случай характеристиките на QS могат да бъдат оценени приблизително: колкото по-сложна е QS, толкова по-точно е приближението.
Класификация на системите за масово обслужване
QS може да бъде два вида:
QS с откази;
QS с чакане (т.е. с опашка).
Обслужването в системи с опашка може да бъде от различно естество:
услугата може да бъде рационализирана;
произволно обслужване;
услуга с приоритет, докато приоритетът може да бъде със или без прекъсване.
Системите за масово обслужване се разделят на:
системи с неограничено чаканеи задачата, получена от QS, се поставя в опашка и чака услуга. Рано или късно тя ще бъде обслужена;
системи с ограничени очаквания, докато се налагат ограничения върху приложението в опашката, например ограничено време, прекарано в опашката, дължината на опашката, общото време, прекарано в QS. В зависимост от вида на QS могат да се използват различни показатели за оценка на ефективността.
За QS с повреди се използват следните показатели за ефективност:
абсолютна производителност А– среден брой приложения, които могат да бъдат обслужени за единица време;
относителна производителност Q– относителен среден брой приложения. В този случай относителната производителност може да се намери с помощта на формулата
Където λ е интензитетът на заявките, получени от QS.
За SMO с очакване абсолютна производителност АИ относителна производителност Qгубят значението си, но други характеристики стават важни:
единица време на чакане в опашка;
среден брой заявления в опашка;
средно време, прекарано в системата.
За QS с ограничена опашка и двете групи характеристики са интересни.
Помислете за n - канална система за опашка с изчакване.
Интензитетът на обслужвания поток е μ. Продължителността на услугата е случайна променлива, предмет на експоненциалния закон за разпределение. Сервизният поток е най-простият Поасонов поток от събития.
Размерът на опашката позволява хората да бъдат в нея m приложения.
За да намерите пределните вероятности, можете да използвате следните изрази.
(0‑1)
Където.
Вероятност за отказ за обслужване на приложение(ще възникне повреда, ако всички канали са заети и има m заявки):
(0‑2)
Относителна честотна лента.
(0‑3)
Абсолютна производителност.
(0‑4)
Среден брой заети канали.
За QS с опашка средният брой на заетите канали не съвпада (за разлика от QS с неуспехи) със средния брой заявки в системата. Разликата е равна на броя заявки, чакащи на опашката.
Нека обозначим средния брой заети канали. Всеки зает канал обслужва средно μ заявки за единица време, а QS като цяло обслужва A заявки за единица време. Разделяйки А на μ, получаваме
(0‑5)
Средният брой приложения в опашката.
За да намерите средния брой приложения, чакащи в опашката, ако χ≠1, можете да използвате израза:
(0‑6)
(0‑7)
където = .
Средният брой приложения в системата.
(0‑8)
Средно време на изчакване за приложение на опашка.
Средното време на изчакване на приложение в опашката може да се намери от израза (χ≠1).
(0‑9)
Средно време, през което едно приложение остава в системата.
Точно както в случая на едноканален QS, имаме:
(0‑10)
Съдържанието на произведението.
Подготовка на експериментални инструменти .
Извършва се в съответствие с общите правила.
Изчисляване чрез аналитичен модел .
1. Подгответе следната таблица в Microsoft Excel.
|
Настроики |
Аналитичен |
Имитация |
|||||||||||||||
|
н |
м |
Tа |
Ц |
ρ |
χ |
P0 |
P1 |
p2 |
Rotk |
У |
нож |
р |
А |
Rotk |
У |
р |
А |
2. В колоните за QS параметрите на таблицата запишете Вашите първоначални данни, които се определят по правилото:
n =1,2,3
m=1,3,5
За всяка комбинация ( n,m) е необходимо да се намерят теоретични и експериментални стойности на QS показатели за следните двойки стойности:
= <порядковый номер в списке группы>
3. Въведете съответните формули в колоните с показателите на аналитичния модел.
Експериментирайте върху симулационен модел.
1. Задайте режим на стартиране с експоненциално разпределено време за обслужване, като зададете стойността на съответния параметър на 1.
2. За всяка комбинация от n, m и стартирайте модела.
Въведете резултатите от пробите в таблицата.
3. Въведете формули за изчисляване на средната стойност на показателя Ptk, q и A в съответните колони на таблицата.
Анализ на резултатите .
1. Анализирайте резултатите, получени чрез теоретични и експериментални методи, като сравнявате резултатите помежду си.
2. За една от комбинациите (n,m) на една диаграма се нанася зависимостта на Ptk от теоретично и експериментално получените данни.
Оптимизиране на QS параметрите .
Решете проблема с оптимизирането на размера на броя на местата в опашкам за две устройства със средно време на обслужване = от гледна точка на получаване на максимална печалба. Като условия на проблема вземете:
- доход от обслужване на едно приложение, равен на 80 USD/час,
- разходите за поддръжка на едно устройство са 1$/час,
- цената за поддържане на едно място в опашката е 0,2 USD/час.
1. За изчисления е препоръчително да създадете таблица:
Първата колона се попълва с броя на устройствата n =1.
Втората колона се попълва със стойностите на числата от естествения ред (1,2,3...).
Всички клетки в третата и четвъртата колона са попълнени със стойности.
Формулите за колоните на таблицата в раздел 0 се прехвърлят в клетките на колоните от пет до четиринадесет.
В колоните с първоначалните данни на секциите Приходи, Разходи, Печалба въведете стойностите (вижте по-горе).
В колоните с изчислени стойности на разделите Приходи, Разходи, Печалба запишете формулите за изчисление:
- брой приложения за единица време
N r =A
- общ доход за единица време
I S = I r *N r
- обща консумация за единица време
E S =E s *n + E q *m
- печалба за единица време
P = I S - E S
Където
Ir - доход от едно приложение,
E s - консумация на устройство,
Ек - цена на място в ред
2. Попълнете редовете на таблицата за n=2 и n=3.
Намерете m opt за n =1,2,3.
3. Начертайте графики на зависимостта C(m) за n=1,2,3 върху една диаграма.
Доклад за работа:
Докладът за работата трябва да включва:
- първоначални данни,
- резултати от изчисления и експерименти със софтуерния модел,
Графики за P отворени,
- таблица с данни, за да намерите най-доброто m и стойността на m opt,
- графики на печалба за единица време в зависимост от m за n=1,2,3.
Контролни въпроси :
1) Дайте кратко описание на многоканалния QS модел с ограничена опашка.
2) Какви показатели характеризират функционирането на многоканален QS с ограничена опашка?
3) Как се изчисляват пределните вероятности на многоканален QS с ограничена опашка?
4) Как да намерим вероятността за неуспешно обслужване на приложение?
5) Как да намеря относителна честотна лента?
6) Каква е абсолютната производителност?
7) Как се изчислява средният брой приложения в системата?
8) Дайте примери за многоканален QS с ограничена опашка.
Задачи.
1) Бензиностанцията разполага с 3 помпи и платформа за 3 коли за изчакване за зареждане. Средно на всеки 4 минути на гарата пристига по една кола. Средното време за обслужване на една машина е 2,8 минути. Определете работните характеристики на бензиностанция.
2) Пунктът за технически преглед на МПС, който разполага с 3 пункта за преглед, приема средно по 1 МПС на всеки 0,4 часа. Паркингът в двора е за 3 коли. Средното време за работа на един пост е 0,5 часа. Определете характеристиките на сервиза.
3) Стоките се доставят до магазина с автомобили. През деня пристигат средно по 6 коли. Помощни помещения за подготовка на стоки за продажба ви позволяват да обработвате и съхранявате стоки, докарани от две превозни средства. В магазина работят трима опаковачи на продукти на смени, всеки от които може да обработи стоките на една машина средно в рамките на 5 часа. Работният ден на опаковчиците е 12 часа. Определете експлоатационните характеристики на магазина, както и какъв трябва да бъде капацитетът на сервизните помещения, така че вероятността за пълна обработка на стоките да е по-голяма от 0,96.
4) Магазинът разполага с три каси. Средното време за обслужване на един клиент е 3 минути. Интензивността на клиентопотока е 7 човека в минута. Броят на клиентите, стоящи на опашка на касата, не може да надвишава 5 души. Купувач, който идва в магазин, в който има по 5 човека на всяка опашка на касата, не чака, а напуска магазина. Определете характеристиките на магазина.
5) Складът на едро освобождава стоките на клиентите. Товаренето на автомобила се извършва от три екипа товарачи, всеки от които се състои от 4 души. Складът може да поеме едновременно 5 автомобила и ако в този момент пристигне нов автомобил, той не се обслужва. Интензитетът на входящия поток е 5 автомобила на час. Скоростта на натоварване е 2 автомобила на час. Дайте оценка на складовата дейност и възможност за нейната реорганизация.
6) Митницата разполага с три терминала. Интензивността на потока от МПС, превозващи товари и подлежащи на митнически контрол, е 30 единици. на ден. Средното време за митническа обработка на терминала за едно превозно средство е 3 часа. Ако има 5 коли на опашка за преминаване през митнически контрол, то пристигащите коли отиват в друга митница. Намерете показатели за ефективност на митниците.
7) Средно автомобилите със строителни материали пристигат на строителната площадка за 40 минути. Средното време за разтоварване на едно превозно средство е 1,8 часа. В разтоварването участват два екипа товарачи. Не повече от 5 превозни средства могат да бъдат на опашка за разтоварване на строителната площадка. Определете показателите за ефективност на строителната площадка.
8) На автомивка с три работни места пристигат средно 12 коли на час. Ако вече има 6 коли на опашката, новопристигналите коли не се присъединяват към опашката, а напускат прането. Средното време за измиване на автомобила е 20 минути, средната цена на услугите за автомивка е 150 рубли. Определете показателите за ефективност на автомивката и средната загуба на приходи през работния ден (от 9 до 19 часа).
9) Интензивността на потока от МПС, превозващи товари и подлежащи на митнически контрол, е 50 единици. на ден. Средното време за митническа обработка на терминала за едно превозно средство е 2,8 часа. Максималната опашка за митнически контрол трябва да бъде не повече от 8 автомобила. Определете колко терминала трябва да бъдат отворени на митницата, така че вероятността от престой на превозното средство да е минимална.
Система с ограничена дължина на опашката. Нека разгледаме канал QS с чакане, който получава поток от заявки с интензитет ; интензивност на обслужване (за един канал); брой места в опашката.
Състоянията на системата са номерирани според броя на заявките, свързани със системата:
без опашка:
Всички канали са безплатни;
Един канал е зает, останалите са свободни;
Каналите са заети, останалите не са;
Всички канали са заети, няма свободни канали;
има опашка:
Всички n канала са заети; едно приложение е на опашката;
Всички n канала са заети, r приложения са в опашката;
Всички n канала са заети, мприложения в опашка.
GSP е показан на фиг. 5.9. Всяка стрелка е маркирана със съответните интензитети на потоците от събития. По стрелките отляво надясно системата винаги се прехвърля от един и същ поток от заявки с интензитет на
Многоканален експоненциален SMOсе различава от едноканален по следния начин. В него има повече от един канал. Входяща заявка се нарежда на опашка, ако всички канали са заети. В противен случай заявката заема безплатен канал. 
(5.56)
Нека напишем изрази за граничните вероятности на състоянията, използвайки нотацията: (вижте 5.45)
Вероятност за провал. Получена заявка се отхвърля, ако всички са заети нканали и всичко мместа в редицата:
(5.57)
Относителната производителност допълва вероятността от повреда до едно:
Абсолютна производителност на QS:
(5.58)
Среден брой заети канали. За SMOпри откази съвпада със средния брой заявления в системата. За SMOс опашка средният брой на заетите канали не съвпада със средния брой приложения в системата: последната стойност се различава от първата със средния брой приложения в опашката.
Нека означим средния брой заети канали с . Всеки зает канал обслужва средно заявки за единица време и SMOкато цяло обслужването е средно Априложения за единица време. Разделяйки едно на друго, получаваме:
Средният брой заявки в опашка може да се изчисли директно като математическо очакване на дискретна случайна променлива:
(5.59)
Тук отново (изразът в скоби) се появява производната на сумата от геометричната прогресия (виж по-горе (5.50), (5.51)-(5.53)), като използваме връзката за нея, получаваме:
Среден брой приложения в системата:
Средно време на изчакване за приложение на опашка. Нека разгледаме редица ситуации, които се различават по състоянието, в което новопристигналата заявка ще намери системата и колко време ще трябва да чака за обслужване.
Ако дадена заявка не намери всички канали заети, тя изобщо няма да трябва да чака (съответните членове в математическото очакване са равни на нула). Ако приложението пристигне в момент, когато всички са заети Пканали, но няма опашка, тя ще трябва да изчака средно време, равно на (защото „потокът от освобождавания“ на каналите има интензитет ). Ако дадено приложение намери всички канали заети и едно приложение пред него в опашката, то ще трябва да изчака средно известно време (за всяко приложение отпред) и т.н. Ако дадено приложение се окаже в опашка от приложения , ще трябва да изчака средно известно време. Ако новопристигнало приложение се окаже в опашката мприложения, тогава изобщо няма да чака (но няма да бъде обслужен).
Средно време на изчакваненамираме, като умножим всяка от тези стойности по съответните вероятности:
(5.60)
Точно както в случая на едноканален QS с изчакване, отбелязваме, че този израз се различава от израза за средната дължина на опашката (5.59) само с фактора , т.е.
Средно време, през което едно приложение остава в системата, същото като при едноканален SMO, се различава от средното време на изчакване със средното време за обслужване, умножено по относителната производителност:
Системи с неограничена дължина на опашка.
Разгледахме канал QS с изчакване, когато не повече от мприложения.
Както и преди, когато се анализират системи без ограничения, е необходимо да се вземат предвид получените отношения за .
Получаваме вероятностите за състояния от формули (5.56) чрез преминаване към границата (при ). Обърнете внимание, че сумата от съответната геометрична прогресия се събира при и се разминава при > 1. Ако приемем, че< 1 и устремив в формулах (5.56) величину мдо безкрайност, получаваме изрази за граничните вероятности на състоянията:
(5.61)
Вероятност за отказ, относителна и абсолютна производителност. Тъй като всяка заявка рано или късно ще бъде обслужена, характеристиките на пропускателната способност на QS ще бъдат:
Получаваме средния брой приложения в опашката от (5.59):
и средното време на изчакване е от (5,60):
Средният брой заети канали, както и преди, се определя чрез абсолютната пропускателна способност:
Средният брой приложения, свързани с QS, се определя като средния брой приложения в опашката плюс средния брой приложения в услуга (среден брой заети канали):
Нарастващата сложност на структурите и режимите на реалните системи усложнява използването на класическите методи на теорията на масовото обслужване поради нарастващото измерение на решаваните проблеми, което е особено характерно за системи с мрежова структура. Един от възможните начини за преодоляване на размерността е използването на модели под формата на мрежи за опашка (Queuing).
SeMOе колекция от краен брой обслужващи възли, в които заявките циркулират, движейки се в съответствие с матрицата за маршрутизиране от един възел към друг. Възелът е винаги отворен SMO. В същото време отделете SMO SMO− структурата на системата и циркулиращите изисквания SeMO, − компоненти на материалните потоци (съобщения (пакети) в комуникационна мрежа, задачи в многопроцесорни системи, контейнери на товарни потоци и др.).
на свой ред SeMOизползвани за определяне на най-важните системни характеристики на информационните системи: производителност;време за доставка на пакета; вероятност за загуба на съобщение и блокиране във възли; области на допустими стойности на натоварване, при които се осигурява необходимото качество на услугата и др.
На теория SeMOКонцепцията за състояние на мрежата е фундаментална. Най-важната характеристика на мрежите МО− вероятности на техните състояния. Да се определят вероятностите на състоянията SeMOизследват произволния процес, протичащ в мрежата. Като вливащи се модели SeMOНай-често се използват и марковски и полумарковски процеси.
3.3. Система за масово обслужване като модел
1.5. Мрежи за опашка
Марков процес с непрекъснато време описва функционирането на експоненциален SeMO.
Мрежата се нарича експоненциаленако входящите потоци от изисквания във всеки SMO Поасон, както и времената на всеки етап от услугата, внедрена по всяко време SMOмрежите имат експоненциаленразпространение. Това ни позволява да приемем, че етапите на обслужване са независими един от друг и не зависят нито от параметрите на входящия поток, нито от състоянието на мрежата, нито от маршрутите на заявките.
Теория на експоненциалите SeMOнай-развит и се използва широко както за изследване на PD мрежи, така и за изследване на многопроцесорни изчислителни системи (CS).Разработени са практически формули за изчисляване на вероятностно-временните характеристики (PTC) на такива мрежи и системи.
Опитите за задълбочен анализ на немарковски модели на мрежови системи срещат значителни трудности, които се дължат по-специално на липсата на независимост от продължителността на престоя на изискванията в различни възли на модели на мрежови системи с нестандартни дисциплини. Така например, при доста реалистично допускане, че дължината на заявката остава постоянна по време на предаването й през мрежови възли, е необходимо да се проследи пътя на всяка заявка, което прави невъзможно аналитичното изчисляване на характеристиките за мрежа с брой възли M>2.
Анализът на трудовете, посветени на изследването или изчисляването на немарковски модели, показва, че решенията, като правило, се получават алгоритмично чрез сложни числени изчисления с помощта на трансформации на Лаплас-Стилтьес, изпълняват се в софтуер, са много трудоемки или имат значителни грешки при оценката на показателите за ефективност на информационните системи (ИС) в областта на средно и тежко натоварване. Следователно, за моделиране SeMO,излизайки от класа на мултипликативните, те използват приближени методи.
Сравнителен анализ на методите за приближено моделиране SeMOи дадените примери показват, че е необходимо да се използват приблизителни методи за изчисляване на SeMO с голяма предпазливост, че при изчисляването на конкретни SeMO, в процеса на решаване на различни приложни проблеми, изглежда необходимо да се проведат изследвания, за да се оцени точността и чувствителността на използвания метод, както и провеждане на симулационен експеримент на оригиналния SeMO за достатъчно голям набор от стойности на различни параметри.
Аналитичните методи за изчисляване на характеристиките на IS се основават, като правило, на анализ на експоненциален CeMO. С помощта на този математически апарат е възможно да се получат аналитични модели за решаване на широк кръг от проблеми при изследване на системи. SeMO е преди всичко набор от взаимосвързани системи за опашка. Ето защо е необходимо да си припомним основните характеристики на тези системи.
Мрежа за опашкапредставлява набор от крайни числа нобслужващи възли, в които циркулират заявки, движещи се в съответствие с матрицата на маршрутизиране от един възел към друг. Един възел винаги е отворен QS (и QS може да бъде от всеки клас). В същото време отделете SMOпоказват функционално независими части от реална система, връзки между SMO- структурата на системата и циркулиращите изисквания SeMO,- компоненти на материалните потоци (съобщения (пакети) в комуникационна мрежа, задачи в многопроцесорни системи, контейнери на товарни потоци и др.).
За визуално представяне SeMOизползва се граф, чиито върхове (възли) съответстват на отделни SMO, а дъгите показват връзките между възлите.
Преходът на приложенията между възлите става незабавно в съответствие с вероятностите за преход 
, p ij- вероятността, че заявката след обслужване в възела азще отиде на възел й. Естествено, ако възлите не са директно свързани един с друг, тогава p ij= 0. Ако от аз- th възел преход само към един възел й, Че p ij= 1.
SeMOкласифицирани по няколко критерия (фиг. 4).
Мрежата се нарича линеен, ако интензитетите на потоците от приложения във възлите са свързани помежду си чрез линейна зависимост
л й=а ijл аз,
къде ij- коефициент на пропорционалност, или спрямо източника
л й=а йл 0 ,.
Коефициент а йнаречен коефициент на предаване, той характеризира дела на заявления, получени в j-ти възел от източника на приложения, или - средният брой пъти, през които приложение преминава през този възел през времето, през което приложението е в мрежата.
Ако интензитетите на потоците на приложенията в мрежовите възли са свързани с нелинейна връзка (например, 
), тогава мрежата се извиква нелинейни..
Една мрежа винаги е линейна, ако приложенията не се губят или умножават в нея.
ОтворетеМрежата е отворена мрежа, в която заявките идват от външната среда и напускат мрежата във външната среда, след като бъдат обслужени. С други думи, характеристиката на отворената верига SeMO(RSeMO) е наличието на един или повече независими външни източници, които генерират приложения, влизащи в мрежата, независимо колко приложения вече са в мрежата. По всяко време в RSeMOможе да има произволен брой приложения (от 0 до ¥).
Ориз. 4. Класификация на мрежите за масово обслужване
IN затворен SeMO (ZSeMO)циркулира фиксиран брой приложения и няма външен независим източник. Въз основа на физически съображения, в ZSeMОколо външната дъга е избрана, върху която е маркирана псевдо-нулаточка, спрямо която могат да бъдат измерени времевите характеристики.
Комбиниранмрежата е мрежа, в която постоянно циркулират определен брой приложения и има приложения, идващи от външни независими източници.
IN хомогененприложения от същия клас циркулират в мрежата. И, обратно, в разнороднимрежите могат да съдържат приложения от няколко класа. Приложенията принадлежат към различни класове, ако се различават поне по един от следните атрибути:
Законът за разпределение на продължителността на услугата във възлите;
Приоритети;
Маршрути (пътища на движение на заявки в мрежата).
IN експоненциаленмрежите с продължителност на услугата във всички възли са разпределени по експоненциален закон, а потоците, влизащи в мрежата с отворен цикъл, са прости (Poisson). Във всички останали случаи мрежата е неекспоненциален.
Ако услугата с приоритет се предоставя в поне един възел, тогава това е - приоритетнето. Приоритетът е знак, който определя реда на обслужване. Ако обслужването на заявки в възли се извършва по реда на получаване, тогава такава мрежа без приоритет.
По този начин ще наречем експоненциален SeMO, отговарящи на изискванията:
Входящи потоци SeMOПоасон;
Във всичко N SMOвремето за обслужване на заявките има експоненциална функция на разпределение на вероятностите и заявките се обслужват по реда на пристигането;
Прехвърляне на приложение от изход азти SMO на входа й- е независимо случайно събитие с вероятност p ij ; p i0- вероятността приложението да напусне CeMO.
Ако приложенията влязат в мрежата и я напуснат, тогава мрежата се нарича отворена. Ако приложенията не влизат или не излизат от мрежата, мрежата се нарича затворена. Броят на приложенията в затворена мрежа е постоянен.
