Оптимизация сетевой модели

Процесс разработки оптимального варианта сетевой модели представляет его оптимизацию.

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

Примерами частной оптимизации являются: минимизация времени выполнения комплекса работ сетевого графика при фиксированных затратах, минимизация численности исследуемых работников, минимизация затрат на комплекс работ при заданном времени выполнения и др.

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

Когда на планируемый к выполнению комплекс работ устанавливают директивный срок его окончания Т_Д, то в ряде случаев необходима оптимизация сетевого графика по времени выполнения комплекса работ.

Для случая детерминированных оценок продолжительности работ при получении планируемого срока завершения работ Т_КР больше директивного (Т_КР > Т_Д) сетевой график является неприемлемым и его необходимо оптимизировать с целью сокращения критического пути до величины, при которой удовлетворяется условие (Т_КР £ Т_Д).

Для случая сетевого графика с вероятностными оценками продолжительности работ вычисляется вероятность свершения завершающего события в заданный срок. Для определения вероятности наступления завершающего события в директивный срок Р_К, предполагая, что значение Т_КР подчиняется закону нормального распределения, рассчитывают значение аргумента нормальной функции распределения вероятностей (функции Лапласа).

(18)

где:	Ss2tij	– сумма дисперсий работ, лежащих на критическом пути;
	n	– число работ на критическом пути.

По значению аргумента Z на основании таблицы значений нормальной функции распределения вероятностей (табл. 1) определяем Р_К. Если значение 0,35 £ Р_К £ 0,65, то можно считать, что разработка уложится в Т_Д. При Р_К £ 0,35 опасность нарушения директивного срока столь велика, что необходимо повторное перепланирование с перераспределением ресурсов. При Р_К ³ 0,65 целесообразно пересчитать сетевой график, т.к. на работах, лежащих на критическом пути, есть избыточные ресурсы.

Таблица 1

Значения нормальной функции распределения вероятностей

Z	PК	Z	PК
0,0	0,5000	– 3,0	0,0013
0,1	0,5398	– 2,9	0,0019
0,2	0,5793	– 2,8	0,0026
0,3	0,6179	– 2,7	0,0035
0,4	0,6554	– 2,6	0,0047
0,5	0,6915	– 2,5	0,0062
0,6	0,7257	– 2,4	0,0082
0,7	0,7580	– 2,3	0,0107
0,8	0,7881	– 2,2	0,0139
0,9	0,8159	– 2,1	0,0179
1,0	0,8413	– 2,0	0,0228

Окончание табл. 1

1,1	0,8643	– 1,9	0,0287
1,2	0,8849	– 1,8	0,0359
1,3	0,9032	– 1,7	0,0446
1,4	0,9292	– 1,6	0,0548
1,5	0,9332	– 1,5	0,0668
1,6	0,9452	– 1,4	0,0808
1,7	0,9554	– 1,3	0,0968
1,8	0,9641	– 1,2	0,1151
1,9	0,9713	– 1,1	0,1357
2,0	0,9772	– 1,0	0,1587
2,1	0,9821	– 0,9	0,1841
2,2	0,9861	– 0,8	0,2119
2,3	0,9893	– 0,7	0,2420
2,4	0,9918	– 0,6	0,2743
2,5	0,9938	– 0,5	0,3085
2,6	0,9953	– 0,4	0,3446
2,7	0,9965	– 0,3	0,3821
2,8	0,9974	– 0,2	0,4207
2,9	0,9981	– 0,1	0,4602
3,0	0,9987	– 0,0	0,5000

Сокращение Т_КР при перерасчетах сетевого графика возможно за счет:

- замены последовательного выполнения работ параллельным способом;

- перераспределение ресурсов между работами, не принадлежащих критической зоне комплекса работ, т.е. не лежащих на критических и подкритических путях, и работами критического пути;

- изменения технологии и организационных условий выполнения комплекса работ;

- выделения на выполнение комплекса работ дополнительных ресурсов и др.

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

Пример 1

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

Таблица 2

№ события	Перечень событий	Код работы	Перечень работ
	Решение о проектировании нового стенда принято	0,1	Разработка технических условий на стенд
		0,2	Утверждение поставщиков узлов

Продолжение табл. 2

	ТУ на стенд разработаны	1,2	Оформление и размещение заказа на покупные узлы
		1,3	Проектирование общей компоновки стенда
	Поставщики узлов утверждены. Заказ на изготовление приобретаемых узлов принят	2,7	Согласование ТУ на узлы и приемка узлов
	Общая компоновка стенда готова	3,4	Отливка заготовки для стола стенда
		3,5	Проектирование механизма передачи вибраций
	Заготовка для стола готова	4,6	Механическая обработка стола
	Проект механизма передачи готов	5,6	Изготовление механизма передачи вибраций
	Стол и механизм для передачи вибраций готовы	6,7	Монтаж механизма передачи вибраций в столе стенда

Окончание табл. 2

	Механизм передачи вибраций смонтирован; покупные узлы получены	7,8	Общая сборка и испытание стенда
	Стенд испытан и готов к эксплуатации

Расчитать t_ож и s²_tож по трем и двум оценкам времени для работ, указанных в перечне, по следующим данным, полученным от ответственного исполнителя.

Таблица 3

i, j	tmin	tнв	tmax	i, j	tmin	tнв	tmax
0, 1				3, 4
0, 2				3, 5
1, 2				4, 6
1, 3				5, 6
2, 7				6, 7
				7, 8

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

Решение

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

Таблица 4

i, j	tmin	tнв	tmax	tож3	s2tож3	tож2	s2tож2
0, 1					2,78	8,0	4,0
0, 2					1,78	11,2	2,56
1, 2					0,11	2,8	0,16
1, 3					0,11	1,8	0,16
2, 7					0,11	1,8	0,16
3, 4					2,78	11,0	4,0
3, 5					0,11	2,8	0,16
4, 6					1,78	9,2	2,56
5, 6					1,78	7,2	2,56
6, 7					0,44	4,6	0,64
7, 8					1,78	5,2	2,56

Рассмотрим вариант с тремя временными оценками, как более точный, дающий наименьшую погрешность.

Нанесем на построенный сетевой график ожидаемое время, найденное по трем временным оценкам.

Определим продолжительность путей и найдем критический:

t(L_0,1,2,7,8) = 7 + 3 + 2 + 4 = 16;

t(L_{0,1,3,4,6,7,8}) = 7 + 2 + 10 + 8 + 5 + 4 = 36 = t(L_кр);

t(L_{0,1,3,5,6,7,8}) = 7 + 2 + 3 + 6 + 5 + 4 = 27;

t(L_0,2,7,8) = 10 + 2 + 4 = 16.

Выделим на графике работы критического пути.

Рис. 3. Сетевой график комплекса работ по созданию вибростенда

Определим вероятность выполнения задания при директивном сроке Т_Д = 37 дней по формуле (18).

S s²_tож3 = 2,78 + 1,78 + 0,11 + 0,11 + 0,11 + 2,78 + 0,11 + 1,78 + 1,78 +

+ 0,44 + 1,78 = 13,56;

.

По таблице значений нормальной функции распределения вероятностей находим, что при Z = 0,3 значение Р_К = 0,6179 находится в заданных пределах (0,35 £ Р_К £ 0,65), следовательно, сетевой график рассчитан правильно.

Пример 2

По данным, приведенным в таблице данных (табл. 5), построить сетевой график, рассчитать его параметры и заполнить таблицу расчета параметров сети (табл. 6).

Таблица 5

i, j	0,1	0, 2	0, 3	1, 2	1, 5	1, 6	2, 3	2, 4	2, 5	2, 7
tij
i, j	3, 4	4, 7	5, 8	6, 8	6, 9	7, 11	8, 11	9, 10	10, 12	11, 12
tij

Таблица 6

Таблица расчета параметров сети

i

i, j

tij

tрi

tпi

tрнij

tроij

tпнij

tпоij

Ri

Rпij

Rcij

Кнij

Решение

Строим сетевой график, наносим на него исходные данные.

Определим продолжительность путей и находим критический:

t(L_{0,1,2,3,4,7,11,12}) = 8 + 12 + 17 + 11 + 3 + 9 + 13 = 73;

t(L_{0,1,2,5,8,11,12}) = 8 + 12 + 16 + 13 + 14 + 13 = 76 = t(L_кр);

t(L_{0,1,2,4,7,11,12}) = 8 + 12 + 6 + 3 + 9 + 13 = 51;

t(L_{0,1,2,7,11,12}) = 8 + 12 + 11 + 9 + 13 = 53;

t(L_{0,1,5,8,11,12}) = 8 + 8 + 13 + 14 + 13 = 60;

t(L_{0,1,6,8,11,12}) = 8 + 5 + 7 + 14 + 13 = 47;

t(L_{0,1,6,9,10,12}) = 8 + 5 + 4 + 5 + 7 = 29;

t(L_{0,2,3,4,7,11,12}) = 6 + 17 + 11 + 3 + 9 + 13 = 59;

t(L_{0,2,4,7,11,12}) = 6 + 6 + 3 + 9 + 13 = 37;

t(L_{0,2,5,8,11,12}) = 6 + 16 + 13 + 14 + 13 = 62;

t(L_0,2,7,11,12) = 6 + 11 + 9 + 13 = 39;

t(L_{0,3,4,7,11,12}) = 7 + 11 + 3 + 9 + 13 = 43.

Рис. 4. Сетевой график комплекса работ

Выделяем на графике критический путь. После этого можно приступать к расчету параметров.

Расчитаем ранние сроки свершения событий. Для удобства расчета события критического пути выделим жирным шрифтом. Расчет ведется по формуле (6).

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

t_р0 = 0;

t_р1 = t_0,1 = 8;

t_р2 = t_р1 + t_1,2 = 8 + 12 = 20;

t_р3 = t_р2 + t_2,3 = 20 + 17 = 37;

t_р4 = t_р3 + t_3,4 = 37 + 11 = 48;

t_р5 = t_р2 + t_2,5 = 20 + 16 = 36;

t_р6 = t_р1 + t_1,6 = 8 + 5 = 13;

t_р7 = t_р4 + t_4,7 = 48 + 3 = 51;

t_р8 = t_р5+ t_5,8 = 36 + 13 = 49;

t_р9 = t_р6 + t_6,9 = 13 + 4 = 17;

t_р10 = t_р9 + t_9,10 = 17 + 5 = 22;

t_р11 = t_р8 + t_8,11 = 49 + 14 = 63;

t_р12 = t_р11 + t_11,12 = t(L_кр) = 63 + 13 = 76.

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

Расчет начинаем от завершающего события по формуле (7).

Если от завершающего до данного события имеется более одного пути, то рассматриваем наиболее продолжительный путь. Значение позднего срока в данном случае – это минимальное число из возможных. Выбором наиболее ранней даты обеспечивается время, необходимое для совершения завершающего события по самому длинному пути. Если выбрать из возможных чисел значение больше минимального, это приведет к увеличению критического пути.

t_п12 = t_р12 = t(L_кр) = 76;

t_п11 = t_п12 – t_11,12 = 76 – 13 = 63;

t_п10 = t_п12 – t_10,12 = 76 – 7 = 69;

t_п9 = t_п10 – t_9,10 = 69– 5 = 64;

t_п8 = t_п11 – t_8,11 = 63 – 14 = 49;

t_п7 = t_п11 – t_7,11 = 63 – 9 = 54;

t_п6 = t_п8 – t_6,8 = 49 – 7 = 42;

t_п5 = t_п8 – t_5,8 = 49 – 13 = 36;

t_п4 = t_п7 – t_4,7 = 54 – 3 = 51;

t_п3 = t_п4 – t_3,4 = 51 – 11 = 40;

t_п2 = t_п5 – t_2,5 = 36 – 16 = 20;

t_п1 = t_п2 – t_1,2 = 20 – 12 = 8;

t_п0 = t_п1 – t_0,1 = 8 – 8 = 0.

Найдем резервы времени событий по формуле (5). Резерв времени события показывает, на какое время можно задержать свершение события, не увеличивая продолжительности критического пути. Резервы времени событий, лежащих на критическом пути, равны нулю, так как у этих событий t_рi = t_пi, а остальных событий больше нуля, следовательно:

R₀ = R₁ = R₂ = R₅ = R₈ = R₁₁ = R₁₂ = 0.

R₃ = 40 – 37 = 3;

R₄ = 51 – 48 = 3;

R₆ = 42 – 13 = 29;

R₇ = 54 – 51 = 3;

R₉ = 64 – 17 = 47;

R₁₀ = 69 – 22 = 47.

Определим сроки начала и окончания работ.

Для работ критического пути t_рнij = t_пнij и t_роij = t_поij, поэтому ранний и поздний сроки начала работ для работ критического пути равны:

t_рн0,1 = t_пн0,1 = t_р0 = 0;

t_рн1,2 = t_пн1,2 = t_р1 = 8;

t_рн2,5 = t_пн2,5 = t_р2 = 20;

t_рн5,8 = t_пн5,8 = t_р5 = 36;

t_рн8,11 = t_пн8,11 = t_р8 = 49;

t_рн11,12 = t_пн11,12 = t_р11 = 63.

Ранние и поздние сроки окончания работ для работ критического пути по формулам (12 – 13):

t_ро0,1 = t_по0,1 = t_п1 = 8;

t_ро1,2 = t_по1,2 = t_п2 = 20;

t_ро2,5 = t_по2,5 = t_п5 = 36;

t_ро5,8 = t_по5,8 = t_п8 = 49;

t_ро8,11 = t_по8,11 = t_п11 = 63;

t_ро11,12 = t_по11,12 = t_п12 = 76.

Рассчитаем ранние сроки начала для остальных работ по формуле (8).

t_рн0,2 = t_рн0,3 = t_р0 = 0;

t_рн1,5 = t_рн1,6 = t_р1 = 8;

t_рн2,3 = t_рн2,4 = t_рн2,7 = t_р2 = 20;

t_рн3,4 = t_р3 = 37;

t_рн4,7 = t_р4 = 48;

t_рн6,8 = t_рн6,9 = t_р6 = 13;

t_рн7,11 = t_р7 = 63;

t_рн9,10 = t_р9 = 17;

t_рн10,12 = t_р10 = 22.

Рассчитаем ранние сроки окончания для остальных работ по формуле (10).

t_ро0,2 = t_р0 + t_0,2 = 0 + 6 = 6;

t_ро0,3 = t_р0 + t_0,3 = 0 + 7 = 7;

t_ро1,5 = t_р1 + t_1,5 = 8 + 8 = 16;

t_ро1,6 = t_р1 + t_1,6 = 8 + 5 = 13;

t_ро2,3 = t_р2 + t_2,3 = 20 + 17 = 37;

t_ро2,4 = t_р2 + t_2,4 = 20 + 6 = 26;

t_ро2,7 = t_р2 + t_2,7 = 20 + 11 = 31;

t_ро3,4 = t_р3 + t_3,4 = 37 + 11 = 48;

t_ро4,7 = t_р4 + t_4,7 = 48 + 3 = 51;

t_ро6,8 = t_р6 + t_6,8 = 13 + 7 = 20;

t_ро6,9 = t_р6 + t_6,9 = 13 + 4 = 17;

t_ро7,11 = t_р7 + t_7,11 = 51 + 9 = 60;

t_ро9,10 = t_р9 + t_9,10 = 17 + 5 = 22;

t_ро10,12 = t_р10 + t_10,12 = 22 + 7 = 29.

Определим поздние сроки окончания работ для работ, не лежащих на критическом пути по формуле (11).

t_по0,2 = t_п2 = 20;

t_по0,3 = t_п3 = 40;

t_по1,5 = t_п5 = 36;

t_по1,6 = t_п6 = 42;

t_по2,3 = t_п3 = 40;

t_по2,4 = t_п4 = 51;

t_по2,7 = t_п7 = 54;

t_по3,4 = t_п4 = 51;

t_по4,7 = t_п7 = 54;

t_по6,8 = t_п8 = 49;

t_по6,9 = t_п9 = 64;

t_по7,11 = t_п11 = 63;

t_по9,10 = t_п10= 69;

t_по10,12 = t_п12 = 76.

Определим поздние сроки начала работ для работ, не лежащих на критическом пути по формуле (9).

t_пн0,2 = t_п2 – t_0,2 = 20 – 6 = 14;

t_пн0,3 = t_п3 – t_0,3 = 40 – 7 = 33;

t_пн1,5 = t_п5 – t_1,5 = 36 – 8 = 28;

t_пн1,6 = t_п6 – t_1,6 = 42 – 5 = 37;

t_пн2,3 = t_п3 – t_2,3 = 40 – 17 = 23;

t_пн2,4 = t_п4 – t_2,4 = 51 – 6 = 45;

t_пн2,7 = t_п7 – t_2,7 = 54 – 11 = 43;

t_пн3,4 = t_п4 – t_3,4 = 51 – 11 = 40;

t_пн4,7 = t_п7 – t_4,7 = 54 – 3 = 51;

t_пн6,8 = t_п8 – t_6,8 = 49 – 7 = 42;

t_пн6,9 = t_п9 – t_6,9 = 64 – 4 = 60;

t_пн9,10 = t_п10 – t_9,10 = 69 – 5 = 64;

t_пн10,12 = t_п12 – t_10,12 = 76 – 7 = 69.

Определим резервы времени работ.

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

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

R_п0,1 = R_п1,2 = R_п2,5 = R_п5,8 = R_п8,11 = R_п11,12 = 0.

R_с0,1 = R_с1,2 = R_с2,5 = R_с5,8 = R_с8,11 = R_с11,12 = 0.

Определим полный резерв времени для работ, не лежащих на критическом пути по формуле (15).

R_п0,2 = t_п2 – t_р0 – t_0,2 = 20 – 0 – 6 = 14;

R_п0,3 = t_п3 – t_р0 – t_0,3 = 40 – 0 – 7 = 33;

R_п2,3 = t_п3 – t_р2 – t_2,3 = 40 – 20 – 17 = 3;

R_п2,4 = t_п4 – t_р2 – t_2,4 = 51 – 20 – 6 = 25;

R_п2,7 = t_п7 – t_р2 – t_2,7 = 54 – 20 – 11 = 23;

R_п3,4 = t_п4 – t_р3 – t_3,4 = 51 – 37 – 11 = 3;

R_п4,7 = t_п7 – t_р4 – t_4,7 = 54 – 48 – 3 = 3;

R_п6,8 = t_п8 – t_р6 – t_6,8 = 49 – 13 – 7 = 29;

R_п6,9 = t_п9 – t_р6 – t_6,9 = 64 – 13 – 4 = 47;

R_п7,11 = t_п11 – t_р7 – t_7,11 = 63 – 51 – 9 = 3;

R_п9,10 = t_п10 – t_р9 – t_9,10 = 69 – 17 – 5 = 47;

R_п10,12 = t_п12 – t_р10 – t_10,12 = 76 – 22 – 7 = 47.

Свободный резерв времени для тех же работ определяем по формуле (16).

R_с0,2 = t_р2 – t_р0 – t_0,2 = 20 – 0 – 6 = 14;

R_с0,3 = t_р3 – t_р0 – t_0,3 = 37 – 0 – 7 = 30;

R_с2,3 = t_р3 – t_р2 – t_2,3 = 37 – 20 – 17 = 0;

R_с2,4 = t_р4 – t_р2 – t_2,4 = 48 – 20 – 6 = 22;

R_с2,7 = t_р7 – t_р2 – t_2,7 = 51 – 20 – 11 = 20;

R_с3,4 = t_р4 – t_р3 – t_3,4 = 48 – 37 – 11 = 0;

R_с4,7 = t_р7 – t_р4 – t_4,7 = 51 – 48 – 3 = 0;

R_с6,8 = t_р8 – t_р6 – t_6,8 = 49 – 13 – 7 = 29;

R_с6,9 = t_р9 – t_р6 – t_6,9 = 17 – 13 – 4 = 0;

R_с7,11 = t_р11 – t_р7 – t_7,11 = 63 – 51 – 9 = 3;

R_с9,10 = t_р10 – t_р9 – t_9,10 = 22 – 17 – 5 = 0;

R_с10,12 = t_р12 – t_р10 – t_10,12 = 76 – 22 – 7 = 47.

Свободный резерв времени данной работы не должен превышать полного резерва времени этой же работы.

Расчет коэффициентов напряженности производится по формуле (17).

Для работ критического пути коэффициент напряженности равен единице.

К_н0,1 = К_н1,2 = К_н2,5 = К_н5,8 = К_н8,11 = К_н11,12 = 1.

Для остальных работ:

К_н0,2 = (62 – 56) / (76 – 56) = 0,30;

К_н0,3 = (43 – 13) / (76 – 13) = 0,48;

К_н1,5 = (60 – 48) / (76 – 48) = 0,43;

К_н1,6 = К_н6,8 = (47 – 35) / (76 – 35) = 0,29;

К_н2,3 = К_н3,4 = К_н4,7 = К_н7,11 = (73 – 33) / (76 – 33) = 0,93;

К_н2,4 = (37 – 13) / (76 – 13) = 0,38;

К_н2,7 = (39 – 13) / (76 – 13) = 0,41;

К_н6,9 = К_н9,10 = К_н10,12 = (29 – 8) / (76 – 8) = 0,31.

Для работ, лежащих на одном пути сетевого графика, коэффициенты напряженности одинаковы.

Результаты расчета сведем в таблицу.

Таблица 7

i	i, j	tij	tрi	tпi	tрнij	tроij	tпнij	tпоij	Ri	Rпij	Rcij	Кнij
	0, 1											1,0
—	0, 2		—	—					—			0,30
—	0, 3		—	—					—			0,48
	1, 2											1,0
—	1, 5		—	—					—			0,43
—	1, 6		—	—					—			0,29
	2, 3											0,93
—	2, 4		—	—					—			0,38
—	2, 5		—	—					—			1,0
—	2, 7		—	—					—			0,41
	3, 4											0,93
	4, 7											0,93
	5, 8											1,0
	6, 8											0,29
—	6, 9		—	—					—			0,31
	7, 11											0,93
	8, 11											1,0
	9, 10											0,31
	10, 12											0,31

Окончание табл. 7

	11, 12											1,0
	—	—			—	—	—	—		—	—	—