Теория массового обслуживания
Оптимальная стратегия распределения заявок различных типов по обслуживающим приборам. Многоканальная система массового обслуживания с неограниченной очередью и параллельными потоками заявок. Построение математической модели. Программа Microsoft Excel.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 22.08.2017 |
| Размер файла | 1,1 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Теория массового обслуживания
Введение
Теория массового обслуживания как ответвление теории вероятностей - наука сравнительно новая. Ее возникновение было обусловлено модернизацией различных предприятий современного общества в начале прошлого столетия. На данный момент теория массового обслуживания может быть применима во множестве областей, однако, не все предприятия ее используют.
В теории массового обслуживания насчитывается большое число различных моделей массового обслуживания. Однако, наиболее популярные системы несложно классифицировать:
· системы массового обслуживания с потерями (отказами)
· системы массового обслуживания с ожиданием
· системы массового обслуживания с ограниченным временем ожидания
· системы массового обслуживания с ограниченной длиной очереди
Системами массового обслуживания с потерями (отказами) называются те системы, в которых при полной загруженности системы, заявки не накапливаются в очереди, а получают отказ и уходят из системы. Для систем массового обслуживания с ожиданием, напротив, характерно, что заявки скапливаются в очередь, причем какой угодно длины. Системы, в которых заявки накапливаются, но время их пребывания в системе ограничено, называются системами массового обслуживания с ограниченным временем ожидания. А для систем массового обслуживания с ограниченной длиной очереди характерно накапливание заявок ровно до определенного числа, предусмотренного данной системой.
Также, системы массового обслуживания разделяют на одноканальные и многоканальные, по числу приборов, соответственно.
В своей работе я делаю попытку найти оптимальную стратегию распределения заявок различных типов по обслуживающим приборам.
Для данной задачи подойдет многоканальная система массового обслуживания с неограниченной очередью и параллельными потоками заявок. Разработанная стратегия сможет быть применима во многих сферах, но в первую очередь, в данной работе она рассматривается, как инструмент способный оптимизировать работу отделения банка. В качестве каналов обслуживания выступают операционисты, производящие обслуживание клиентов.
Обзор литературы
В современном мире системы массового обслуживания становятся более популярными. Об этом свидетельствуют научные статьи по этой тематике, которых становится все больше. Чаще системы массового обслуживания рассматриваются либо в общем виде, либо для конкретных приложений. Область применения теории массового обслуживания очень обширна: ТМО можно применять в различных сферах обслуживания (магазины, аэропорты, поликлиники, банки, и т.д.), в информатике и биоинформатике, и даже в медицине и эпидемиологии.
В настоящее время, теория массового обслуживания насчитывает значительное количество различных моделей и их модификаций, каждая из которых подходит для того или иного процесса. Наиболее интересными для данной работы представляются системы массового обслуживания с различными типами заявок, бесконечной очередью (бесконечным накопителем), а также, системы вида M|M|1| ?. Эти системы наиболее популярны в сфере обслуживания. Например, Лонцих и Шулешко в своей статье [1] рассматривают экономическую систему, для которой, с помощью математической модели M|M|1| ? формализовали ее сферу деятельности с целью оптимизации работы и увеличения прибыли. В качестве экономической системы для их исследования была взята автомойка с одним обслуживающим прибором.
Другим интересным применением систем массового обслуживания стала статья Романенко [2] в которой он представил оптимальную программу управления параметрами системы обслуживания перевозок узлового аэропорта. Уникальность данной статьи заключается в организации СМО, а именно в наличии нестационарных потоков и частичной взаимопомощи между обслуживающими каналами.
На данный момент времени существует большое число модификаций системы M|M|1| ?. Например, в работе Кирпичникова и Титовцева [3] представлена модель, полученная путем модификации классической одноканальной системы массового обслуживания и системы с ограниченной очередью (M|M|1|E). Данная модель была математически формализована. Все типы заявок авторы разделили на "терпеливые" и "нетерпеливые". "Нетерпеливые" заявки попадают в очередь до тех пор, пока общее число заявок в очереди не достигнет заданного значения E. После того, как очередь заполнена, "нетерпеливые" заявки получают отказ и не обслуживаются, в то время как "терпеливые" попадают в очередь в любом случае и находятся там, пока не будут обслужены.
Построение математической модели
Для начала стоит рассмотреть систему в общем виде. В нашей системе массового обслуживания обслуживающих приборов и параллельных потоков заявок, независимых между собой, которые поступают в систему с интенсивностью .
Интенсивности обслуживания заявки i-го типа будут равны
Тогда
среднее время обслуживания заявки i-го типа.
В данной системе массового обслуживания применяется смешанная стратегия распределения заявок: заявки каждого типа распределяются по окнам с определенной вероятностью . Соответственно вероятность того, что заявка i-го типа будет направлена на j-ый прибор.
Для каждого потока заявок сумма таких вероятностей должна равняться 1:
Тогда интенсивность входящего потока на j-ом приборе будет считаться по формуле:
А интенсивность обслуживания на j-ом приборе в свою очередь равна:
Где среднее время обслуживания на j-ом приборе.
Тогда
где среднее время обслуживания заявки i-го типа вероятность того, что будет обслужена заявка i-го типа.
Выбор критерия эффективности и постановка задачи оптимизации
Для того, чтобы оптимизировать систему массового обслуживания, нужно определить критерий, по которому будет оцениваться эффективность оптимизации. В данной работе, в качестве критерия эффективности был выбран параметр "средняя длина очереди". Соответственно, для такой системы обслуживания, цель оптимизации - максимально сократить среднюю длину очереди, тем самым минимизировать время ожидания клиента в очереди, что в целом и является задачей оптимизации для этой системы массового обслуживания. Данный критерий оценки эффективности широко используется в системах массового обслуживания и является одним из наиболее очевидных. При рассмотрении данной системы массового обслуживания, можно заметить, что минимизировать среднюю длину очереди представляется возможным при правильно подобранной совокупности вероятностей, с которыми i-ый тип заявки поступает на j-ый прибор.
В данной системе мы будем рассматривать каждый отдельный прибор как самостоятельную систему типа M|M|1| ?.
Следовательно, средняя длина очереди на j-ом приборе будет равна:
Что в свою очередь для нашей системы:
Подставим имеющиеся значения, тогда
Тогда средняя длина очереди для всей системы:
Подставим значения:
Исследование зависимости критерия эффективности от стратегии управления
Для подбора оптимальных вероятностей была использована программа Microsoft Excel. Используя входные параметры с помощью надстройки "поиск решений" были получены результаты.
На примере простого набора данных, были найдены вероятности.
В качестве входных данных были заданы:
число обслуживающих приборов
число входящих потоков
интенсивность 1-го потока
интенсивность 2-го потока
интенсивность 3-го потока
интенсивность 4-го потока
интенсивность обслуживания заявки 1-го типа
интенсивность обслуживания заявки 2-го типа
интенсивность обслуживания заявки 3-го типа
интенсивность обслуживания заявки 4-го типа
На основе подобранных вероятностей был посчитан выбранный критерий эффективности, средняя длина очереди:
Для того, чтобы проверить, зависит ли критерий эффективности от выбранной стратегии оптимизации, заменим полученные вероятности на случайные значения.
Как видно на таблице, после изменений средняя длина очереди увеличилась: программа прибор обслуживание
Это демонстрирует, что выбранная стратегия подходит, и оптимизирует систему массового обслуживания по выбранному критерию эффективности.
Решение задачи оптимизации. Программная реализация.
Для подсчета средней длины очереди системы была разработана программа на языке Python. Данный язык программирования показался мне наиболее простым и удобным для решения данной задачи. Python является высокоуровневым языком программирования, нацеленным на облегчение читабельности кода и повышением производительности использующего его разработчика. Python имеет довольно простой для понимания синтаксис, что в свою очередь значительно упрощает его использование, но, в то же время, он не уступает другим языкам по объемам полезных функций, встроенных в стандартную библиотеку.
На вход программа от пользователя получает значения количества приборов, количества потоков, значения интенсивностей входящих потоков и интенсивности обслуживания заявок, а также, подобранные вероятности. Далее программа выводит значение средней длины очереди.
Листинг программы:
print ('Введите данные')
print ('количество приборов n')
n = int (input())
print ('число потоков N')
nn = int (input())
l = []
for i in range (0,n):
print ('Введите l',i+1)
l.append(int(input()))
mu = []
for j in range(0,nn):
print ('Введите mu',j+1)
mu.append(int(input()))
p = [[0]* n for i in range(n)]
for i in range(0,n):
for j in range(0,nn):
print ('Введите p[',i+1,'.',j+1,']')
p[i][j] = float(input())
if p[i][j]>1:
print ('ошибка, вероятность больше 1')
break
LL = []
kk = 0
for j in range(0,nn):
kk=0
for i in range(0,n):
k=0
k= p[i][j] * l[i]
kk=kk+k
if kk != 0 :
LL.append(kk)
MM = []
ss=0
for j in range(0,nn):
ss=0
for i in range(0,n):
s=0
s=(p[i][j]*l[i])/(LL[j]*mu[i])
ss=ss+s
if ss != 0 :
zz=0
zz=1/ss
MM.append(zz)
LS =[]
for j in range(0,nn):
v=0
v=((LL[j]**2)/(MM[j]**2))/(1-(LL[j]/MM[j]))
LS.append(v)
KK = []
for j in range(0,nn):
k=LL[j]/MM[j]
KK.append(k)
k=0
LA = 0
for j in range(0,nn):
LA = LA + LS[j]
print('--------------------------------------------------------------------')
print ('Количество приборов n =',n)
print ('Количество входящих потоков N =',nn)
print ('Интенсивности входящих потоков:')
for i in range(0,n):
print('l[',i+1,'] =',l[i])
print('Интенсивности обслуживания заявок:')
for j in range(0,nn):
print('mu[',j+1,'] =',mu[j])
print('Вероятности распределения заявок:')
for i in range(0,n):
for j in range(0,nn):
print ('p [',i+1,'.',j+1,'] = ',p[i][j])
print ('Значения загрузки приборов:')
for j in range(0,nn):
print ('K[',j+1,']=',KK[j])
print('Средняя длина очереди для СМО:')
print('L =',LA)
Проверим правильность работы программы, используя данные из пункта 5.
Численные примеры.
В качестве примера, произведем оптимизацию системы массового обслуживания со входными параметрами:
число обслуживающих приборов
число входящих потоков
интенсивность 1-го потока
интенсивность 2-го потока
интенсивность 3-го потока
интенсивность 4-го потока
интенсивность 5-го потока
интенсивность 6-го потока
интенсивность обслуживания заявки 1-го типа
интенсивность обслуживания заявки 2-го типа
интенсивность обслуживания заявки 3-го типа
интенсивность обслуживания заявки 4-го типа
интенсивность обслуживания заявки 3-го типа
интенсивность обслуживания заявки 4-го типа
С помощь Поиска решений были найдены следующие вероятности для оптимальной смешанной стратегии:
Далее, используя написанную программу, посчитаем значение средней длины очереди всей системы:
Чтобы проверить, оптимальны ли выбранные вероятности, посчитаем среднюю длину очереди для случайных вероятностей:
Очевидно, что алгоритм работает, так как в первом случае значение средней длины очереди
В то время как для второго варианта - это значение составило почти в полтора раза больше:
Выводы
Были посчитаны критерии эффективности и найдены оптимальные смешанные стратегии для нескольких систем с различными входными параметрами. Статистика показывает, что распределять заявки по приборам нужно таким образом, чтобы загрузка для каждого прибора была приблизительно одинакова. Путем изменения подобранных вероятностей мы удостоверились, что выбранный критерий эффективности, все же, лучше при вероятностях, которые были найдены.
Статистический анализ показал, что найденные оптимальные решения для разных численных примеров сводятся к поиску таких вероятностей, при которых заявки распределяются равномерно и это наводит на предположение что минимальная длина очереди получается, когда все приборы нагружены одинаково.
Список литературы
1. Лонцих Павел Абрамович, Шулешко Александр Николаевич Моделирование и оценка качества работы одноканальных систем массового обслуживания // Вестник ИрГТУ. 2012. №11 (70) С.235-238.
2. Романенко Владимир Алексеевич Оптимизация управления технологическими процессами узлового аэропорта как системы массового обслуживания с нестационарными потоками и частичной взаимопомощью каналов // УБС. 2012. №36 С.209-247.
3. Кирпичников А.П., Титовцев А.С. Открытая одноканальная система массового обслуживания с отказами и неограниченной очередью // Вестник Казанского технологического университета. 2006. №4 С.87-94.
4. Теория массового обслуживания. / Ивченко Г.И., Каштанов В.А., Коваленко И.Н. - Москва: Издательство "Высшая школа", 1982
Размещено на Allbest.ru
Подобные документы
Общая характеристика системы массового обслуживания, исходные данные для ее создания. Особенности построения алгоритма имитационной модели задачи о поступлении заявок (клиентов) в канал (парикмахерскую). Описание функционирования математической модели.
курсовая работа [154,1 K], добавлен 19.05.2011Торговый центр как однофазная многоканальная система с одной очередью конечной длины Структура и элементы моделей системы массового обслуживания. Очередь и дисциплины ее обслуживания. Принципы и этапы моделирования средств массового обслуживания на ЭВМ.
лабораторная работа [93,2 K], добавлен 04.06.2009Функционирование систем массового обслуживания с разными типами заявок. Построение математической модели, постановка задачи оптимизации среднего времени ожидания. Решение задачи оптимизации системы. Разработка программного кода для оптимизации системы.
дипломная работа [581,7 K], добавлен 27.10.2017Основное назначение систем массового обслуживания (СМО): обслуживание потока заявок. Моделирование СМО для стоянки такси, определение характеристик эффективности работы в качестве статистических результатов моделирования. Схема процесса функционирования.
курсовая работа [1,2 M], добавлен 27.12.2011Построение имитационной модели системы массового обслуживания, список и содержание ее активностей. Блок-схема алгоритма моделирования и текст процедуры. Моделирование случайных независимых величин и процессов. Оптимизация системы массового обслуживания.
курсовая работа [4,0 M], добавлен 28.05.2013Схема межпроцессного взаимодействия; создание программы моделирования обслуживания заявок в системе с двумя очередями и одним обслуживающим прибором. Структура сообщений, параметров и ограничения очередей; кодирование и функциональное тестирование.
курсовая работа [33,3 K], добавлен 12.05.2013Изучение понятия многофазовых систем. Рассмотрение примеров разомкнутых и замкнутых систем массового обслуживания с ожиданием и с неограниченным потоком заявок. Определение значений среднего времени ожидания заявки при неэкспоненциальном распределении.
контрольная работа [151,5 K], добавлен 16.09.2010Определение назначения и описание функций имитационных моделей стохастических процессов систем массового обслуживания. Разработка модели описанной системы в виде Q-схемы и программы на языке GPSS и C#. Основные показатели работы имитационной модели.
курсовая работа [487,4 K], добавлен 18.12.2014Функционирование систем массового обслуживания с разными типами заявок. Построение математической модели. Постановка задачи оптимизации среднего времени ожидания. Решение задачи оптимизации и разработка программного кода для оптимизации системы.
курсовая работа [538,5 K], добавлен 11.08.2017Программа, моделирующая систему массового обслуживания (СМО). Моделирование программы имитации работы турникетов на стадионе (многоканальная СМО) в визуальной среде Delphi 7. Описание программного модуля, листинг программы и руководство пользователя.
курсовая работа [3,8 M], добавлен 20.08.2009
