Файл: Поселковый магазин.pdf

Введение

Поток покупателей в магазине подчиняется закону Пуассона с интенсивностью 249 человек в час. Способы оплаты могут быть одного из двух типов. оплата наличными составляет 49% от всего потока. В магазине имеется 3 кассы, которые обслуживают покупателей. Время обслуживания равномерно распределено на интервалах для оплаты наличными: вероятность попасть в интервал (86,158) секунд равна 0,17, в интервал (158,230) секунд — оставшаяся вероятность; для оплаты карточками: вероятность попасть в интервал (16,57) секунд равна 0,33, в интервал 57,98) секунд — оставшаяся вероятность. В устройстве принята дисциплина обслуживания D (с раздельными очередями к разным приборам). Выбор кассы осуществляется на основании критерия - минимальная загрузка устройства. Необходимо сравнить две ее модификации А (одинаковый приоритет у потоков) и В (разный приоритет (меньший у большего потока) с точки зрения критерия минимального среднего времени ожидания.

Требуется:

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

1. Основная часть

1.1 Обзор подходов

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

---

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

1.2 Обоснование выбора

Т. к. по условию задачи имеется несколько кассовых терминалов и очередь покупателей неограниченна, мы имеем дело с многоканальной системой массового обслуживания с ожиданием. Процесс массового обслуживания, описываемый данной моделью, характеризуется интенсивностью входного потока λ , при этом параллельно может обслуживаться не более S клиентов (заявок). Средняя продолжительность обслуживания одной заявки равняется 1/µ . Входной и выходной потоки являются пуассоновскими. Режим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, причем длительность процедуры обслуживания каждым из каналов является случайной величиной, подчиненной экспоненциальному закону распределения. Конечная цель использования S параллельно включенных обслуживающих каналов заключается в повышении (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно S клиентов.

---

2. Аналитическая модель

Граф состояний многоканальной системы массового обслуживания имеет вид, показанный на рис. 1. 1.

Рис. 1.1. Граф состояний многоканальной системы массового обслуживания.

Состояния СМО имеют следующую интерпретацию: S0 - все каналы свободны;

S1 - занят один канал, остальные свободны;

…………………………………………………….

Sk - заняты ровно k каналов, остальные свободны;

…………………………………………………….

Sn - заняты все n каналов, остальные свободны;

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

0=λ*P_n-1-(λ+n*µ)*P_n+(n+1)*µ* P_n+1, 1≤n≤S

0=λ*P_n-1-(λ+S*µ)*P_n+S*µ* P_n+1, n<S (1.1)

Решение системы уравнений (1.1) имеет вид

(1.2)

Где

(1.3)

Решение будет действительным, если выполняется следующее условие:

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

- вероятность того, что в системе находится n клиентов на обслуживании, определяется по формулам (4.33) и (4.34);

- среднее число клиентов в очереди на обслуживание

(1.4)

- среднее число находящихся в системе клиентов (заявок на Обслуживание и в очереди)

(1.5)

- средняя продолжительность пребывания клиента (заявки на обслуживание) в очереди

(1.6)

- средняя продолжительность пребывания клиента в системе

(1.7)

3. Имитационная модель

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

---

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

1. создание или уничтожение транзактов;
2. изменение числового атрибута объекта;
3. задержка транзакта на определенный период времени;
4. изменение маршрута движения транзакта в модели. Версия GPSS, реализованная в системе GPSSWorld, содержит 53 типа блоков.

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

1. Блоки, осуществляющие модификацию атрибутов транзактов:
   • генерирование и уничтожение транзактов GENERATE, SPLIT, TERMINATE, ASSEMBLE;
   • временная задержка ADVANCE;
   • синхронизация движения двух MATCH и нескольких GATHER транзактов;
   • изменение приоритета транзакта PRIORITY;
   • изменение параметров транзактов ASSIGN, INDEX, MARK, PLUS.
2. Блоки, изменяющие последовательность движения транзактов (блоки передачи управления):DISPLACE, TRANSFER, LOOP, TEST, GATE.
3. Блоки, связанные с группирующей категорией: ADOPT, ALTER, EXAMINE, JOIN, REMOVE, SCAN.
4. Блоки, описывающие объекты аппаратной категории:
   • одноканальные устройства (технические средства) SEIZE, RELEASE, PREEMPT, RETURN,FUNAVAIL, FAVAIL;
   • многоканальные устройства (памяти) ENTER, LEAVE, SAVAIL, SUNAVAIL;
   • ключи (логические переключатели) LOGIC.
5. Блоки, сохраняющие необходимые значения для дальнейшего использования: SAVEVALUE,MSAVEVALUE.
6. Блоки для получения статистических результатов:
   • Очереди QUEUE, DEPART;
   • Таблицы TABULATE.
7. Блоки для организации списка пользователя: LINK, UNLINK.
8. Блоки для организации ввода-вывода:
9. Специальные блоки: BUFFER, COUNT, EXECUTE, INTEGRATION, SELECT, TRACE,UNTRACE.

3.1. Листинг моделей

Для имитационных моделей в системе GPSS был выбран интервал моделирования 1 секунда. Таким образом период моделирования составил N*8*3600 = 34560 тактов. Среднее время между заявками равно 3600/A ≈ 14,46 такта (секунды).

Модель СМО модификации A:

GENERATE (Poisson(1,14.46)) ;Пуассон со средним временем в сек.

TRANSFER 0.51,type1,type2 ;выбор типа потока

type1 SELECT MIN 1,1,3,,FR ;выбор кассы с мин загрузкой

QUEUE P1 ;занятие отдельной очереди

SEIZE P1 ;занятие выбранной кассы

DEPART P1 ;фиксация выхода из очереди

TRANSFER 0.83,i1i3,i3i4 ;выбор интервала распределения

i1i3 ADVANCE 122,36

TRANSFER ,relType1

i3i4 ADVANCE 194,36

relType1 RELEASE P1 ;освобождение прибора

TERMINATE

---

type2 SELECT MIN 1,1,3,,FR ;выбор кассы с мин загрузкой

QUEUE P1 ;занятие отдельной очереди

SEIZE P1 ;занятие выбранной кассы

DEPART P1 ;фиксация выхода из очереди

TRANSFER 0.67,i5i7,i7i8 ;выбор интервала распределения

i5i7 ADVANCE 44.5,28.5

TRANSFER ,relType2

i7i8 ADVANCE 77.5,20.5

relType2 RELEASE P1 ;освобождение прибора

TERMINATE

GENERATE 34560 ;заданное время в секундах

TERMINATE 1

START 1

Модель СМО модификации В, отличаться от модификации А только наличием блоков установки приоритетов:

GENERATE (Poisson(1,14.46)) ;Пуассон со средним временем в сек.

TRANSFER 0.51,type1,type2 ;выбор типа потока

type1 PRIORITY 2 ;задание высокого приоритета

SELECT MIN 1,1,3,,FR ;выбор кассы с мин загрузкой

QUEUE P1 ;занятие отдельной очереди

SEIZE P1 ;занятие выбранной кассы

DEPART P1 ;фиксация выхода из очереди

TRANSFER 0.83,i1i3,i3i4 ;выбор интервала распределения

i1i3 ADVANCE 122,36

TRANSFER ,relType1

i3i4 ADVANCE 194,36

relType1 RELEASE P1 ;освобождение прибора

TERMINATE

type2 PRIORITY 1 ;задание низкого приоритета

SELECT MIN 1,1,3,,FR ;выбор кассы с мин загрузкой

QUEUE P1 ;занятие отдельной очереди

SEIZE P1 ;занятие выбранной кассы

DEPART P1 ;фиксация выхода из очереди

TRANSFER 0.67,i5i7,i7i8 ;выбор интервала распределения

i5i7 ADVANCE 44.5,28.5

TRANSFER ,relType2

i7i8 ADVANCE 77.5,20.5

relType2 RELEASE P1 ;освобождение прибора

TERMINATE

GENERATE 34560 ;заданное время в секундах

TERMINATE 1

START 1

3.2. Результаты моделирования

Результаты моделирования работы СМО модификации E:

GPSS World Simulation Report - var14modeE.13.1

Saturday, September 26, 2015 02:17:38

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 34560.000 24 3 0

NAME VALUE

I1I3 8.000

I3I4 10.000

I5I7 18.000

I7I8 20.000

RELTYPE1 11.000

RELTYPE2 21.000

TYPE1 3.000

TYPE2 13.000

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1 GENERATE 2402 0 0

2 TRANSFER 2402 0 0

TYPE1 3 SELECT 1193 0 0

4 QUEUE 1193 776 0

5 SEIZE 417 0 0

6 DEPART 417 0 0

7 TRANSFER 417 0 0

I1I3 8 ADVANCE 76 0 0

9 TRANSFER 76 0 0

I3I4 10 ADVANCE 341 2 0

RELTYPE1 11 RELEASE 415 0 0

12 TERMINATE 415 0 0

TYPE2 13 SELECT 1209 0 0

14 QUEUE 1209 793 0

15 SEIZE 416 0 0

16 DEPART 416 0 0

17 TRANSFER 416 0 0

I5I7 18 ADVANCE 135 1 0

19 TRANSFER 134 0 0

I7I8 20 ADVANCE 281 0 0

RELTYPE2 21 RELEASE 415 0 0

22 TERMINATE 415 0 0

23 GENERATE 1 0 0

24 TERMINATE 1 0 0

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

1 281 0.996 122.550 1 2399 0 0 0 4

2 272 0.997 126.715 1 470 0 0 0 298

3 280 0.996 122.990 1 1130 0 0 0 1267

QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY

1 168 4 285 5 68.506 8307.276 8455.620 0

2 480 298 570 3 321.204 19475.112 19578.155 0

3 1268 1267 1547 3 401.020 8958.789 8976.196 0

CEC XN PRI M1 ASSEM CURRENT NEXT PARAMETER VALUE

2404 0 34560.000 2404 0 1

FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE

2399 0 34573.880 2399 18 19 1 1.000

---