Правила построения сетевых моделей

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

• 1. События правильно пронумерованы, т. е. для каждой работы (i, j) i При невыполнении этого требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем:
  • — нумерация событий начинается с исходного события, которому присваивается № 1;
  • — из исходного события вычеркивают все исходящие из него работы (стрелки) и на оставшейся сети находят событие, в которое не входит ни одна работа, ему и присваивают № 2;
  • — затем вычеркиваются работы, выходящие из события № 2, и вновь находят событие, в которое не входит ни одна работа, и ему присваивают № 3, и так продолжается до завершающего события, номер которого должен быть равен количеству событий в сетевом графике;
  • — если при очередном вычеркивании работ одновременно несколько событий не имеют входящих в них работ, то их нумеруют очередными номерами в произвольном порядке.
• 2. Отсутствуют тупиковые события (кроме завершающего), т. е. такие, за которыми не следует хотя бы одна работа.
• 3. Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа.
• 4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие событие с ним же самим.

Более подробно эти требования описаны, например, в [13], [17]. При невыполнении указанных требований не имеет смысла приступать к вычислениям характеристик событий, работ и критического пути.

Расчет характеристик сетевых моделей

Для событий рассчитывают три основные характеристики: ранний и поздний срок совершения события, а также его резерв.

Ранний срок свершения события t_р определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причем t_р(1) = 0, a t_p(N) = t_кр (L_кр)

(3.46).

Поздний срок свершения события t_п характеризует самый поздний допустимый срок, к которому должно совершаться событие, не вызывая при этом срыва срока свершения конечного события:

(3.47).

Этот показатель определяется «обратным ходом», начиная с завершающего события, с учетом соотношения t_n(N) = t_р(N).

Все события, за исключением событий, принадлежащих критическому пути, имеют резерв R (i):

(3.48).

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

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

Ранний срок начала — , (3.49).

Ранний срок окончания — , (3.50).

Поздний срок окончания — , (3.51).

Поздний срок начала — , (3.52).

Полный резерв времени — , (3.53).

Независимый резерв времени ;

(3.54).

или.

(3.55).

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

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

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

Названные выше характеристики СМ могут быть получены на основе аналитических формул (3.46)-(3.55), а процесс вычислений отображается либо на самом графике СМ, либо в матрице размерности N x N, либо в таблице. Рассмотрим алгоритмы табличного метода расчета сетевого графика на конкретном примере решения задачи организации труда при реализации некоторого проекта.

Пример 3.11. Пусть реализуется проект по строительству АЗС, при этом привлекаемые рабочие могут выполнять любую из выделенных по принятой технологии работ. Менеджер проекта установил, что в данном проекте от начала до завершения работ можно выделить 5 событий, и существуют 6 различных видов работ, связывающих эти события. При первоначальном распределении рабочих по видам работ по имеющимся нормативам трудоемкости были рассчитаны длительности выполнения работ (в днях), таким образом, сетевой график реализации данного проекта имеет вид модели, представленной ранее на рис. 3.7.

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

Рассмотрим этапы табличного метода расчета данной сетевой модели; результаты этого расчета приведены в табл. 3.17 в графах 1−9.

Этап 1. Перечень работ и их продолжительность запишем во вторую и третью графы табл. 3.17, при этом работы записываются последовательно в гр. 2: сперва начинающиеся с номера 1, затем с номера 2 и т. д.

Этап 2. В первой графе поставим число К_пр, показывающее количество работ, непосредственно предшествующих событию i, с которого начинается рассматриваемая работа. Для работ, начинающихся с номера 1, предшествующих работ нет (К_пр = 0). Для работы, начинающейся на номер k, просматриваются все верхние строчки второй графы и отыскиваются работы, заканчивающиеся на этот номер k. Количество найденных работ записывается в первую графу во все строчки, соответствующие работам, начинающимся с номера k. Например, для работы (4, 5) в графу 1 поставим цифру 2, так как на номер 4 оканчиваются две работы: (1,4) и (3,4).

Таблица 3.17

Этап 3. Заполнение таблицы начинается с расчета раннего срока работ t_p(i). Для работ, имеющих цифру «ноль» в первой графе, в графе 4 также заносятся нули и рассчитываются соответствующие значения для графы 5 (ранний срок окончания как суммы соответствующих чисел в графе 4 и графе 3 (см. формулу (3.51)). В нашей модели таких работ три; в первой строчке графы 5 ставим 0 + 6 = 6, аналогично по второй и третьей строке.

Для заполнения следующих строк графы 4 для работ (i, j) просматриваются заполненные строки графы 5, содержащие работы, оканчивающиеся на номер i, и максимальное из найденных значений (если их несколько) переносится в графу 4 для обрабатываемых строк. Так, в нашем примере в четвертой строке в графе 4 ставим 6, а в графе 5 — 15 (6 + 9 = 15). Аналогично в пятой строке в графе 4 и графе 5 ставим соответственно 5 и 17 (5 + 12 = 17). В последней шестой строке в графе 4 ставим 17 (наибольшее из чисел 8 и 17 в графе 5) и соответственно в графу 5 ставим 21 (17 + 4 = 21).

Этап 4. Графы 7 и 6 заполняются «обратным ходом», т. е. снизу вверх. Для этого просматриваются строки (работы), оканчивающиеся на номер N последнего события, и из графы 5 выбирается максимальная величина; эта величина записывается в графу 7 по всем строчкам, оканчивающимся на N (см. формулу (3.51)), с учетом равенства t_п (N) = t_p(N). Затем заполняется графа 6 по этим строкам как разность между графой 7 и графой 3 (см. формулу (3.52)). В нашем примере таких строк две (четвертая и шестая), для которых в графе 5 стоят числа 15 и 21; выбираем наибольшее из них (21) и записываем его в графу 7 по этим строкам, после чего заносим соответствующие числа в графу 6.

Далее просматриваются строки, оканчивающиеся на номер события, предшествующего завершающему, т. е. на (N — 1). Для этих строк просматриваются все строчки графы 6, лежащие ниже и начинающиеся с номера (N — 1); среди них в графе 6 выбирается минимальная величина, которая переносится в графу 7 по обрабатываемым строкам, после чего заполняется графа 6. В нашем примере таких строк две (третья и пятая); ниже их с номера 4 начинается одна (последняя) работа, и в графе 6 стоит 17, следовательно, в графе 7 по этим строчкам ставим число 17, после чего заполняется графа 6.

Затем аналогичный процесс повторяется для строк, оканчивающихся на (N — 2), (N — 3) и т. д. до тех пор, пока не будут заполнены все строки по графы 7 и 6. В нашем примере результаты приведены в соответствующих графах табл. 3.17.

Этап 5. Показатели графы 8 рассчитываются как разности соответствующих показателей граф 6 и 4 или граф 7 и 5 (см. формулы (3.48) или (3.53)). Чтобы заполнить графу 9, можно предварительно рассчитать резервы времени каждого события по формуле (3.48), а затем воспользоваться формулой (3.55). В нашем примере резервы времени для каждого из пяти событий равны соответственно: R(1) = 0; R(2) = 12 — 6 = 6; R(3) = 5 — 5 = 0; R(4) = 17 — 17 = 0; R(5) = 0. Последующие результаты по формуле (3.55) приведены в графе 9 табл. 3.17.

Этап 6. На этом этапе подводятся основные итоги расчета. Учитывая, что нулевой резерв времени имеют только работы (R_п = 0) и события (R (i) = 0), которые принадлежат критическому пути, получаем, что критическим является путь L_Kp = (1, 3, 4, 5), продолжительность которого (t_кр) равна 21 дню. Так как работы (1, 2), (1, 4) и (2, 5) имеют ненулевые резервы R_п, то очевидно, что путем перевода некоторого числа рабочих с этих работ на работы, принадлежащие критическому пути, можно сократить продолжительность этого пути и тем самым сократить сроки выполнения проекта в целом, т. е. осуществить оптимизацию сетевого графика.