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

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

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

Все сказанное свидетельствует в пользу того, что логику работы клерка и всего магазина в целом надо отделить друг от друга и определить в разных классах, иначе сам принцип объектного моделирования будет выхолощен. Введем классы Клерк (Clerk) и Магазин (Shop)- Прежде чем перечислять их поля данных, подчеркнем следующее обстоятельство. В условии задачи дано максимальное значение объема группы - шесть. В общем случае можно ограничить и минимальное значение, которое назовем минимальным индексом группы (МИГ)- Смысл новою понятия заключается в то, что свободный клерк не начнет обслуживание клиентов до тех пор, пока длина первичной очереди не станет равна значению МИГ. Если к моменту накопления нужного количества клиентов свободных клерков несколько, выбор клерка, начинающего обслуживать эту группу, осуществляется случайным образом. Понятно, что стандартное значение МИГ — единица.

Еще один вопрос — взаимные ссылки между классами. В рассматриваемой  системе объекты классов Clerk и Shop не являются равноправными, так как каждый из объектов класса Clerk входит в зону ответственности единственного объекта класса Shop, но не наоборот. Поскольку объект Shop управляет системой в целом, ему необходим доступ к любому объекту Clerk для передачи ему различных сообщений (например, указание принять заказ). Каждый из клерков отвечает только за себя, и ему ссылка на Shop не нужна, так как всем информационным обменом руководит Shop. Поскольку перекрестных ссылок пет, тип указателя при объявлении поля класса Shop можно указывал, в явном виде (Clerk**), если, конечно, класс Clerk описан в header-файле раньше, чем класс Shop.

Перечислим поля данных класса Clerk.

Неизменяемые поля:

• среднее время нахождения клерка в пути (60 с);
• максимальное отклонение от среднего для времени нахождения клерка в пути (30 с);
• среднее время расчета одного клиента (120 с);
• максимальное отклонение от среднего для времени расчета одного клиента (60 с);
• уникальный номер клерка.

 

Изменяемые поля:

• вторичная очередь. Моделируется массивом указателей на объекты класса Client. Если клерк свободен, очередь пуста;
• клиент, с которым в данный момент производится расчет. Поле данных имеет смысл только при нахождении клерка в состоянии Расчет;
• текущее число клиентов, у которых принят заказ и которые ожидают возвращения клерка. Не то же самое, что длина вторичной очереди, поскольку в процессе расчета клиентов длина очереди меняется. Эго поле данных характеризует именно размер пакета заказов. Равен -1, если клерк свободен;
• время, оставшееся до прибытия клерка на склад. Значение поля данных активно только в состоянии движения на склад за товаром. В любом другом состоянии равно -1;
• время, оставшееся до возвращения клерка со склада Значение поля данных активно только в состоянии движения со склада с товаром. В любом другом состоянии равно -1;
• время, оставшееся до окончания расчета текущего клиента. Значение поля данных активно только в состоянии расчета клиентов. В любом другом состоянии рано -1;
• время, оставшееся до завершения поиска товаров. Значение поля данных активно только в состоянии поиска товаров при нахождении клерка на складе. В любом другом состоянии равно -1;
• время, прошедшее с момента принятия заказа Поле данных необходимо для сбора статистики о длительности цикла клерка — от принятия заказа до расчета последнего клиента. Если клерк свободен, значение равно -1.

Поля данных класса Shop. Неизменяемые поля:

• количество клерков (3). Для удобства реализации сделано глобальной переменной;
• максимальный объём одного заказа (6). Для удобства реализации сделано глобальной переменной;
• минимальный индекс группы (1);
• средняя интенсивность входного потока (0,5 заявок в минуту);
• массив указателей на объекты класса Clerk.

Изменяемые поля:

• первичная очередь клиентов. Из-за отсутствия ограничений на максимальную длину моделируется связным списком;
• время, оставшееся до прибытия следующей заявки из входного потока;
• текущая длина первичной очереди (вычисляемое поле).

Отношения дружественности между классами построены следующим образом: друзьями класса Client являются Clerk и Shop, другом класса Clerk - класс Shop.

2.3 События и методы

 

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

1. Прибытие клерка на склад.
2. Завершение поиска заказанного товара.
3. Прибытие клерка с товаром к ожидающим ею клиентам.
4. Завершение расчетов с очередным клиентом.
5. Принятие заказа у клиентов из первичной очереди.

Подробнее остановимся на реализации последнего метода. Если первичная очередь не пуста и ее длина достигла значения МИГ, объект Shop пытается препоручить как можно больше клиентов одному из свободных клерков. После того как клерк выбран, ему посылается сообщение, соответствующее методу 5, с двумя параметрами: указателем на первичную очередь, чтобы клерк мог скопировать часть ее клиентов во вторичную, и количеством клиентов, заказы у которых магазин предписывает принять клерку. Возвращает же он объекту Shop указатель на клиента первичной очереди, который теперь становится в этой очереди первым, то есть на новую голову связного списка. Первичную очередь Shop продвигает сам. Все эти действия выполняет метод-диспетчер run().

Методы класса Shop:

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

 

3. Реализация модели

3.1 Программная реализация

 

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

• описывает поведение системы;
• строит теории и гипотезы, которые могут объяснить наблюдаемое поведение;
• использует эти теории для предсказания будущего поведения системы, то есть тех воздействий, которые могут быть вызваны изменениями в системе или изменениями способов ее функционирования.[1]

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

 

3.2 Построение графиков

3.2.1 Программа gnuplot

Gnuplot портативная программа для визуализации данных и создания графиков функций для операционных систем UNIX, IBM OS/2, MS Windows, DOS, Macintosh, VMS, Atari и многих других. Эта программа защищена авторским правом, но свободна для распространения.

Gnuplot поддерживает множество видов графиков как двух-, так и трехмерных. Он может рисовать, используя линии, точки, боксы, контуры, векторные поля, поверхности и различный связанный текст.[2]

Gnuplot имеет собственную систему команд, может работать интерактивно (в режиме командной строки) и выполнять скрипты, читаемые из файлов. Также используется в качестве системы вывода изображений в различных математических пакетах: GNU Octave, Maxima и других. [3]

Gnuplot поддерживает много различных форматов для выдачи: интерактивные графические терминалы (с мышью и функциями горячих клавиш), прямой вывод на плоттеры и современные принтеры, запись в различные форматы файлов (eps, fig, jpeg, LaTeX, metafont, pbm, pdf, png, postscript, svg и так далее). Gnuplot легко расширяем для включения новых функций. [2]

3.2.2 Использование программы для построения графиков

Для того, чтобы нарисовать график, достаточно указать набор  команд в тэгах <plot>...</plot>. Основные команды состоят из задания области  определения функции (для одномерных графиков это переменная «x», для двухмерных «x», «y»), и команды отрисовки одномерной или двухмерной функции, заданной в символьном виде. Синтаксис функции интуитивно понятен, «+», «-», «*», «/» обозначают стандартные арифметические операторы (умножение должно быть явным, никаких математических сокращений типа «3x» и т. п.), «**» означает возведение в степень, скобки "(", «)» используются для задания приоритета.

Кроме операторов, есть набор  стандартных математических функций:

Тригонометрические функции sin, cos, tan, константа pi, и им обратные asin, acos, atan.

Гиперболические функции sinh, cosh, tanh.

Экспонента exp и натуральный  и десятичный логарифмы: log и log10 соответственно.

Трехмерные графики  рисуются аналогично, нужно задать диапазоны для области определения и использовать команду «splot». [4]

 

 

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

 

Цифровые данные, полученные при 1000-минутном моделировании. Усредненные результаты:

• Количество поступлений – 477;
• Обслужено клиентов – 460;
• Средне число занятых клерков – 2,65
• Средняя длительность периода занятости клерка – 11,84 мин;
• Средняя длина первичной очереди – 1,31;
• Среднее число клиентов в магазине – 8,55;
• Среднее время пребывания клиента в магазине – 18,04 мин;
• Средний объем одного заказа – 2,026;
• Среднее время пребывания в первичной очереди – 18,04-11,84=6,2 мин.

На рис. 1-3 приведены графики зависимости от числа клерков, соответственно, загрузки системы, среднего числа клерков и среднего времени пребывания клиента в системе. Из графиков видно, что оптимальное число клерков – четыре. Дальнейшее увеличение числа клерков к значимому улучшению показателей функционирования не приводит. Добавление же четвертого клерка все еще позволяет существенно улучшить эти показатели. Приведем их:

• Средне число занятых клерков – 3,32
• Средняя длительность периода занятости клерка – 11,78 мин;
• Средняя длина первичной очереди – 1,192;
• Среднее число клиентов в магазине – 8,451;
• Среднее время пребывания клиента в магазине – 16,05 мин;
• Средний объем одного заказа – 1,983;
• Среднее время пребывания в первичной очереди –

16,05-11,78=4,27 мин.

Рис. 1 Зависимость коэффициентов загрузки от числа клерков

 

Рис. 2 Зависимость среднего числа клиентов в магазине от числа клерков

 

Рис. 3 Зависимость среднего времени пребывания клиента в магазине от числа клерков