Сетевая модель и ее основные элементы.
При управлении разработками сложных программ возникает задача рационального планирования и координации большого комплекса различных работ. Примером может быть разработка и освоение выпуска новой сложной техники. Характерным для таких сложных комплексов, связанных между собой работ, является то, что отдельные работы не могут быть выполнены независимо друг от друга, выполнение ряда работ не может быть начато раньше, чем завершены другие.
Системы сетевого планирования и управления (СПУ) обеспечивают системный подход к решению вопросов организации управления, т. е. рассмотрение всего комплекса работ как единого неразрывного комплекса взаимосвязанных работ, направленных на достижение общей конечной цели. Логико-математическое описание, формирование планов и управляющих воздействий в этом случае осуществляется на базе использования особого класса моделей, называемых сетевыми моделями. Поэтому начнем знакомство с этими моделями с изложения понятия сетевой модели.
Основным плановым документом в системе СПУ является сетевой график (сетевая модель или сеть), представляющий собой информационно-динамическую модель, в которой отражаются взаимосвязи и результаты всех работ, необходимых для достижения конечной цели разработки.
Простейшая одноцелевая сетевая модель на небольшом комплексе работ показаны на рис. 1.
Рис. 1. Пример сетевого графика небольшого комплекса работ
Сетевая модель изображается в виде сетевого графика (сети), состоящего из стрелок и кружков.
Ориентированный граф, в котором существует лишь одна вершина, не имеющая входящих дуг, и лишь одна вершина, не имеющая выходящих дуг, называется сетью. Сеть, моделирующая комплекс работ, называется его сетевой моделью или ее сетевым графом. Дуги, соединяющие вершины графа, ориентированы в направлении достижения конечного результата при осуществлении комплекса работ.
Наиболее распространен способ представления моделируемого комплекса работ в понятиях событий и работ.
Понятие «событие» означает факт получения результатов вследствие завершения одной или небольших работ. Каждая работа заключена между двумя событиями, так как с события, завершающего одну или несколько работ, начинаются другие работы. Событие может наступить только тогда, когда окончатся все предшествующие ему работы.
Событие, с которого начинается выполнение всех работ комплекса, называется исходным. Исходное событие не имеет предшествующих ему работ и событий.
Событие, которым заканчивается выполнение всех работ комплекса, называется завершающим. Завершающее событие не имеет последующих за ним работ и событий.
Событие, непосредственно предшествующее работе (с которого начинается работа), называется начальным, а непосредственно следующее за ней (которым заканчивается работа) называется конечным.
Н а сетевой модели событиям соответствуют вершины графа и обозначаются: графически:
Событие, для наступления которого выполняется одна работа, называется простым, а если выполняются две и более работ, то такое событие называется сложным.
Работа – это тот или иной процесс между двумя событиями. Понятие «работа» имеет следующие значения:
- «действительная работа» – процесс, требующий затрат времени и ресурсов. На графе изображается сплошной стрелкой
- «фиктивная работа» – логическая связь между двумя или несколькими работами, указывающая на то, что начало одной работы зависит от результатов другой. Фиктивная работа не требует затрат времени и ресурсов. Ее продолжительность равна нулю. На сетевой модели фиктивная работа изображается пунктирной стрелкой.
Работы на сетевой модели изображаются стрелками между двумя событиями i и j, где i – начальное событие, а j – конечное событие данной работы.
Любая последовательность работ в сетевой модели (сетевом графе), в которой конечное событие одной работы совпадает с начальным событием второй следующей за ней работы, называется путем. В сетевой модели различают несколько видов путей:
- путь от исходного события до завершающего события называется полным путем;
- путь от исходного события до данного – путь, предшествующий данному событию;
- путь от данного события до завершающего – путь последующий за данным событием;
- путь между какими-либо промежуточными событиями – путь, последующий за данным событием;
- путь между какими-либо промежуточными событиями – путь между событиями i и j;
- полный путь наибольшей продолжительности называется критическим путем.
Каждой дуге (работе) сетевой модели приписывают число, называемое длиной дуги (продолжительностью работы). Соответственно длиной пути называется сумма длин последовательности дуг (работ), составляющих данный путь. Длина дуги выражает время, необходимое для выполнения работы, представленной данной дугой.
Начальная информация, необходимая для построения сетевой модели, должна содержать перечень всех работ и последовательность их выполнения, т. е. отношения непосредственно предшествования между работами комплекса.
Работы (дуги) на сетевых графиках обозначают индексами i и j, где i – номер начального события работы, а j – номер конечного события. События должны быть пронумерованы так, чтобы для любой работы (в том числе и фиктивной) всегда i j. Для получения такой нумерации применяется метод разделения событий на ранги, сущность которого заключается в следующем.
Исходному событию присваивается нулевой ранг. Вычеркнув все дуги (работы), выходящие из исходного события, определяют события, не имеющие входящих дуг. Этим событиям присваивается первый ранг. Вычеркнув все дуги, выходящие из событий первого ранга, снова получим события без входящих дуг. Им присваивается 2-й ранг и т. д.
После распределения всех событий по рангам нумерация событий осуществляется следующим образом. Исходное событие нулевого ранга получает номер 0. Событиям первого ранга в произвольном порядке присваиваются номера от 1 до n1, где n1 – число событий первого ранга; событиям второго ранга присваиваются номера от n1+1 до n1+n2, где n2 – число событий второго ранга и т. д.
В зависимости от задач управления в системах СПУ применяют различные типы сетевых моделей, отличающихся составом информации о комплексе работ. Среди них можно выделить два основных типа: модели с учетом только временных характеристик (ограничения на ресурсы не накладываются) и модели с учетом временных и ресурсных характеристик.
Модели первого типа не являются оптимизационными. Но, несмотря на это, их применение в системах СПУ позволяет эффективно решать существенные проблемы управления, а именно – найти минимальное время, в течение которого может быть выполнен весь комплекс работ. И определить календарные сроки начала и окончания каждой работы комплекса, обеспечивающих выполнение всего комплекса в найденное минимальное время.
Модели второго типа относятся к задачам распределения ресурсов. Эти задачи являются оптимизационными и встречаются в различных постановках. В зависимости от принятого критерия оптимальности и характера ограничений их можно разбить на две основные группы.
- задачи минимизации сроков наступления завершающего события при соблюдении заданных ограничений на использование ресурсов.
- задачи оптимизации некоторого показателя качества использования ресурсов при заданных сроках выполнения комплекса работ. К этой группе можно отнести в частности задачу минимизации ресурсов при заданном времени выполнения комплекса работ.
Основной временной характеристикой комплекса работ и каждой отдельной работы является их продолжительность. Оценки продолжительности выполнения отдельных работ могут быть детерминированными и вероятностными. Первые используются в тех случаях, когда предполагаемая продолжительность работ может быть оценена точно с относительно небольшой ошибкой. Если и ее продолжительность работы не поддается точному определению и представляет собой случайную величину, используются вероятностные оценки. В первом случае сетевая модель называется детерминированной, во втором – вероятностной. Сетевые модели могут быть также смешанными, поскольку для некоторых работ могут существовать детерминированные оценки, а для некоторых – вероятностные.
Продолжительность работы i, j обозначают tij. Оценка величины tij проводится:
- по действующим нормативам;
- по накопленным данным с достаточно высоким % повторяемости работ;
- методом экспертных оценок;
- на основе вероятностных оценок.
На основании статистических данных установлено, что распределение случайной величины t ij определяется так называемым бэта-распределением. Это распределение имеет место в тех случаях, когда случайная величина зависит от большого числа случайных факторов, оказывающих незначительное влияние, и от нескольких существенно влияющих факторов.
В системах СПУ используются три вероятностные оценки:
- t min ij – минимальное время, необходимое для выполнения работы при наиболее благоприятных условиях;
- t max ij – максимальное время, необходимое для выполнения работы при наименее благоприятных условиях;
- t нб ij – наиболее вероятное время выполнения работы при нормальных, наиболее часто встречающихся условиях.
Все эти оценки даются ответственными исполнителями или экспертами.
Величины t min ij, t max ij, t нб ij используются для вычисления ожидаемого значения продолжительности работы tожij, представляющего собой математическое ожидание случайной величины t ij и среднеквадратического отклонения y, характеризующего степень разброса реального закона распределения случайной величины t ij от принятого бэта-распределния. Кривая бэта-распределения имеет вид:
Вследствие различного подхода к учету возможного отклонения реального закона распределения от принятого бэта-распределения и ошибок в определении величин tminij, tmaxij, tнбij, а также некоторых других факторов создано несколько пар зависимости для расчета tожij и y. Из них в системе СПУ наиболее часто применяются следующие пары зависимостей:
При степени охвата работ различают первичные, частные и комплексные сетевые модели.
Первичные сетевые модели представляют собой детализированные изображения частей комплекса и составляются ответственными исполнителями работ. Частные сетевые модели стоятся на основе первичных.
Сшивание частной модели заключается в объединении первичных моделей в одну общую модель, завершающее событие (события) которой соответствует заданной частной цели (целям). Для сшивания частной модели необходимо строго установить идентичность граничных событий в первичных сетевых моделях.
Комплексная (сводная) сетевая модель охватывает все работы комплекса. Сшивание комплексной модели производится аналогично сшиванию частных моделей.