26023

Понятие очереди. Классификация

Доклад

Информатика, кибернетика и программирование

Понятие очереди. Очереди характеризуются правилами стояния в очереди дисциплиной обслуживания количеством мест в очереди сколько клиентов максимум может находиться в очереди структурой очереди связь между местами в очереди. Бывают ограниченные и неограниченные очереди. Это такие системы в которых на пребывание заявки в очереди накладываются некоторые ограничения.

Русский

2013-08-17

50.44 KB

12 чел.

1. Понятие очереди. Классификация.

Очереди характеризуются правилами стояния в очереди (дисциплиной обслуживания), количеством мест в очереди (сколько клиентов максимум может находиться в очереди), структурой очереди (связь между местами в очереди). Бывают ограниченные и неограниченные очереди.

По дисциплине обслуживания СМО подразделяют на три класса:

1. СМО с отказами, в которых заявка, поступившая на вход СМО в момент, когда все каналы  заняты,  получает «отказ» и покидает СМО («пропадает»).  Чтобы  эта  заявка  все  же была обслужена, она должна снова поступить на вход СМО и рассматриваться при этом как заявка, поступившая впервые. Примером СМО с отказами может служить работа АТС: если набранный телефонный номер (заявка, поступившая на вход) занят, то заявка получает отказ, и,  чтобы  дозвониться  по этому  номеру,  следует  его  набрать  еще  раз (заявка  поступает  на вход как новая).

2. СМО с ожиданием (неограниченным ожиданием или очередью). В таких системах заявка, поступившая в момент занятости всех каналов, становится в очередь и ожидает освобождения канала, который примет ее к обслуживанию. Каждая заявка, поступившая на вход, в конце концов будет обслужена. Такие СМО часто встречаются в торговле, в сфере бытового и медицинского обслуживания, на предприятиях (например, обслуживание станков бригадой наладчиков).

3.  СМО смешанного типа (с ограниченным ожиданием). Это такие системы,  в которых на пребывание заявки в очереди накладываются некоторые ограничения.

Эти ограничения могут накладываться на длину очереди, т.е. максимально возможное число заявок, которые одновременно могут находиться в очереди. В качестве примера такой системы можно привести мастерскую по ремонту автомобилей, имеющую ограниченную по размерам стоянку для неисправных машин, ожидающих ремонта.

Ограничения ожидания могут касаться времени пребывания заявки в очереди, по истечению которого она выходит из очереди и покидает систему, либо касаться общего времени пребывания заявки в СМО (т.е. суммарного времени пребывания заявки в очереди и под обслуживанием).

В  СМО с  ожиданием и в СМО смешанного  типа применяются различные схемы обслуживания заявок из очереди.  Обслуживание  может  быть  упорядоченным,  когда заявки из очереди обслуживаются в порядке их поступления в систему, и неупорядоченным, при котором заявки из очереди обслуживаются в случайном порядке. Иногда применяется обслуживание с приоритетом, когда  некоторые заявки из очереди  считаются приоритетными и поэтому обслуживаются в первую очередь.


2. СМО с отказами и частичной взаимопомощью для массовых потоков. Граф, система уравнений, расчетные соотношения.

Постановка задачи. На систему обслуживания, имеющую n каналов обслуживания, поступает пуассоновский поток заявок с интенсивностью λ. Если все каналы заняты, заявка получает отказ в обслуживании, если хотя бы один канал свободен, принимается к обслуживанию. Время обслуживания заявки τ - случайная величина, распределенная по показательному закону с параметром µ. Окончание обслуживания можно рассматривать как появление на выходе системы обслуженной заявки. Таким образом, обслуженные отдельными каналами заявки образуют пуассоновский поток событий с интенсивностью µ.

Поведение такой системы массового обслуживания можно описать Марковским случайным процессом ξ(t), представляющим собой число заявок, находящихся в системе (для рассматриваемой системы оно совпадает с числом каналов занятых обслуживанием). Возможные состояния этого процесса E = (0, 1, . . . , n). Найдем характеристики рассматриваемой СМО в стационарном режиме.

Граф, соответствующий рассматриваемому процессу, представлен на рисунке 1.

Рис. 1. Граф СМО с отказами и частичной взаимопомощью

Система уравнений для стационарного распределения вероятностей имеет вид:

Решение данной системы дает стационарное распределения числа заявок в многоканальной системе с отказами:

Данная формула соответствует закону распределения Эрланга. Обозначив α =λ/µ - среднее число заявок, поступающих в систему за среднее время обслуживание одной заявки в одном канале, перепишем распределение Эрланга:

Здесь P (j, α), R(n, α) - распределение вероятностей и функция распределения пуассоновского закона.

Характеристики многоканальной системы массового обслуживания с отказами в стационарном режиме.

1. Вероятность отказа в обслуживании (вероятность того, что все каналы заняты):

2. Вероятность обслуживания заявки (относительная пропускная способность системы):

Вероятность обслуживания можно получить другим образом:

Здесь k - среднее число каналов, занятых обслуживанием, µk - средняя число заявок, обслуженных в единицу времени (абсолютная пропускная способность системы), λ - среднее число заявок, поступающих в единицу времени.

3. Среднее время обслуживания заявки в отдельном канале:

4. Среднее число каналов, занятых обслуживанием:

Среднее число каналов, занятых обслуживанием, можно рассчитать, используя формулу:


 

А также другие работы, которые могут Вас заинтересовать

75018. Не будьте собі ворогом. Конспект уроку здорового способу життя 47 KB
  Мета заходу: Виховувати в учнів негативне ставлення до вживання наркотиків бажання і вміння вести здоровий спосіб життя критично ставитись до своїх негативних вчинків. Що стається з наркоманом а продовжує радіти життю; б постійно шукає де б дістати наркотик; в пригнічений; г життя – муки. Втрачаєш радість життя. Можеш покінчити життя самогубством.
75019. Здоров’я народу - багатство країни. Позакласний захід з народознавства для 6-7-х класів 98.5 KB
  Українське житло мало чотиригранну будову – чотири стіни відповідали чотирьом сторонам світу. Вікна виходили на схід і на південь – до сонця. З північного боку, де панували темні, злі сили, вікон не було.
75020. Дванадцять місяців, народознавчий проект 162 KB
  Чи потрібні сучасній молоді знання про народні свята традиції Чи варто відроджувати їх ці питання визначили проблему. Мета проекту: ознайомлення учнів з багатством культурної спадщини українського народу; формування ціннісного ставлення до скарбів української духовної культури народного мистецтва традицій і звичаїв свого народу...
75021. Структура наукового дослідження, план-конспект уроку 128 KB
  Структура наукового дослідження Мета. Познайомити слухачів із методологією наукової творчості сформувати у них теоретичні знання про основні компоненти структури наукового дослідження та практичні вміння будувати структуру наукового дослідження користуватися одержаними знаннями при написанні наукових робіт стимулювати творчість дослідницькі вміння. Бесіда Яке слово найбільш підходить до поняття структура наукового дослідження Будова схема. Із чого починається наукове дослідження Із обґрунтування актуальності теми дослідження.
75023. Прийшла зима весела. Новорічне свято для учнів 3-4 класів 88 KB
  Ось палац наш крижаний Щоб зустріти рік Новий Ми запрошуєм гостей І дорослих і дітей. До нас у крижаний палац Запрошуємо друзі вас На новорічний бал святковий – Чудовий радісний казковий У містечку казковому – Крижаному чудовому – І цікаво і весело Буде всій дітворі У містечку казковому – Крижаному чудовому Ми гостей привітаємо Разом з Новим роком усіх Хай збуваються всі мрії Оживає світ казок В незабутнє святодиво Для дорослих і діток І вітаннями теплими Із піснями легендами З маскарадами іграми Йде до нас Новий рік Дід...
75024. Новогодние приключения, представление для учащихся 7-8 классов 95 KB
  Формирование эстетического восприятия прекрасного в окружающей действительности; воспитание интереса и стремления детей к развитию художественных способностей и творческой деятельности в различных видах искусства и литературы, усовершенствование эстетических знаний, умений и навыков...
75025. Україна велика повстала зі сну. Виховний захід 2.34 MB
  Узагальнити та систематизувати знання учнів про Україну, її історію, державні та народні символи. Розвивати увагу, память, виразність читання. Виховувати любов до рідної країни, почуття патріотизму...
75026. АЛГОРИТМ ИСПУСКАНИЯ ЛУЧЕЙ НА ВЕКТОРНО-РАСТРОВЫХ ГИС-МОДЕЛЯХ В ЗАДАЧАХ РАСЧЕТА ШУМОВОГО ЗАГРЯЗНЕНИЯ СЕЛИТЕБНОЙ ТЕРРИТОРИИ 4.07 MB
  разработка эффективных алгоритмов расчета эквивалентных уровней шумов на селитебной территории с возможностью построения шумовых карт. Алгоритмизация и моделирование процесса распространения звуковых волн в условиях городской застройки.