Детерминированная модель - Вероятностные сетевые модели

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

Приведем требования к одноцелевой СМ с одним исходным событием:

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

Перед построением сетевой модели технологическую последовательность работ заносят в таблицу (Таблица3).

Таблица 3. Технологическая последовательность работ

Предшествующие работы ()

Данные работы ()

--

0,1

0,2

0,3

0,1

1,4

0,1

2,5

0,1

2,6

0,1

3,6

1,4

4,7

2,5

5,7

2,6 3,6

6,8

4,7 5,7

7,8

Построенный по этой таблице сетевой график приведен на Рис. 1

сетевой график типа

Рис. 1. Сетевой график типа "узел-событие"

Так как сеть - это ориентированный граф, который определяется через бинарное отношение, он также однозначно определяется через матрицы инцидентности[19]. А поскольку работы упорядочены во времени, и дуга связивсегда идет от события с меньшим номером к событию с большим номером, то достаточно определить матрицу смежности. Расчет временных и других параметров в компьютерных системах требует табличного или матричного представления проекта.

Количество столбцов и строк в матрице равно количеству событий. Каждый столбец и строка нумеруются по порядку согласно количеству событий. Затем на пересечении каждой строки, соответствующей начальному событию, и столбцу, соответствующему последующему событию, ставится "1", а во всех остальных случаях - "0".

Наряду с понятиями работ и событий в сетевом моделировании очень важным является понятие пути.

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

Полный путь - это непрерывная последовательность работ между исходным и завершающим событием сетевой модели. Суммарная продолжительность работ, лежащих на пути, определяет длину пути[14]. Таких путей в сетевой модели может быть несколько.

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

Учитывая время выполнения работы,

Таблица 3 дополняется еще одним столбцом под названием "Продолжительность" (Таблица 4).

Таблица 4. Технологическая последовательность работ с учетом продолжительности

Предшествующие работы

()

Данная работа()

Продолжительность

--

0,1

2

0,2

2

0,3

1

0,1

1,4

4

0,1

2,5

5

0,1

2,6

8

0,1

3,6

3

1,4

4,7

1

2,5

5,7

4

2,6 3,6

6,8

5

4,7 5,7

7,8

3
сетевая модель

Рис. 2. Сетевая модель "узел-событие" суказанием временных параметров

Модель "узел-работа" (AoN) имеет существенные отличия от предыдущей. В узле содержится следующая информация (Рис. 3).

параметры, описываемые в узле модели

Рис. 3 Параметры, описываемые в узле модели "узел-работа"

На Рис.4 представлена модель "узел-работа", эквивалентная изображенной на Рис.5.

сетевая модель

Рис. 4. Сетевая модель "узел-работа" с временными параметрами

Особенностью построения СМ "узел-работа" являются:

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

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

.

Раннее начало данной работы равно максимальному из ранних окончаний предшествующих:

.

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

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

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

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

То есть полный резерв времени работ, который можно вычислить по любой из двух формул

Для критических работ будет равен нулю.

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

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

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

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

Если известна продолжительность каждой работы, можно вычислить длительность всего проекта. Один из базовых и наиболее простых методов анализа - Метод критического пути (МКП) заключается в определении работ (событий), которые должны быть выполнены (наступить) точно в срок, их длительности не могут быть увеличены без увеличения длительности всего проекта. На такие работы обычно направляется больше ресурсов.

Когда все временные параметры вычислены, остается только обозначить критический путь на графике. Расчет критического пути можно проводить, используя особые способы записи на самом графике (четырехсекторный метод, дробный метод, метод потенциалов). Все методы эквивалентны, так как используют единый аппарат расчета[11, с. 254].

Похожие статьи




Детерминированная модель - Вероятностные сетевые модели

Предыдущая | Следующая