Моделирование работы ремонтного цеха с использованием языка имитационного моделирования систем.

 

Продемонстрируем теперь принципы построения и проведения дискретного имитационного эксперимента с использованием языка имитационного моделирования систем на примере ремонтного цеха авиапредприятия.

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

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

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

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

______________________________________________________________________________

Блок №1 Тип узла Длительность Время Момент Тип узла Длительность Время Момент

ремонта поступления наступления ремонта поступления наступления

следующего следующего

события события

Следую-

щий узел 2 75 1002 1002 1 68 1018 1018

 

 

Узлы, 2 75 1002 -

ожидающие 4 52 992 - 4 52 992 -

ремонта 3 84 976 - 3 84 976 -

 

 

Узлы, 3 43 972 1040 3 43 972 1040

находящиеся 1 21 936 1017 1 21 936 1017

В ремонте 2 62 896 1003 2 62 896 1003

 

 

Счетчик 1000 1002

Времени

 

 

Счетчик

отремонтиро- 1 2 3 4 5 1 2 3 4 5

ванных узлов 12 22 20 31 15 12 22 20 31 15

_______________________________________________________________________________________________

 

Следую-

щий узел 1 68 1018 1018 1 68 1018 1018

 

 

Узлы,

ожидающие 2 75 1002 -

ремонта 4 52 992 - 2 75 1002 -

 

 

Узлы, 3 84 976 1087 3 84 976 1087

находящиеся 3 43 972 1040 4 52 992 1089

В ремонте 1 21 936 1017 3 43 972 1040

 

 

Счетчик 1003 1017

Времени

 

Счетчик

отремонтиро- 1 2 3 4 5 1 2 3 4 5

ванных узлов 12 23 20 31 15 13 23 20 31 15

________________________________________________________________________________

Рис. 13. Формализованная модель ремонтного цеха.

 

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

Верхняя строчка в блоке № 1 описывает очередной узел, который должен поступить в систему. Как показано на рисунке, это узел типа 2, на её ремонт требуется 75 часов, а поступить она должна в момент времени 1002. Указанный момент времени также является моментом наступления следующего события.

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

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

Предположим, что все события, которые могли бы осуществиться к моменту времени 1000, уже произошли. Пусть данный момент является началом очередного цикла. Определим время наступления следующего возможного события путем просмотра всех моментов наступления событий. Поскольку список узлов, ремонтируемых в данный момент, упорядочен по времени окончания ремонта, то фактически остается сравнить время в момент прихода очередной заявки со временем, указанным в первой строке массива данных, относящихся к узлам, находящимся в ремонте. Следуя данным, приведенным в блоке № 1, определяем, что следующим событием является поступление нового узла в момент 1002, поэтому в блоке № 2 счетчик времени устанавливается на 1002.

Если при поступлении узла обнаруживается, что все участки заняты, то его ставят в очередь. При этом соответствующее место в списке данных (первая строка) освобождается, и освободившееся место сразу же заполняется данными об узде, которая поступит в систему в момент времени 1018. Теперь можно начать следующий цикл. Следующим событием является завершение ремонта узла в момент времени 1003. В блоке № 3 на рис. 13 показано состояние системы к моменту окончания этого события. Счетчик времени установлен на 1003, а отремонтированный узел покидает систему после того, как число в счетчике отремонтированных узлов, относящееся к узлам этого типа, увеличивается на единицу.

Поскольку в очереди были узлы, первый из них по списку становится на ремонт. Время его ремонта равно 84; следующее событие, связанное с окончанием ремонта данного узла, наступает в момент времени 1087. В рассматриваемом случае новый узел, поступающий в ремонт, имеет самое большое время окончания ремонта, и поэтому ставится в конец списка узлов, находящихся в ремонте. В результате все записи сдвигаются на одну позицию, как в списке узлов-очередников, так и в списке узлов, находящихся в ремонте. Ремонт очередного узла будет закончен в момент 1017, что, как ранее, приводит к увеличению числа на счетчике готовых узлов на единицу, а в ремонт поступает первый узел из списка очередников.

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

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

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

Теперь операция удаления и добавления записи или изменения порядка записи сводится к процедуре обработки указателей. Например, чтоб удалить запись С из цепочки А, В, С,D…, достаточно указатель в записи В «переориентировать» на D. Если некоторая запись стирается, то её место в памяти компьютера можно использовать под запись на другой цепочке, но соответствующие переобозначения (перекодировку) можно произвести позже. Например, для того, чтобы переместить запись Z между В и С , указатель записи В направляют к Z , а в указатель записи Z помещают адрес записи С . Таким образом, процесс изменения цепочки состоит из сери перемещений и вставок.

При обработке списков не требуется «физически» перемещать записи. Таким образом, с помощью данной процедуры можно эффективно изменять категорию записи путем перенесения её из одной цепочки в другую, и, кроме того, данная процедура позволяет легко управлять списками, которые непрерывно изменяют свои размеры. Обработка списков является важной частью классических языков имитационного моделирования систем, таких как GPSS (General Purpose System Simulation).

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

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

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

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

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

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

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

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

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

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

В системе GPSS формализованная модель ремонтного цеха (Рис. 13) преобразуется таким образом, что, в конце концов, выглядит в виде структурной схемы Рис. 14. Посмотрим, как работает эта схема.

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

В блоке ASSIGN каждому узлу присваивается номер типа как один из его параметров; конкретное значение параметра получается из распределения, задаваемого с помощью функции FN2. Запись поступает в блок QUEUE , где помещается в очередь, в которой находится до тех пор, пока не появится свободное место в постоянном объекте (хранилище), которому присвоена метка MACH, а емкость принята равной трем.

 

GENERATE 100, FN1 ADVANCE 50, FN3

1, FN2, PH LEAVE MACH

ASSIGN

TABULATE TAB

QUEUE QUE

SAVEVALUE

ENTER MACH PH1+1,XH

 

DEPART QUE TERMINATE 1

 

Рис. 14. Модель ремонтного цеха на языке GPSS.

 

Как только появляется свободное место, запись занимает его, поступая в блок ENTER. Затем запись немедленно переходит в блок DEPART и исключается из очереди, а затем поступает в блок ADVANCE на время ремонта соответствующего узла. Процесс взаимодействия в системе GPSS организован таким образом, что если участок свободен в момент поступления узла, то запись пройдет через все блоки: от блока GENERATE до блока ADVANCE.

После того как ремонт закончен, запись переходит в блок LEAVE и освобождает участок, поступает в блок TABULATE, где регистрируется время пребывания в системе, затем переходит в блок SAVEVALUE, где происходит увеличение на единицу показания счетчика узлов соответствующего типа, наконец, запись поступает в блок TERMINATE, где она стирается.

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