Методы и модели системы массового обслуживания

1

Размещено на http://www.allbest.ru/

Министерство образования Российской Федерации

Федеральное агентство по образованию

Московский государственный открытый университет

Факультет информатики и радиоэлектроники

Кафедра вычислительной техники и программирования

Курсовая работа

тема: Методы и модели системы массового обслуживания

по дисциплине: Компьютерное моделирование

Москва 2009

Введение

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

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

Средства, обслуживающие требования, называются обслуживающими устройствами или каналами обслуживания. Например, к ним относятся каналы телефонной связи, посадочной полосы, мастера-ремонтники, билетные кассиры, погрузочно-разгрузочные точки на базах и складах.

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

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

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

1. Теоретическая часть. Основные элементы СМО

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

В зависимости от формирования СМО, ее различают на:

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

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

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

По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

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

1.1 Характеристики СМО

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

1. Среднее время обслуживания;

2. Среднее время ожидания в очереди;

3. Среднее время пребывания в СМО;

4. Средняя длина очереди;

5. Среднее число заявок в СМО;

6. Количество каналов обслуживания;

7. Интенсивность входного потока заявок;

8. Интенсивность обслуживания;

9. Интенсивность нагрузки;

10. Коэффициент нагрузки;

11. Относительная пропускная способность;

12. Абсолютная пропускная способность;

13. Доля времени простоя СМО;

14. Доля обслуженных заявок;

15. Доля потерянных заявок;

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

17. Среднее число свободных каналов;

18. Коэффициент загрузки каналов;

19. Среднее время простоя каналов;

1.2 Параметры структуры СМО

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

Простейшей одноканальной моделью с вероятностным входным потоком и процедурой обслуживания является модель, характеризуемая показательным распределением как длительностей интервалов между поступлениями требований, так и длительностей обслуживания. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид

,

где - интенсивность поступления заявок в систему.

Под интенсивностью потока понимают

,

где m(t, t+) - среднее число событий в интервале (t, t+).

Плотность распределения длительностей обслуживания:

,

где - интенсивность обслуживания.

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

Для простейшего потока интенсивность = const.

Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способности системы. Система имеет два состояния: S0 - канал свободен и S1 - канал занят. Обозначим вероятности состояний:

P0(t) - вероятность состояния S0 , P1(t) - вероятность состояния S1 . Составим систему уравнений Колмогорова:

,

C учетом того, что , решение системы такое:

;

Для 1-канальной СМО с отказами вероятность есть не что иное, как относительная пропускная способность системы

По истечении большого интервала времени (при ) достигается стационарный режим:

Абсолютная пропускная способность (А) - среднее число заявок, которое может обслужить СМО в единицу времени:

или

Вероятность отказа в обслуживании заявки будет равна вероятности состояния "канал занят":

.

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

Если в момент появления заявки на входе в СМО хотя бы один канал свободен от обслуживания, ее обслуживание будет начато немедленно. Однако вполне вероятна ситуация, когда все m каналы заняты обслуживанием. В этом случае обслуживание заявки задерживается, и заявка встает в очередь. Таким образом, вторым важным компонентом является очередь, параметром которой является число мест в очереди n. В приоритетных системах очередь может быть разделена на несколько очередей, для каждой из которых должно быть указанно число мест. На число мест в очереди может быть наложено ограничение, это может быть сделано для каждой очереди в отдельности, так и на все очереди в целом. При этом могут быть конфликтные ситуации. При этом на заявку может быть отказ системы принять заявку.

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

1.3 Входящий поток

Входящий поток наиболее распространен в практике это простейший поток заявок, обладающий свойствами стационарности, ординарности и отсутствия последствия.

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

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

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

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

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

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

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

Среднее число требований, поступающих в систему обслуживания за единицу времени, называется интенсивностью поступления требований.

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

1.4 Выходящий поток

Совокупность обслуженных и потерянных заявок образует выходящий поток СМО.

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

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

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

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

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

(чел./мин, р./ дн., кг/ч, докум./дн.),

где - среднее время обслуживания.

Важной характеристикой СМО, объединяющей л и м, является интенсивность нагрузки

1.5 СМО с отказами

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

По ниже написанным формулам можно рассчитать СМО с отказами:

1. Вероятность простоя каналов обслуживания, когда нет заявок (k = 0):

2. Вероятность отказа в обслуживании, когда поступившая на обслуживание заявка найдет все каналы занятыми (k = n):

;

3. Вероятность обслуживания:

;

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

;

1.6 СМО с неограниченным ожиданием

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

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

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

Для систем с ожиданием существует дисциплина очереди:

1. Обслуживание в порядке очереди по принципу “первым пришел - первым обслужен”;

2. Случайное неорганизованное обслуживание по принципу “последний пришел - первым обслужен”;

3. Обслуживание с приоритетами по принципу “самые главные вне очереди”;

По ниже написанным формулам можно вычислить СМО с неограниченным ожиданием:

Вероятность простоя каналов, когда нет заявок (k = 0):

;

Предполагается, что .

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

, ;

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

;

2. Вероятность того, что заявка окажется в очереди:

;

3. Среднее число заявок в очереди:

;

4. Среднее время ожидания заявки в очереди:

;

5. Среднее время пребывания заявки в СМО:

;

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

;

7. Среднее число свободных каналов:

;

8. Коэффициент занятости каналов обслуживания:

;

9. Среднее число заявок в СМО:

;

1.7 СМО с ожиданием и ограниченной длиной очереди

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

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

Ограничения на длину очереди могут быть из-за:

1. Ограничения сверху времени пребывания заявки в очереди;

2. Ограничения сверху длины очереди;

3. Ограничения общего времени пребывания заявки в системе.

По ниже написанным формулам можно рассчитать СМО с ожиданием и с ограниченной длиной очереди:

1. Вероятность простоя каналов обслуживания, когда нет заявок (k = 0):



;

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

;

3. Вероятность обслуживания:

;

4. Абсолютная пропускная способность:

;

5. Среднее число занятых каналов:

;

система массовый обслуживание поток

6. Среднее число заявок в очереди:

;

1.8 Одноканальная СМО с ожиданием

Пусть простейший поток заявок на обслуживание - простейший поток с интенсивностью л.

Интенсивность потока обслуживания равна м. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что СМО не может вместить более N заявок, т.е. заявки, не попавшие в ожидание, покидают СМО. Состояния СМО имеют следующий вид:

S0 - канал свободен;

S1 - канал занят, очереди нет;

S2 - канал занят, одна заявка в очереди;

Sn - канал занят, n-1 заявка в очереди;

SN - канал занят, N-1 заявка в очереди.

Процесс в данной системе будет описан системой алгебраических уравнений:

где ;

n - номер состояния.

Система уравнений имеет следующее решение;



Выполнение условия необязательно, поскольку число допускаемых в СМО заявок контролируется путем введения ограничения на длину очереди. Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1):

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

;

2. Относительная пропускаемая способность СМО:

;

3. Абсолютная пропускная способность СМО:

;

4. Среднее число находящихся в СМО заявок:

;

5. Среднее время пребывания заявки в СМО:

;

6. Средняя продолжительность пребывания заявки в очереди:

;

7. Среднее число заявок в очереди:

1.9 Многоканальная СМО с ожиданием

Пусть входной и выходной поток с интенсивностями л и м, соответственно. СМО имеет С каналов обслуживания. Средняя продолжительность обслуживания одного клиента равна.

Многоканальное СМО с ожиданием и неограниченной очередью может быть описано с помощью системы алгебраических уравнений:

;

;

Здесь есть вероятность того, что в СМО n клиентов находится на обслуживании. Среднее число клиентов в очереди на обслуживание определяется следующей формулой:

 .

Среднее число находящихся в СМО клиентов (на обслуживании и в очереди):

.

Средняя продолжительность пребывания клиента (заявки) в очереди:

.

Средняя продолжительность пребывания клиента в СМО:

.

2. Практическая часть

2.1 Задача по СМО с отказами

Пример 1. Контроль готовой продукции фирмы осуществляют 3 контролера. Если изделие поступает на контроль, когда все контролеры заняты проверкой готовых изделий, то оно остается не проверенным. Среднее число изделий, выпускаемых фирмой 18 изд./ч. Среднее время на проверку одного изделия 6 минут.

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

Решение.

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

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

3. Вероятность обслуживания:

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

5. Доля каналов, занятых обслуживанием:

6. Абсолютная пропускная способность:

Поскольку у нас вышло, что и нам нужно узнать, сколько контролеров нужно поставить, мы возьмем и увеличим количество контролеров до n=6.

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

2. Вероятность обслуживания:

Ответ: Вероятность того, что при n=3 деталь пройдет необслуженной, составляет 27%, и контролеры будут заняты на 43%.

2.2 Задача по СМО с неограниченным ожиданием

Пример 2. Приходная касса городского района с временем работы 8 часов в день, проводит прием от населения коммунальных услуг и различных платежей в среднем от 280 человек в день.

В приходной кассе работает 4 оператора. Средняя продолжительность обслуживания одного клиента составляет 4 минуты.

Определить характеристики работы приходной кассы как объекта СМО.

Решение.

1. Вероятность простоя кассы городского района в течении рабочего дня:

2. Вероятность застать кассу городского типа занятой:

3. Вероятность очереди:

4. Среднее число заявок в очереди:

Ответ. Вероятность простоя приходной кассы городского района равна 5% рабочего времени, вероятность посетителю оказаться в очереди 0,2179 чел., среднее время ожидания посетителями обслуживания 0,3738 мин.

2.3 Задача по СМО с ожиданием и ограниченной длиной очереди

Пример 3. На АЗС установлено 21 колонка для выдачи бензина. Около станции находится площадка на 3 автомашины для ожидания заправки. На станцию прибывает в среднем 25 машин/ч. среднее время заправки одной автомашины 2,5 мин.

Определить вероятность отказа.

Решение.

1. Вероятность простоя колонок АЗС:

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

3. Вероятность обслуживания:

4. Абсолютная пропускная способность:

Выводы и рекомендации

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

Большой вклад в развитие СМО внесли очень много ученых по всему миру. Так же в развитие СМО были вложены работы и старания многих российских ученых. Одни из самых известных были и есть такие ученые как Гнеденко и Хинчин. Они не щадили себя и свои силы для развития СМО.

Библиографический список

1. Бережная Е.В., Бережной В.И. «Математические методы моделирования экономических систем», 2001г.

2. Саульев В.К. «Математические методы теории массового обслуживания», 1999г.

3. Бусленко Н.П. «Автоматизация имитационного моделирования сложных систем».

4. Яковлев С.А. «Моделирование систем».

Размещено на Allbest.ru