Элементарное моделирование и SimPy

Моделирование работы магазина с несколькими кассами

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

Simpy: моделирование очередей в магазинахс несколькими терминалами

Другим немаловажным аспектом моделирования является то, что оно позволяет погрузиться в вымышленный мир, заставить этот мир жить по собственному сценарию. Компьютерные игры — своеобразные модели реальности: использование таких моделей (а иногда и создание) может быть очень увлекательным! Даже такое важное направление науки как математика в целом, может рассматриваться как моделирование; известный математик В.И. Арнольд говорил: "Математика — это та часть естествознания, в которой эксперименты дешевы" (не дословное цитирование). И хотя такое сравнение оставляет несколько обиженными математиков-теоретиков, данное высказывание вполне естественно, если проследить историю развития математики — ее предметом (быть может до последнего времени...) всегда были модели наблюдаемых процессов. Не будем однако здесь погружаться в дискуссии относительно важности прикладной и абстрактной математики, а ограничимся более приземленной задачей — построим элементарную модель работы магазина.

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

Модель работы магазина. Будем полагать, что магазин имеет некоторое число касс (это количество можно задавать), каждая из которых обслуживает посетителя случайное число секунд (но не более заданной величины, назовем ее SERVICE_DURATION);  Также будем полагать, что посетители приходят каждые t секунд, где t – случайное равномерно распределенное число, взятое из интервала [0, ARRIV_INTER] (ARRIV_INTER - задается в модели).

Дополнительно,  будем полагать, что посетители приходят в течение 10 часов работы магазина; после того, как 10 часов прошло, новые посетители не принимаются и обcлуживаются только те, кто уже вошел.

Поскольку Python — удобный и относительно простой язык программирования, создание такой модели без каких-либо сторонних средств — может стать полезным упражнением; но здесь мы рассмотрим более интересный (и удобный) способ реализации  модели — на базе системы моделирования процессов дискретного времени SimPy. Также отмечу, что равномерное распределение времен появления посетителей взято мною лишь для примера; выбор любого другого распределения или случайного процесса лишь несколько изменит  формулы, применяемые для моделирования и принципиального значения для построения модели не имеет.

Немного о SimPy

На официальном сайте проекта SimPy он позиционируется как "SimPy is a process-based discrete-event simulation framework based on standard Python" или, при попытке перевода на русский язык,  что-то вроде  "SimPy — это система для разработки событийно-ориентированных моделей дискретного времени для языка программирования Python". 

Важной особенностью SimPy является организованная в нем система прерывания процессов, посредством использования генераторов языка Python. Генераторы в Python — позволяют прерывать выполнение функции с возможностью последующего возвращения и выполнения "оставшейся" ее части (более подробно о генераторах (на русском) можно прочитать, например, здесь).

Simpy Logo

В общих чертах создание модели при помощи SimPy представляет следующую последовательность действий:

  1. Определение (инициализация) среды моделирования;
  2. Создание интересующих нас событий дискретного времени, собственно, того, что мы будем моделировать;
  3. Интеграция созданных событий с модельной средой;
  4. Запуск модели/просмотр/анализ результатов

Рассмотрим простейший пример.

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

Создадим и запустим модель для этого простейшего случая.

 

from __future__ import print_function

import simpy
import random

def man(env):
    while True:
        print('{0}: Hi! I am walking...'.format(env.now))
        yield env.timeout(random.randint(0, 10))
        print('{0}: Hi! I am standing...'.format(env.now))
        yield env.timeout(5)


env = simpy.Environment()

env.process(man(env))

env.run(until=100)

Функция man, представляет собой функцию процесса действий человека; поскольку в модели говорится, что процесс этот бесконечен, мы используем здесь бесконечный цикл while. Итак, человек идет и в этом состоянии он находится для определенности случайное число единиц времени от 0 до 10: это выражается строкой

yield env.timeout(random.randint(0, 10))

Эта строка "замораживает" состояние объекта (это состояние здесь, однако, эфемерно, просто мы выводим на экран строку, что "Я иду...";) на некоторое случайное число шагов. Далее, по прошествии этого числа шагов, человек останавливается (здесь мы выводим строку - "Я стою" - в коде эти фразы даны на английском), это состояние сохраняется на 5 временных единиц. Потом процесс повторяется сначала...

Эта функция выполнялась бы бесконечно, но она вызывается внутри инициализированной "среды моделирования" env, и, кроме того, имеет точки прерывания yield. Запуская модель env.run(until=100) мы указываем, что моделирование должно прекратиться, как только модельное время (переменная env.now) достигнет 100, этим, совместно с yield, обеспечивается выход из бесконечного цикла.

В результате выполнения модели, мы получим, что-то вроде этого:

0: Hi! I am walking...
7: Hi! I am standing...
12: Hi! I am walking...
21: Hi! I am standing...
26: Hi! I am walking...
30: Hi! I am standing...
35: Hi! I am walking...
41: Hi! I am standing...
46: Hi! I am walking...
49: Hi! I am standing...
54: Hi! I am walking...
58: Hi! I am standing...
63: Hi! I am walking...
67: Hi! I am standing...
72: Hi! I am walking...
81: Hi! I am standing...
86: Hi! I am walking...
86: Hi! I am standing...
91: Hi! I am walking...
91: Hi! I am standing...
96: Hi! I am walking...

SimPy-модель магазина

Создание модели начнем с импорта необходимых модулей и определения констант.

# -*- coding: utf-8 -*-

# Будем приобщаться к стилю Python 3...
from __future__ import print_function

# Импорт среды SimPy
import simpy

# Для генерации случайных чисел
import random


# Инициализация среды моделирования
env = simpy.Environment()


# Ресурс обслуживания; в данном случае - capacity - число касс,
# которые обслуживают покупателей
bcs = simpy.Resource(env, capacity=6)


# Длительность покупки\получения услуги
# Здесь и всюду в этой модели мы полагаем, что единица модельного 
# времени соответствует 1 секунде реального времени
SERVICE_DURATION = 20 * 60 # т.е. максимальная длительность обслуживания 20 мин
# В реальности - время обслуживания равномерно распределенная случайная величина
# на интервале [0, 20 * 60]

# Интервал появления нового посетителя магазина
ARRIV_INTER = 4 * 60
# В реальности - время появления нового посетителя равномерно распределенная
# случайная величина на интервале [0, 4 * 60]

# Время пока посетителей запускают в магазин (10 часов)
# После 10 часов работы магазин закрывают и обслуживают только оставшихся, 
# если таковые имеются...
CONSUMER_TIME = 3600 * 10

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

# Источник посетителей предполагает, что
# посетители приходят 10 часов подряд от начала работы магазина, 
# далее поступление новых посетителей прекращается
def source_men(env):
    ind = 0
    while env.now < (CONSUMER_TIME - ARRIV_INTER): # Посетители приходят 10 часов подряд CONSUMER_TIME = 3600*10
        ind += 1
        yield env.timeout(random.randint(0, ARRIV_INTER))
        man = Man(env, bcs, name='Mr:%s' % ind)
        env.process(man.run())

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

# Объект этого класса - посетитель магазина
class Man(object):
    def __init__(self, env, res, name='default'):
        self.name = name  # Имя посетителя, мы же должны их различать !!!
        self.env = env  # Среда моделирования
        self.res = res  # используемый при моделировании ресурс, в данном случае - касса

    def run(self):
        # сделаем счетчики статистики глобальными, они нужны для построения 
        # графиков после моделирования
        global myquelen, maxwaits, timelist_q,timelist_w
        # человек пришел и сразу встал в очередь: она увеличилась на 1
        myquelen += 1
        print(u"Добрый день! Меня зовут {0} и я \
прибыл в магазин в {1} (время)".format(self.name, self.env.now))
        # Запомним время, чтобы посчитать потом время пребывания в очереди
        time = self.env.now
        # Запрос свободной кассы...
        with self.res.request() as req:
            # Нет ничего свободного... в очередь...
            yield req
            # Свободная касса появилась...
            # Человек поступает на обслуживание и очередь уменьшается на 1
            myquelen -= 1
            # запомним текущую длину очереди
            queue.append(myquelen)
            # запомним текущее время
            timelist_q.append(self.env.now)
            # вспомогательная переменная, (wait-time) - время, проведенное в очереди
            wait = self.env.now
            # время обслуживание - просто случайное число, генерируем его
            serving_duration = random.randint(0, SERVICE_DURATION)
            # обслуживаемся в кассе...
            yield self.env.timeout(serving_duration)
            # Обслужились
            print(u"Я {0}; Я обслуживался {1} единиц времени, и \
ждал в очереди {2} единиц времени".format(self.name, serving_duration, wait-time))
            # Запомним время проведенное в очереди
            maxwaits.append(wait-time)
            # Запомним текущее время
            timelist_w.append(self.env.now)
            print(u"Меня обслужили и сейчас ({0} -- текущее время) \
я покидаю магазин.".format(self.env.now))

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

по этой ссылке (7,3 KB)

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

Добрый день! Меня зовут Mr:1 и я прибыл в магазин в 36 (время)
Добрый день! Меня зовут Mr:2 и я прибыл в магазин в 152 (время)
Добрый день! Меня зовут Mr:3 и я прибыл в магазин в 224 (время)
Я Mr:1; Я обслуживался 189 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (225 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:4 и я прибыл в магазин в 235 (время)
Добрый день! Меня зовут Mr:5 и я прибыл в магазин в 282 (время)
Я Mr:4; Я обслуживался 191 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (426 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:6 и я прибыл в магазин в 485 (время)
Я Mr:5; Я обслуживался 245 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (527 -- текущее время) я покидаю магазин.
Я Mr:3; Я обслуживался 353 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (577 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:7 и я прибыл в магазин в 639 (время)
Добрый день! Меня зовут Mr:8 и я прибыл в магазин в 711 (время)
Добрый день! Меня зовут Mr:9 и я прибыл в магазин в 786 (время)
Я Mr:6; Я обслуживался 336 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (821 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:10 и я прибыл в магазин в 867 (время)
Добрый день! Меня зовут Mr:11 и я прибыл в магазин в 953 (время)
Добрый день! Меня зовут Mr:12 и я прибыл в магазин в 1028 (время)
Я Mr:9; Я обслуживался 357 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (1143 -- текущее время) я покидаю магазин.
Я Mr:2; Я обслуживался 1060 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (1212 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:13 и я прибыл в магазин в 1253 (время)
Добрый день! Меня зовут Mr:14 и я прибыл в магазин в 1345 (время)
Я Mr:7; Я обслуживался 871 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (1510 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:15 и я прибыл в магазин в 1530 (время)
Я Mr:11; Я обслуживался 647 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (1600 -- текущее время) я покидаю магазин.
Я Mr:10; Я обслуживался 806 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (1673 -- текущее время) я покидаю магазин.
Я Mr:15; Я обслуживался 103 единиц времени, и ждал в очереди 70 единиц времени
Меня обслужили и сейчас (1703 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:16 и я прибыл в магазин в 1742 (время)
Добрый день! Меня зовут Mr:17 и я прибыл в магазин в 1765 (время)
Я Mr:8; Я обслуживался 1076 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (1787 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:18 и я прибыл в магазин в 1923 (время)
Добрый день! Меня зовут Mr:19 и я прибыл в магазин в 1929 (время)
Я Mr:16; Я обслуживался 219 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (1961 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:20 и я прибыл в магазин в 1974 (время)
Добрый день! Меня зовут Mr:21 и я прибыл в магазин в 2054 (время)
Я Mr:12; Я обслуживался 930 единиц времени, и ждал в очереди 115 единиц времени
Меня обслужили и сейчас (2073 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:22 и я прибыл в магазин в 2195 (время)
Я Mr:17; Я обслуживался 515 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (2280 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:23 и я прибыл в магазин в 2344 (время)
Добрый день! Меня зовут Mr:24 и я прибыл в магазин в 2352 (время)
Я Mr:13; Я обслуживался 1121 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (2374 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:25 и я прибыл в магазин в 2483 (время)
Добрый день! Меня зовут Mr:26 и я прибыл в магазин в 2594 (время)
Я Mr:14; Я обслуживался 1109 единиц времени, и ждал в очереди 165 единиц времени
Меня обслужили и сейчас (2619 -- текущее время) я покидаю магазин.
Я Mr:19; Я обслуживался 695 единиц времени, и ждал в очереди 32 единиц времени
Меня обслужили и сейчас (2656 -- текущее время) я покидаю магазин.
Я Mr:18; Я обслуживался 734 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (2657 -- текущее время) я покидаю магазин.
Я Mr:20; Я обслуживался 598 единиц времени, и ждал в очереди 99 единиц времени
Меня обслужили и сейчас (2671 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:27 и я прибыл в магазин в 2815 (время)
Я Mr:25; Я обслуживался 193 единиц времени, и ждал в очереди 174 единиц времени
Меня обслужили и сейчас (2850 -- текущее время) я покидаю магазин.
Я Mr:21; Я обслуживался 592 единиц времени, и ждал в очереди 226 единиц времени
Меня обслужили и сейчас (2872 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:28 и я прибыл в магазин в 2942 (время)
Я Mr:23; Я обслуживался 378 единиц времени, и ждал в очереди 275 единиц времени
Меня обслужили и сейчас (2997 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:29 и я прибыл в магазин в 3067 (время)
Я Mr:24; Я обслуживался 435 единиц времени, и ждал в очереди 304 единиц времени
Меня обслужили и сейчас (3091 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:30 и я прибыл в магазин в 3127 (время)
Я Mr:30; Я обслуживался 6 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (3133 -- текущее время) я покидаю магазин.
Я Mr:26; Я обслуживался 472 единиц времени, и ждал в очереди 77 единиц времени
Меня обслужили и сейчас (3143 -- текущее время) я покидаю магазин.
Я Mr:22; Я обслуживался 778 единиц времени, и ждал в очереди 179 единиц времени
Меня обслужили и сейчас (3152 -- текущее время) я покидаю магазин.
Я Mr:29; Я обслуживался 278 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (3345 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:31 и я прибыл в магазин в 3355 (время)
Добрый день! Меня зовут Mr:32 и я прибыл в магазин в 3517 (время)
Добрый день! Меня зовут Mr:33 и я прибыл в магазин в 3558 (время)
Я Mr:28; Я обслуживался 696 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (3638 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:34 и я прибыл в магазин в 3673 (время)
Добрый день! Меня зовут Mr:35 и я прибыл в магазин в 3746 (время)
Я Mr:33; Я обслуживался 245 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (3803 -- текущее время) я покидаю магазин.
Я Mr:31; Я обслуживался 469 единиц времени, и ждал в очереди 0 единиц времени
Меня обслужили и сейчас (3824 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:36 и я прибыл в магазин в 3826 (время)
Я Mr:27; Я обслуживался 1027 единиц времени, и ждал в очереди 35 единиц времени
Меня обслужили и сейчас (3877 -- текущее время) я покидаю магазин.
Добрый день! Меня зовут Mr:37 и я прибыл в магазин в 3885 (время)
Добрый день! Меня зовут Mr:38 и я прибыл в магазин в 3918 (время)
Добрый день! Меня зовут Mr:39 и я прибыл в магазин в 4017 (время)

Но самое интересное, это выводы, которые могут быть получены при помощи такой модели.

Анализ работы магазина

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

Запустим модель со следующими параметрами

capacity=6 (количество касс)

SERVICE_DURATION = 20 * 60 (макс. время обслуживания клиента на кассе)
ARRIV_INTER = 4 * 60 (макс. время прихода нового клиента)
CONSUMER_TIME = 3600 * 10 (время, пока клиентов запускают в магазин)

В результате чего, получим следующий результат:

SimPy: длина очереди в магазине

SimPy: время ожидания в магазине

Таким образом, несмотря на значительное число касс, и неплохое начало (вначале рабочего дня очереди нулевые!!!), где-то в середине рабочего образуются очереди до 7 человек, со временем ожидания в очереди для отдельных клиентов около 10 минут. Самое важно, что вначале дня этого нет и может показаться, что так будет всегда (например, понаблюдали 2 часа - вроде количество касс достаточно, справляются.... но модель показывает, что возможны небольшие "удлинения" очереди).

Изменим наши условия, и уменьшим число касс на единицу, при сохранении остальных параметров:

capacity=5 (количество касс)

SERVICE_DURATION = 20 * 60 (макс. время обслуживания клиента на кассе)
ARRIV_INTER = 4 * 60 (макс. время прихода нового клиента)
CONSUMER_TIME = 3600 * 10 (время, пока клиентов запускают в магазин)

SimPy: длина очереди в магазине

SimPy: время ожидания в магазине

Стоило уменьшить число касс на 1 и у нас появляются уже очереди из 15-20 человек, где люди должны ожидать около 40 минут! Что же произойдет, если число касс уменьшить еще на 1?!

capacity=4 (количество касс)

SERVICE_DURATION = 20 * 60 (макс. время обслуживания клиента на кассе)
ARRIV_INTER = 4 * 60 (макс. время прихода нового клиента)
CONSUMER_TIME = 3600 * 10 (время, пока клиентов запускают в магазин)

Моделирование магазина: график длины очереди

SimPy: модель магазина: время ожидания в очереди

Итак, в этом случае нас ждет полный ужас: очереди возрастут до 60 человек и некоторые из посетителей будут ожидать в них около 3 часов! Почему так?! одна из причин — достаточно большое максимальное время обслуживания (оно может достигать 20 минут); Если этот параметр уменьшить, то и количество касс можно также будет сократить... но поиск оптимального решения —  уже совершенно другая задача, решать которую безусловно намного проще,  используя (и расширяя) данную модель на базе SimPy.

blog comments powered by Disqus