Модели сетевого планирования и управления

5. МОДЕЛИ СЕТЕВОГО ПАНИРОВАНИЯ И УПРАВЛЕНИЯ

5.1. Сетевая модель и ее основные элементы

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

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

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

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

Главными элементами сетевой модели являются события и работы.

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

Во-вторых, это ожидание – протяженный во времени процесс, не требующий затрат труда (например, процесс сушки после покраски).

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

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

Среди событий сетевой модели выделяют исходное и завершающее события. Исходное событие не имеет предшествующих работ и событий, относящихся к представленному в модели комплексу работ. Завершающее событие не имеет последующих работ и событий.

События на сетевом графике (или, как еще говорят, на графе) изображаются кружками (вершинами графа), а работы – стрелками (ориентированными дугами). Вершины и дуги графа показывают связи между работами и их последовательность. Пример фрагмента сетевого графика представлен на рис. 5.1.

Рисунок 5.1 – Фрагмента сетевого графика

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

5.2. Правила построения сетевого графика

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

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

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

2.     В сетевом графике не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа.

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

4.     Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой.

5.     В сети рекомендуется иметь одно исходное и одно завершающее событие.

5.3. Временные параметры сетевых графиков

Одно из важнейших понятий сетевого графика – понятие пути.

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

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

В таблице 5.1 приведены основные временные параметры сетевых графиков.

Рассмотрим содержание и расчет указанных параметров.

Таблица 5.1 – Основные временные параметры сетевых графиков

Начнем с параметров событий. Ранний (или ожидаемый) срок свершения i-го события – это самый ранний момент времени, к которому завершаются все предшествующие этому событию работы. Счёт времени будем вести от момента наступления начального события. Для удобства расчётов, полагаем, что ранний срок свершения исходного (1-го) события равен нулю (т.е. ). Ранний срок любого последующего события (j-го) определяется продолжительностью самого длительного из предшествующих путей. Отсюда, для определения ранних сроков свершения событий имеем рекуррентное соотношение:

.                                                        (5.1)

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

.                                                          (5.2)

Разность между поздним и ранним сроками свершения события составляет резерв времени i-го события:

.                                                                      (5.3)

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

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

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

Теперь перейдем к параметрам работ.

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

Очевидно, что ранний срок начала работы (i,j) совпадает с ранним сроком наступления начального (предшествующего) события i, т.е.

.                                                                                     (5.4)

Тогда ранний срок окончания работы (i,j) определяется по формуле

.                                                                      (5.5)

Ни одна работа не может окончиться позже допустимого позднего срока своего конечного события i. Поэтому поздний срок окончания работы (i,j) совпадает с поздним сроком свершения её конечного события:

,                                                                      (5.6)

а поздний срок начала этой работы равен разности между поздним сроком свершения её конечного события и продолжительностью:

.                                                         (5.7)

Таким образом, в рамках сетевой модели моменты начала и окончания работы тесно связаны с соседними событиями ограничениями (5.4) – (5.7).

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

.                                                                       (5.8)

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

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

Полный резерв времени работы (i,j) показывает на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв  определяется по формуле

.                                                         (5.9)

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

Свободный резерв времени – это запас времени, которым можно располагать при выполнении данной работы при условии, что начальное и конечное  её событие наступят в свои ранние сроки:

.                                                         (5.10)