7. Элементы сетевого планирования

7.1. Основные понятия

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

Сетевые графики выполняются с соблюдением определенных правил:

1. Они должны иметь только одно исходное событие (исток сети J) – начало работ комплекса;

2. Они должны иметь только одно завершающее событие (сток сети S) – окончание всех работ комплекса;

3. Прежде чем строить сеть, надо составить подробный спи­сок работ комплекса. В отношении каждой работы выяснить:

а) ее связи с другими работами;

б) ее место в комплексе;

в) ее конечные ре­зультаты (события).

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

Пример 29. По данным табл. 39 построить сеть.

Таблица 39

Обозначение работы	а1	а2	а3	а4	а5	а6	а7	а8	а9
Непосредственно предшест­вующие работы	–	–	–	а1	а1 а2	а1 а2	а3 а5	а4 а6 а7	а3 а5
Продолжительность работы	3	6	4	5	1	9	6	8	5

Решение: работы а₁, а₂, а₃ не имеют предшествующих, поэтому реа­лизация комплекса начинается с этих работ и изображаем их прямыми, выходящими из одного события 1 (исток J сети) (рис. 18).

Рис. 18

Дуги а₁, а₂, а₃ и так далее располагаются произвольно. Работе а₄ предшествует работа а₁. Далее надо изобразить работы а₅ и а₆, им предшествуют одни и те же работы а₁ и а₂. Во избежание путаницы на сетях не рекомендуется изображать параллельными дугами одновременно выполняемые работы. В подобных случаях вводятся дополнительные события и фиктивные работы (нулевой продолжительности), которые изображаются штриховыми линиями. Их назначение – показать, что данная работа не может быть выполнена ранее какого-либо события или работы. Учитывая это, введем фиктивную работу, соединив событие 2 работы а₁ с событием 3 работы а₂. После этого изобразим а₅ и а₆ дугами, выходящими из события 3, причем дуги а₃, а₅ должны прийти в одно событие (работа а₇ начинается после них), такое событие уже есть – это 4, а дуги а₄, а₆ аналогично идут в событие 5. Так как работа а₈ может быть начата только после работ а₄, а₆ и а₇, поэтому работу а₇ направим в событие 5. И, наконец, дуги а₈ и а₉ моделируют заключительные работы комплекса, поэтому сведем их в одно завершающее событие 6 (сток сети S).

Замечание. Правильность нуме­рации событий (вершин графа) можно проверить алгоритмом Фалкерсона (упорядочить граф).