Календарное планирование. Сетевые графики и оптимизационные задачи

1. Основные элементы и параметры сетевых графиков

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

Существует несколько методов расчета сетевых моделей:

- табличный;

- секторный (или расчет графика на графике);

- метод потенциалов.

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

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

Рисунок 1.1. Характеристики действительной работы

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

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

Рисунок 1.2. Характеристика ожидания

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

Рисунок 1.3. Графическое изображение фиктивной работы

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

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

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

Работы и события, лежащие на критическом пути, называются критическими:

где ti — продолжительность i-й работы;

А — исходное событие сети;

Z — завершающее событие сети.

Рисунок 1.4. Общая схема кодирования работ и событий сетевого графика

i-j — код рассматриваемой работы;

i — код начального события;

j — код конечного события;

h-i — код предшествующей работы;

h — код предшествующего события;

j-k — код последующей работы;

k — код последующего события;

ti-j — продолжительность рассматриваемой работы;

Tрн.i-j — раннее начало работы — время самое раннее из возможных сроков начала данной работы;

Тро.i-j — раннее окончание работы — время окончания работы при раннем ее начале;

Тпн.i-j — позднее начало работы — самый поздний из допустимых сроков ее начала, при котором общая продолжительность работ (критический путь) не увеличивается;

Тпо.i-j — позднее окончание работы — время окончание работы при позднем ее начале;

Ri-j — общий (полный) резерв времени работы — количество времени, на которое можно перенести начало работы или увеличить ее продолжительность, не изменяя общего срока строительства;

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

Расчет характеристик (временных параметров) сетевого графика производим в следующем порядке:

1.3.1. Выполняем расчет ранних характеристик последовательно от начального события (исходного сети) Трнi-j = О. Тогда для первой работы раннее окончание определяем по формуле

Тро.i-j = Трн.i-j + ti-j . (1.1)

Для последующей работы Трнj-k определяется по формуле

Трн.j-k = Тро.i-j = Трн.i-j + ti-j. (1.2)

Если в событие входят две и более работ, то принимают:

Трн.j-k = max Тро.i-j = max (Трн.i-j + ti-j). (1.3)

Для завершающего события модели (k):

Тро.k = max Тро.j-k = Ткр . (1.4.)

1.3.2. Выполняем расчет поздних характеристик последовательно от конечного события работы (завершающего события модели) к начальному событию. Для завершающего события (k):

Тпо.k = Тро.k = Ткр. (1.5)

Для последней работы j-k:

Тпо.j-k = max Тро.j-k, (1.6)

тогда

Тпн.j-k = Тро.j-k – tj-k = Ткр – tj-k (1.7)

Для остальных (рассматриваемых) работ:

Тпо.i-j = Тпн.j-k = min Тпн.j-k, (1.8)

тогда

Тпн.i-j = Тпо.i-j – ti-j = min Тпн.j-k – ti-j. (1.9)

Для исходного события:

Тпн.h = min Трн.h = 0. (1.10)

1.3.3. Определяем резервы времени.

Общий (полный) резерв времени Ri-j определяем как разность поздних и ранних сроков начала или окончания работы:

Ri-j = Тпн.i-j - Трн.i-j = Тпо.i-j - Тро.i-j. (1.11)

Частный (свободный) резерв времени ri-j определяем разностью значений раннего начала последующей работы и раннего окончания данной работы:

ri-j = Трн.j-k – Тро.i-j. (1.12)

Для работ, лежащих на критическом пути, общий и частный резервы времени равны 0:

Ri-j = ri-j = 0. (1.13)

1.3.4. В ходе расчета параметров сетевого графика выполняем следующие проверки:

- при расчёте поздних характеристик для исходного события (h):

Тпн.h = Трн.h =0; (1.14)

- общий резерв времени для любой работы должен быть больше или равен частному резерву времени:

Ri-j ≥ ri-j. (1.15)

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