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

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

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

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

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

выяснить очередность всех операций. Для этого составляют список операций, непосредственно предшествующих каждой операции;

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

325

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

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

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

Рис. 11.23

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

326

О Пример. На рис. 11.24 изображены сеть G и упрощенная сеть Gy При упрощении выброшены дуги а, (3, у. Последовательность выполнения работ при этом не изменилась. Дугу 6 выбросить нельзя, так как после этого дуги аА и а7 будут неразличимы. •

Сетевой график не может содержать циклов. Если предположить, что имеется некоторый цикл (Oj, а2,ап1, ап, ау), то операция йу может быть выполнена только после завершения операции ап, операция ап — только после завершения операции ап1, операция а2 — только после завершения операции av В этом случае проект никогда не может быть выполнен.

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

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

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

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

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

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

327

Ранние сроки начала и окончания работ. Предположим, что выполнение работы начато в момент времени t-0. Пусть ґ~ — заданная продолжительность работы (рр р}), где p., Pj — начальная и конечная вершины дуги. Величины ttj записывают на соответствующих дугах сетевого графика и считают их длинами.

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

Если из вершины pt выходит несколько работ, то ранние сроки начала этих работ совпадают и называются ранним сроком наступления события рґ Ранний срок начала работы (рр р}) обозначают tP.w, а ранний срок наступления события р. — соответственно ТР. Для удобства величины TP записывают в верхней трети каждой вершины (рис. 11.25).

Если работа начата в ранний срок начала, то время ее окончания называется ранним сроком окончания работы. Ранний срок окончания работы (рр рр обозначают tP°.

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

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

Полагают 7^ = 0.

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

TP = max (Г*? + tu).

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

Подсчитывают ранние сроки начала и окончания работ:

tf=T?, $°=/f+V (11.7)

328

Полагаем Tf 0. После этого рассматриваем вершины в порядке их номеров:

Т£ ~ + hi ~ 0 + 2 = 2, в левую треть вершиныр2 ставим номер вершины рх;

max{7^ +123; Tf + tn} тах{8; 4} = 8, в левую треть вершины р3 записываем номер вершины р2 (так как при движении из р2 получено значение 7^); 7?=7| + ґ24 = 2 + 5 = 7;

7| = тах{7? +145; 7f + /35} = тах{7 + 1; 8 + 7} = 15.

После этого находим ранние сроки начала и окончания работ:

*рн_п Л>н_п fPK-O fPH-0 fPH-R fPH-7 '12 —'13 —'23 — ' '24 — ' '35 ~~ ' '45 — '

ff° = 2, # = 4, £ = 8, tg = 7, /£=15, /£° = 8.«

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

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

Алгоритм построения критического пути. Начинают построение с конечной вершины. В ее левой трети стоит номер той верши 

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

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

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

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

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

Поздним сроком окончания работы называется наибольшее допустимое время окончания работы без нарушения срока завершения всего проекта. Поздний срок окончания работы (ррр) обозначают ty°. Можно определить поздний срок начала работы (р., рр (его обозначают ti™) по формуле

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

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

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

Для j = п -1, и 2,2, 1 вычисляют

Tf= min (Tkn-tjk).

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

О Пример. Положим для сети, изображенной на рис. 11.26, время окончания всего комплекса работ Т= 7^ = 15 и поставим это значение в правую треть вершины р5. Перейдем к событию р4: Т4 = Т5 ~ Us= 15 ~ 1 = 14Аналогично находим Tf = 15 7 = 8.

Из вершиныр2 выходят две работы, поэтому Т2 = min{T3 -t23; Т4 ~ = ПШ1^8 6; 14 5} = 2. Аналогично получаем Г° = 0. •

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

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

tf = Tf, tf = t™-t... (11.9)

Резервы времени. Рассмотрим некоторую работу (ррр}). Найдем время, которое можно выделить для выполнения этой работы без задержки срока окончания всего проекта. Работа (р., рр не может быть начата раньше срока Tf и должна быть закончена не позднее времени TJ1. Для выполнения этой работы нужно затратить не более TJ1 Tf единиц времени. По плану эту работу можно сделать за tg единиц времени.

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

Полный резерв времени работы (р., рр обозначают Rg, он равен

^Tf-Tf-ty (11.10)

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

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

331

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

Величина

r9=7*-7?-t9 (11.11)

называется свободным резервом времени работы (p., pp. Если использовать свободный резерв на некоторой операции, то последующие работы могут быть по-прежнему начаты в свои ранние сроки.

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

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

Л24=Г4п-Г2р-/24 = 14-2-5 = 7,

/■„=77-71-^ = 7-2-5 = 0,

R45= 77-7^-^=15-71 = 7,

»45= 71-7-/-^ = 15-7-1 = 7,

Л13=2'зи-77-Г1з = 8-0-4 = 4>

гп= 7|7^-^3 = 8-0-4 = 4. •

Если поздние сроки найдены при Т= Т, то для любой вершикр

ны, лежащей на критическом пути, TP = Tj1, TP = TP + tt]. Следовательно, Ry = г у = 0.