26023

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

Доклад

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

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

Русский

2013-08-17

50.44 KB

17 чел.

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

52515. Тексти для диктантів в 5 – 9 класах. Найбільше багатство – здоров’я 127 KB
  Боріться за здорове життя Тому головним девізом у кожного з нас повинен бути: постійний контроль і аналіз власних вчинків Пояснювальний диктант Пояснити правопис слів з подвоєними приголосними звуками Дбай про фізичну культуру. Диктант по памяті Визначити іменники та дієслова Біг сприяє розвитку легенів укріплює серцевий мяз сприяє обміну речовин позитивно впливає на нервовий стан. Коментований диктант Написання слів з подвоєними приголосними звуками правопис ь ьо апострофа Плавання покращує діяльність серцево ...
52516. Збірник диктантів з української мови 5 клас За матеріалами підручника Р. Мовчан «Українська література» 103.5 KB
  Окрім того можна доповнити диктанти іншими видами діяльності. Пояснювальні диктанти. Творчі диктанти Утворіть словосполучення з поданими словами. Пояснювальні диктанти
52517. Літературні диктанти 169.5 KB
  Учень відразу ж записує у зошит відповіді на запитання вчителя. Лінійні диктанти полегшують діяльність учнів тим що остання літера кожного слова відповіді є першою літерою наступного слова. Зразки літературних диктантів 5 клас Народна казка âМудра дівчинаâ Акродиктант Якщо ви правильно дасте відповіді на всі питання то з других літер сліввідповідей складете словощо вкаже різновид казки âМудра дівчинаâ. Що в світі прудкіш над усе Скільки ліктів полотна...
52518. Типи і приклади літературних диктантів 594.5 KB
  Літературними диктантами називаються такі види роботи які дають змогу швидко і різнобічно перевірити знання учнів з теми що вивчається. Літературні диктанти подібні до тестових завдань. Літературні диктанти як правило можуть проводитись на початку уроку перевірка домашнього завдання актуалізація опорних знань чи в його кінці підсумок узагальнення виконуються в зошитах чи на окремих аркушах можливе їх...
52519. Усі уроки географії у 6 класі 3.11 MB
  Посібник містить розробки усіх уроків географії у 6 класі за Програмою 12-річної школи із використанням сучасних методів та прийомів навчання. Особливу увагу автор приділив рекомендаціям щодо проведення етапу мотивації, а також варіативності завдань для актуалізації та закріплення. Пропонуються також додаткові матеріали, завдання творчого рівня.
52520. Усі уроки географії. 7 клас 1.61 MB
  Посібник підготовлено відповідно до нової програми Міністерства освіти і науки України. Він представляє собою детальні розробки уроків відповідно до авторського календарного планування, причому кілька тем уроків представлені двома альтернативними варіантами. Для кожного уроку зазначено: мету, як навчальну з предмета, так і виховну, розвивальну; тип; найдоступніше обладнання; опорні та базові поняття; об’єкти географічної номенклатури.
52521. Усі уроки географії. 8 клас 1.16 MB
  Завершальним етапом роботи учнів на уроці є підсумок уроку. Здебільшого пропонуються прийоми, які дозволяють учням зробити його самостійно. Розробку уроку завершують різні види домашнього завдання. Представлені уроки тематичного оцінювання, завдання яких складені подібно до завдань, які використовувались під час ЗНО, відповідають програмним вимогам щодо знань і вмінь.
52522. Ділення раціональних чисел 153.5 KB
  Обладнання: фізична карта світу макет козацької чайки піратського корабля сигнальні картки карткизавдання; підручник для 6го класу: Математика Мерзляк А. Щоб зорієнтуватися в просторі нам треба розвязати завдання за правильними відповідями відшукати слово яке вкаже на курс нашої подорожі. ІІІ етап Поповнення запасів їжі і питної води Робота з сигнальними картками: Тестові завдання учні підіймають картку з правильною на їх думку відповіддю...
52523. Найбільший спільний дільник кількох чисел ( НСД) 34 KB
  Мета: сформулювати поняття спільного дільника кількох чисел найбільшого спільного дільника взаємно простих чисел; домогтися засвоєння алгоритму знаходження НСД кількох чисел. Коротко це можна записати так: НСД45, 30 = 15. Для довільних чисел і b пишуть так НСД; b.