4. Введение в теорию сетевого планирования

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

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

Пусть сеть задана парой (X,U), где X – множество вершин, а U – множество дуг. На множестве вершин введем бинарное отношение Подчинености вершин. Будем говорить, что вершина I Подчинена вершине K и писать IK, если в сети (X,U) Существует путь из I в K.

На множестве дуг введем аналогичное отношение Подчинености дуг. Будем говорить, что дуга (I,K) подчинена дуге (I¢,K¢) и писать (I,K)(I¢,K¢), если в сети (X,U) существует путь из K в I¢.

Очевидно, введенное отношение на сети является транзитивным и антисиметричным.

Сеть называется Взвешенной, если ее вершинам или/и дугам приписаны числа – “веса”.

Длиной пути M(I1,…,In), обозначим ее |M(I1,…,In)|, из вершины I1 в вершину In во взвешенной сети является сумма весов, включенных в него элементов. Пусть M*(I,K) самый длинный путь из I в K.

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

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

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

Определение 4.3. Сетевая модель (График) проекта – это его представление в виде взвешенной сети, которое позволяет изобразить графически связи между работами проекта.

Существует два типа сетевых моделей:

1. “работы-вершины”;

2. “работы-дуги”.

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

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

В рамках данного пособия будем рассматривать сетевые модели типа работы-дуги.

В построенной сетевой модели:

Ø каждой работе проекта поставлена в соответствие дуга сети;

Ø дуга, которая не имеет прообраза в множестве работ и введена для задания отношения подчиненности, называется Фиктивной;

Ø отношение подчиненности на множестве нефиктивных дуг отражает отношение подчиненности на множестве работ проекта;

Ø каждой нефиктивной дуге сети приписан вес, равный продолжительности соответствующей работы, а фиктивной дуге – нулевой вес.

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