КРИТИЧЕСКИЙ ПУТЬ В СЕТЕВОМ ПЛАНИРОВАНИИ

Секция «Экономические науки». Подсекция «Математические методы в экономике»

КРИТИЧЕСКИЙ ПУТЬ В СЕТЕВОМ ПЛАНИРОВАНИИ

Баженов Д.В., аспирант

Херсонский национальный технический университет, Украина

Кафедра экономической кибернетики

Знание критического пути важно по двум причинам: оно позволяет (1) выделить из комплекса «угрожающие» работы, наблюдать за ними и форсировать их, (2) ускорить выполнение комплекса привлечением резервов, «скрытых» в некритических работах. Увеличение длительности критической работы приводит к отсрочке завершения комплекса. Задержка с выполнением некритических работ не влияет на завершение комплекса. Форсирование работ не дается даром, а требует вложения денег. Возникает типичная задача исследования операций: какие ресурсы и в какие работы нужно вложить, чтобы время выполнения комплекса не превысило заданной величины, а затраты были минимальны. Другая задача состоит в перераспределении ресурсов: как нужно перераспределить ресурсы, чтобы время выполнения всего комплекса было минимальным? При другом способе задания комплекса работ узлы обозначают «элементарные» работы, стрелки – логические связи между ними. Преимуществом первого способа является то, что его легко приспособить к учету времени выполнения работ и всего комплекса в целом. Преимущество второго способа состоит в том, что легко вносить новые связи, обнаруженные в ходе выполнения работ.

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

Таблица 1

Список элементарных операций

№	Операция	Опирается	Ранг	Операция	№	Операция	Опирается
1	а₁		1	b₁	1	b₁
2	а₂	а₁, a₃	2	b₅	2	b₂
3	а₃		1	b₂	3	b₃
4	а₄	а₁, a₂, а₃	3	b₆	4	b₄
5	а₅		1	b₃	5	b₅	b₁, b₂
6	а₆		1	b₄	6	b₆	b₁, b₂, b₅
7	а₇	а₁, a₄, а₁₀	6	b₁₂	7	b₇	b₁, b₅
8	а₈	а₁, a₂	3	b₇	8	b₈	b₁, b₅
9	а₉	а₃, a₄, а₅	4	b₉	9	b₉	b₂, b₃, b₆
10	а₁₀	а₉	5	b₁₁	10	b₁₀	b₉
11	а₁₁	а₇, a₁₂	7	b₁₅	11	b₁₁	b₉
12	а₁₂	а₁, a₂	3	b₈	12	b₁₂	b₁, b₆, b₁₁
13	а₁₃	а₄, a₅, а₁₀	6	b₁₃	13	b₁₃	b₃, b₆, b₁₁
14	а₁₄	а₃, a₄, а₅	4	b₁₀	14	b₁₄	b₁₁
15	а₁₅	а₁₀	6	b₁₄	15	b₁₅	b₈, b₁₂

В таблице 1 даны четыре операции первого ранга: a₁, a₃, a₅ и a₆. Если операция опирается на операции первого ранга, ее называют операцией второго ранга. После распределения операций по рангам, им приписывают новые номера, начиная с первого ранга. Будем считать операции а₁, а₂, ... упорядоченными. Связи между операциями комплекса отобразим сетевым графиком. Операции изображены дугами, а события, которые состоят в завершении операций и возможности начать новые – вершинами. Вершины сетевого графа обозначаются числами (номерами событий), операции – a₁, a₂, ... Используем список элементарных операций таблицы 2.

Таблица 2

Список элементарных операций

№ п/п	Операция	Опирается	Время t_i
1	а₁		10
2	а₂		5
3	а₃		15
4	а₄	а₁, a₂	18
5	а₅	а₂, a₃	19
6	а₆	а₄	18
7	а₇	а₅, a₆	8
8	а₈	а₅, a₆	25
9	а₉	а₇	30
10	а₁₀	а₈	8

Начальный узел комплекса («начало операций») обозначен 1. Из узла выходят изображающие операции стрелки а₁, а₂ и а₃ в узлы 2, 3 и 4. Совместное выполнение операций а₁ и а₂ изображено 23_, к которому ведут пунктирные стрелки, обозначающие имеющуюся логическую связь. Из 23 идет стрелка а₄, изображающая операцию а₄, опирающаяся на операции а₁ и а₂; в конце стрелки находится узел 5 выполнения операции а₄ и т.д.

Завершающий узел 12 означает конец выполнения всего комплекса операций. На графе не обозначены связи, которые логически вытекают из других; например операция a₈ опирается на операции а₃, а₅ и а₆, а операция a₈ на графе опирается лишь на операции а₅ и а₆.

Если t_i – время начала операции a_i, то T_i=t_i+t_i – время ее окончания (t_i – длительность выполнения операции a_i). Если операция a_i опирается на a_j, a_k и a_l, то ее выполнение не может начаться раньше, чем закончатся операции a_j, a_k и a_l. Это можно записать как

Для операций первого ранга a₁, a₂ и a₃ имеем

, , , и , .

Операция a₄ опирается на a₁, a₂: ее выполнение можно начать в момент t₄, когда закончится выполнение операций a₁ и a₂:

Момент времени окончания операции a₄:

Аналогично для других операций имеем:

и .

Время окончания всех операций

Не все операции влияют на время выполнения комплекса. Среди них есть c суммарной длительностью Т, которые находятся на пути от начального узла 1 до конечного узла n. Эти операции называются критическими, а путь – критическим путем. Выполнение критической операции (1) начинается в момент времени, когда закончатся операции, на которые она опирается, и (2) длится не больше планового времени.

Знание критического пути важно по двум причинам: оно позволяет (1) выделить из комплекса операций наиболее «угрожающие», наблюдать за ними и при необходимости их форсировать; (2) ускорить выполнение комплекса привлечением резервов, «скрытых» в некритических операциях.

Сетевой график содержит критический путь, но может случиться так, что таких путей несколько. Чтобы найти критические операции, нужно знать операцию a_i₁ с максимальным временем окончания T_i₁. Если t_i₁ – время начала выполнения первой критической операции, то оно определяется как максимальное значение моментов времени завершения операций, на которые опирается а_і₁. Поэтому для a_i₂ имеем t_i₁=T_i₂. По определению, операция а_i₂ критическая. И так далее, пока не будет найдена операция a_ik первого ранга, для которой t_ik_-1=t_ik. Цепь указанных операций a_ik, a_ik_-1,..., a_i₁ определит возможный критический путь.

Сетевой граф комплекса операций используется для оптимизации плана выполнения. Улучшение проводят с различными целями. Например, может случиться так, что время выполнения всех операций не удовлетворяет; возникает вопрос об ускорении, при котором время Т не превысит заданной величины Т₀. Для этого нужно ускорить выполнение критических операций, так как уменьшение их продолжительности окажет влияние на время Т. Однако может случиться и так, что критический путь изменится и наиболее слабыми местами со временем станут другие операции.