Преподаватель который помогает студентам и школьникам в учёбе.

Поселковый магазин

Содержание:

Введение

Поток покупателей в магазине подчиняется закону Пуассона с интенсивностью 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 построен в предположении, что модель сложной системы можно представить совокупностью элементов и логических правил их взаимодействия в процессе функционирования моделируемой системы. Набор абстрактных элементов, называемых объектами, небольшой. Также набор логических правил ограничен и может быть описан стандартными операциями. Комплекс программ, описывающих функционирование объектов и выполняющих логические операции, является основой для создания программной модели.

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

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

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

Блоки, осуществляющие модификацию атрибутов транзактов:
- генерирование и уничтожение транзактов GENERATE, SPLIT, TERMINATE, ASSEMBLE;
- временная задержка ADVANCE;
- синхронизация движения двух MATCH и нескольких GATHER транзактов;
- изменение приоритета транзакта PRIORITY;
- изменение параметров транзактов ASSIGN, INDEX, MARK, PLUS.
Блоки, изменяющие последовательность движения транзактов (блоки передачи управления):DISPLACE, TRANSFER, LOOP, TEST, GATE.
Блоки, связанные с группирующей категорией: ADOPT, ALTER, EXAMINE, JOIN, REMOVE, SCAN.
Блоки, описывающие объекты аппаратной категории:
- одноканальные устройства (технические средства) SEIZE, RELEASE, PREEMPT, RETURN,FUNAVAIL, FAVAIL;
- многоканальные устройства (памяти) ENTER, LEAVE, SAVAIL, SUNAVAIL;
- ключи (логические переключатели) LOGIC.
Блоки, сохраняющие необходимые значения для дальнейшего использования: SAVEVALUE,MSAVEVALUE.
Блоки для получения статистических результатов:
- Очереди QUEUE, DEPART;
- Таблицы TABULATE.
Блоки для организации списка пользователя: LINK, UNLINK.
Блоки для организации ввода-вывода:
Специальные блоки: 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

470 0 34584.550 470 10 11 1 2.000

1130 0 34775.500 1130 10 11 1 3.000

2405 0 69120.000 2405 0 23

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

GPSS World Simulation Report - var14modeF.13.1

Saturday, September 26, 2015 02:22:05

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 34560.000 26 3 0

NAME VALUE

I1I3 9.000

I3I4 11.000

I5I7 20.000

I7I8 22.000

RELTYPE1 12.000

RELTYPE2 23.000

TYPE1 3.000

TYPE2 14.000

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1 GENERATE 2403 0 0

2 TRANSFER 2403 0 0

TYPE1 3 PRIORITY 1180 0 0

4 SELECT 1180 0 0

5 QUEUE 1180 657 0

6 SEIZE 523 0 0

7 DEPART 523 0 0

8 TRANSFER 523 0 0

I1I3 9 ADVANCE 91 1 0

10 TRANSFER 90 0 0

I3I4 11 ADVANCE 432 1 0

RELTYPE1 12 RELEASE 521 0 0

13 TERMINATE 521 0 0

TYPE2 14 PRIORITY 1223 0 0

15 SELECT 1223 0 0

16 QUEUE 1223 1074 0

17 SEIZE 149 0 0

18 DEPART 149 0 0

19 TRANSFER 149 0 0

I5I7 20 ADVANCE 51 0 0

21 TRANSFER 51 0 0

I7I8 22 ADVANCE 98 1 0

RELTYPE2 23 RELEASE 148 0 0

24 TERMINATE 148 0 0

25 GENERATE 1 0 0

26 TERMINATE 1 0 0

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

1 218 0.997 158.003 1 926 0 0 0 887

2 209 0.997 164.885 1 306 0 0 0 162

3 245 0.996 140.514 1 1778 0 0 0 682

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

1 947 887 1105 4 499.162 15611.809 15668.528 0

2 309 162 371 3 197.344 18383.324 18533.188 0

3 682 682 927 3 167.863 6258.179 6278.498 0

FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE

2405 0 34572.000 2405 0 1

306 1 34600.292 306 22 23 1 2.000

926 2 34649.257 926 9 10 1 1.000

1778 2 34699.194 1778 11 12 1 3.000

2406 0 69120.000 2406 0 25

4. Анализ результатов

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

Случайная величина	Мат. ожидание	Результаты моделирования (режимы A/B)
Количество покупателей	AN8 = 2390,4	2402/2403
Доля расчетов наличными	B = 0,49	0,496/0,491
Среднее время обслуживания на кассе (режим A)	B(I2(I1+I3)/2+(1-I2)(I3+I4)/2)) +(1-B)( I6(I5+I7)/2+(1-I6)*(I7+I8)/2)) = 121,6871	FACILITY 1/2/3 = 122.550/126.715/122.990
Количество обслуженных покупателей (режим A)	N83600*С/121,6871 = 856,9	FACILITY 1+2+3 = 281+272+280 = 833

Различия между расчетными и полученными в результате моделирования значениями не превышают 4%, что, в некотором смысле, позволяет надеяться на корректность построенной модели.

Следует отметить, что из-за того, что количество порождаемых заявок значительно превосходит возможности приборов по их обработке, приборы практически всё время заняты обработкой (коэффициент использования 0,096-0,097). Из-за этого решения о выборе прибора делается на основании мельчайших различий в коэффициентах использования. Это приводит к сильной неравномерности в длине очередей к приборам. Во многих реальных случаях это может считаться недостатком организации СМО.

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

(QUEUE1.ENTRY*AVE.TIME + QUEUE2.ENTRY*AVE.TIME + QUEUE3.ENTRY*AVE.TIME) / (QUEUE1.ENTRY + QUEUE2.ENTRY + QUEUE3.ENTRY)

Для модификации А среднее время ожидания составит 11377 секунд, а для модификации В 12439 секунд. Т.е. дисциплина обслуживания А (без приоритетов) является более выгодной с точки зрения минимального среднего времени ожидания.

Заключение.

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

Список литературы

Шрайбер Т.Дж. Моделирование на GPSS, пер. с англ. М.Машиностроение. 1980г. 592с.
Кудрявцев Е. М. К88 GPSS World. Основы имитационного моделирования различных систем. – М.: ДМК Пресс, 2004. – 320 с.
Справочное руководство по GPSS WORLD
А. И. Васильев Имитационное моделирование информационных и вычислительных систем с использованием GPSS , Владивосток, 2004