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

8. Сетевая модель

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

     Событие – момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта.

     Порядок построения сетевого графика.

1. В сетевой модели не должно быть “тупиковых” событий, т.е. событий, из которых не выходит ни одна работа, за исключением завершающего события.
2. В сетевом графике не должно быть событий (кроме исходного), которым не предшествует хотя бы одна работа.
3. В сети не должно быть замкнутых контуров и петель, т. е путей, соединяющих некоторые события с ними же самими.
4. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой.
5. В сети рекомендуется иметь одно исходное и одно завершающее событие.

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

      Критический путь – наиболее продолжительный полный путь в сетевом графике.

Временные параметры сетевых графиков

Элемент сети, характеризуемый параметром	Наименование  параметра	Условное обозначение  параметра
Событие i	Ранний срок свершения события Поздний срок свершения события Резерв  времени события	tp(i) tn(i) R(i)
Работа (i,j)	Продолжительность работы Ранний  срок начала работы Ранний  срок окончания работы Поздний срок начала работы Поздний срок окончания работы Полный  резерв времени работы Частный резерв времени работы первого вида Частный резерв времени работы второго вида иди свободный  резерв времени работы Независимый резерв времени работы	t(i,j) tрн(i,j) tро(i,j) tпн(i,j) tпо(i,j) Rп(i,j) R1(i,j)  Rс(i,j)    Rн(i,j)
Путь  L	Продолжительность пути Продолжительность критического пути Резерв  времени пути	t(L) tкр R(L)

 

      Оптимизация сетевого графика – процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения.

      Частная оптимизация – минимизация времени выполнения комплекса работ при заданной стоимости, минимизация стоимости комплекса работ при заданном времени выполнения проекта.

      Комплексная оптимизация – нахождение оптимального соотношения величин стоимости и сроков выполнения проекта в зависимости от конкретных целей, ставящихся при его реализации. 
 
 

     8.1. Пример решения  задачи

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

      Таблица 8.1.1

№ п/п	Работа (i,j)	Продолжительность работы, сутки		Коэффициент затрат  на ускорение работы h(i,j)	Стоимость работы, усл. руб. С=(i,j) при t(i,j)= b (i,j)
		мини- мальная а(i,j)	макси- мальная b (i,j)
1	(0,1)	10	20	6	35
2	(0,2)	12	32	3	50
3	(1,2)	2	12	3	15
4	(1,3)	2	7	8	10
5	(2,7)	2	7	3	10
6	(3,4)	16	26	2	50
7	(3,5)	8	13	6	15
8	(4,6)	12	22	4	40
9	(5,6)	20	25	4	30
10	(6,7)	8	13	5	25
11	(7,8)	6	11	9	20
Итого					300

 

     Решение. Исходный для оптимизации план (см. рис.8.1.1) имеет максимальную продолжительность работ t(i,j)= b (i,j) и соответственно минимальную стоимость С=З00 (усл. руб.). Найдем все полные пути сетевого графика. 

Рис. 8.1.1

     Их  четыре:

     L₁ продолжительностью t(L₁)=89 (суток);

     L₂ продолжительностъю t_кр= t(L₂)=99 (суток);

     L₃  продолжительностью t(L₃)=50(сугок);

     L₄ продолжительностью t(L₄)=50 (сугок).

     Для удобства дальнейших расчетов представим эти пути графически в виде цепочек работ (рис. 8.1.2), в которых цифры над стрелками показывают коэффициенты затрат на ускорение работ h(i,j), а под стрелками — максимально возможные величины уменьшения продолжительности работ Dt(i,j) = b (i,j)- а(i,j). 

     Рис. 8.1.2

     I ш а г. Уменьшить продолжительность выполнения комплекса можно, как известно, только за счет сокращения продолжительности работ критического пути t_кр=t(L₂). Из работ критического пути L₂ наименьший коэффициент затрат на ускорение h(i,j) имеет работа (3,4):  
h_min(i,j)= min{h (0, 1); h (1, .3); h (3, 4); h (4, б); h (б, 7); 
h (7, 8)}= min{6; 8; 2; 4; 5; 9}=2, т.е. h_min(i,j)= h (3, 4)=2. Продолжительность работы t(3,4) можно сокращать не более чем на 10 суток. При этом изменится длина только критического пути (с 99 до 89 суток)  — L₂ единственного из четырех путей, проходящего через работу (3,4). А стоимость проекта за счет ускорения работы (3,4) возрастет до 320 (усл. руб.). Итак, на 1 шаге:

, где 89≤t≤99;

     новые длины путей равны t(L₁)= t(L₂)=89; t(L₃)= t(L₄)=50.

     II ш а г. Теперь мы имеем два критических пути L₁ и L₂ и сократить срок выполнения проекта можно за счет одновременного сокращения их продолжительности. Сократить одновременно t(L₁) и t(L₂) можно, уменьшив продолжительность работ, лежащих на этих путях: либо t(0, 1), либо t(6,7), либо t(7, 6). Останавливаемся на t(6, 7), поскольку при этом обеспечивается минимум затрат на ускорение работы: h_min(i,j)=min{h(0,1);h(1,3); h(6,7); h(7,8)}=min{6; 8; 5; 9}=5, т.е.  
h_min(i,j)=h (6, 7)=5.

     Продолжительность работы t(6,7), можно уменьшить не более на 5 суток. На эту величину уменьшатся длины критических путей t(L₁) и t(L₂), а следовательно, и срок выполнения проекта t= t(L₁) и t= t(L₂). При этом стоимость проекта увеличится с 320 до 345 (усл. руб.). Итак, на II шаге:

где 84≤t≤89;

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

     III ш а г. h_min(i,j)= min {h(0, 1); h(1, 3); h(7, 8)} = min (6; 8; 9}=6, т.е. h_min(i,j)=h(0,1)=6. Сокращая продолжительностъ работы t(0, 1) до 10 суток, найдем

где 74≤t≤84

 

     IV ш а г. h_min(i,j)=  min {h(1, 3); h(7,6)} = min {8; 9} = 8, т.е.  
h_min(i,j)=  h(1, 3)= 8. Сокращая продолжительность работы t(1, З) до 5 суток, найдем

     где 69≤t≤74

     

     V ш а г. Сокращая продолжительность работы t (7, 8) до 5 суток, найдем (учитывая, что h (7, 8)=9)

     где 64≤t≤69

     

     VI ш а г. Теперь несокращенными остались продолжительности трех критических работ: t(3, 5) и t(5, 6) критического пути L₁, каждую из которых можно сократить до 5 суток, и t(4, 6) критического пути L₂, которую можно сократить до 10 суток. Сокращение какой-либо одной из названных величин не приведет к сокращению продолжительности выполнения проекта, ибо при этом сократится лишь один из двух путей, а длина несокращенного пути, который станет единственным критическим путем, не изменится. Поэтому последовательно сокращая t(4, 6) и t(5, 6) до 5 суток (с учетом времени сокращения продолжительности работ), найдем (теперь коэффициент затрат на ускорение работ равен  
h(4, 6)+h(5, 6)= 4+4= 8):

     где 59≤t≤64;

   

     VII ш а г. Продолжительность работы t(4, 6) можно сократить еще до 5 суток и на тот же срок можно сократить t (3, 5) (иначе срок выполнения проекта не изменится). Полагая, что h (4, 6)+h (3, 5)=4+6=10, найдем

     где 54≤t≤59 

     График  оптимальной зависимости стоимости  проекта С(t) от продолжительности его выполнения показан на рис. 8.1.3. С помощью этого графика можно, с одной стороны, оценить минимальную стоимость проекта при любом возможном сроке его выполнения, а с другой стороны — найти предельную продолжительность выполнения проекта при заданной его стоимости. Например, при продолжительности проекта t=79 (суток) минимальная стоимость выполнения рассматриваемого комплекса составит 375 (усл. руб.), а при стоимости выполнения комплекса, например, 540 (усл. руб.) предельная продолжительность проекта составит 55 (суток). С помощью функции С(t) можно оценить дополнительные затраты, связанные с сокращением сроков завершения комплекса. Так, сокращение продолжительности проекта с 79 до 55 суток потребует дополнительных затрат 540-375=165 (усл. руб.). 

Рис. 8.1.3