3. Сетевые модели планирования и управления проектами
1 . Сетевые модели ланирования и уравления роектами Проектом называют совокуность работ, наравленных на достижение некоторой цели. Работы роекта, как равило, частично уорядочены. Выолнение работы не может быть начато до завершения всех редшествующих ей работ. Продолжительность выолнения каждой работы известна. Предолагается, что начатая работа родолжается без ерерыва до ее завершения. Проект считается выолненным, если выолнены все его работы. Сетевая модель это графическое редставление роекта. Она озволяет найти минимальные сроки завершения роекта и отдельных работ, а также оределить множество критических работ, увеличение родолжительности выолнения любой из которых риводит к увеличению времени выолнения всего роекта. Построение сетевой модели роекта Пример.. (строительство дома). При строительстве дома необходимо выолнить такие работы, как создание одъездных дорог, одготовка котлована, возведение фундамента, одводка коммуникаций, монтаж здания, крыши, отделочные работы и т.. Каждую работу роекта можно начать выолнять только осле завершения всех редшествующих ей работ. Наример, фундамент возводится только осле одготовки котлована. В то же время некоторые работы, наример одводка коммуникаций и отделочные работы, могут осуществляться араллельно. Сетевая модель роекта редставляет собой графическое оисание лана работ, оказывающее взаимосвязь между всеми работами, выолнение которых необходимо для завершения роекта. В терминах теории графов сетевая модель это ориентированный граф без контуров и етель с неотрицательными весами вершин или дуг. При анализе роектов исользуются два тиа сетевых моделей, которые условно можно назвать: ) «работы-вершины»; 2) «работы-дуги». В сетевой модели ервого тиа вершины являются образами работ, а дуги служат для отображения отношения редшествования между работами. В модели второго тиа, наряду с работами-дугами, рассматриваются также новые онятия события, которым соответствуют вершины сети.
2 Событие отражает результат завершение одних работ и возможность начала других. Наравление дуги сети задает отношение редшествования работ роекта. Указанные выше модели являются эквивалентными в том смысле, что для любого роекта можно остроить как одну, так и другую модель. В данном особии, как и в [, ], рассматриваются сетевые модели тиа «работы-дуги». В таких моделях для задания соотношения редшествования работ-дуг часто риходится вводить фиктивные дуги нулевой длины (родолжительность выолнения соответствующих фиктивных работ равна нулю). Нефиктивные дуги будем называть также фактическими. Оределение.. Сети с одним и тем же множеством фактических дуг назовем эквивалентными, если они задают одно и то же отношение редшествования дуг-работ. Вершину, не имеющую входящих в нее дуг, будем называть входом, а вершину, из которой не выходит ни одной дуги, выходом сетевой модели. Без ограничения общности можно считать, что сетевая модель имеет один вход и один выход. Если исходная сеть не обладает этим свойством, то можно ввести фиктивный вход (выход) и связать с ним все входы (выходы) фиктивными дугами. Полученная сеть, очевидно, эквивалентна исходной сети. Пример.2. Привести сетевую модель, изображенную на рис.. к эквивалентной сети с одним входом и одним выходом Рис.. Решение. Входами сети являются вершины 2, и. Введем доолнительную вершину и свяжем ее фиктивными дугами (, 2), (, ) и (, ) со всеми входами. 2
3 Вершины и 2 являются выходами сетевой модели. Добавим вершину и соединим с ней фиктивными дугами (, ), и (2, ) все выходы сетевой модели Рис..2 На рис..2 редставлена новая сеть с одним источником и одним стоком. Фиктивные дуги изображены унктирными линиями..2. Урощение сетевой модели В ряде случаев исходную сеть можно уростить, исключив часть вершин и фиктивных дуг. Введем следующие обозначения: S = ( X, U) сеть с множеством вершин X и множеством дуг U; (j) начальная вершина дуги j; k(j) конечная вершина дуги j; U множество фактических дуг сети; U множество дуг из U, ринадлежащих объединению всех утей из входа сети в вершину ; U множество дуг из U, ринадлежащих объединению всех утей из вершины в выход сети. Зафиксируем ару вершин и k, для которых ) не существует дуги j U, инцидентной одновременно и k; 2) не существует дуг q, U, для которых () = (q), где k() = I и k(q) = k или k() = k(q), где () = и (q) = k.
4 Результатом оерации склеивания вершин и k будет сеть S, олученная из исходной сети S удалением вершины k и замыканием инцидентных ей дуг на вершину. Когда в результате склейки между какой-то арой вершин и l в S будет более одной дуги: если среди них есть фактическая дуга, то удаляются все араллельные ей фиктивные дуги; если и l в S связаны только фиктивными дугами, то все они кроме одной удаляются. Таким образом, если в исходной сети S дуга имела вершину k начальной (конечной), то в олученной сети S эта дуга имеет начальной (конечной) вершину. Очевидно, в S существует уть из одной вершины в другую тогда и только тогда, когда такой уть есть в S. Эквивалентность сетей S и S роверяется с омощью следующего необходимого и достаточного условия. Пусть вершины и k удовлетворяют условиям 2, оисанным выше. Сеть S, олученная из S склеиванием и k и удалением k, эквивалентна S тогда и только тогда, когда выолняется хотя бы одно из условий: U = U k или U = U k. Пример.. Уростить сетевую модель, редставленную на рис Рис. Решение. Очевидно, для выолнения риведенных выше условий вершины кандидаты на склеивание должны быть соединены фиктивной дугой. Рассмотрим такие ары вершин в данной сети. Вершины и удовлетворяют свойствам 2. Очевидно, U = = = U. Следовательно, вершины и могут быть склеены. Для вершин и 0 свойство 2 не выолняется, так как вершина связана с обеими вершинами и 0 фактическими дугами. Следовательно, и 0 нельзя склеить.
5 Для вершин 2 и свойства 2 выолняются, но U 2 = U = = и U 2 = U = . Следовательно, вершины 2 и не могут быть склеены с сохранением эквивалентности сетей. Вычисление араметров сетевой модели Пусть задана сеть, вершины которой ронумерованы числами,, n, а дуги числами,, m. Тогда сетевую модель можно редставить сиском дуг, каждая из которых закодирована числами: j номер дуги; (j) номер начальной вершины дуги j; k(j) номер конечного вершины дуги j; τ j длина дуги (длительность выолнения работы) j. Оределение.2. Рангом R события называется число дуг в ути максимальной (о числу дуг) длины, ведущему из входа сети в вершину. Алгоритм Форда вычисляет ранги событий следующим образом: Шаг 0. Полагаем R = 0 для всех =,, n. Пусть в результате (k ) шагов найдены ранги R. Шаг k. Просматривая оследовательно дуги (работы) j =,, m, вычисляем R k(j) = max. Если на очередном шаге ранги всех вершин сети не изменились, то алгоритм завершает свою работу. Иначе олагаем k = k + и овторяем шаг k. Пример.. Найти ранги событий для сетевой модели, изображенной на рис. где рядом с каждой дугой указан ее номер Рис.. Решение. На нулевом шаге олагаем R = 0 для всех вершин =,, 8. На ервом шаге алгоритма оследовательно росматриваем все дуги и ересчитываем ранги их концевых вершин: работа = (, 8) : R 8 = max = max =, работа 2 = (, ) : R = max = max =,
6 работа = (8, ) : R = max = max = 2, и т. д. Продолжая вычисления, олучаем табл. Ранг События Шаг 0 Шаг Шаг 2 Шаг Таблица. На третьем шаге ранги событий не изменись. Следовательно, алгоритм завершает свою работу и ранги событий R =, R 2 =, R =, R = 0, R =, R =, R =, R 8 = 2. Оределение.. Нумерацию событий сетевой модели назовем равильной, если (j) < k(j) для каждой работы j =,, m. Правильную нумерацию событий (вершин сети) легко осуществить, зная их ранги. Вершинавход с рангом 0 олучает номер. Вершины ранга олучают номера 2,, n, ранга 2 номера n +,, n 2, и т. д. Пример.. Осуществить равильную нумерацию событий в сетевой модели римера.. Решение. Так как ранги событий найдены, то равильная нумерация событий осуществляется следующим образом: входу (т. е. событию с рангом 0) риисываем номер ; событиям ранга (событиям и ) номера 2 и ; событиям ранга 2 (8) номер ; событиям ранга (, 2 и ) номера, и ; выходу () номер 8. Оределение.. Длиной ути μ(, k) из вершины в вершину k во взвешенном графе назовем величину, равную сумме весов входящих в него дуг, которую обозначим μ(, k). Путь из в k, имеющий максимальную длину, обозначим μ * (, k). Далее редолагается равильная нумерация вершин, ри которой, в частности, вершина это источник, а n сток. Оределение.. Наиболее ранним временем настуления события назовем величину T = μ * (, ).
7 Величина T соответствует минимально возможному времени выолнения всех работ, редшествующих событию. Обозначим через T кр = T критическое время роекта (минимальное n время выолнения роекта), а через μ * (, n) критический уть сетевой модели. Работы и события, ринадлежащие критическому ути, называются критическими. Задержка настуления любого критического события риведет к увеличению срока завершения всего роекта T кр. Оределение.. Наиболее оздним временем настуления события назовем величину T = Tкр μ * (, n). Величина T равна максимальному времени свершения события, не риводящему к увеличению времени выолнения всего роекта. Сегмент [T, T ] называется интервалом свободы события. Для того чтобы событие было критическим, необходимо и достаточно T = T. Резервы времени выолнения работ это величины, характеризующие максимально возможное время, на которое можно увеличить родолжительность выолнения работ или задержать начало их выолнения, чтобы время начала выолнения других работ не изменилось. Оределение.. Полным резервом времени выолнения работы j на- зывается величина Π = T T τ. j k( j) ( j) j Необходимым и достаточным условием ринадлежности работы критическому ути является равенство нулю ее олного резерва. Оределение.8. Свободным резервом времени выолнения работы j называется величина T T τ k( j) ( j) j. Свободный резерв может быть исользован для выявления работ, задержка которых на эту величину не риводит к изменению олных резервов всех оследующих работ. Наиболее ранние времена настуления событий могут быть найдены ри омощи следующего алгоритма Форда: Шаг 0. Для каждого события =,, n олагаем T = 0. Пусть в ре- зультате (k ) шагов найдены времена T. Шаг k. Последовательно росматриваем все работы j =,, m и вычисляем T k ( j) max < T k( j), T ( j) τ >j = +. Если все времена T не изменились, то алгоритм заканчивает свою работу. Иначе олагаем k = k + и выолняем следующий шаг алгоритма.
8 Сисок дуг можно уорядочить таким образом, что T будут найдены за один росмотр работ. Пусть события ронумерованы равильно. Оределение.. Если для каждой ары дуг и q, когда μ(, (q)), выолняется неравенство < q, то говорят, что сисок дуг равильно уорядочен. Правильная уорядоченность дуг согласуется с отношением редшествования работ, т. е. если редшествует q, то имеет место неравенство < q. Для олучения равильной уорядоченности дуг достаточно уорядочить их о номерам конечных вершин (ри равильной нумерации оследних). В вершине не заканчивается ни одна дуга. Все дуги I 2, входящие в вершину 2, олучают номера,, I 2. Дугам I, входящим в вершину, риисываются номера I 2 +,, I 2 + I, и т. д. Если дуги равильно уорядочены, то алгоритм Форда найдет T за один росмотр дуг в орядке их нумерации j =,, m. Приведем алгоритм Форда для вычисления наиболее оздних времен настуления событий: Шаг 0. Для каждого события =,, n олагаем T = Tкр. Пусть в ре- зультате (k ) шагов найдены времена T. Шаг k. Последовательно росматриваем все работы j =,, m и вычисляем T mn ( ) T n T n τ j j k j j =. Если осле выолнения очередного шага все времена T не изменились, то алгоритм заканчивает работу. Иначе олагаем k = k + и выолняем следующий шаг алгоритма. При равильно-уорядоченном сиске работ величины T находятся за один шаг алгоритма, если работы росматривать в обратном орядке j = m. Когда величины T и T известны, остальные характеристики сетевой модели (критические работы, события, резервы и т..) могут быть найдены за один росмотр сиска работ. Пример.. Пусть сетевая модель задана табл..2. Таблица.2 Номер дуги Дуга Длина дуги
9 Требуется найти вход и выход сети, ранние и оздние времена настуления событий, время выолнения роекта, олные резервы времени для каждой работы-дуги, критические работы и ути. Нумерацию вершин и дуг не менять. Решение. Просматривая сисок дуг, выясняем, что вершина не фигурирует в качестве концевой вершины ни одной дуги. Это вход сети. Аналогично для нахождения выходов сети оределяем, какие из вершин не являются начальными вершинами дуг. Такая вершина одна. Она является выходом сетевой модели. Найдем ранние времена настуления событий, исользуя алгоритм Форда. Полагаем T = 0 для всех =. На ервом шаге алгоритма росматриваем все работы и ересчитываем ранние времена настуления их концевых событий в соответствии с рекуррентными соотношениями алгоритма Форда. В частности, для ервых двух работ имеем: работа = (, ) : T = max < T, T +τ >= max = 2, работа 2 = (, ) : T = max < T, T +τ 2 >= max = 2. Результаты вычислений ранних времен омещены в табл. где в ервом столбце находятся номера событий, а в верхней строке номера шагов алгоритма. После третьего шага ранние времена настуления событий не изменились ни для одного из них, оэтому алгоритм завершает свою работу. Время выолнения роекта соответствует раннему времени настуления события и равно T кр = T =. / k Таблица.
10 Найдем оздние времена настуления событий. Положим T = Tкр = для всех вершин =. Просматриваем оследовательно все работы и ересчитываем оздние времена настуления событий, соответствующих концевым вершинам работ-дуг. Так для ервых двух работ имеем: работа = (, ): = mn < T, T τ >= mn =, T работа 2 = (, ): = mn = mn =. T T Результаты вычислений омещены в табл. /k Таблица. Найдем олные резервы времени для каждой работы и оместим их в табл. Таблица. Дуга j П j Для римера риведем вычисления данной характеристики для ервых двух работ: работа = (, ) : П = T T τ = = 0, работа 2 = (, ) : П 2 = T T τ 2 = 0 2 =. Критическими работами являются те, олный резерв времени которых равен нулю. В данном случае это работы, и 0. Критическому ути ринадлежат события, у которых ранние и оздние времена их свершения совадают. В нашем римере это события. 0
11 Уражнения. Уростить сетевую модель, изображенную на рис Рис.. 2. Для сетевой модели из римера. вычислить ранги событий.. Пусть сетевая модель задана табл. Таблица. Номер дуги Дуга Длина дуги Найти вход и выход сети, ранние и оздние времена настуления событий, время выолнения роекта, олный резерв времени для каждой работыдуги, критические работы и ути. Нумерацию вершин и дуг не менять.