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

ВВЕДЕНИЕ

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

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

изучить теоретические основы систем массового обслуживания, структуру функционирования СМО;

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

построить сеть Петри изучаемой СМО.

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

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

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

1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

.1 Цели и задачи имитационного моделирования и исследования

стохастический дискретный моделирующий

Имитационное моделирование - это метод исследования, при котором изучаемая система заменяется моделью, с достаточной точностью описывающей реальную систему, с которой проводятся эксперименты с целью получения информации об этой системе. Экспериментирование с моделью называют имитацией (имитация - это постижение сути явления, не прибегая к экспериментам на реальном объекте) [1].

К имитационному моделированию прибегают, когда:

·        дорого или невозможно экспериментировать на реальном объекте;

·        невозможно построить аналитическую модель: в системе есть время, причинные связи, последствие, нелинейности, стохастические (случайные) переменные;

·        необходимо сымитировать поведение системы во времени.

Цель имитационного моделирования состоит в воспроизведении поведения исследуемой системы на основе результатов анализа наиболее существенных взаимосвязей между её элементами или другими словами - разработке симулятора (англ. <#"785737.files/image001.gif">

Рисунок 1.1 Граф состояния СМО

Число состояний в графе на единицу больше, чем суммарное число каналов обслуживания и мест в очереди.

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

где P_i - вероятность того, что система находится в состоянии S_i, i=

λ_i(i-1) или λ_i(i+1) - интенсивность перехода, или среднее число переходов системы в единицу времени из состояния S_i в состояние S_i+1 или S_i-1.

Используя эту систему уравнений, а также уравнения

_i=1,

Вероятность P_i любого i-ого (i=) состояния можно вычислить по следующему общему правилу: вероятность нулевого состояния рассчитывается как

затем берется дробь, в числителе которой стоит произведение всех интенсивностей потоков по стрелкам, ведущим слева направо от состояния S₀ до состояния S_i, а в знаменателе - произведение всех интенсивностей по стрелкам, идущим справа налево от состояния S_i до состояния S₀, и эта дробь умножается на рассчитанную вероятность P₀ [5].

.5 Типы СМО

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

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

S - все каналы свободны, k=0;

S - занят один канал, остальные свободны, k=1;

S - заняты два канала, остальные свободны, k=2;

S - заняты все n каналов, k=n, очереди нет;

S - заняты все n каналов, одна заявка в очереди, k=n+1,

S - заняты все n каналов, r заявок в очереди, k=n+r,

Вероятности состояний получим из формул для многоканальной СМО с ограниченной очередью при переходе к пределу при m. Следует заметить, что сумма геометрической прогрессии в выражении для p расходится при уровне загрузки p/n>1, очередь будет бесконечно возрастать, а при p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО[3].

…

…

Рис.1.2 Граф состояний многоканальной СМО с неограниченной очередью

Для него определены выражения для предельных вероятностей состояний:

  …;

Поскольку отказа в обслуживании в таких системах не может быть, то характеристики пропускной способности равны:

среднее число заявок в очереди -

среднее время ожидания в очереди -

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

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

Эта вероятность определяет среднюю долю времени простоя канала обслуживания. Вероятность занятости обслуживанием k заявок -

На этом основании можно определить вероятность, или долю времени занятости всех каналов обслуживанием

Если же все каналы уже заняты обслуживанием, то вероятность состояния определяется выражением

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

Среднее число заявок, находящихся в очереди и ожидающих обслуживания, равно:

Среднее время ожидания заявки в очереди по формуле Литтла:  и в системе

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

;

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

;

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

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

2. Разработка программной модели

.1 Концептуальная схема модели

Перед нами стоят три основные задачи:

·        построение концептуальной модели и ее формализация.

·        алгоритмизация модели системы и ее машинная реализация.

·        получение и интерпретация результатов моделирования системы[8].

Разработанная концептуальная схема визуально представлена на рис. 2.1.

Рисунок 2.1 Концептуальная схема обслуживания клиентов

.2 Модель системы (Q-схема)

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

Рисунок 2.2 Q-схема модели

И1 - источник заказов.

Ключ КЛ1 - проверяет занятость каналов обслуживания, и не превышение очереди на обслуживание 5 заказов.

Ключ КЛ2 - определяет количество попыток дозвона: если оно меньше 9 - набор повторяется, если больше - набор прекращается.

Н - очередь обслуживания.

К1 - канал обслуживания заявок клиентов.

массовое обслуживание моделирование система

3. ЭФФЕКТИВНОСТЬ РАБОТЫ СЛУЖБЫ ЗАКАЗА ТАКСИ КАК СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

3.1 Реинжиниринг службы такси бизнес-процессов

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

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

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

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

Моделирование генерации заявок осуществляется на основе различных вероятностных законов.

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

длина очереди;

занятость обслуживающего персонала;

количество обработанных заявок.

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

Подсистема «Очередь» должна обрабатывать поступившие заявки поочередно при условии наличия двух видов заявок либо заявки одного типа при условии отсутствия заявок другого типа на рис. 3.1.

Рисунок 3.1 Модель компонента подсистемы «Очередь» на основе СП

В данном примере модели позиции Р1 и Р2 служат накопителями заявок. Переходы t1 и t2 предназначены для перемещения заявки в случае образования очереди в одной из позиций и отсутствия заявок в другой.

Подсистема «Обработчик очереди» предназначена для:

поочередной обработки заявок;

проверки поступления первой заявки для надстройки подсистемы;

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

Модель подсистемы показана на рис. 3.2.

Рисунок 3.2 Модель компонента обслуживания для отделов

Связь между подсистемами обеспечивают переходы t1 и t2 . Переход метки из позиции Р2 в позицию Р1 говорит о начале обработки заявки компонентом подсистемы.

Подсистемы «Статистика обработки», «Заявок всего» и «Обработано всего» реализованы с помощью позиций, которые являются накопителями.

Эти подсистемы служат для оценки эффективности полученной конфигурации.

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

В разработанной модели переход t1 служит для связи компонента с подсистемой «Обработчик очереди». Позиция Р2 используется для получения метки из подсистемы «Подключение компонентов подсистем», что позволит подсистеме «Обработчик очереди» запустить заявку на выполнение. Переход t2 отправляет обработанную заявку в подсистему «Статистика обработки».

Модуль «Подключения компонентов подсистем» обеспечивает возможность ввода новых компонентов при условии образования заданного количества заявок ожидающих обработки в очереди (рисунок 3.5). Здесь позиция Р1 должна быть связана с «Генераторами заявок» и служит накопителем всех заявок поступивших на обработку подсистемами «Экономического отдела» и «Отдела платежей», и связывается с переходом t2 компонентов обслуживания, тем самым обеспечивается контроль количества заявок, находящихся в системе и ожидающих обработки.

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

Рисунок 3.3 Модель элемента модуля «Подключение компонентов подсистем»

Переход возвращает метки в позицию Р1 и генерирует метку в позицию Р2, тем самым подключая компонент. Позиция Р1 связывается с переходом t1 компонентов обслуживания подсистем, тем самым уменьшая количество заявок ожидающих обработки, при начале их обслуживания подсистемами. Обработку очереди, в соответствии с выдвинутыми требованиями, обеспечивают подсистемы «Обработчик очереди».

Рисунок 3.4 Пример конфигурации отделения службы такси

Отдел «Платежей», моделируемый однотипными компонентами, учитывает интенсивность потоков заявок и перестраивается в процессе работы. Пример конфигурации отделения платежей в службе такси представлен на рис. 3.5.

Рисунок 3.5 Пример конфигурации отделения платежей в такси.

Представленная конфигурация содержит в себе 14 позиций:

Позиции Р1, Р2 - накопители заявок;

Позиции Р3, Р4 - статистика обработки;

Позиция Р5 - обработчик очереди;

Позиция Р6 - очередь заявок;

Позиции Р7, Р9 - кассы;

Позиции Р8, Р10- промежуточные позиции;

Позиции Р11, Р12- выход заявок из системы;

Позиция Р13 - обработанные заявки;

Позиция Р14 - общее количество заявок.

Дерево конфигурации отделения платежей в такси выглядит следующим образом:

10011000100001

 t12

  10000100100001

   t16

  10001000010001

   t21

  10001000100111

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

.2 Анализ системы показателей качества

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

Предполагалось, что моделируемая система службы такси характеризуется следующими параметрами: время между прибытиями клиентов распределено по экспоненциальному закону, вместимость очереди N11 = 4, N12 =10 клиентов, канал обслуживания К1- модель такси, К2 и К3-работники операционного отдела службы такси.

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

Проанализировав поочередно компоненты системы, можно сделать

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

Вероятность того, что все обслуживающие устройства свободны, слишком мала (23%), т.е. практически все время работы офиса сотрудники работают без перерыва, в результате, это сказывается на эффективности выполнения их обязанностей. Среднее время ожидания клиента W=6,57, к сотруднику такси W=4,78. Таким образом, время ожидания слишком велико, и клиенты могут не дождаться и уйти. Анализ свидетельствует о недостатке операторов и машин. В результате этого, такси теряет не только клиентов, но и прибыль.

Анализ результатов позволяет определить оптимальное количество

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

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

ЗАКЛЮЧЕНИЕ

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

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

Также были решены задачи, поставленные в начале работы:

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

проведен анализ системы массового обслуживания на примере службы такси;

построена сеть Петри изучаемой СМО.

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

СПИСОК ЛИТЕРАТУРЫ

1.Википедия [Электронный ресурс] URL: http://ru.wikipedia.org/wiki/ Теория_массового_обслуживания (дата обращения 15.06.2014).

.Грандарс, [Электронный ресурс], URL: http://www.grandars.ru/student/vysshaya-matematika/ model-sistemy-massovogo-obsluzhivaniya.html (дата обращения 15.06.2014).

. Казаков, О.Л. Экономико-математическое моделирование [Текст]: Учебное пособие / Казаков О.Л., Миненко C.Н., Смирнов Г.Б. - М.: МГИУ, 2006. - с.73

. Самаров, К.Л. Элементы теории [Текст]: Учебное пособие / Самаров К.Л. - © ООО «Резольвента», 2009 - с.3-4.

. Казаков, О.Л. Экономико-математическое моделирование [Текст]: Учебное пособие / Казаков О.Л., Миненко C.Н., Смирнов Г.Б. - М.: МГИУ, 2008. - с.73-76.

. Самаров, К.Л. Элементы теории [Текст]: Учебное пособие / Самаров К.Л. - © ООО «Резольвента», 2009 - с.4-5.

. Лаврусь, О.Е. Теория массового обслуживания [Текст]: Методические указания, учебная программа и задания для контрольных работ № 1, 2 для студентов заочной формы обучения специальности 071900 “Информационные системы в технике и технологиях” / Лаврусь О.Е., Миронов Ф.С. - Самара, 2008.

.Википедия [Электронный ресурс] URL: http://ru.wikipedia.org/wiki/Сети_ Петри (дата обращения 16.06.2014).

. Информатика и программирование [Электронный ресурс] URL: http://it.kgsu.ru/SetiPetri/sp003.html (дата обращения 16.06.2014)

. Библиофонд. Электронная библиотека [Электронный ресурс] URL: http://bibliofond.ru/view.aspx?id=698162 (дата обращения 16.06.2014) .