Лекция 2. Тема Лекция. Формализованное построение моделей проектов. Преобразование сетевого графа "работывершины" в сопряженную
 Скачать 272.04 Kb.
|
|
Тема 5. Лекция. Формализованное построение моделей проектов. 2.2. Преобразование сетевого графа "работы-вершины" в сопряженную сетевую модель "работы-дуги" Преобразования сети "работы-вершины" в сопряженную модель "работы-дуги" канонического вида, допускают в искомой сети параллельные операций. Для исключения дублирования работ искомой сети предусмотрена коррекция связей между событиями [2]. Информация о составе и взаимосвязях операций комплекса представляется в виде перечня работ, j-му элементу которого поставлено в соответствие множество номеров работ (позиций плана) R(j). При этом, если обозначить через NR(j) номер операции проекта, то каждый элемент множества R(j) определяет операцию комплекса, для исполнения которой требуется работа NR(j). Эти элементы определяют множество операций, непосредственно следующих за работой NR(j). Предполагается, что перечень операций комплекса упорядочен, т.е. операция, следующая за работой NR(j), расположена в списке после работы NR(j). Для формализованных процедур упорядочения и преобразования в качестве идентификаторов операций можно использовать их порядковые номера. В дальнейшем термины "работа", "номер работы" равно как "операция" и "номер операции" будем использовать как равносильные. Наличие номера операции в обозначении дуги позволяет использовать в сети параллельные работы, выходящие из одной вершины и имеющие общие конечное событие. Формирование модели "работы-дуги" производится в порядке возрастания номеров элементов упорядоченного списка NR. В процессе преобразования событиям последовательно присваиваются номера из натурального ряда чисел. Исходя из канонического представления сети, начальные события работ, не имеющих предков, получают номер исходного (первого) события сети. Существование номеров начальных событий всех остальных работ на момент их участия в формировании сети обеспечивается упорядоченностью операций комплекса. Нумерация конечного события работы NR(j) и начальных событий операций из R(j) производится, исходя из возможности их объединения с элементами построенного ранее фрагмента. При этом применяемые виды коррекции обеспечивают уникальность представления операций. В рассматриваемом алгоритме нас будут также интересовать начальные события элементов множества R(j). Процедура включения работы NR(j) и элементов R(j) в структуру модели проекта имеет итерационный характер. Каждая итерация состоит: 1) в последовательном выделении из множества R(j) некоторого подмножества элементов, имеющих общую начальную вершину; 2) в преобразовании построенного ранее фрагмента сети, целью которого является определение конечного события работы NR(j) и начальных событий элементов рассматриваемого подмножества. При этом незавершенным вершинам фрагмента соответствуют нулевые номера их событий. Обозначим через I1(S i j ) - подмножество работ подсписка R(j), выходящее из события S фрагмента сети и соответствующее i-й итерации преобразования; k - число итераций (различных начальных вершин элементов списка R(j)). Тогда условие перехода к рассмотрению следующего элемента списка NR определяется как k ∪ I1(S i j )=R(j). (1) i=1 Согласно принятому правилу формирования сетевой модели "работы- дуги" нумерация конечных событий операций производится в порядке их расположения в упорядоченном списке NR. Поэтому перед включением работы NR(j) и элементов подсписка R(j) в структуру модели завершенные конечные события имеют только операции, расположенные в указанном списке под меньшими номерами. Конечные события всех остальных операций комплекса, включая элемент NR(j), и начальные события непосредственно следующих за ними работ, пока не принимавших участия в формировании фрагмента сети, остаются без номеров до момента их включения в сетевую модель проекта. В основе процедуры преобразования лежит очевидный факт, что для завершенных событий фрагмента множество всех работ I(S i j ), выходящих из некоторой вершины S 1 j , содержит в себе (или совпадает) подмножество элементов I1(S j i ), для которых данная вершина фрагмента является начальной, т.е. I1(S j i ) ⊂ I(S j i ) (или I1(S j i ) = I(S j i )). Рассмотрим возможные виды отношений между элементами построенного фрагмента сети, работой NR(j) и множеством R(j). Обозначим предварительно через P возможный номер конечного события работы NR(j). В данном случае значение текущей переменной P на единицу превышает максимальный номер события построенного фрагмента сети. 1. Если множество R(j) совпадает с множеством работ, выходящих из вершины сети S 1 j (I(S 1 j ) = I1(S 1 j ) = R(j)), то конечное события работы NR(j) совпадает с начальным событием работ множества I(S i j ). При этом номер P сохраняется для обозначения последующих событий модели. На рис.5 приведен пример включения работы NR(j) в структуру создаваемой модели. 2. Если некоторое событие S 1 j , отображающее начальные вершины всех элементов множества R(j) ⊂ R(j) = I1(S 1 j ), является исходным и для других работ фрагмента (R(j) ⊂ I(S 1 j )), то присвоить конечному событию работы NR(j) и начальным событиям работ из R(j) номер P и дополнить корректируемый фрагмент сети фиктивной связью (S 1 j , P). Эта процедура исключает в I(S 1 j ) работы из R(j) и сохраняет отношение непосредственного следования между работами фрагмента, входящими в событие S 1 j , и элементами множества R(j). Пример преобразования подобного вида приведен на рис. 6. 3. Если множества I(S i j ) ( 1 ≤ i ≤ k ) и R(j) не совпадают и R(j) содержит I(S i j ) (I(S i j ) ⊂ R(j); I(S i j ) = I1(S i j ) ), то присвоить конечному событию работы NR(j) номер P и отобразить ее непосредственное предшествование подмножеству работ I1(S i j ) фиктивной связью (NP, S i j ). Данный вид коррекции изображен на рис. 7. 4. Если множества R(j) и I(S i j ) (1 ≤ i ≤ k) не содержатся одно в другом, но имеют общие элементы ( R(j) ∩ I(S i j ) ), то присвоить конечному событию работы NR(j) значение переменной P. Кроме того, для определения начальной вершины подмножества I1(S i j ) в в сеть вводится новое событие P 1 , номер которого на момент коррекции превышает на единицу номер максимального события фрагмента. Если при включении в сеть множества R(j) данное преобразование выполняется впервые, то номер события P 1 равен увеличенному на единицу значению текущей переменной P. Чтобы сохранить заданную взаимосвязь операций, события S i j и P следует соединить с вершиной P 1 фиктивными работами ( S i j , P 1 ) и ( P, P 1 ). На рис. 8 приведен пример, иллюстрирующий рассмотренный вид преобразования. i 1 i 2 i 3 * * * i R(j) k ⊂ P NR(j) * i 2 i 3 i 1 S 1 j * * i (S ) k ⊂ I 1 j * i 1 i 2 i 3 S 1 j * * * NR(j) i 1 i 2 i 3 * * i R(j) k ⊂ P NR(j) i 1 i 2 i 3 * * * i R(j) k ⊂ P NR(j) i 1 i 2 i 4 S 1 j * * * * i 3 i (S ) k ⊂ I 1 j i 1 i 2 i 3 * * * P NR(j) S 1 j * i 4 Рис. 5. Рис. 6. Примечание. В соответствии со вторым, третьим и четвертым правилами преобразования конечному событию операции NR(j) неизменно присваивается текущее значение переменной P. Поэтому независимо от вида коррекции необозначенные начальные события работ из R(j) ( работ множества I1(0 i j ) ) получают номер P. Очевидно, что, одношаговые преобразования первого и второго видов, применимы ко всем элементам множества R(j). Рассмотрим общий случай циклического процесса включения в фрагмент сетевой модели операции NR(j) и работ множества R(j). Число итераций преобразования определяется количеством различных начальных событий элементов множества R(j). Когда данный подсписок содержит работы, выходящие из нескольких вершин фрагмента, формирование искомой сети производится в соответствии с правилами, предусмотренными пунктами 3 и 4. Так как i-я итерация каждого из рассматриваемых видов коррекций обеспечивает сопряженность преобразования, то, учитывая непересекаемость подмножеств I1(S i j ) и независимость обозначения конечного события работы NR(j) от видов и очередности проводимых преобразований, можно сделать вывод о сопряженности процедуры включения работы NR(j) и элементов множества R(j) в фрагмент сети. k ∩ I1(S i j ) = ∅ (2) i (S ) k i ⊂ I j i 1 i 3 i 1 i 2 i 4 * * * * i R(j) k ⊂ P NR(j) S 1 j i 1 i 2 i 3 * * * i 2 i 3 * * * P NR(j) S 1 j * i 4 i 3 i 1 i 2 i 4 * * * * i R(j) k ⊂ P NR(j) i (S ) k i ⊂ I j S 1 j i 1 i 2 i 6 * * * * i 5 P 1 i 1 i 2 i 5 * * * P NR(j) S 1 j * i 4 * i 3 * i 6 i=1 Рассмотренные правила коррекции раскрывают основное смысловое значение введения дополнительных дуг-связей. Отображая результаты проводимых преобразований, фиктивные работы обеспечивают уникальность представления операций в сети комплекса, не нарушая при этом отношений непосредственного следования между работами. Так как сопряженность преобразования обеспечивается коррекцией взаимосвязей между завершенными событиями фрагмента, то конечные события фиктивных работ всегда имеют номер. Еще одно важное свойство формализованной процедуры построения сетевой модели состоит в том, что за исключением преобразований первого вида за конечным событием работы NR(j) сохраняется его предварительный номер P. Свойство инвариантности используется при организации машинных процедур построения сети типа "работы-дуги". Все наши рассуждения проводились, исходя из предположения, что множество R(j) остается неизменным на протяжении всего процесса преобразования. Мы специально обращаем на это внимание, так как известны попытки построения сетевых моделей типа "работы-дуги", использующие процедуры последовательного аннулирования элементов рассмотренных подмножеств I1(S i j ) из множества непосредственно следующих работ R(j). После применения второго, третьего и четвертого правил формирования сети при переходе к рассмотрению следующего элемента списка NR (j = j + 1) номер текущего события создаваемой сети должен превышать на единицу максимальное из значений переменных P и P 1 ( P = max( P, P 1 ) + 1 ). Описанная процедура формирования сети выполняется для всех операций, имеющих потомков. Как мы убедимся при рассмотрении примера, иллюстрирующего работу данного алгоритма, после операций, не имеющих потомков, в списке NR могут находиться элементы, предшествующие выполнению некоторых работ проекта. Поэтому при отсутствии дополнительных сведений, упорядоченный список операций просмотрен до (N - 1)-го элемента. Заключительный этап определения завершающего события сети состоит в определении конечных событий работ, не имеющих потомков (R(j) = ∅ ). Очевидно, что номера их начальных событий были определены при обозначении конечных событий непосредственно предшествующих работ или при нумерации операций, выходящих из исходного события сети. Учитывая, что текущее событие сети отображает конечные события элементов списка NR, присвоим значение переменной P всем операциям комплекса, не имеющих потомков. Наличие в сети одного завершающего события соответствует каноническому ее представлению. Очевидно, что последняя процедура построения сети не нарушает отношения следования между работами. В процессе проводимых преобразований номера начальных события некоторых работ могут превышать номера их конечных событий. В то же время, некоторые алгоритмы расчета сетевых моделей ориентированы на упорядоченную нумерацию событий сети, где номер начального события i каждой операции должен быть меньше номера ее конечного события j (i < j). Чтобы это необязательное I-J правило выполнялось, в сети, полученной в результате работы данного алгоритма, следует ввести новую нумерацию событий. Разберем алгоритм преобразования на конкретном примере. В таблице 1 упорядоченным списком NR и подсписками непосредственно следующих работ представлен сетевой граф "работы- вершины". Для большей наглядности дуги искомой модели, за исключением фиктивных работ, помечены соответствующими номерами операций. Упорядоченность списка операций комплекса вовсе не означает, что все его операции без потомков расположены в конце данного списка. Определяющим фактором здесь является способ упорядочения. Таблица 1. П/П NR Непосредственно следующие операции 1 11 R(11) = {4} 2 12 R(12) = {1,2,3} 3 13 R(13) = {4,8} 4 3 R(3) = {8} 5 1 R(1) = {4,6} 6 2 R(2) = {5,6,7} 7 8 R(8) = {10} 8 4 R(4) = {9} 9 5 R(5) = {9} 10 6 R(6) = 0 11 7 R(7) = {10} 12 9 R(9) = 0 13 10 R(10) = 0 Из примера видно, что седьмая операция, за которой следует десятая работа, расположена в списке NR после шестой операции, не имеющей потомков. Шаг 1. Нумерация событий 11-й операции и начального события 4-й работы. Начальному событию, не имеющей предшественников 11-й операции присваивается номер исходного события сети - номер один. Номер ее конечного события, а также номер начального события 4-й операции (R(11) = {4} ) совпадает с номером текущего события сети P (P = 2). Увеличить на единицу номер текущего события сети (P = 3). 1 2 11 4 Рис. 9.1. Шаг 2. Нумерация событий 12-й операции и начальных событий работ из R(12). Начальное событие 12-й работы получает номер один. Номер ее конечного события, а также номера начальных событий 1-й, 2-й и 3-й операций совпадает с номером текущего события сети P (P=3). Увеличить на единицу номер текущего события сети (P = 4). Шаг 3. Нумерация событий 13-й операции определение начальных событий работ из R(13). Начальное и конечное события операции 13 получают соответственно номера 1 и 4. Учитывая, что I(2) ( R(13) (третий вид коррекции), события 4 и 2 соединяются фиктивной работой (4, 2). При этом номер начального события 1 2 3 11 12 4 1 2 3 Рис. 9.2. 8- й операции получает номер 4. Увеличить на единицу номер текущего события сети (P = 5). Шаг 4. Нумерация конечного события 3-й операции и коррекция начального события восьмой работы. Конечное событие 3-й операции получает номер пять (P=5). Подсписок R(3) содержит одну операцию, выходящую из четвертого события. В свою очередь, четвертое событие является начальным для восьмой и фиктивной (4, 2) работ. В соответствии со вторым видом коррекции фрагмента начальное событие 8-й операции получает номер пять. Кроме того, события 4 и 5 соединяются фиктивной связью (4, 5). Увеличить на единицу номер текущего события сети (P = 6). Шаг 5. Нумерация конечного события 1-й операции и определение начальных событий работ из R(1). Конечное событие 1-й операции получает номер шесть (P=6). I(2) = {4}, R(1) = {4, 6} - третий вид коррекции фрагмента. В этом случае события 6 и 2 соединяются фиктивной работой (6, 2). При этом конечному событию 6-й операции присваивается номер шесть. 1 2 4 3 11 12 13 4 1 2 3 8 Рис. 9.3. 14 Увеличить на единицу номер текущего события сети (P = 7). Шаг 6. Нумерация конечного события 2-й операции и определение начальных событий элементов подсписка R(2). Конечное событие 2-й операции получает номер семь (P=7). Множество I(6), содержащее шестую и фиктивную операцию (6,2) (I(6) = { 6, (6, 2) }, и R(2) = {5, 6, 7} определяют четвертый вид коррекции. В соответствии с ним 6-я операция, как элемент нового подмножества, получает восьмой номер начального события (P1 = P + 1 = 8; I1(8) = {6}), а 1 2 4 3 5 6 11 12 13 4 1 2 3 8 6 1 2 4 3 5 11 12 13 4 1 2 8 Рис. 9.5. 14 16 15 1 2 4 3 5 11 12 13 4 1 2 3 8 Рис. 9.4. 14 15 события 6 и 7 соединяются фиктивными связями (6, 8), (7, 8). Номер текущего события P определяется из условия: P = max(7, 8) + 1 = 9. Шаг 7. Нумерация конечного события 8-й операции и начального события 10-й работы. Множество R(8) содержит операцию, начальное событие которой не обозначено. Поэтому конечное событие восьмой операции и начальное событие 10-й работы получают номер текущего события - 9. Увеличить на единицу номер текущего события сети (P=10). 1 2 4 3 5 7 6 8 11 12 13 4 1 2 3 8 5 7 6 Рис. 9.6. 15 14 16 17 18 1 2 4 3 5 9 7 6 8 11 12 13 4 1 2 3 8 5 7 10 6 Рис. 9.7. 18 17 16 14 15 Шаг 8. Нумерация конечного события 4-й операции и начального события 9-й работы. В данном случае в точности повторилась ситуация предыдущего шага. После включения 9-й работы в фрагмент сети номер ее начального события, определяемый значением P (P = 10), совпадает с номером конечного события 4- й работы. Увеличить на единицу номер текущего события сети (P=11). Шаг 9. Определение конечного события 5-й операции. Совпадение множеств I(10) и R(5) (I(10) = R(5) = {9}) определяет первый вид преобразования фрагмента. При этом номер текущего события остается без изменения. Примечание. Шестая операция комплекса не имеет потомков. Поэтому в соответствии с алгоритмом происходит переход к рассмотрению одиннадцатого элемента упорядоченного списка NR. 1 2 4 3 5 9 7 6 8 10 11 12 13 4 1 2 3 8 5 7 10 6 9 Рис. 9.8. 18 17 16 14 15 1 2 4 3 5 9 7 6 8 10 11 12 13 4 1 2 3 8 5 7 10 6 9 Рис. 9.9. 15 14 16 17 18 Шаг 10. Определение конечного события 7-й операции. Совпадение множеств I(9) и R(7) определяет первый вид преобразования, отождествляющего конечное событие 7-й операции с 9-м событием фрагмента. Номер текущего события не изменяется. На этом процесс включения операций комплекса в фрагмент сети заканчивается, так как 12-й и 13-й элементы упорядоченного списка не имеют потомков. Заключительный этап преобразования заключается в присвоении незавершенным событиям сети, отображающим завершающее событие комплекса, номера текущего события P. В нашем примере конечные события 6- й, 9-й и 10-й операций получают номер 11. 1 2 4 3 5 9 7 6 8 10 11 12 13 4 1 2 3 8 5 7 10 6 9 Рис. 9.10. 18 17 16 14 15 Машинное представление сетевой модели в терминах работ и событий задается в виде двух векторов I и J, i-е компоненты которых есть соответственно номера начального и конечного событий операции i (1 < i > KN ), где KN - количество работ (включая фиктивные связи) сети "работы- дуги". Размерность векторов совпадает с количеством связей сети "работы- дуги". При этом, если обозначить через N количество работ проекта, то фиктивным работам, образовавшимся в результате коррекции взаимосвязей между событиями, присваиваются номера, начиная с номера N+1. Списковая структура модели на рисунке 12.11 представлена в таблице 2. Таблица 2. Работы проекта Фиктивные работы K 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 I 3 3 3 2 7 8 7 5 10 9 1 1 1 4 4 6 6 7 J 6 7 5 10 10 11 9 9 11 11 2 3 4 2 5 2 8 8 Для выполнения I-J правила в искомой сети следует ввести новую нумерация событий. приятием. 1 2 4 3 5 9 7 6 8 10 11 11 12 13 4 1 2 3 8 5 7 10 6 9 Рис. 9.11 15 14 16 17 18 |