в сетевом графике не должно быть «тупиковых» событий, из которых не выходит ни одна работа, за исключением завершающего события;
в сетевом графике не должно быть «хвостовых» событий, кроме, исходного (начального), которым не предшествует хотя бы одна работа;
в сети не должно быть замкнутых контуров и петель, т.е. путей, соединяющих некоторые события с ними же самими;
любые два события должны быть непосредственно связаны не более чем одной работой-дугой.
В случае нарушения условия 1 или 8 рекомендуется ввести фиктивное событие и фиктивную работу. Последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей, называется путем. Любой путь от начальной вершины (истока) к конечной вершине (стоку) называется полным. Если дугам графа сопоставлены какие-то числовые характеристики, то граф называется взвешенным, а числовые характеристики – весами.
Упорядочение сетевого графика заключается в таком расположении событий и работ, при котором для любой работы предшествующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием. Другими словами, в упорядоченном сетевом графике все работы-дуги направлены слева направо: от событий с меньшими номерами к событиям с большими номерами.
Критическим называется наиболее продолжительный из полных путей. Критический путь определяет минимально необходимое время выполнения всех работ, называемое критическим сроком. Работы и события, лежащие на критическом пути, называются критическими.
Задача. Построить сетевой график выполнения работ:
определить критический путь, ранние и поздние сроки выполнения работ и резервы времени выполнения работ.
Решение.
Построение сетевого графика.
2. Анализ сетевого графика
Цель анализа сетевого графика заключается в том, чтобы выявить резервы времени работ, не лежащих на критическом пути, и направить их на работы, лимитирующие срок завершения комплекса работ. Результатом этого является сокращение продолжительности критического пути.
Можно выделить следующие этапы анализа. Прежде всего устанавливается, соответствует ли график требованиям к его построению. Если требования нарушены, то производится соответствующая корректировка. Здесь пересматривается топология сети и график упорядочивается.
Далее определяется время выполнения каждой работы, и рассчитываются параметры сетевого графика. Анализируются резервы времени выполнения работ и возможность их использования с целью сокращения сроков выполнения работ, лежащих на критическом пути.
Полные пути и их продолжительности:
1 – 2 - 4 – 5 – 6 → 4/3 + 6/4 + 11/6 + 9/6 = 30/19
1 – 2 – 5 – 6 → 4/3 + 5/2 + 9/6 = 18/11
1 – 3 – 5 – 6 → 10/5 + 12/6 + 9/6 = 31/17
Нахождение критического пути.
Путь 1 – 3 – 5 – 6 – наиболее продолжительный из полных путей называется критическим.
31/17 – это минимальное время выполнения работ для достижения поставленной задачи является критическим сроком и обозначается tкр. Работа и события, лежащие на критическом пути, называют критическими.
Если выполнение какой-либо критической работы будет задержано, это задержит выполнение всего комплекса работ.
Чтобы ускорить выполнение поставленной задачи, необходимо сократить сроки выполнения критических работ.
Некритические работы могут обладать резервами времени, на которое можно задержать выполнение некритической работ, сократив при этом затраты на выполнение всего комплекса работ.
Для определения резервов времени событий необходимо рассчитать ранние и поздние сроки совершения событий.
Ранний (или ожидаемый) срок tp(j) совершения j-го события определяется продолжительностью максимального пути, предшествующего этому событию.
tp(j) = max t (Lnj),
где t (Lnj) – любой путь, предшествующий j-му событию, т.е. путь от исходного до j-го события сети. Если событие имеет несколько предшествующих путей, а следовательно несколько предшествующих событий i, то для оценки раннего срока совершения j-го события следует выбирать максимальный из предшествующих путей,
tp(j) = maxi,j [tp (i) + t (i, j)].
Расчет раннего срока наступления событий для примера на рис. 1.
tp1 = 0;
tp2 = tp1 + t (1, 2) = 0 + 4= 4;
tp3 = tp1 + t (1, 3) = 0 + 10 = 10;
tp4 = tp2 + t (2, 4) = 4 + 6 = 10;
tp5 = max [ tp4 + t (4, 5); tp2 + t (2, 5); tp3 + t (3; 5)] = max [(10 + 11); (4 + 5); (10 + 12)] = [21; 9; 22] = 22;
tp6 = tp5 + t (5; 6) = 22 + 9 = 31
Задержка свершения события по отношению к своему раннему сроку не отразится на сроке свершения завершающего события (а значит, и на сроке выполнения комплекса работ) до тех пор, пока сумма срока свершения этого события и продолжительность максимального из последующих за ним путей не превысит длины критического пути.
Поэтому поздний (или предельный) срок tp(j) свершения j-го события равен:
tp(j) = tкр – max t(Lnj)
где Lnj – любой путь следующий за j-м событием, т.е. путь от j-го до завершающего события сети.
Если событие j имеет несколько последующих путей i, то поздний срок свершения j-го события находится как минимальный из последующих путей.
tp(j) = min j,i [ tn(i) – t(j, i)].
Расчет поздних сроков свершения событий.
tn6 = tкр = 31;
tn5 = tn6 – t (5, 6) = 31 – 9 = 22;
tn4 = tn5 – t (4, 5) = 22 – 11 = 11;
tn3 = tn5 – t (3, 5) = 22 – 12 = 10;
tn2 = min [tn4 – t (2, 4); tn5 – t (2, 5)] = [(11 – 6); (22 – 5)] = [5, 17] = 5;
tn1 = min [tn2 – t (1, 2); tn3 – t (1, 3)] = [(5 – 4); (10 – 10)] = [1, 0] = 0;
Определение резерва времени события.
Резерв времени события определяется как разность между поздним и ранним сроками его свершения.
R(j) = tn(j) – tp(j).
Резерв времени события показывает, на какой допустимый период времени можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения комплекса работ. Для работ отмечается полный резерв времени работы – максимальное количество времени, на которое можно задержать начало работ или увеличить ее продолжительность, не изменяя длительность критического срока:
Rпол(i, j) = tn(j) – tp(i) - t(i, j). Для этого примера
Rп (2, 5) = tп (5) - tр (2) - t(2, 5) = 22 – 4 – 5 = 13;
Rп (4, 5) = tп (5) - tр (4) - t(4,5) = 22 – 10 – 11 = 1;
3. Оптимизация сетевого графика экономического процесса
Оптимизация сетевого графика представляет процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения.
Оптимизация проводится с целью сокращения длительности критического пути, выравнивания коэффициентов напряженности работ, рационального использования ресурсов. В первую очередь принимаются меры по сокращению продолжительности работ, находящихся на критическом пути. Это достигается
- перераспределением всех видов ресурсов, как временных (использование времени некритических путей), так и трудовых, материальных, энергетических (например, перевод части исполнителей, оборудования с некритических путей на работы критического пути);
- сокращением трудоемкости критических работ за счет передачи части работ на другие пути, имеющие резервы времени;
- параллельным выполнением работ критического
При выполнении заказа используются следующие данные о выполнении работ и связанных с ними затрат:
Таблица 2
Требуется минимизировать затраты на выполнение всего комплекса работ за 21 сутки.
Оптимизацию можно провести двумя способами:
Первый способ заключается в уменьшении продолжительности выполнения работ, осуществляемых в нормальном режиме, начиная с тех, которые дают наименьший прирост затрат.
Алгоритм решения поставленной оптимизационной задачи представлен первым способом в таблице:
Таблица 3
Итак, при снижении продолжительности выполнения всего комплекса работ с 31 суток до 21 сутки оптимальные затраты составляют 1060 + 480 = 1540.
Второй способ заключается в увеличении продолжительности выполнения работ, осуществляемых в ускоренном режиме, начиная с тех, которые дают наибольший прирост затрат.
Таблица 4
Итак, при повышении продолжительности выполнения всего комплекса ускоренного режима работ до 21 суток оптимальные затраты составляют 1710 – 170 = 1540.