pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

В некоторых случаях ошибки, допущенные при установлении логи­ ческой связи между работами, приводят к образованию контура. Это такая последовательность работ, в том числе и фиктивных, когда при прохожде­ нии их на сетевом графике в направлении стрелок начальный и конечный узлы совпадают. На рис. 7.3, в контур образуют работы д3, а4 и а5. Наличие контура означает, что некоторая работа следует после самой себя, поэтому контуры подлежат обнаружению, после чего структурная таблица пере­ сматривается с целью их исключения.

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

Рассмотрим на сетевом графике различные пути, двигаясь по кото­ рым, можно пройти из начального узла 0 в конечный узел К. Например, некоторые из таких путей для сетевого графика, изображенного на рис. 7.3, б, проходят через следующие события и работы:

1)0 — а3— 3 — а4— 4 — а4_2— 2 — а6— 6;

2)0 — а7— 7 — а.\ — 1— ci\-9 — 9 — ci2— 2 — Дб — 6; 3)0 — U\\ — 11 — cig— 9 — #2 — 2 — а6— 6.

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

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

Рис.7.4. Сетевой график с выделенным критическим путем

На этом графике всего четыре возможных пути. Они проходят через узлы: 0 - 1 - 5 ; 0 - 2 ---- 5; 0 - 2 - 4 -5 ; 0 - 3 - 4 -5 . Наиболее длинным по продолжительности, то есть критическим, путем является путь 0 - 2 - 4 - 5. Его продолжительность равна сумме длительностей работ я2>^6 и а% и

составляет 5 + 7 + 1 = 13. Это и будет минимально возможным временем выполнения всего проекта.

Работы, входящие в состав критического пути, также называют критическими. В данном случае это работы а2, ав и а%. Особенность крити­ ческих работ заключается в том, что задержка на некоторый промежуток времени в выполнении любой из них обязательно приводит к увеличению продолжительности выполнения всего мероприятия на тот же промежуток времени. Поэтому основное внимание руководителя должно быть привле­ чено именно к выполнению критических работ. В этом и состоит смысл выделения критического пути на сетевом графике.

Работы, не находящиеся на критическом пути, называются некри­ тическими. В отличие от критических работ, некоторая задержка с их вы­ полнением не приводит к увеличению продолжительности выполнения всего проекта. Для некритических работ можно определить резервы вре­ мени, т. е. максимально допустимое время их задержки, которое еще не скажется на сроке окончания всего мероприятия.

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

7.2.2. Графоаналитический метод отыскания

критического пути

Этот метод позволяет решить задачу непосредственно с помощью сетевого графика, но в этом случае необходимо уже при его построении определенным образом учесть известные продолжительности работ. Такой модернизированный сетевой график будем называть временным сетевым графиком [7] и строить его следующим образом. Сначала проводится ось абсцисс, на которой выбирается определенный масштаб времени в соот­ ветствии с единицами времени, в которых измеряется продолжительность выполнения работ комплекса. В начале координат располагается исходный узел 0. Длина стрелки, изображающей любую работу комплекса, и угол ее наклона к оси абсцисс выбирается так, чтобы величина ее проекции на эту ось была равна продолжительности данной работы (в выбранном мас­ штабе). Очевидно, что при таком способе, как и для обычного сетевого графика, всегда существует сколько угодно вариантов изображения любой конкретной работы. Например, на рис. 7.5, а показаны три возможных ва­ рианта изображения одной и той же работы продолжительностью 4 единицы.

Пусть теперь некоторая работа а6 опирается на работы а2, аз и я4, которые уже построены на временном сетевом графике (рис. 7.5, б). Для

построения работы а6 найдем среди последних трех работ ту, которая за­ вершается позже остальных. В данном случае это работа а3. Тогда стрелка, изображающая работу д6, должна выходить из узла 3, символизирующего окончание работы д3, а узлы 2 и 4 соединяются с узлом 3 пунктирными стрелками. Аналогичным образом выбирается конечный узел К. Он будет совпадать с узлом, которым оканчивается работа с наиболее поздним мо­ ментом завершения.

Рассмотрим пример построения временного сетевого графика. Пусть дана структурная таблица, в которой наряду с указанием последова­ тельности выполнения работ приведена и продолжительность каждой из них (табл. 7.6). Предварительно работы комплекса уже упорядочены в со­ ответствии с найденными для них рангами, и эти упорядоченные работы обозначены здесь яь д2,.. а\2.

Т а б л и ц а 7.6

Номер	Работа	Продолжи­	Опирается	Номер	Работа	Продолжи­	Опирается
п/п		тельность	на работы	п/п		тельность	на работы
1	а\	6	_	7	а7	4	Д4, Дб
2	а2	5	-	8	Д8	7	аА
3	а3	3	-	9	а9	7	а5, ап
4	я4	4	аъ	10	а\о	4	а7
5	Я5	9	Дь Д2	11	а\\	10	as, «8, Лю
6	ав	2	а и а2	12	а Х2	6	Я9, а\\

Временной сетевой график, построенный по данным этой таблицы в соответствии с сформулированными выше правилами, изображен на рис. 7.5, в. Последовательность построения соответствует нумерации работ. Из исходного узла 0 проводят стрелки, соответствующие каждой из работ 1-го ранга - в данном случае это работы а2, ДзСтрелки строят в соответст­ вии с указанным выше правилом. Так, проекция стрелки, изображающей работу <2i, на ось Оt должна быть равна t\ = 6. Работа я4опирается на работу д3, поэтому изображающая ее стрелка выходит из узла 3. Работа а5 соглас­ но табл. 7.6 опирается на работы ахи а2у причем работа а\ заканчивается позже, чем а2. Поэтому стрелка а5выходит из узла 1, а узел 2 соединяется с ним пунктирной стрелкой. Далее процесс построения временного сетевого графика продолжается аналогичным образом.

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

234

в

Рис. 7.5. Временные сетевые графики:

а - варианты изображения одной и той же работы; б - фрагмент временного сетевого графика; в - временной сетевой график, соответствующий табл. 7.6

Выясним теперь, по каким стрелкам - сплошным, а не пунктир­ ным - можно пройти от исходного узла 0 до конечного узла 12. В данном случае это будет путь, состоящий из следующих работ: аи ав9 al9 а]0, аи, а]2 (см. рис. 7.5, в), он выделен двойными стрелками. Построенный маршрут и будет критическим путем, а перечисленные выше работы, входящие в его состав, - критическими работами. Все остальные работы будут некритиче­ скими. Резервы времени для них также можно найти с помощью времен­ ного сетевого графика. Рассмотрим с этой целью участки маршрутов, со­ стоящие только из некритических работ, в том числе и фиктивных, начи­ нающиеся и заканчивающиеся в узлах на критическом пути. Их называют

некритическими дугами. Таких дуг на рис. 7.5, в семь:

1)0 — 0.2 — 2 — &2 - 1— 1;

2)0 — аъ— 3 — аА— 4 — д4_6— 6;

3)0 — б?з — 3 — — 4 — cig— 8 — ag_ ю — 10;

235

4)1 — а5— 5 — tf5-io— 10;

5)1 — a5— 5 — ад — 9 — а9_ц — 11;

6)7 — д7_5 — 5 — ад — 9 — Я9_ц — 11;

7)7 — я7-5 — 5 — <35_ю — Ю.

Для каждой из критических дуг вычислим теперь две суммы:

1)сумму продолжительностей находящихся на ней некритических работ, помня, что длительности фиктивных работ равны нулю;

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

Рассмотрим первую из некритических дуг. На ней находятся одна некритическая работа а2 и одна фиктивная работа а2. ь а между узлами 0 и 1 на критическом пути лежит только одна критическая работа а\. Поэтому

упомянутая разность равна R2 = t\ - 12 - 6 - 5 = 1. Это и есть резерв време­ ни для работы а2\ ее продолжительность можно увеличить на 1, не отодви­ гая сроков выполнения всех критических работ. Для второй некритической дуги резерв составит R3>4= t\+ te - (t3+ U) = (6 + 2) - (3 + 4) = 1.

Следовательно, выполнение обеих работ, а3 и а4, может быть за­ держано в сумме не более, чем на 1. Аналогично, для третьей дуги: ^з,4,8 = (U + h + h + *ю) - (h + U + h) = 16 -1 4 = 2, т. e. общий резерв для работ д3, а4 и ag равен 2. Резервы для остальных дуг равны: R5= /6+ Ь + fio- = 1 - приходится на работу а$; R5$ = t6 + t7 + t\o + tu - (t5 + tg) = 4 - это время можно распределить между работами а5 и а9 с учетом предыдущего равенства, R5 = 1. Для шестой дуги имеем Rg = Г]0 + tu - tg = 7. Последнее равенство новой информации не приносит, так как предыдущее требование R5 9 = 4 является более жестким. То же самое можно сказать о последней

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

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

Отметим, что сетевой график может иметь не один, а несколько критических путей. Если бы, например, продолжительность работы а4 в предыдущем примере была на единицу больше, то наряду с рассмотрен­ ным существовал бы и второй критический путь, проходящий через узлы

0,3,4, 6, 7, 10, 11, 12.

7.2.3. Алгоритм отыскания критического пути

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

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

Обозначим через Р? наиболее ранний возможный срок начала /-й работы. Это срок, необходимый для выполнения всех работ, предшест­ вующих данной. Через Р? обозначим наиболее ранний срок ее окончания. Очевидно, что

Р? = />?+*„

(7.2)

где и - известная продолжительность /-й работы.

Первая часть алгоритма состоит в последовательном определении ранних сроков начала и окончания каждой из работ комплекса, начиная с а\. Для нее, как и для всех работ 1-го ранга, ранний срок начала полагают равным нулю. Сразу же после того, как для какой-либо работы определен ранний срок начала, по формуле (7.2) вычисляют ранний срок ее окончания.

Если некоторая работа ак опирается только на одну работу ар то

ранний срок ее начала равен раннему сроку окончанияj- й работы:
Р > Р у	(7.3)
Пусть теперь работа атопирается на две или более работ	я,-,... .

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

?т =шах ...}. (7.4)

Перебирая работы в порядке возрастания их номеров, определяем с помощью приведенных формул ранние сроки их начала и окончания. Мак­ симальный из сроков окончания всех работ будет равен сроку Т заверше­ ния проекта в целом.

Например, дана упорядоченная структурная таблица работ с указа­ нием их продолжительности (табл. 7.7).

Работам аи а2, аъ никакие работы не предшествуют, следовательно, ранний срок начала каждой из них принимаем равным нулю: =

= Р" = О, а сроки их окончания вычисляем по формуле (7.2):

237

ро = / >н+Г] = 3; po = p n + t 2 = 5; Р ° = Р « + / 3 = 2 .

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

Работа опирается на работы а2, а3, поэтому согласно уравнению (7.4) ранний срок ее начала должен быть равен максимальному из ранних сроков окончания работ а2 и я3, то есть

	Рабо­	Продол­
Но­	та	житель­
мер		ность
п/п		U
	Я/
1	2	3
1	tfi	3
2	а2	5
3	аз	2
4	а4	4
5	as	3
6	аь	7
7	а7	6
8	а%	1

Р ” =шах{Р°2, Р 30} = шах{5,2} = 5.						(7.5)
					Т а б л и ц а 7.7
	Ранний срок		Поздний срок		Полный	Свобод­
Опирает­	начала	окон­	начала	окон­	резерв	ный ре­
ся на рабо­		чания		чания	време­	зерв
ты	Р?	Р,°		П?	ни	времени
			п Г		Rf	Rf
4	5	6	1	8	9	10
-	0	3	2	5	2	0
-	0*—		0	5	0	0
-	0 /	2	3	5	3	3
аз,а2	5^— -^9		5	9	0	0
а и а2	3	/ 6	5	8	2	0
а5	6/	13	8	15	2	2
С1\, 04, #5	9*—> 15		9	15	0	0
#6, <37	1 5 ^ - 1 6		15	16	0	0

Ранний срок окончания работы а4 вычислим по формуле (7.2):

P ° = P » + t 4 = 5+ 4 = 9.

Поскольку работа д5опирается на работы яi и я3, имеем

Р" =max{P° ,Р 3} = max {3,2} = 3.	(7.6)
Срок ее окончания равен
P ° = P » + t 5 = 3 + 3 = 6.
Работа ав опирается только на а5. Следовательно, ранний срок нача­
ла работы а6 равен раннему сроку окончания работы а5 -	см. (7.3), то есть

Р1 =Р°5 = 6; Р% = P g +r 6= 6 + 7 = 13.

Работа aj опирается на три работы: а\, а4, а5, поэтому Р^ = max { Р ?, PJ, Р§} = max { 3, 9, 6 } = 9;

Р? =Р? + /7=9 + 6 = 15;

238

Р$ = max { Р°в,Р 7 } = max { 13, 15 } = 15;

Р% —Pg + tg= 15 + 1 = 16.

Отыскиваем в графе 6 табл. 7.7 максимальное число - это макси­ мальный из всех ранних сроков окончания работ. В данном случае он равен 16 и относится к работе а8. Поэтому срок завершения всего проекта равен Т= 16.

Второй этап состоит в определении критических работ. С этой це­ лью графы 5 и 6 табл. 7.7 просматривают снизу вверх. Прежде всего счи­ тают критической ту работу, ранний срок окончания которой равен сроку завершения всего проекта. В данном примере это работа а&. Из графы 5 определяют ранний срок ее начала Р$ = 15, а из графы 4 - работы, на кото­ рые она опирается: д6 и а7. В графе 6 среди чисел в соответствующих им строках 6 и 7 отыскивают то, которое совпадает с ранним сроком начала критической работы а%. Это число 15, относящееся к работе я7. Поэтому она тоже будет критической. Стрелки в табл. 7.7 указывают последова­ тельность обращения к числам в графах 5 и 6. Работа д7опирается на рабо­ ты дь а4, а5, а ранний срок ее начала равен 9. Среди строк 1, 4, 5 в графе 6 число 9 находится в четвертой строке, т. е. относится к четвертой работе. Это, следовательно, еще одна критическая работа. Действуя аналогичным образом, находим последнюю критическую работу а2. Таким образом, кри­ тическими являются работы а2, я4, я7, а8. Их суммарная продолжитель­ ность равна продолжительности критического пути.

Третий этап алгоритма состоит в последовательном определении поздних сроков начала и окончания работ. Это предельные сроки, при ко­ торых выполнение всех последующих работ за отведенное им время еще позволит завершить все мероприятие за время Г, равное сроку его выполнения.

Обозначим поздние сроки начала и окончания /-й работы через Щ и Ilf соответственно. Аналогично формуле (7.2) имеем

’

(7.7)

Расчет поздних сроков начала и окончания работ ведется от конца к началу. При этом заполняют графы 7 и 8 табл. 7.7, двигаясь снизу вверх. Вначале, анализируя графы 2 и 4, отыскивают завершающие работы - это те, на которые ни одна работа комплекса не опирается. Поздний срок окончания завершающих работ полагают равным сроку Т завершения все­ го проекта. Затем по формуле (7.7) для каждой из завершающих работ оп­ ределяют поздний срок ее начала.

В данном случае завершающей будет единственная работа - а%. Для нее, следовательно, Я 8Н= Т = 16. По формуле (7.7) найдем поздний срок ее начала:

Я 8Н= Я 8° - t 8 = 16 - 1 = 15.

239

Далее последовательно переходят к работам с меньшими номерами. Пусть предстоит определить поздний срок окончания работы я,. Если на нее опирается единственная работа aKi то поздний срок окончания работы <3/ равен позднему сроку начала работы ак\

Щ = Щ .

(7.8)

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

вы &т>‘'ч т. е.

77° = min { Л ”, 1 7 % (7.9)

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

Из данных, содержащихся в графе 4 табл. 7.7, видно, что на работу a-i опирается единственная работа а%. Поэтому согласно формуле (7.8)

#7 = Щ = 15. Поздний срок начала этой работы вычислим по формуле

(7.7): Щ = Щ - Г 7= 15 -6 = 9.

На работу я6, как видно из табл. 7.7, также опирается только одна работа as, следовательно,

Я6° = Я 8Н= 15;

Щ= Щ - te = 1 5 -7 = 8.

На работу а5, опираются уже две работы: аь и аъ Поэтому поздний срок ее окончания определяем по формуле (7.9):

Щ = min {Л 6Н, Щ } = min {8, 9} = 8;

Щ = Щ - г 5 = 8 - 3 = 5.

Аналогичные вычисления позволяют найти поздние сроки оконча­ ния и начала всех остальных работ:

Я 4° = Я 7н = 9;

Щ = Щ - и = 9 - 4 = 5;

Я3° = min {#4 , Щ) = min {5, 5} = 5;

Я3Н= Я 30 - / з = 5 - 2 = 3;

240

Щ= Щ = 5;

Щ= Щ - 1 2 = 5 - 5 = 0;

П° = min {# 5Н, Я 7Н}= min {5, 9} = 5;

Щ = Щ - Ь = 5 - 3 = 2 .

Последний этап - расчет резервов времени некритических работ. Для них различают полный и свободный резервы времени.

Полный резерв времени /-й работы R" - это максимальное время, на которое можно задержать ее начало или увеличить продолжительность выполнения работы, не изменяя срока завершения всего проекта. Его вы­ числяют как разность между поздним и ранним сроками окончания данной работы:

Д,п= Я ° -/> 0.

(7.10)

Значения полного резерва времени работ для рассматриваемого примера приведены в графе 9 табл. 7.7. Для их вычисления достаточно в каждой строке вычесть из числа, стоящего в графе 8, число, находящееся в графе 6. Например,

Я ? = Л ? - Р ° = 5 - 3 = 2.

Свободный резерв времени z-й работы Rf является частью ее полного резерва. Это запас времени, на который можно отсрочить ее нача­ ло или увеличить продолжительность выполнения работы при условии, что она начинается в свой ранний срок и ранние сроки начала последую­ щих работ не изменяются. Для вычисления свободного резерва времени любой работы, не являющейся завершающей, отыскивают ближайшую из работ комплекса, опирающуюся на данную, и определяют ранний срок ее начала. Из этого числа вычитают ранний срок окончания данной работы. Например, из данных графы 4 видно, что для работы а\ из числа опираю­ щихся на нее работ ближайшей, имеющей наименьший Рн, является рабо­ та а5. Поэтому свободный резерв времени работы ахравен разности между ранним сроком начала 5-й работы и ранним сроком окончания 1-й работы:

R\=P*b - P \ = 3 - 3 = 0 .

Для завершающих работ в качестве уменьшаемого в этой разности берут срок Т окончания всего проекта. Так, Р \ = Т - Р\ = 16 - 16 = 0.

Величины свободного резерва времени работ приведены в десятой графе табл. 7.7.