Амкнутая система с неоднородными каналами: моделирование грузовых автоперевозок

Распределение Эрланга названо в честь А. Эрланга (A. Erlang), впервые применившего его в задачах теории массового обслуживания и телефонии.

Это распределение интенсивно применяется в задачах телекоммуникации для моделирования входящего потока вызовов.

 

 

 

2. Описание системы

Моделируемая система состоит из одного бульдозера, четырех самосвалов и двух механизированных погрузчиков. Бульдозер сгребает землю к погрузчикам. Для начала погрузки перед погрузчиками должны лежать две кучи земли. Один самосвал полностью загружается одной кучей. Каждая из куч относится только к одному, «своему» погрузчику, одна – для одного, другая – для другого, то есть перед каждым погрузчиком должно лежать по куче, с которой будет работать (загружать самосвал) только этот погрузчик. Время, затрачиваемое бульдозерами на подготовку фронта работ до начала погрузки, имеет распределение Эрланга и состоит из суммы двух экспоненциальных величин, каждая из которых имеет математическое ожидание равное 4 мин (это соответствует эрланговскому распределению с математическим ожиданием 8 мин и дисперсией 32). Кроме наличия земли для начала погрузки требуется погрузчик и порожний самосвал. Время погрузки распределено экспоненциально с математическим ожиданием 14 мин для первого погрузчика и 12 мин для второго.

Рис.1. Система грузовых автоперевозок (концептуальная модель системы)

После того как самосвал загружен, он уезжает к месту разгрузки, разгружается и вновь возвращается на погрузку. В пункте разгрузки находится только одно разгрузочное место, где самосвал может разгрузиться, то есть два и более самосвалов одновременно разгружаться не могут. Для краткости будем называть такое разгрузочное место разгрузчиком (название условное, так как самосвал разгружается сам). Время нахождения самосвала в пути распределено нормально, причем в загруженном состоянии он тратит на дорогу в среднем 22 мин, а в порожнем – 18 мин. Среднеквадратичное отклонение в обоих случаях равно 3 мин. Время разгрузки распределено равномерно на интервале от 2 до 8 мин. После погрузки каждого самосвала погрузчик должен «отдыхать» в течении 5 мин, а затем вновь может приступать к погрузке.

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

1. Модельное время

За единицу модельного времени принимаем секунду. Случайные величины, распределенные равномерно, генерируем сразу в секундах. Случайные величины, распределенные по закону Эрланга, экспоненциально и нормально, генерируем в минутах, чтобы избежать потери точности при численном решении уравнений и интегрировании, затем результат умножаем на 60 и округляем до ближайшего целого числа. Дальнейшее масштабирование времени в этой задаче использовать не будем.

2. Классы и объекты

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

Введем два класса – Пункт погрузки (Fuller) и Пункт разгрузки (Emptier). Хотя в условии задачи количество погрузчиков и разгрузчиков фиксировано (соответственно, 2 и 1), сделаем эти значения полями данных классов, чтобы повысить общность моделирующей программы и облегчить эксперименты с ней в дальнейшем. В связи с обобщением задачи на случай произвольного числа k погрузчиков необходимо добавить пояснение. Погрузка начинается только тогда, когда бульдозер нагреб k куч  - по одной перед каждым погрузчиком. Соответственно, время работы бульдозера при наличии k погрузчиков имеет распределение Эрланга порядка k.

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

Теперь разберемся, нужно ли выделять в отдельный класс самосвалы. В первую очередь отметим, что в условии задачи не сказано, какую именно статистику о работе системы нужно собрать. Это оставлено на усмотрение исследователя. Главным показателем, несомненно, является производительность, выражаемая в количестве земли, перевезенной в пункт разгрузки. Единицей ее измерения примем 1 самосвал. Каждый из самосвалов в пунктах погрузки и разгрузки выступает в качестве заявки на обслуживание. Так как система замкнутая, время пребывания заявки (самосвала) отслеживать не нужно, но, тем не менее, отдельный класс для самосвалов ввести следует. Дело в том, что не на всем протяжении производственного цикла самосвал находится «под патронажем» других объектов – во время курсирования между пунктами погрузки и разгрузки он выступает как самостоятельная обособленная единица, для которой  нужно отслеживать время, оставшееся до прибытия в один из пунктов. И то и другое время задано собственными законами распределения. Таким образом, вводим класс Самосвал (HeavyCar), представленный в системе четырьмя объектами.

Проектирование класса HeavyCar затруднений не вызывает. Его полями данных являются времена до завершения пути туда и обратно и состояния, в котором он в данный момент находится. Примем для состояний следующую нумерацию:

• Состояние 1 – в очереди к погрузчику;
• Состояние 2 – непосредственно на погрузке;
• Состояние 3 – загруженный самосвал движется к пункту разгрузки;
• Состояние 4 – в очереди к разгрузчику;
• Состояние 5 – непосредственно на разгрузке;
• Состояние 6 – порожний самосвал движется к пункту погрузки.

Выходы самосвала из состояний 1, 2, 4, 5 будут моделироваться пунктами погрузки и разгрузки, из состояний 3 и 6 – самим самосвалом. Заметим, что номер состояния является логическим избыточным полем данных, так как его значение можно вычислить из информации, поставляемой полями данных, как самого самосвала, так и других объектов. Все же включим состояние самосвала в число полей данных для упрощения моделирования системы.

Самосвалу также нужна связь с пунктами погрузки и разгрузки для передачи им сообщений о своем прибытии на них. Это достигается уже опробованным способом – приведением «пустых» указателей.

Для класса Fuller динамическую информацию о погрузчиках будем хранить в массивах. Эта информация включает указатель на загружаемый самосвал и время, оставшееся до окончания его загрузки, время, оставшееся до окончания «отдыха» погрузчика, наличие или отсутствие подготовленной бульдозером кучи земли перед погрузчиком. Размеры этих массивов равны количеству погрузчиков. Необходим также массив, содержащий указатели на самосвалы, находящиеся в очереди на погрузку, размер которого равен количеству самосвалов в системе.

Аналогии этих массивов требуются и в качестве полей данных класса Emptier, за исключением времени, оставшегося до окончания «отдыха» (так как отдыхать некому – самосвал разгружается сам), и признаков готовности кучи земли (для разгрузки это не требуется).

Приведем полные списки полей данных классов.

1. Класс HeavyCar

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

• Среднее время пути груженого самосвала (22);
• Среднеквадратичное отклонение в пути груженого самосвала (3);
• Среднее время в пути порожнего самосвала (18);
• Среднеквадратичное отклонение времени в пути порожнего самосвала (3);
• Порядковый номер (уникальный идентификатор);
• Указатель на Пункт погрузки;
• Указатель на Пункт разгрузки;

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

• Состояние самосвала (от 1 до 6);
• Время, оставшееся до прибытия на разгрузку;
• Время, оставшееся до прибытия на погрузку.

2. Класс Fuller

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

• Количество погрузчиков (2);
• Производительность бульдозера (по условию – 0,25 кучи в минуту);
• Продолжительность отдыха после погрузки (300);
• Массив производительностей погрузчиков (0,0714; 0,0833).

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

• Время до окончания подготовки бульдозером фронта работ – двух куч;
• Массив значений времени, оставшегося до окончания погрузки каждым погрузчиком;
• Массив указателей на объекты класса HeavyCar, обслуживаемые в данный момент погрузчиками;
• Массив указателей на объекты класса HeavyCar, находящиеся в очереди на погрузку;
• Массив значений времени, оставшегося до окончания «отдыха» погрузчиков;
• Массив признаков того, готова ли для погрузчика куча земли.

3. Класс Emptier

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

• Количество разгрузчиков (1);
• Минимальное время разгрузки (120);
• Максимальное время разгрузки (480).

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

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

Количество самосвалов зададим как глобальную переменную, описанную в заголовочном файле.

3. События и методы

Класс HeavyCar не имеет моделирующих методов, за исключением метода run(), так как все события, происходящие с самосвалом, моделируются методами других классов. С пунктом погрузки могут происходить следующие события:

• Окончание работы бульдозера;
• Прибытие в пункт очередного самосвала;
• Окончание загрузки самосвала одним из погрузчиков;
• Окончание «отдыха» одного из погрузчиков.

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

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

Условие завершения всех начатых работ, чтобы не усложнять программу, учтем только при вычислении основной характеристики – количества разгруженных самосвалов. Это сделано следующим образом. В момент завершения рабочего дня, то есть истечения восьмичасового интервала времени, проверяется состояние каждого самосвала. Если самосвал находится в очереди на погрузку или движется порожняком, он оставляется без внимания. При любом другом состоянии он должен «дойти» до разгрузки, поэтому к числу разгруженных самосвалов прибавляется единица.

4. Листинг программы

Реализация классов:

#include<cstdio>

#include<ctime>

#include "erlang.h"       //генераторы распределений Эрланга

//и экспоненциального

#include "normal.h"       //генератор нормального распределения

#include "random.h"

FILE *qu1;                //файл для сбора статистики  о длине очереди

//на погрузку

FILE *qu2;                //файл для сбора статистики  о длине очереди

//на разгрузку

enum states {Que_Fuller=1,Full,Full_Move,Que_Emptier,Empty,Empty_Move};

int S=4;                  //количество самосвалов

int completed=0;          //счетчик разгруженных самосвалов

float que1_ave=0;         //счетчик средней длины очереди  на погрузку

float que2_ave=0;         //счетчик средней длины очереди  на разгрузку

long int total;           //счетчик общего времени моделирования

float ro_fuller=0;        //счетчик средней загрузки пункта  погрузки

long int ro_buld=0L;      //счетчик средней загрузки бульдозера