3.5.5. Метод критического пути в управлении

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

Тогда управление проектом в заданные сроки и при заданных ресурсах позволит:

• координировать исполнение работ всеми соисполнителями;

• предвидеть возможные задержки каждой работы и проекта в целом;

• устанавливать последовательность и сроки использования ограниченных ресурсов;

• анализировать компромиссные решения по затратам и срокам исполнения.

Для управления такими проектами были разработаны метод сетевого планирования и управления (СПУ) и метод критического пути (МКП).

Ориентированный граф является единственным средством для анализа проектов, требующих выполнения большого числа взаимосвязанных операций (работ). Такой граф имеет одну вершину-исток, которая представляет начало работ по всему проекту, и одну вершину-сток, которая представляет окончание всего проекта.

Между вершинами истоком и стоком есть множество вершин-событий, фиксирующих начало и/или окончание работы или комплекса работ t(i), а множество дуг, связывающих вершины-события, есть работы. Длина дуги-работы характеризует затраты временных или иных ресурсов (i, j).Комплекс работ отображается на графе несколькими заходящими или исходящими дугами для одной вершины-события. Но это не мультиграф, т. к. каждая дуга имеет независимую вершину-исток или вершину-сток. В графе не должно быть петель и контуров. Если две или несколько работ должны начинаться одновременно, но привязаны к различным вершинам-истокам, то между этими вершинами должно быть отмечено ожидание. Чаще всего эти вершины соединяют пунктирной линией, отмечая как бы фиктивную работу.

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

Рассмотрим фрагмент сети (см. рис. 3.32), включающий в себя пять вершин-событий и шесть дуг-работ: вершина-исток – x₀ – есть начало работ по проекту в момент времени t₀, вершина-сток - х_k – есть окончание работ по проекту в момент времени t_k, дуги-работы - ₀₁ и ₀₂ – имеют начало в момент t₀. Вершина-событие х₁ есть окончание одной работы ₀₁ в момент времени t₁=t₀+₀₁ и формирует начало комплекса работ ₁₂ и ₁₃. Вершина-событие х₂ есть окончание работ ₀₂ и ₁₂ в моменты времени t₂’=t₀+₀₂ и t₂”=t₁+₁₂. Работа - _2k не может начаться пока не будут окончены работы ₀₂ и ₁₂. Поэтому начало работы _2k можно определить по значению t₂=max{t₂’, t₂”}.

При наличии нескольких дуг-работ, заходящих в вершину-событие следует определять для каждого события сети ранний момент его наступления t^p(x_i), как наиболее позднее окончание предшествующих работ, т. е. t^p(x_i)=max{(t^p(x_j)+_i,j)}.

Вершина-событие х₃ есть окончание работы ₁₃ в момент времени t₃=t₁+₁₃ и определяет возможность начать работы _3k. Так как работы _2k и _3k должна начаться одновременно (см. пунктирную линию), то следует найти максимальное значение времени ожидания t_ожид.=max{t₂, t₃}.

Работы _2k и _3k обеспечивают завершение проекта к моменту времени t_k=max{t_ожид.+_2k, t_ожид.+_3k}.

Следовательно, наибольшая продолжительность работ по проекту есть максимальное значение t_k.

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

При наличии нескольких дуг-работ, исходящих из вершины-события следует определять для каждого события сети поздний момент его наступления t^п(x_i), как наименьшее раннее окончание последующих работ, т. е. t^п(x_i)=min{(t^п(x_j)-_i,j)}.

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

Для событий, связанных с ожиданием ранний и поздний моменты времени расчитываются по формулам:

t^p_ожид^.(х_i;х_j)=max{t^p(х_i); t^p(х_j)}, tⁿ_ожид^.(х_i;х_j)=min{tⁿ(х_i); tⁿ(х_j)}.

Максимально время, на которое можно задержать наступление некоторого события без задержки срока завершения всего проекта, называют резервом времени события, т. е. t⁰(х_i)=(tⁿ(х_i)-t^p(х_i)).

Максимально время, на которое можно продлить исполнение работы без задержки срока завершения всего проекта, называют резервом времени на работу, т. е. ⁰_i,j=(tⁿ(х_j)- t^p(х_i)-_i,j).

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

t⁰(x_i)=0,

⁰_i,j=(tⁿ(х_j)-t^p(х_i)-_i,j)=0.

Для компактного графического изображения всех показателей каждого события каждую вершину-событие представим в виде круга, разбитого на четыре сектора. В каждом секторе указаны четыре показателя: индекс вершины (i), ранний момент события t^p(x_i), поздний момент события tⁿ(x_i) и резерв времени на событие t⁰(x_i). Дуги графа изображают работы, а пунктирная линия – фиктивную работу - ожидание.

Для иллюстрации возможностей сетевого управления работами по проекту рассмотрим сетевую модель (см. рис. 3.33).

Алгоритм расчета раннего момента наступления событий:

шаг 1: принять для начальной вершины графа t^p(0)=0 и p=0, где p-шаг итерации;

pi	i	j=hi	t^p(j)={(t^p(i)+(i, j))}	t^p(j)=maxi{(t^p(i)+(i, j))}
0	0	1	t^p(1)=t^p(0)+(0, 1)=3	t^p(1)=3
		2	t^p(2)=t^p(0)+(0, 2)=2
1	1	2	t^p(2)=t^p(1)+(0, 2)=8	t^p(2)=8
		3	t^p(3)=t^p(1)+(1, 3)=5	t^p(3)=5
		5	t^p(5)=t^p(1)+(1, 5)=10
2	2	4	t^p(4)=t^p(2)+(2, 4)=18
3	3	5	t^p(5)=t^p(3)+(3, 5)=13	t^p(4)=t^p(5)=18
4	4	6	t^p(6)=t^p(4)+(4, 6)=20
		7	t^p(7)=t^p(4)+(4, 7)=22	t^p(7)=22
5	5	6	t^p(6)=t^p(5)+(4, 6)=22	t^p(6)=22
		k	t^p(k)=t^p(5)+(5, k)=24
6	6	k	t^p(k)=t^p(6)+(6, k)=27
7	7	k	t^p(k)=t^p(7)+(7, k)=23	t^p(k)=27

шаг 2: определить на шаге итерации p ранний момент наступления события j по формуле: t^p(j)=(t^p(i)+(j, i)), где t^p(i) - события i с известным ранним моментом наступления; (j, i) –продолжи- тельность работы (i, j) от события, имеющего t^p(i);

а) если к вершине j подходит одна дуга (i, j), то принять t^p(j)=(t^p(i)+(j, i)),

б) если к вершине j подходит несколько дуг {(i, j)}, то сравнить и найти максимальное значение раннего момента наступления события j по формуле: t^p(j)=max_i{(t^p(i)+(i, j))}.

шаг 3: если p=(n-1), то конец, иначе принять p=(p+1) и перейти к шагу 2 алгоритма.

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

Алгоритм расчета позднего момента наступления события:

шаг 1: принять для конечной вершины графа tⁿ(k)=t^p(k) и р=0, где р-шаг итерации;

шаг 2: определить на шаге итерации р поздний момент наступления события j по формуле: tⁿ(j)=(tⁿ(i)-(j, i)), где tⁿ(i)-событие i с известным поздним моментом наступления; (j, i) –продолжитель- ность работы (i, j) от события, имеющего tⁿ(i);

а) если от вершины j отходит одна дуга (i, j), то принять tⁿ(j)=(tⁿ(i)-(j, i);

б) если от вершины j отходит несколько дуг (i, j), то сравнить и найти минимальное значение позднего момента наступления события j по формуле: tⁿ(j)=min_i{(tⁿ(i)-(j, i))};

шаг 3: если р=(n-1), то конец, иначе принять р=(р+1) и перейти к шагу 2 алгоритма.

Результаты вычисления представлены таблицей.

pi	i	j=hi^-1	t^n(j)=(t^n(i)-(j, i))	t^n(j)=mini{(t^n(i)-(j, i))}
0	k	7	t^n(7)=(t^n(k)-(k, 7))=26	t^n(7)=26
		6	t^n(6)=(t^n(k)-(k, 6))=22	t^n(6)=22
		5	t^n(5)=(t^n(k)-(k, 5))=21
1	7	4	t^n(4)=(t^n(7)-(4, 7))=22
2	6	5	t^n(5)=(t^n(6)-(5, 6))=18
		4	t^n(4)=(t^n(6)-(4, 6))=20	t^n(5)=t^n(4)=18
3	5	3	t^n(3)=(t^n(5)-(3, 5))=10	t^n(3)=10
		1	t^n(1)=(t^n(5)-(1, 5))=11
4	4	2	t^n(2)=(tn(4)-(2, 4))=8	t^n(2)=8
5	3	1	t^n(1)=(t^n(3)-(1, 3))=8
6	2	1	t^n(1)=(t^n(2)-(1, 2))=3	t^n(1)=3
		0	t^n(0)=(t^n(2)-(0, 2))=6
7	1	0	t^n(0)=(t^n(1)-(0, 1))=0	t^n(0)=0

Алгоритм расчета резерва времени события:

шаг 1: принять р=0, где р-шаг итерации;

шаг 2: определить на шаге итерации р индекс события i и резерв его ожидания по формуле: t⁰(i)=(tⁿ(i)-t^p(i));

шаг 3: если р=(n-1), то конец, иначе принять р=(р+1) и перейти к шагу 2.

pi	0	1	2	3	4	5	6	7	8
i	0	1	2	3	4	5	6	7	k
t^0(i)	0	0	0	5	0	0	0	4	0

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

Алгоритм расчета резерва времени на работу:

шаг 1: принять р=0 и выделить любую дугу (i,j);

шаг 2: определить резерв времени для работы (i,j) по формуле _i,j^0.=(tⁿ(j)- t^p(i)-_j,i);

шаг 3: если р=m, где m-число дуг, то конец, иначе р=(р+1), выделить новую дугу (i,j) и перейти к шагу 2 алгоритма.

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

pi	(i,j)	i,j^0		pi	(i,j)	i,j^0
1	(0, 1)	0		7	(3, 5)	5
2	(0, 2)	6		8	(4, 6)	2
3	(1, 2)	0		9	(4, 7)	4
4	(1, 3)	5		10	(5, 6)	0
5	(1, 5)	8		11	(5, k)	3
6	(2, 4)	0		12	(6, k)	0
				13	(7, k)	4

Произведенный анализ показывает, что

• события 1, 2, 4, 5, 6, имеют резерв времени равный нулю; cледовательно, они принадлежат критическому пути;

• работы (0, 1); (1, 2); (2, 4); (5, 6); (6, k) имеют резерв времени равный нулю; cледовательно, они также принадлежат критическому пути;

• события 3 и 7 имеют резерв времени, что позволяет ослабить внимание на исполнение работ ₁₃, ₃₅, ₄₇, _7k или уменьшить затраты на исполнение этих работ, но не более указанных резервов;

• работы (0;2); (1;5); (4;6); (5;k) имеют резерв времени, что позволяет продлить исполнение этих работ или уменьшить затраты ресурсов, но не более указанных резервов.

Выполненные расчеты представлены на рис. 3.33. Там же показан полужирной линией критический путь, соединяющий события, имеющие нулевой резерв времени, дугами-работами, также имеющими нулевой резерв времени.