Построение сетевых моделей комплексов работ.

СЛП ЖЦ РО как взаимосвязанный набор ОС представляет естественную основу для формирования математическом модели комплекса работ по реализации его ЖЦ.

Понятие СМ КР.

Между понятиями «стадия ЖЦ РО» и «работа» может быть установлено взаимно однозначное соответствие: СЛП стадии фиксирует содержание работы (научное, техническое, производственное) и может рассматриваться как часть ее описания (лингвистическая переменная). Понятие работа помимо фиксации содержания некоторой трудовой деятельности фиксирует более детально обеспечивающие компоненты (ингредиенты) этой деятельности, включающие энергию (Е), материалы (предметы труда) (М), оборудование (средства труда) (Eq), кадры (субъект труда) (Sb), информацию (I) (рабочая документация), организационный механизм (Mg). Эти компоненты представляют объект, который может быть назван «комплексным обеспечением» способа (F) функционирования ОС. ИЛМ комплексного обеспечения, как РО, обычно имеет шесть уровней описания (приведены четыре промежуточных уровня):

r = 2 : установлены требования к содержанию компоненты;

r = 3 : определены признаки (показатели и факторы);

r = 4 : установлены шкалы для измерения признаков;

r = 5 : установлены допустимые области значений признаков (математическое описание работы приведено в гл.2).

Таким образом, структура комплекса ОС с учетом СЛП комплексного обеспечения изоморфна структуре КР. Комплекс рассматривается в виде сетевой модели, являющейся отображением элементов комплекса и связей между ними. Графический образ СМ именуется сетью, графом сети или сетевым графиком комплекса. СМ имеет две группы свойств : топологические (структурные) и параметрические (количественные характеристики отдельных работ и их совокупностей).

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

Имеются два основных способа задания СМ в виде графа GI : X - множество работ, U - множество связей между работами. Это СМ типа «вершины-работы», так называемые сети предшествования. GII: X - множество событий, U - множество работ, связывающих события. Это СМ типа «вершины-события» наиболее распространены.

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

Структура СМ (и самого комплекса работ) можетбыть детерминированной (все работы безусловно выполняются) и не­определенной нечеткой (по крайней мере одна работа выполня­ется в зависимости от некоторых априорно не заданных усло­вий). Обозначение типа структуры СМ имеет вид:x/у/z , гдех- буква р (если вершины графа - работы), с (если со­бытие); у - (натуральное) число целей КР; z - буквы Д (де­терминированная), Н (недетерминированная) или С (стохасти­ческая). Например, тип P/1/С означает одноцелевую сеть со стохастической структурой.

Построение СМ типа С/N/Д

Пусть N=1. В СМ данного типа отношение U, задан­ное на X, является строгим или совершенно строгим поряд­ком, поскольку оно выражает логическое, а значит, в временное следование (предшествование) работ.

Из определения типа СМ вытекают следующие правила построения сети.

П1. Для " работы uÎU $! событие ( ) предшествую­щее началу работы (исходное или начальное событие), и событие ( ), следующее за окончанием работы (завершающее для данной работы). Графически каждая работа изображается един­ственной для всей сети стрелкой, связывающей и и на­правленной от к . ( , ÎX). Вся сеть, таким образом, представляет собой ориентированный граф.

П2. $! исходное и завершающее события сети в целом. Если это не выполнено, то в сеть вводятся новые события (взамен или наряду с имеющимися), предшествующие всем событиям без входящих дуг и/или следующее за всеми событиями без входящих дуг.

ПЗ. В сети не должно быть контуров. Наличие контура свидетельствует о логически противоречивом определении работ, либо о неадекватном типе СМ для данного КР. В последнем случае необходимо выбрать другой тип СМ.

П4. Вершины-события должны адекватно отражать отноше­ние следования между инцидентными ему стрелками-работами: выходящая стрелка-работа (u ^вых ) должна логически следовать за всеми входящими стрелками-работами (u^вх ) Если для некоторой (u ^вых ) это не выполнено, то в сеть вводят новое coбытие, которому предшествуют только работы, предшествующие (u ^вых ), следя за выполнением П1 (однократным вхождением работы в сеть).

П5. Если условием для начала выполнения работы (u ^вых ) является окончание выполнения только части работы u ^вх ,то последняя должна быть представлена композицией двух последовательных работ,u1 ^вх , u2 ^вх после чего u ^вых в сети должна следовать непосредственно за u1 ^вх.

П6. Сеть должна быть правильно заиндексирована. Индексируются все события и работы и притом однозначно. Если события уже заиндексированы, то индекс работы uможет быть образован как упорядоченная пара индексов < , > где I(x) есть индекс события xÎ X . Для снятия индексной омонимии работ между двумя событиями сети должно быть не более одной работы. Если это не выполнено, то вводятся дополни­тельные события по одному на каждую из параллельных работ и по одной связи этих "новых” событий с одним из "старых”.

В качестве индекса события удобно брать натуральные чи­сла (номера)N(x), таким образом, чтобы по сравнительной величине номеров можно было делать заключение о логическом следовании (эта часть правила не является обязательной), т.е. если x>y ÞN(x)<N(y), где <x,y > Î U, x,yÎX.

Одам из способов правильной нумерации (носит название метода рангов) состоит в следующем.

Рангом вершины в ориентированном графе без контуров называется длина пути максимальной длины, соединяющего дан­ную вершину с исходной.. При этом длина путей определяется как число составляющих эти пути дуг. Все вершины графа разбиваются на группы вершин одного ранга по следующему алго­ритму. Исходной вершине сети приписывается ранг r(I)=0 , так как ему предшествуют только пути нулевой длины. Удаляются все дугиu: =I и в оставшейся части графа помечаются вершины без входящих дуг (в полном графе такая вершина всегда единственна), которые образуют группу вершин первого ранга, так как все они связаны с Iпутями, состоящими из единст­венной дуги. Если получены вершины ранга r то после их удаления оставшиеся без входящих дуг вершины будут иметь по определению ранг (r+1) Поскольку сеть конечна, число шагов алгоритма также конечно. После разбиения всех вершин на груп­пы нумерация осуществляется следующим образом;

N( I ) º 0; N(x’) =

где - число вершин первого ранга;

N( x ^r )=

где - число вершин первых r рангов.

Внутри группы номера из отведенного диапазона paсставляются произвольно, Поскольку каждой вершине r ранга обязательно предшествует вершина (r-1) - ранга, то нумерация оказывается правильной. Алгоритм можно использовать и на этапе построения сети для выявления контуров: если они есть, то на определенном шаге алгоритма все оставшиеся вершины будут иметь хотя бы одну входящую дугу.

При построении СМ типа С/N/Д,N > 1 необязательным является правило П2. Однако для применения алгоритма правильной нумерации формальное его выполнение полезно осуществить.

Построение СМ типа С/N/H

Пусть N=1. В СM типа С/N/Д каждое событие можно рассматривать как импликацию вида: , где i, j - индексы работ, предшествующих и следующих за событием соответственно, а /\ - знак конъюнкции. Однако практика дает основания для введения в СМ событий других типов с использованием логических связок дизъюнкции (соединительного V или разделительного ИЛИ). Например, тип события может быть:

Оно означает, что как только будет завершена хотя бы одна из работ , возникают условия для выполнения одной (и только одной) из работ .

Таким образом, наступление события при одном и том же множестве { } может быть определено тремя разными способами, теми же способами могут быть определены и условия для выполнения работ { }. Возможно таким образом oпределить девять типов событий.

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

Рис. 1. Типы событий в СМ

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

Под ЧСС события на входе понимается количество работ из множества { u_i ^вх }, которое должно быть выполнено, чтобы событие наступило. ЧСС принимает значения

от 0 (для исходного события) до ê{ }ê, где êxê - число элементов в множестве Х. При ЧСС = 1 реализуется логика " ", при ЧСС = ê{ }ê реализуется логика “/\”, при промежуточных значениях реапизуется одна из разновидностей логики ИЛИ. Аналогично вводится ЧСС события на выходе. Использование понятия ЧСС позволяет упростить графическое изображение, сведя его к виду, изображенному на рис. 1б. Если ЧСС_вых < ê { } ê, но ê { } ê > 1, то вершина называется “ветвящей”. Возможны типы событий, использующие понятие ЧСС только по входу (см. рис. 1в), а по выходу использующие обычные логические связки, и наоборот.

Таким образом, в сетях с недетерминированной структурой не требуется выполнения всех работ комплекса: некоторые работы могут оказаться не выполненными ни разу, а конечная цель КР будет все же достигнута. Более того, одна и та же работа может быть выполнена более одного раза (многократно), хотя на сети ей соответствует только одна стрелка. Это означает, что в графе сети имеются контуры различной длины. Указанные особенности приводят к тому, что при построении сети не обязательны правила П3 и П6. Остальные правила остаются всиле. При наличии контуров в сети события также будут наступать многократно. В этих случаях ЧСС задается для каждой реализации события (рис. 1г).

Если N > 1, то остаются в силе замечания, сделанные относительно CM типа C/N/Д, с учетом новых типов событий.

Построение СМ КР ЦНТП.

В качестве иллюстрации правил и процедур построения СМ КР на основе СЛП ниже приводятся простейшие примеры СМ КР ЦНТП. Пусть проектируется одноцелевая НТП по созданию структурно простого ОНТ . СЛП ОНТ имеет вид (3) . ИЛМ ОНТ трехуровневая.

Тогда все состояния ЖЦОНТ отображаются графом, представленным на рисунке 2. В графе существует 42 различных полных пути, каждому из которых соответствует свой вариант развития объекта , свой ЖЦ. Пусть выбран для определенности путь, соответствующий стратегии ”лучше больше информации, но о меньшем числе компонент”. Этот путь для наглядности показан двойными стрелками. Изоморфной СМ для этого СЛП ОНТ будет цепной граф, каждой вершине которого - событию - соответствует состояние ОНТ, а каждой дуге-работе соответствует ОС, осуществляющая преобразование состояния, описанное в п. 1.1.4. Очевидно, что это СМ типа С/1/Д.

Рис. 2. Граф состояний ОНТ L=5, R=3.

Пусть теперь СЛП ОНТ имеет вид (3а). Траектория развития объекта остается прежней. Однако теперь в результате деятельности ОС “наука” создается несколько вариантов значений каждой компоненты СЛМ. СМ, соответствующая этому случаю, приведена на рис. 3. Для наглядности и простоты принято, что у каждой компоненты имеются два альтернативных значения. В результате выполнения всех работ (детерминированная структура СМ) было бы создано 32 различных ОНТ, образующих один двумерный ПНТ, либо 2 одномерных ПНТ по 16 элементов в каждом. На рис. 3,а представлен фрагмент СМ, соответствующий значениям компонент V1 , P11, L111, и приводящий к созданию четырех ОНТ. Структура данной СМ может рассматриваться и как недетерминированная (рис. 3б), если все вершины первых пяти рангов рассматривать как ветвящие. Эта СМ является базовой по отношению к целому ряду СМ, отличающихся количеством и составом ОНТ, и последовательностями их достижения. На рис. 3в представлен вариант СМ, полученной из базовой путем введения последовательной (вместо параллельной) разработки каждого ОНТ.

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

Рис.3. СМ ЦНТП различных типов:

a-С/4/Д; б-C/4/H; с-C/1/Д

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

1.3. Структурные преобразования СМ

Современные методы проектирования СМ. широко используют типовые СМ относительно самостоятельных (частных) КР, так называемых организационных модулей, из которых путем объединения (иногда говорят “сшивания”) получают сводные СМ более масштабных КР. Частные СМ возникают и при многоэшелонной организации работ с участием нескольких исполнителей.

СМ реальных ЦНТП могут быть значительно сложнее за счет детализации СЛП по основаниям: структурная сложность ОНТ; структуризация ЖЦ OC; структуризация комплексного обеспечения ОС. Большие размерности полученных структур сводных СМ вынуждают применять специальные процедуры структурных преобразований CM для более сжатого их описания.

Таким образом, необходимы процедуры объединения (сшивания) и сжатия (укрупнения) СМ.

1.3.1. Структурные преобразования СМ типа С/N/Д

Объединение CМ. Пусть две объединяемые СМ, заданные своими графами ( , ), i = 1,2имеют тип C/1/Д. При построении сводной СМ (ее граф ( , )) необходимо учесть отношения следования между работами, принадлежащими разным частным СМ, которые заданы в виде

{< u ₁, u ₂ >}, где u_i Є U_i, i = 1,2.

Пусть такая пара единственна, Эти работы называют сопряженными.

Процедура построения G₀(X₀, U₀)выглядит следующим о6разом.

1. Строится = U и = U

2. Поскольку между двумя событиями, являющимися общими для и , могут оказаться две работы, что противоречит правилу построения П6, то необходимо ввести дополнительные события и работы-связи (п. 1.2.2). Таким образом строятся новые множества: = U и = U

3. Если событие имеет несколько предшествующих работ в и/или если имеет несколько последующих работ в , а также, если u ₁ - составная работа, то для обеспечения адекватности отражения в связи < u ₁, u ₂ > необходимо выполнить правила П4, П5 (п. 1.2 .2), путем введения дополнительных событий = { , } и дополнительных работ связей ={< , >, < , >, < , >}. Таким образом,

= U и = U .

4. Поскольку начальные и конечные события в и мoгут не совпадать, то необходимо обеспечить выполнение правила П2 (п. 1.2.2) вводом событий = { , } и работ – связей

= {< , >, < , >, < , >, < , >}.

Таким образом, окончательно

= = U ; = = U

5. С тем, чтобы выполнить правила П3, П6 (п. 1.2.2) необходимо правильно занумеровать сводную сеть и исключить контуры, если они обнаружены. Таким образом, построенная сводная СМ удовлетворяет всем правилам, принятым для данного типа структур СМ. Очевидно, сказанное распространяется на произвольное количество объединяемых сетей и пар сопряженных работ.

Примерыобъединения:

1) X 1 Ç X2 = {( I2º C1)} - последовательное сопряжение KP;

2) X 1 Ç X2 = {( I1º I2), ( C1 ºC 2)} - параллельное сопряжение КР.

Укрупнение СМ. Разработано два типа процедур укрупнения графа G(x, U)СМ типа С /N/Д:

а) по заданному подграфу G’(Х’,U’);

б) по заданным (этапным) вершинам-событиям

а) Укрупненным графом ( , )называется граф, в котором:

1. = X/X’вн, где X’внX’ - множество внутренних, X’гр Х' - множество граничных вершин подграфа:

= , = 0;

, если u U : ( ) ( );

, если u = < , > u = < , > u ,

т.е. из укрупняемого графа удаляются все внутренние вершины подграфа .

2. = , где u , если ( ) ( );

u , если ({ , } ) ( L( , ) | ( L( , ))) ,

т.е. новые дуги заносятся в только между граничными вершинами G’ и только в том случае, если они были связаны в G’ путями {L}, не содержащими других граничных вершин.

СЛП (содержание) новых работ определяется через СЛП работ-путей {L}.

б) Укрупненным графом ( , )называется граф, в котором:

1. = ({I,C} по соглашению).

2. = , где новые работы-дуги заносятся в по тем же правилам, что и в случае а). Поэтому обобщением случаев а) и 6) является процедура укрупнения по заданному подграфу и заданным вершинам - событиям этого подграфа, при которой задается G’(X’, U’) и одновременно задаются некоторые вершины , которые должны быть сохранены.

Принцип процедур укрупнения основан на обеспечении в G(X ,U) той же связности (топологической эквивалентности) сохраняемых вершин (новых вершин не появляется).

Разукрупнение СМ. Иногда граф G(X ,U)"разрезают” на фрагменты так, что они образуют упорядоченное множество (эту процедуру иногда называют разукрупнением СM). В этом случае анализ может вестись пофрагментно, что значительно проще практически.

Простейшими числовыми характеристиками структуры СМ типа Р(С)/N/Д являются: число событий; число работ; наибольший ранг собьгтия; число путей в графе между двумя заданными вершинами (число полных путей /L(I,С)/; число путей, предшествующих данному событию x - /L(I,x)/; число путей, следующих за данным собьггием x - /L(х,С)/; число полных путей, проходящих через данное событие x -/L(I,x,C)/; число полных путей, проходящих через данную работу <x, y>-/L(I ,<x, y>,C)/.

Все они характеризуют с той или иной стороны сложность и связность графа сети.

Аналогичные характеристики структуры имеют место и для СМ типа Р(С)/N/H, Однако появляются и дополнительные.

1.3.2. Структурные преобразования СМ типа С/N/С

Объединение СМ происходит по правилам, которые должны быть согласованы с правилами построения объединяемых сетей рассматриваемого типа. В частности, при выполнении операций над множествами и необходимо контролировать логические типы событий по входу и по выходу, переопределять ЧСС.

Укрупнение СМ также проводится с некоторыми новыми особенностями. Пусть недетерминированность структуры имеет характер стохастичности, точнее, случайности, т.е. каждая работа uÎUбудет иметь вероятность ее осуществления в составе данного комплекса (аналог величины степени принадлежности элемента u нечеткому множеству U), Î(0,1].Укрупненность СМ будет означать построение более простой, но топологически эквивалентной по отношению к сохраненным событиям сети. Топологическая эквивалентность будет характeризоваться теперь количественно, как постоянство вероятности достижимости вершин графа. На рис. 4,а-е приведены простейшие характерные примеры процедур укрупнения по подграфу. Укрупненная сеть будет иметь вид G°=({I,C}, { }), т.е. единственной дуги с сохраненными граничными событиями укрупняемой сети.

Рис. 4. Примеры укрупняемых фрагментов СМ типа С/1/С

В некоторых случаях СМ типа C(P)/N/C могут быть oписаны с помощью хорошо разработанного аппарата конечных цепей Маркова, например случаи д и е на рис. 4. Базовой характеристикой таких СМ является функция распределения вероятностей векторной случайной величины {n₁, ...,n_x, ..., n_c}:

F(n_I, ..., n_x, ..., n_c) = P{n_{1 £} n_I Ù _… Ù n_{x £} n_x Ù ... Ù n_c £ n_c },

где n_x - целочисленная случайная величина, равная кратности свершения события х для n_c -кратного достижения завершающего события, в частности для случая = 1

Знание этой функции позволяет рассчитать любые топологические параметры СМ, представляющие интерес для руководства КР, например Е[n_x], D[n_x] xÎX, а также Е[n_u], D[n_u], uÎU.

Для преобразований и анализа сетей более общего вида рекомендуется использовать имитационное моделирование CM на ЭВМ.

Упражнения к главе 1

1. Построить и сравнить графы состояний РО при а) L = 3, R = 2; б) L = 3, R = 3; в) L = 3, R = 4

2. Построить и сравнить графы состояний при а) L = 4, R = 3, б) L = 6, R = 3

3. Подсчитать число различных траекторий развития объекта в каждом из случаев упражнений 1, 2

4. В графе состояний РО (L = 5, R = 3) выбрать ветвящую вершину и сформулировать правила выбора каждой альтернативы

5. Построить граф состояний для системы Q = <V, P, L>, состоящей из двух подсистем

6. Построить СЛП ОНТ и программы работ по его созданию (по профилю специальности)

7. Построить процедуры преобразования: а) СМ типа P/N/Д в СМ типа C/N/Д; б) СМ типа С/N/Д в СМ типа P/N/Д

8. Построить и правильно занумеровать полную сеть типа С/1/Д, у которой çxçравно a) 4, б) 5

9. Построить СМ КР по созданию системы из упр. 5 типа С/N/H c числом альтернатив в каждой вершине равным двум

10. В каких случаях для нумерации СМ типа С/N/H может быть использован метод рангов?

11. Обосновать алгоритм правильной нумерации событий сети, в частности, доказать, что

a) после удаления из графа вершин x : r(x) £ r в графе найдется по крайней мере одна вершина без входящих дуг;

б) вершины одного ранга не связанны между собой дугами.