11.13. задачи сетевого планирования

11.13. задачи сетевого планирования

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

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

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

При построении графа каждую операцию изображают в виде ориентированной дуги. Связи между операциями также представляются в виде дуги. Д|усу;вдшшз конца дуги, соответствующей предшествующей операции, в начало следующей ОПС' рации. Чтобы отличить операции от связей, операции изображают сплошными линиями, а связи — пунктирами. Вершины графа называют событиями. Временем наступления события считают время, когда завершено выполнение всех операций, входящих в соответствующую вершину.

Граф, представляющий взаимосвязь отдельных работ проекта, называется сетевым графиком. На рис. Но2§роен сетевой график для комплекса операций, задаваемых табл. 11.1.

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

О Пример. На рис. 11.24 изображены сеть G и упрощенная сеть (?!. При упрощении выброшены дуги a, ft, у. Последователь

5Яг

ность выполнения работ при ЭТОМ „ аг

не изменилась. Дугу S выбросить нельзя, так как после этого дуги — работы а4 и а7 — будут неразличимы^

Сетевой график не может содержать циклов. Если предположить, что имеется некоторый

цикл (av аг о„_і, а„, аД то

операция а 2 — только

операция at может быть выполнена только после' завершения операции а„, операция ап — только после завершения операции а„_ь

после завершения операции av В этом случае проект никогда не может быть выполнен.

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

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

Алгоритм получения правильной нумерации вершин

Нумеруют все начальные вершины

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

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

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

Предположим, что выполнение работы начато в момент времени t — О. Пусть tjj — заданная продолжительность работы (р„ pj). Величины tjj записывают на соответствующих дугах сетевого графика и считают их длинами.

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

Если из вершины pi выходит несколько работ, то ранние сроки начал этих работ совпадают и называются ранним сроком наступления события р,. Ранний срок начала работы (р„ pj) обозначают t^j, а ранний срок наступления события p,— Tj. Для удобства

величины Tf записывают в верхней трети каждой вершины (рис. 11.25).

Если работа начата в ранний срок начала, то

время ее окончания называется ранним сроком

окончания работы. Ранний срок окончания работы (р,, pj) обозначается / Ц •

Рис. и .25 Для вычисления ранних сроков наступления

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

Алгоритм расчета ранних сроков начал и окончаний работ

Полагают Г?=0.

Для »=2, 3, п вычисляют

77= max (П+/«)•

k.(pk.

Номер к-й вершины, при движении из которой получено значение Tf, заносят в левую треть вершины pt (рис. 11.25).

После нахождения величин 77 можно подсчитать ранние сроки начал и окончаний работ:

fP,= T'P /Р? = /Р!14-/..

* tj х и * IJ * IJ ■ 'у

О Пример. Найти ранние сроки начал и окончаний работ для сети, изображенной на рис. 11.26.

Полагаем 74 = 0. После этого рассматриваем вершины в порядке их номеров; Т~ Т + г12 = 0 + 2=.2. В левую треть вершины рг ставим номер вершины;^; Т=тъх(Т + 1гъ, 7?-H13)=max(8, 4)= 8. В левую треть вершины ръ записываем номер вершины рг (так как при движении из рг получено значение 7*5); Г5=Г5+*,4 = 2 + 5 = 7, Г|=тах(ГЇ + /4ї, Г5+/33)=тах(7 + 1,8 + + 7)= 1:5. После этого находим ранние сроки начал и окончаний работ: /й = 0, (Гз = 0, /g = 2, t\%=2, /£=8, t\% = 7, tfi=2, *B = 4, 'g = 8, rg = 7, fi? = 15, 'Sf = 8. •

Критическое время и критический путь. Ранний срок наступления конечного события называется критическим временем и обозначается 7Лр. Весь проект не может быть завершен раньше момента времени 7^, т. е. критическое время — это ми" р3 нимальный срок окончания

всего комплекса работ. На се- РисИ.26

тевом графике — это длина пути наибольшей длины из начальной вершины в конечную.

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

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

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

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

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

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

Поздние сроки начал и окончаний работ. Задают время Т выполнения всего комплекса работ. Очевидно, что должно выполняться неравенство 7> Т^. Обычно берут Г= Т^.

Поздним сроком окончания работы называется наибольшее допустимое время окончания работы без нарушения срока завершения всего проекта. Поздний срок окончания работы {pit pj) обозначается Можно определить поздний срок начала работы (pi, pj) t ™ по формуле

л ГШ t ПС f

ijj—tij— t-,j.

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

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

1. Полагают Т = Т.

2. Для j=n — , л—2, 2, I вычисляют

Г;= min (Tl-tJk).

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

Затем просматривают все вершины в порядке убывания их номеров. /Для каждой вершины рассматривают множество всех выходящих работ. Из поздних сроков наступления их конца вычитают продолжительность этих работ. Минимальная из этих разностей и равна Tj. Величину Tj записывают для удобства вычислений в правой трети вершины р} (см. рис. 11.25).

О Пример. Положим для сети, изображенной на рис. 11.26, время окончания всего комплекса работ 7 = 7^=15 и поставим это значение в правую треть вершины рь. Перейдем к событию РьГ}= Г!-«43 = 15-1 = 14. Аналогично находим 7Л=15-7 = 8.

Из вершины р2 выходят две работы, поэтому Г;=тіп(Г?-/23. П-/243)-тіп(8-6, 14-5)=2. Аналогично получаем Гї = 0. #

Из алгоритма вычисления поздних сроков следует, что увеличение наиболее позднего срока окончания проекта Т на t единиц ведет к увеличению поздних сроков наступления всех событий 'также на t единиц.

После определения Tj можно вычислить поздние сроки начала и окончаний всех работ проекта: t ™ = Tj, t ™ = / ™ —

Резервы времени. Рассмотрим некоторую работу (р„ р^. Найдем время, которое можно выделить для выполнения этой работы без задержки срока окончания всего проекта. Работа (ph pj) не может быть начата раньше срока Г? и должна быть закончена не позднее времени Tj. Для выполнения этой работы нужно затратить не более Tj—Tf единиц времени. По плану эту работу можно сделать за ttJ единиц времени.

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

Полный резерв времени работы (р„ pj) обозначают RtJ, он равен

R,j=Tj-Tf-ttj.

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

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

Найдем время, которое можно дополнительно выделить для выполнения работы {р,, pj) без введения дополнительных ограничений на время выполнения последующих работ. Для этого выполнение работы должно быть закончено к моменту времени Tj. Таким образом можно выделить Tj—T? единиц времени на выполнение работы (р„ pj).

Величина Гу= Tj—Tf— ttJ называется свободным резервом времени работы (ри Pj). Если использовать свободный резерв на некоторой операции, то последующие работы могут быть по-прежнему начаты в свои ранние сроки.

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

Для сети, изображенной на рис. 11.26, имеем

Л14=П-П-'24=14-2-5 = 7, г24=П-71-/24 = 7-2-5 = 0, Л45 = П-П-^5 = 15-7-1 = 7, г„=Г!-П-/45=15-7-1 = 7, Л13 = Г;-Г!-/13 = 8-0-4=4, г13 = Г5-Гї-Гіз = 8-0-4 = 4.

Если поздние сроки найдены при Т— Г1р, то для любой вершины, лежащей на критическом пути, Tj = Tj, Т$=Т? + іц. Следовательно, /?(/=гу=0.