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

Таблица 1.6 моделирования для операции автосамосвала, могла быть несколько упрощена не явно моделируя автосамосвалы как объекты. То есть уведомления о событии могли быть написаны как (EL, t) и так далее, и событийные переменные отслеживали просто номера самосвалов в каждой части системы, где некоторые самосвалы участвовали. При таком представлении могли быть собраны те же самые статистические вычисления коэффициентов использования. С другой стороны, если оценивалось бы среднее "системное" время пребывания или соотношение самосвалов, проводящих больше чем 30 минут в "системе" (где "система" относится к очереди загрузки и погрузчикам, а так же к очереди на взвешивание и весам), тогда объектам автосамосвалы, были бы необходимы атрибуты (DTi) равные времени прибытия в очередь загрузки. Всякий раз, когда самосвал оставлял бы весы, время пребывания самосвала могло быть вычислено как текущее модельное время (t) минус атрибут времени прибытия. Это новое время пребывания использовалось бы для модификации вычислений для накопленных статистик: S = полное время пребывания всех самосвалов, которые были в "системе" и F = число самосвалов, время пребывания которых было больше чем 30 минут. Этот пример снова иллюстрирует понятие, что до некоторой степени сложность модели зависит от оцениваемых критериев качества работы.

ПРИМЕР 1.6 (Повторно обращение к проблеме самосвала)

События и действия были идентифицированы в Примере 3.5. Используя подход со сканированием действий, условия для начала каждого действия будут:

Таблица

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

2. Обработка списков

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

Раздел 3.2.1 описывает основные свойства и операции, выполняемые в списках. Раздел 3.2.2 обсуждает использование массивов для обработки списков и использования индексов массива для создания связанных списков. Массивы являются более простым механизмом для описания основных операций, чем более обобщающее понятие динамически распределенные связанные списки, обсуждаемые в разделе 3.2.3. Наконец, раздел 3.2.4 кратко представляет некоторые из современных методов для управления списками.

Цель этого обсуждения обработки списка не состоит в том, чтобы подготовить читателя для работы со списками и их обработку на универсальном языке как, например, ФОРТРАН, C ++, а скорее обеспечить понимание у читателя списков, а так же основных концепций и операций.

Списки: Основные свойства и операции

Как предварительно обсуждено, списки - упорядоченный набор или упорядоченные записи. В имитации каждая запись представляет один объект или одно намеченное событие. Так как списки упорядочиваются, они имеют вершину или голову (первый элемент в списке); некоторый способ обхода списка (чтобы найти второй, третий, и т.д. элементы в списке); и конец или хвост (последний элемент в списке). Главный указатель - переменная, которая направляет или указывает на запись вершины списка. Некоторые списки могут также иметь указатель хвоста, который указывает на последний элемент в списке.

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

Для любого типа списка главные действия в обработке списка - добавлять запись в список и удаляют запись из списка. Определим главные операции в списке:

1. Удаление записи из вершины списка.

2. Удаление записи из любого места в списке.

3. Добавление записи объекта в вершину или конец списка.

4. Добавление записи в произвольную позицию списка, определенную в соответствии с правилом.

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

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

При моделировании на компьютере вне зависимости от того, используется ли универсальный язык как, например ФОРТРАН, C или C ++ или пакет имитационного моделирования, каждая запись объекта и намеченное событие храниться в физическом месте компьютерной памяти. Имеются две основные возможности: (a) Все записи хранятся в массивах. Массивы содержат последовательные записи в непрерывных местах в компьютерной памяти. Они поэтому могут быть упомянуты индексом массива, о котором можно думать как о номере строки в матрице. (b) Все объекты и намеченные события представлены структурами (как в C) или классами (как в C ++), и распределены по оперативной памяти произвольно и ссылаются указателями на запись или структуру.

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

Использование массивов для обработки списка

Метод хранения списка в виде массива типичен для ФОРТРАНА, но может использоваться в других процедурных языках. Поскольку большинство версий ФОРТРАНА не имеет фактических структур данных типа записи, запись может быть осуществлена как строка в двухмерном массиве или как множество параллельных массивов. Для удобства используется система обозначений R (i) для обращения к i-ой записи в массиве, и это может быть сохранено для используемого языка. Наиболее современные пакеты имитационного моделирования не использует массивы для хранения списка, а скорее использует динамически распределенныее записи, которые создаются сначала, когда нужно, и разрушаются, когда они больше не нужны.

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

При использовании массивов для сохранения списков, имеются два основных метода для хранения направления расположения записей в списке. Один метод состоит в том, чтобы хранить первую запись в R(1), вторую в R (2) и так далее, и последнюю в R (tailptr), где tailptr используется, чтобы обратиться к последнему элементу в списке. В то время как эта простая концепция проста для понимания, этот метод будет чрезвычайно неэффективен для большинства списков кроме самые коротких, у которых число записей меньше пяти. Поскольку при добавлении элемента, например в позицию 41 в списке из 100 элементов, последние 60 записей должны быть физически перемещены вниз на одну позицию массива для выделения пространства под новую запись. Даже если это было бы список "первый пришел - первый вышел" удаление первого элемента будет неэффективно, поскольку все остающиеся элементы должны были бы физически продвинуты на одну позицию в массиве. Физический метод перестановки управления списками не будет далее обсуждаться. Поскольку необходимо чтобы метод отслеживал и перестраивал логически упорядоченные элементы в списке без физического перемещения записи в компьютерной памяти.

Во втором методе переменная названная главный указатель с именем headptr, указывает на запись вершины списка. Например, если бы запись в позиции R(11) была бы записью в вершине списка, то headptr имел бы значение 11. Кроме того, каждая запись имеет поле сохраняемого индекса или указателя следующей записи в списке. Для удобства, допустим R(i, next) представляет поле следующего индекса.

ПРИМЕР 1.7 (Список для самосвалов в очереди взвешивания)

В Примере 3.5 проблемы самосвалов, предполагается, что образовалась очередь ожидания из трех самосвалов на взвешивание в том же порядке как для ЧАСОВ во время 10 в табл. 3.6, которая определяется как DT 3, DT 2, и DT 4. Предположим далее, что модель прослеживает один атрибут каждого самосвала, его время прибытия в очередь взвешивания, модифицируя каждый раз его время прибытия. Наконец, предположим, что объекты сохранены в записях в массиве с размерностью от 1 до 6, одна запись на каждый самосвал. Каждый объект представлен записью с 3 полями, первое - идентификатор объекта, второе время прибытия в очередь взвешивания и последнее поле - указатель "к точке" следующей записи, если таковые вообще имеются в списке. Очередь взвешивания представлена следующим образом:

[ DTi, время прибытия в очередь взвешивания, следующий индекс]

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

R(1) = [ DT 1, 0.0, 0]

R(2) - [ DT 2, 0.0, 0]

R(6) = [ DT 6, 0.0, 0]

Тогда для ЧАСОВ со временем 10 в табл. 1.6 для моделирования список объектов в очереди взвешивания был бы определен так:

Список создается в логическом порядке для прохода списка, начиная с главного указателя и перехода к следующей записи по указателю, что касается примера:

Нулевой вход для следующего указателя в R(4), также как tailptr = 4, указывает, что DT 4 конечный элемент списка.

При использовании следующих указателей для дисциплины FIFO как, например очередь взвешивания в этом примере, операции добавления и удаления записей объекта, когда самосвалы присоединяется и покидают очередь взвешивания, особенно простые. Когда ЧАСЫ установлены на время 12, самосвал DT 3 начинает взвешивание и оставляет очередь взвешивания. Чтобы удалять запись объекта DT 3 из вершины списка, надо модифицировать главный указатель, устанавливая его равным следующему значению указателя записи вершины списка, как в:

headptr = R(headptr, next)

Для этого примера получим:

headptr = R(3, next) = 2

Значение для самосвала DT 2 в R(2) теперь вверху списка.

Точно так же для ЧАСОВ со временем 20, самосвал DT 5 прибывает в очередь взвешивания и присоединяется к концу очереди. Чтобы добавлять записи DT 5 объекта в конец списка, предприняты следующиешаги:

R(tailptr, next) = 5 (предварительно модифицирует следующее поле указателя последнего элемента)

tailptr = 5 (модифицирует значение указателя хвоста)

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

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

3. Использование динамического распределения и связанных списков

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

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

В нашем примере, мы будем использовать систему обозначений для записей, идентичную предыдущему разделу (3.2.2):

Объекты: [ID, атрибут, следующий указатель]

Намеченные события: [тип события, время события, другие данные, следующий указатель]

Но мы не будем ссылаться на систему обозначений массива R(i) как прежде, потому что это ввело бы в заблуждение. Если бы по некоторым причинам мы хотели бы ввести третий элемент в список, то мы должны были бы просмотреть список, считая элементы, пока мы не достигли бы третьей записи. В отличие от массивов нет никакого способа отыскать непосредственно i-ю запись в связанном списке, поскольку фактические записи могут быть сохранены в любом произвольном месте в компьютерной памяти и не сохранены рядом как для массива.

ПРИМЕР 1.8 (Список будущих событий и проблема самосвала)

Основываясь на табл. 3.6 намеченные события в проблеме самосвала Примера 3.5 расширены, чтобы включить указатель на следующее намеченное событие в списке будущих событий, и они могут быть представлены как:

[ event type, event time, DT i , nextptr ]

например

[ EL, 10, DT 3, nextptr ],

где EL- конец события загрузки, которое произойдет в будущее время 10 для самосвала DT 3, а поле nextptr указывает на следующую запись в СБС. Имейте в виду, что записи могут быть сохранены где-нибудь в компьютерной памяти и не обязательно сохранены рядом. Рис. 3.9 представляет список будущих событий для ЧАСОВ со временем 10 взятый из табл. 3.6. Четвертое поле в каждой записи - значение указателя на следующую запись в списке будущих событий.

Языки C и C ++ и другие универсальные языки используют различную систему обозначений для ссылки на данные для указателя переменных. Для целей обсуждения, если R - указатель на запись, то

R Eventtype, R Eventtime, R next

являются типом события, время события и следующая запись намеченного события, а R указывает «на». Например, если R установлено равным указателю головы для СБС для значения ЧАСОВ 10, то

R eventtype = EW

R eventtime = 12

R next - указатель для следующего намеченного события в СБС,

Рис. 1.9. Список будущих событий для самосвалов со связями

Так что

R next eventtype = EL

R next eventtime = 20

R next next является указателем на третье намеченное событие в СБС.

Если одно из полей указателя нулевое (или пустой указатель), то эта запись - последний элемент в списке, и указатель переменной tailptr указывает на эту последнюю запись, как изображено на рис. 3.9.

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

Для некоторых целей желательно проходить или искать элементы списка, начиная с хвоста также как и от головы. Для таких целей может использоваться двунаправленный список. Записи в двунаправленном списке имеют два поля указателя, одно для следующей записи и одно для предыдущей записи. Хорошие ссылки, в которых обсуждаются массивы, одно- и двусвязные списки, поиск и прохождение списков - Cormen и др. [1990] и Sedgewick [1998].

Цель этого раздела кратко представить некоторых из современных идей.

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

Заключение

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

Список использованных источников

1.Лужанский Б.Е. «Оценка стоимости научно-технической продукции. Имитационное моделирование инновационного бизнес-процесса (бизнеса)». - Вопросы оценки, №2, 2009.

2.Риск-анализ инвестиционного проекта: Учебник для вузов/Под ред. М.В. Грачевой. - М.: ЮНИТИ-ДАНА, 2001. -351 с.

3.Нейлор Т. Машинные имитационные эксперименты с моделями экономических систем. М., Мир,2010.

4.Шеннон Р. Имитационное моделирование систем: искусство и наука.»Мир», М.:1978.418 с.

5.Ермолович Л.Л., Сивчик Л.Г., Толкач Г.В., Щитникова И.В. Анализ хозяйственной деятельности предприятия: Учеб. пособие / под ред. Л.Л. Ермолович - Мн.: Интерпрессервис; Экоперспектива, 2009. - 576 с.

6.Баканов М. И. Теория экономического анализа / М. И. Баканов, А. Д. Шеремет. - М.: Финансы и статистика, 2001. - 416 стр.

7.Экономико-математические методы и модели: курс лекций для студентов экон. специальностей днев. и заоч. форм обучения / авт. - сост. Е.А.Кожевников. - Гомель: ГГТУ им. П.О.Сухого, 2006. - 178 с.

Размещено на Allbest.ru