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

Содержание 

Введение

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

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

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

Все системы массового  обслуживания имеют следующие основные элементы:

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

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

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

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

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

в) Дисциплина очереди или правила поведения  очереди. Это правила, в соответствии с которыми обслуживающий механизм принимает поступившую заявку на обслуживание. Например, “первым пришел – первым обслуживается”, “последним пришел – первым обслуживается”, “случайный отбор заявок” и т.п.

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

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

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

Характеристики эффективности  СМО:

1. Среднее число обслуживаемых заявок СМО в единицу времени;
2. Среднее число заявок, покидающих СМО не обслуженными;
3. Среднее время ожидания в очереди и т.п.

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

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

При изучении СМО можно  выделить три класса задач: задача анализа поведения систем, статические задачи, операционные задачи.

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

Q(t) – длина очереди в момент времени t, т.е. число требований находящихся в системе;

W(t) – продолжительность ожидания обслуживания относительно требования, которое поступило в момент времени t;

I_n – продолжительность n-го периода простоя системы.

На практике часто  используется показатель, который называется степенью загруженности обслуживающего прибора или коэффициентом нагрузки:

.

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

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

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

Используются следующие обозначения:

M – пуассоновское или экспоненциальное распределение;

D – постоянная величина;

E_k – распределение Эрланга;

G – произвольное распределение;

GI – распределение в случае независимых событий.

Например, система M /D /s – система с s приборами, обслуживающая поступающие требования за строго определенный интервал времени, поступающие требования образуют пуассоновский поток.

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

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

           Цель работы: освоение принципов моделирования СМО и получение навыков проведение имитационного эксперимента с использованием полученной модели.

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

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

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

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

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

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

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

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

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

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

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

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

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

При исследовании эффективности  работы системы обслуживания важную роль играют различные способы расположения в системе каналов обслуживания.

Анализ задания и принятия допущений

Код задания для варианта 4 имеет следующий вид:

«δХNIA2в»

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

• Двухканальная СМО с параллельной работой каналов и занятием их в соответствии  с установленными вероятностями р1 и рn, у которой на входе простейший поток с параметрами λх;
• В системе необходимо создать допустимую очередь с ограниченной длиной ( );
• Заявки без приоритетов – обслуживание по принципу «первым пришел – первым обслуживается».

Разработанная модель должна соответствовать следующими условиями:

• Моделирование системы прекращается с достижением определения среднего времени пребывания заявок в системе;
• Результат моделирования должен представлять ограничение объема по времени моделирования  ( ).

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

• Время обслуживания заявки в канале является случайной величиной, распределенной по экспоненциальному закону распределения ;
• Если время ожидания заявки в очереди истекло, она покидает систему и считается не обслуженной.

Кроме того, для реальной СМО дополнительно принимают допущения и задаются следующие параметры:

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

Построение концептуальной модели

Для построения концептуальной модели необходимо разбить общий  процесс рассмотрения заявок на подпроцессы, выделить логику поведения заявок. Для этого составим алгоритм на уровне функциональных блоков (рис 1.).

Рис 1. Укрупненная структура  модели СМО

Алгоритм моделирования СМО

Начальные условия:

1)   Рассматриваемая в задаче СМО представляет собой СМО с:

•   Двухканальным обслуживанием;
•   Двухканальным входным потоком ( имеет 2 входа, на один из которых  поступают случайный поток Заявок I, на другой вход – поток Заявок II).

2)   Определение времен поступления и обслуживания заявок:

•   Времена поступления и обслуживания заявок генерируются случайно с заданным показательным законом распределения;
•   Интенсивности поступления и обслуживания заявок заданы;

3)   Функционирование рассматриваемой СМО:

•   Каждый канал обслуживает в каждый момент времени одну заявку;
•   Если в момент поступления новой заявки свободен хотя бы один канал, то пришедшая заявка поступает на обслуживание;
•   Если отсутствуют Заявки то система простаивает.

4)   Дисциплина обслуживания:

•   Приоритет Заявок I: если система занята (оба канала обслуживают заявки), причем один из каналов занят Заявкой II, Заявка I вытесняют Заявку II; Заявка II покидает систему необслуженной;
•   Если к моменту поступления Заявки II оба канала заняты, Заявка II не обслуживается; 
• Если к моменту поступления Заявки I оба канала обслуживают Заявки I, поступившая Заявка I покидает систему необслуженной;

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

Принцип моделирования:

•   Вводим начальные условия: общее время работы системы, значения интенсивностей потоков заявок; число реализаций работы системы;
•    Генерируем моменты времени, в которые прибывают заявки, последовательность прихода Заявок I Заявок II, время обслуживания каждой пришедшей заявки;
•   Считаем сколько заявок было обслужено, а сколько получило отказ;
•   Рассчитываем критерий эффективности СМО.

Программная реализация 

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

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

 Описание интерфейса:           

 При каждом новом запуске программы сначала вводится число реализаций работы системы, затем при каждой новой реализации вводится время функционирования СМО –Т. При поступлении новой заявки программа выводит сообщение (Поступила заявка 1, Поступила Заявка 2).Программа выводит сообщения об обслуживании/необслуживании вновь поступившей заявки. Затем, по окончании времени функционирования системы выводится сколько заявок поступило и сколько из них было обслужено, а сколько получило отказ. Далее программой производится расчет и вывод основных выбранных характеристик СМО.

Листинг программы представлен в приложении 1.           

 Работа программы и получение данных для анализа работы СМО           

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

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

 Новые значения  интенсивностей::      =2, =2, =2, =1.

Т.о. исследуем работу системы при следующих вариантах:

Результаты работы системы представлены в приложении 2.

Заключение

           Целью данного курсового проекта было построение модели двухканальной СМО и без приоритетов. Модель СМО была и реализована с помощью программы в среде TURBO PASKAL. В процессе нескольких реализаций работы СМО для двух вариантов значений интенсивностей поступления заявок в были получены результаты функционирования системы.  
            Проведенное исследование приведенные в приложениях 1-2.  
Список литературы

1. Фомин Г.П., Математические методы и модели в коммерческой деятельности. М: Финансы и статистика, 2010.
2. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения, М: Наука,2011.
3. Вентцель Е.С. Исследование операций, М:Наука, 2012.
4. Лифшиц А.Л. Статистическое моделирование СМО, М., 2010.
5. Советов Б.А., Яковлев С.А. Моделирование систем, М: Высшая школа, 2005.
6. Гмурман В.Е. Теория вероятностей и математическая статистика, М: Высшая школа, 2010.

Приложение 1

Листинг программы. 
 
^ PROGRAM CAN_SMO; 
TYPE 
CHANNAL = (FREE, CLAIM1, CLAIM2); 
TIME = word; 
INTENSITY = word; 
STATISTICS = word; 
VAR 
CHANNAL1, CHANNAL2 : CHANNAL;{Каналы } 
_T_, t, tc1, tc2 : TIME; {Время} 
l1, l2, n1, n2 : INTENSITY; {Интенсивности } 
served1, not_served1, 
served2, not_served2, 
S : STATISTICS; {Статистика} 
M,N:INTEGER;{число реализаций} 
FUNCTION W(t : TIME; l : INTENSITY) : boolean;{Определяет появилась ли заявка} 
Begin {по интенсивности потока l} 
if random < l/60 then W := TRUE else W := FALSE; 
End; 
FUNCTION F(t : TIME; n : INTENSITY) : TIME;{Определяет сколько будет обрабатываться заявка} 
Begin {по интенсивности обслуживания заявок n} 
F := t +round(60/(n)); 
End; 
BEGIN 
M:=0; 
^ WRITELN('ВВЕДИТЕ ЧИСЛО РЕАЛИЗАЦИЙ РАБОТЫ СМО'); 
READLN(N); 
REPEAT 
M:=M+1; 
writeln(M, '-ая реализация'); 
randomize; 
CHANNAL1 := FREE; CHANNAL2 := FREE; 
l1 := 3; l2 := 1; n1 := 2; n2 := 1; 
served1 := 0; not_served1 := 0; 
served2 := 0; not_served2 := 0; 
write('Введите время исследования СМО - Т: '); readln(_T_); 
repeat 
if tc1 = t then 
begin 
if CHANNAL1 = CLAIM1 then inc(served1) else inc(served2); 
^ CHANNAL1 := FREE; 
writeln('Канал1 выполнил заявку'); 
end; 
if tc2 = t then 
begin 
if CHANNAL2 = CLAIM1 then inc(served1) else inc(served2); 
CHANNAL2 := FREE; 
writeln('Канал2 выполнил заявку'); 
end; 
if W(t,l1) then 
begin 
writeln('Поступила заявка1'); 
if CHANNAL1 = FREE then 
begin CHANNAL1 := CLAIM1; tc1 := F(t,n1); writeln('Канал1 принял заявку1'); end 
else if CHANNAL2 = FREE then 
begin CHANNAL2 := CLAIM1; tc2 := F(t,n1); writeln('Канал2 принял заявку1'); end 
else if CHANNAL1 = CLAIM2 then 
begin CHANNAL1 := CLAIM1; tc1 := F(t,n1); inc(not_served2); writeln('Канал1 принял заявку1 вместо заявки2'); end 
else if CHANNAL2 = CLAIM2 then 
begin CHANNAL2 := CLAIM1; tc2 := F(t,n1); inc(not_served2); writeln('Канал2 принял заявку1 вместо заявки2'); end 
else begin inc(not_served1); writeln('заявка1 не обслужена'); end; 
end; 
if W(t,l2) then 
begin 
 
writeln('Поступила заявка2'); 
if CHANNAL1 = FREE then 
begin CHANNAL1 := CLAIM2; tc1 := F(t,n2); writeln('Канал1 принял заявку2');end 
else if CHANNAL2 = FREE then 
begin CHANNAL2 := CLAIM2; tc2 := F(t,n2); writeln('Канал2 принял заявку2');end 
else begin inc(not_served2); writeln('заявка2 не обслужена'); end; 
end; 
inc(t); 
until _T_ = t; 
S := served1 + not_served1 + served2 + not_served2; 
writeln('время работы СМО ',_T_); 
writeln('обслужено каналом1: ' ,served1); 
writeln('обслужено каналом2: ',served2); 
writeln('Поступило заявок : ',S); 
writeln('Обслужено заявок : ',served1+served2); 
writeln('Не обслужено заявок : ',not_served1+not_served2); 
{writeln('Интенсивность поступления заявок в систему : ',(served1+served2)/_T_:2:3);} 
writeln('Абсолютная пропускная способность системы : ',(served1+served2)/T:2:3); 
writeln('Вероятность отказа : ',(not_served1+not_served2)/S*100:2:1,'%'); 
writeln('Относительная пропускная способность системы: ',(served1+served2)/S:2:3); 
readln; 
^ UNTIL M>=N; 
writeln('моделирование закончено'); 
END.

Приложение 2

 
Результаты работы СМО.