2.5.2. СЕТЕВОЕ ПЛАНИРОВАНИЕ (РАСЧЕТ ПО МЕТОДУ PERT) С НЕЧЕТКИМИ ОЦЕНКАМИ ПРОДОЛЖИТЕЛЬНОСТИ РАБОТ

Рассматривается классическая задача организации проекта, разбитого на отдельные работы. Множество работ образует семейство дуг некоторого ориентированного графа без циклов. Эти дуги отражают ограничения на порядок следования работ, причем каждой дуге приписывается определенное значение продолжительности выполнения соответствующей работы. Известны самый ранний срок начала проекта и при необходимости — самый поздний срок его окончания Таким образом, здесь используется представление типа «потенциал — этапы” [14].

Бывают ситуации, когда сроки выполнения работ априори плохо известны и оцениваются субъективно. Их можно естественным образом представить в виде нечетких интервалов. Обозначим через нечеткую продолжительность выполнения работы, характеризуемой дугой в графе , где — вершины графа.

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

нумеруют вершины графа по возрастающим рангам (см. алгоритм нумерации в работе

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

где множество работ, предшествующих -й работе.

Упорядочение вершин обеспечивает выполнение условия

Самый ранний срок окончания проекта

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

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

Рис. 2.8

Когда продолжительности работ точнб не известны и представлены нечеткими интервалами, то этот алгоритм остается справедливым при замене операций сложения, вычитания, максимизации, минимизации их расширениями на отучай нечетких аргументов (разд. 2 3.2 и 2.3.3, работы [4,5]).

В программе, помещенной в приложении, можно найти процедуры, реализующие указанные операции на нечетких интервалах Дня операции максимизации и минимизации используется вариант аппроксимации с использованием формулы (2.38). Если Эта приближеннаяоперация еще сохраняет свойство ассоциативности. Расширенная операция получается точно так же заменой максимума на минимум в вышеприведенном выражении. На практике рассматриваются трапециевидные нечеткие интервалы. Становится возможным прямое обобщение алгоритма расчета самого раннего и самого позднего сроков наступления событий благодаря тому, что в нашем случае его результаты суть монотонные функции данных; следовательно, можно избежать проблем, связанных с несобственными представлениями этих результатов (разд. 2.4).

Рассмотрим пример, изображенный на рис. 2.8, со следующими нечеткими оценками продолжительности работ:

Зададимся самым ранним сроком начала проекта и самым поздним сроком его окончания . Легко получить следующие результаты:

Например, время

Интервал становится интервалом, ограниченным нечеткими величинами; критичность вершины становится в большей или меньшей степени неопределенной в зависимости от того, насколько накладываются друг на друга нечеткие числа и Например, такое наложение наблюдается для вершины 1. Понятие критического пути обсуждается в гл 3 (а также в гл 7 работы [4]). В приложении дана программа вычисления распределений в виде трапециевидных нечетких интервалов.

Замечания. 1. Когда данные являются точными, вершины, лежащие на критическом пути, определяются расчетом самого позднего срока работ из условия равенства срока окончания проекта самому раннему возможному сроку окончания проекта Тогда вершина, расположенная на критическом пути, находится из условия При анализе неточных данных такая процедура уже не имеет смысла, так как величина отражает неточность данных о продолжительности работы Поскольку эта неточность может возрастать, имеется риск ее двукратного учета при вычислении Т, из условия Следовательно, здесь необходимо определять величину независимо от величины (более детально вопрос об определении самого раннего и самого позднею сроков окончания работ при сетевом планировании в нечеткой среде обсуждается в работе [4]).

Другой подход к той же задаче сетевого планирования с неточно известными данными заключается в рассмотрении величин продолжительности работ как случайных переменных. Однако в силу возникновения проблем зависимости между различными путями графа, а следбвательно, и между переменными, связанными с величинами и известные алгоритмы поиска кратчайшего или, наоборот, длиннейшего пути трудно приспособить к вероятностным исходным данным. Известно, что построение вероятностного аналога метода PERT - труднорешаемая проблема, в то время как вышеизложенный подход, основывающийся на нечетких величинах, оказывается более простым для практической реализации благодаря тому, что в нем рассматриваются наихудший и наилучший случаи, а также потому, что в силу результатов, полученных в разд 2.4, стандартный алгоритм сетевого планирования в применении к нечетким данным дает точные распределения возможностей дня и (более детально это анализируется в работе [4]).