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

Дипломная работа

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

Имитационное моделировани

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

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

simulation modeling

Имитационное моделирование позволяет имитировать поведение системы во времени. Причём плюсом является то, что временем в модели можно управлять: замедлять в случае с быстропротекающими процессами и ускорять для моделирования систем с медленной изменчивостью. Можно имитировать поведение тех объектов, реальные эксперименты с которыми дороги, невозможны или опасны. С наступлением эпохи персональных компьютеров производство сложных и уникальных изделий, как правило, сопровождается компьютерным трёхмерным имитационным моделированием. Эта точная и относительно быстрая технология позволяет накопить все необходимые знания, оборудование и полуфабрикаты для будущего изделия до начала производства. Компьютерное 3D-моделирование теперь не редкость даже для небольших компаний.

Имитация как метод решения нетривиальных задач получила начальное развитие в связи с созданием ЭВМ в 1950-х — 1960-х годах.

Можно выделить разновидности имитации:

  • Метод Монте-Карло (метод статистических испытаний);
  • Метод имитационного моделирования (статистическое моделирование)[10].

Системы, в которых в случайные моменты времени возникают заявки на обслуживание и имеются устройства для обслуживания этих заявок, называются системами массового обслуживания (СМО) [3].

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

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

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

Как одноканальные СМО, так и многоканальные СМО делятся на СМО с отказами и СМО с очередью (ожиданием).

В СМО с отказами заявка, поступившая в момент, когда все каналы обслуживания заняты, получает «отказ» в обслуживании и покидает СМО.

9 стр., 4002 слов

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

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

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

СМО с очередью различаются по принципу построения очереди.

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

1. Случайный выбор заявки из очереди;

2. Выбор заявки из очереди в зависимости от её приоритета;

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

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

«Первым пришел — первым обслуживаешься», так и по схеме: «Последним пришел — первым обслуживаешься».

СМО с очередью делятся также на СМО с неограниченным ожиданием и СМО с ограниченным ожиданием.

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

в СМО, рано или поздно будет обслужена.

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

где P i — вероятность того, что система находится в состоянии Si , i=

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

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

i =1,

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

затем берется дробь, в числителе которой стоит произведение всех интенсивностей потоков по стрелкам, ведущим слева направо от состояния S 0 до состояния Si , а в знаменателе — произведение всех интенсивностей по стрелкам, идущим справа налево от состояния Si до состояния S0 , и эта дробь умножается на рассчитанную вероятность P0 [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].

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

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