Определение основных показателей сетевого графика

Расчёт основных показателей сетевого графика проводится по приве­дённым выше формулам.

Сетевой график строится так, чтобы все дуги – работы были направлены слева направо. Над дугами (стрелками) проставлены длительности работ.

Покажем табличный способ расчёта основных показателей сетевого графика (рисунок 6.3).

Упорядочим сетевой график. Нумерация событий графика осуществляется следующим образом. Находим исходное событие, в которое не входит ни одна стрелка и присваиваем ему номер 1. Затем вычёркиваем все выходящие из него работы (стрелки) и на оставшейся части сети вновь находим событие, в которое не входит ни одна стрелка. Этому событию присваиваем номер 2. После определения события 2 вычёркиваем все выходящие из него стрелки и по предыдущему критерию находим событие 3. Если на графике оказывается несколько событий, в которые не входят стрелки, присваиваем следующий номер любому событию. Процесс нумерации продолжается до полного завершения процедуры. Окончательный вид сети на рисунке 6.4.

Рисунок 6.4 – Пронумерованный сетевой график

Расчёт показателей сетевого графика проведём в квадратной таблице, число строк и столбцов которой равно числу событий в графике.

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

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

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

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

4. Знаменатель последнего главного квадрата принимается равным
числителю этого квадрата. Нижняя часть таблицы рассчитывается в
обратном порядке. Знаменатели нижних побочных квадратов равны
разности знаменателя главного и числителя нижнего побочного в той же строке.

5. Знаменатели главных квадратов равны минимуму знаменателей нижних побочных в том же столбце (таблица 6.1).

Таблица 6.1 – Расчёт показателей сетевого графика

Из таблицы 6.1 находятся показатели сетевого графика:

1. Ранние сроки наступления событий (числители главных квадратов).

2. Поздние сроки наступления событий (знаменатели главных квадратов).

3. Резервы времени событий (разность между знаменателем и числителем главного квадрата).

В нашем случае критическими событиями (не имеющими резервов) являются 1, 2, 3, 4, 6, 7. Они составляют критический путь. Продолжительность критического пути равна 19 (числитель или знаменатель последнего главного квадрата).

4. Ранний срок наступления работы (i, j) (числитель главного квадрата, соответствующего номеру i).

5. Ранний срок окончания работ (знаменатели верхних побочных
квадратов).

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

7. Поздний срок окончания работы (i, j) (знаменатель главного квадрата, соответствующего номеру j).

8. Общие резервы времени работ (разность между знаменателем главного квадрата и знаменателем верхнего побочного в том же столбце).

9. Свободные резервы времени работ (разности между числителем главного квадрата и знаменателем верхнего побочного квадрата в том же столбце).

Воспроизведём график сети, проставив над каждым событием слева ранний, а справа – поздний сроки наступления события.

Окончательно имеем:

Временные характеристики работ:

6.4 Оптимизация сетевого графика

Важнейшей задачей оптимизации сетевых графиков является нахождение такого варианта, при котором минимизируются суммарные издержки выполнения всего комплекса работ. При этом исходят из предположения, что затраты на выполнение какой-либо работы находятся в обратной зависимости от продолжительности её выполнения. Если все работы, включённые в сетевой график, выполняются с нормальной продолжительностью, то общая стоимость всех работ является минимальной. И наоборот, если все работы выполняются с минимальной продолжительностью, стоимость всех работ достигает максимума. Для получения минимальной продолжительности выполнения всего комплекса не требуется ускорять все работы. При ускорении некритических работ, стоимость всего комплекса возрастает, а продолжительность критического пути не уменьшается. Отсюда возникает задача нахождения такого варианта выполнения комплекса работ, при котором ускоряются лишь необходимые работы с учётом степени возрастания общей стоимости всех работ.

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

Введём следующие обозначения:

t_ij⁽⁰⁾ – минимальная продолжительность (i, j)-й работы;

t_ij⁽¹⁾ – нормальная продолжительность (i, j)-й работы;

у_ij – любая возможная продолжительность (i, j)-й работы в интервале t_ij⁽⁰⁾ ≤ у_ij ≤ t_ij⁽¹⁾;

C_ij⁽⁰⁾ – стоимость выполнения (i, j)-й работы при минимальной продолжительности;

C_ij⁽¹⁾ – стоимость выполнения (i, j)-й работы при нормальной продолжительности;

h_ij – коэффициент изменения стоимости (i, j)-й работы, характеризующий увеличение стоимости (i, j)-й работы при ускорении её на единицу времени в интервале от t_ij⁽¹⁾ до t_ij⁽⁰⁾.

Зависимость стоимости выполнения какой-либо работы от её продолжительности можно изобразить в виде графика (рисунок 6.5).

Рисунок 6.5 – Графическое изображение коэффициента стоимости

Кривая, изображённая на графике, показывает изменение стоимости

выполнения работы при увеличении времени её выполнения от t_ij⁽⁰⁾ до t_ij⁽¹⁾. Если допустима прямолинейная аппроксимация этой зависимости, то коэффициент h_ij может быть вычислен по формуле

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