2. СЕТЕВОЙ ГРАФИК КОМПЛЕКСА РАБОТ. ВРЕМЕННОЙ СЕТЕВОЙ ГРАФИК

Предположим, что нам задана упорядоченная структурная таблица комплекса работ, например, табл. 2.1.

Таблица 2.1

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

Этот график можно строить по-разному. Чаще всего изображают работы, входящие в комплекс, стрелками, а события, состоящие в выполнении каких-то работ и возможности начать новые работы — кружками или «узлами».

Для примера изобразим в виде сетевого графика структуру табл. 2.1 (рис. 10.1). Узлы будем обозначать работы

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

Рис. 10.1

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

Как уже было сказано, существуют разные формы сетевых графиков (см., например, [17]). В одних стрелками графа обозначаются работы, а узлами — события, состоящие в выполнении одной или нескольких работ; в других — узлами обозначаются работы, а стрелками — логические связи между ними. Структурную табл. 2.1 можно изобразить графически и по этому, второму способу (см. рис. 10.2). На этом рисунке жирной линией обведены кружки ад, изображающие последние работы комплекса, на которые не опираются уже никакие дальнейшие работы.

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

Поэтому мы будем пользоваться первым способом.

Таблица 2.2

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

Рис. 10.2

Получится таблица вида табл. 2.2, в которой структурные связи — те же, что в табл. 2.1 и на графиках рис. 10.1, 10.2 (устранены только «лишние» связи), но в правом столбце указаны времена выполнения отдельных работ, выраженные в любых единицах времени (часы, недели, месяцы). Такую таблицу мы будем называть структурно-временной.

Временною структуру комплекса работ, вместе с логической структурой, можно изобразить на одном и том же графике, который мы будем называть временным сетевым графиком. Мы будем его строить следующим образом. График ориентируется вдоль оси времени на которой в каком-то масштабе откладываются времена выполнения работ. Как и на графике рис. 10.1, стрелками изображаются работы, но длина каждой стрелки не произвольна, а такова, что ее проекция на ось абсцисс 0 равна времени выполнения данной работы. Логические связи между работами по-прежнему обозначаются пунктирными стрелками, не означающими никакой реальной работы (иногда их толкуют как «фиктивные» работы).

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

Временной сетевой график для комплекса работ, заданного в табл. 2.2, показан на рис. 10.3. При построении временнбго сетевого графика расположение узлов по вертикали (по оси ординат) берется произвольным, абсцисса же каждого узла равна времени окончания соответствующей работы. Длина каждой стрелки считается от центра до центра кружка.

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

Рис. 10.3

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

Стрелка опирающаяся на должна начаться в узле имеющем наибольшую абсциссу из узел соединяем с пунктирной стрелкой. Узел которым заканчивается стрелка имеет абсциссу

Стрелка начинается в узле и кончается в узле с абсциссой Стрелка опирающаяся на должна начинаться от узла имеющего, по сравнению с большую абсциссу; из направляем пунктирную стрелку. Стрелка а, кончается в узле с абсциссой Стрелка начинается в том же узле с абсциссой Те — 46 и кончается в узле с абсциссой Стрелка ад с проекцией начинается в узле и кончается в узле с абсциссой Стрелка опирающаяся на , начинается в узле и кончается в узле с абсциссой

Так как работа завершается последней, то узел означает окончание всего комплекса работ; отметим этот узел жирным кружком и соединим с ним пунктирной стрелкой узел — окончание предыдущей работы на которую, кроме конца работ, ничто не опирается.

Таким образом, временной сетевой график комплекса работ построен.

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

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

Работы из длительностей которых составлено время Т, называются критическими работами, а цепочка соответствующих им стрелок на сетевом графике — критическим путем. На рис. 10.3 критический путь показан двойными стрелками.

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

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

Назовем «некритической дугой» совокупность некритических работ и узлов, начинающуюся и кончающуюся на критическом пути (принимая во внимание и пунктирные стрелки). На рис. 10.3 имеются четыре некритических дуги:

На первой из этих дуг лежит одна некритическая работа на второй — две некритические работы на третьей — две некритические работы на четвертой — две некритические работы

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

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

На второй некритической дуге лежат две некритические работы на замыкающем участке критического пути — три критические работы Значит, общий резерв времени, приходящийся на работы равен:

Его можно любым образом распределить между работами

На третьей некритической дуге резерв равен:

Так как нам уже известно, что с работой мы можем запоздать не более чем на 5 единиц времени, а с работой — не более чем на 12, то требование, чтобы сумма опозданий была не более 22, не говорит нам ничего нового.

На четвертой некритической дуге имеется резерв

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

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

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

Решение. Сетевой график комплекса дан на рис. 10.4 Критический путь обозначен двойными стрелками и состоит из работ:

Таблица 2.3

Рис. 10.4

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

при этом время Т окончания комплекса работ по обоим критическим путям будет одно и то же:

Кроме этих двух на графике (рис. 10.4) могут быть обнаружены еще некоторые критические пути; предоставляем читателю найти их самостоятельно. Выделяем на сетевом графике (рис. 10.4) четыре некритические дуги:

На каждой из этих дуг имеется по одной некритической работе: Резервы времени для них равны соответственно:

Некритическая дуга в наших условиях не дает новых данных о резервах времени.