История и основные понятия теории систем массового обслуживания

  

 Содержание:

 

      Введение.

1. История и основные понятия теории систем массового обслуживания
1. Классификация СМО и их основные элементы.
2. Элементы практического применения теории систем массового обслуживания
3. Системы массового обслуживания на современном этапе

Заключение

Список литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Введение.

 

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

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

 

 

2.  История и основные понятия теории систем массового обслуживания

Первоначальное развитие теории массового обслуживания связано с именем датского ученого А.К. Эрланга (1878-1929),с его трудами в области проектирования и эксплуатации телефонных станций. Целью решения задач было упорядочить работу телефонной станции и заранее рассчитать качество обслуживания потребителей в зависимости от числа используемых устройств. В 1909 году Эрланг применил теорию вероятностей к исследованию зависимости обслуживания телефонных вызовов от числа поступающих на телефонную станцию вызовов.

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

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

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

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

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

 

1. Классификация СМО и их основные элементы.

 

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

 

 

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

 

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

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

          где Т - среднее значение интервала между поступлением очередных требований.

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

Закон распределения Пуассона выражается формулой:

 

где  P _k(t)  вероятность того, что в обслуживающую систему за время t поступит именно k требований; где λ. - среднее число требований, поступивших на обслуживание в единицу времени.

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

 

достаточно высоким  приближением. Почему такое предположение в ряде важных случаев оказывается верным, дает ответ общая теорема А.Я.Хинчина.

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

Одним из признаков закона распределения Пуассона является равенство математического ожидания случайной величины и дисперсии этой же величины, т.е α=σ²

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

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

При показательном законе распределения времени обслуживания вероятность P_{t_обс} события, что время обслуживания продлиться не более чем t, равна:

где v - интенсивность обслуживания одного требования одним обслуживающим устройством, которая определяется из соотношения:   

(1) где t_обс- среднее время обслуживания одного требования одним обслуживающим устройством.

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

    

где n - количество обслуживающих устройств.

Важным параметром СМО  является коэффициент загрузки α, который определяется по формуле: (2)

Из (1) и (2) получаем, что                    

Для СМО с ожиданием  количество обслуживаемых устройств n должно быть n>α, иначе очередь будет неограниченно расти.

Для эффективной работы СМО с отказами и смешанного типа это условие может быть ослаблено, n≥α

 

 

 

 

 

 

 

 

 

 

 

 

3. Элементы практического применения теории систем массового обслуживания

Рассмотрим  систему массового обслуживания на примере обслуживания рабочих необходимым инвентарем.

Допустим, что в инвентарной  кладовой работают два человека. Требуется  определить, в какой степени они  своевременно обеспечивают заявки на обслуживание, поступающие от рабочих; не обходятся ли простои рабочих в очереди дороже, чем дополнительное содержание еще одного или двух работников кладовой?

Таблица 1. – Расчет полного  числа прихода рабочих в кладовую

Число приходов в единицу  времени (за 15 мин)	Наблюдаемое число приходов, %	Наблюдаемая частота  приходов, %	Полное число приходов рабочих (гр.1 * гр.2)	Число приходов в единицу  времени (за 15 мин)	Наблюдаемое число приходов, %	Наблюдаемая частота  приходов, %	Полное число приходов рабочих (гр.1 * гр.2)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14	0 0 1 3 5 8 10 12 13 16 18 20 19 21 25	0 0 0,33 1,00 1,67 2,67 3,33 4,00 4,33 5,33 6,00 6,67 6,33 7,00 8,33	0 0 2 9 20 40 60 84 104 144 180 220 228 273 350	15 16 17 18 19 20 21 22 23 24 25 26	23 20 18 16 13 11 10 8 5 3 1 1 300	7,67 6,67 6,00 5,33 4,33 3,67 3,33 2,67 1,67 1,00 0,33 0,33 99,99	345 320 306 288 247 220 210 176 115 72 25 26