Нахождение критического пути в сетевом планировании в условиях нечеткого задания времени

2. Скороход СВ. Моделирование целей управления в условиях неопределенности / Информационные системы и технологии в управлении и организации производства. Труды международной конференции «Татищевские чтения: актуальные проблемы науки и практики». - Тольятти: Изд-во Волжского университета им. В.Н.Татшцева, 2004. - С. 253-258.

3. Скороход СВ. Применение нечётких чисел для оценки квалификации персонала / Известия

ТРТУ, Тематический выпуск «Интеллектуальные САПР». - Таганрога: Изд-во ТРТУ,

№3(47), 2005. - С. 214-216.

М. В. Курмаз

НАХОЖДЕНИЕ КРИТИЧЕСКОГО ПУТИ В СЕТЕВОМ ПЛАНИРОВАНИИ В УСЛОВИЯХ НЕЧЕТКОГО ЗАДАНИЯ ВРЕМЕНИ

Задача сетевого планирования состоит в том, чтобы графически, наглядно и системно отобразить и оптимизировать последовательность и взаимозависимость

, , достижение конечных целей. Для отображения и алгоритмизации тех или иных действий или ситуаций используются экономико-математические модели, которые называются сетевыми моделями, простейшие из них - сетевые графики.

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

Основными образующими элементами сетевой модели являются события и работы.

Термин работа используется в сетевом планировании для обозначения процессов и связей между событиями.

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

мгновенно. Поэтому каждое событие, включаемое в модель, должно быть полно и , -посредственно предшествующих ему работ.

События сетевого графика - это вершины графа (обычно изображаются кружками), работы - дуги графа (обычно обозначаются стрелками).

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

Критический путь имеет свое особое значение, так как работы, входящие в , , при помощи сети. Для сокращения сроков выполнения проекта необходимо в первую очередь сокращать продолжительность работ, лежащих на критическом пути.

Основные правила построения сетевых моделей:

♦ Использовать максимально-рациональное запараллеливание работ, обеспечивающее возможное сокращение сроков разработки;

♦ Сетевая модель (график) не должна содержать тупиковых событий, кроме

, ;

♦ Не должно быть событий, в которые не входит ни одна работа , кроме ис-

;

♦ Сетевая модель не должна с одержать замкнутых контуров;

♦ Направление стрелок, обозначающих работы, должно быть слева-направо, от исходного события к завершающему событию.

Составление сетевого графика.

Каждый кружок-событие делится на 4 сектора. В верхнем левом секторе кружка проставляется номер события (1,2,3,...п). На рис.1 представлена схема фрагмента построения сетевого графика в общем виде, в котором 1 - номер предшествующего события; ] - номер последующего события; 11-] - продолжительность работы, соединяющая 1-е и ]-е события.

Рис.1. Схема фрагмента построения сетевого графика

В правом верхнем секторе указывается ранний срок свершения события 1р. Ранний срок свершения исходного события принимается равным нулю. Ранний срок свершения последующего (]) события определяется: к раннему сроку предше-(1) , два события. Если к событию ведут несколько путей (узловое событие), то в расчет принимается максимальная сумма: 1р] = тах (ф1 + 11]).

, -порядке их номеров, рассчитываем ^ всех событий от исхо дного до завершающего. После заполнения правых секторов сетевого графика

рассчитывается критический путь ( Ькр.) - максимальный срок выполнения всего комплекса работ при данной организации ОКР.

В правом нижнем секторе указывается поздний срок свершения события Ш. , , , пути, поздний срок равен раннему, т.е. для этих событий в правом секторе записываем то же число, что и в левом. ф = Ь1. Определение позднего срока свершения события начинается с завершающего события, т.е. с конца графика и ведется строго в обратном порядке, приближаясь к исходному событию.

Поздний срок получаем вычитанием из позднего срока последующего события продолжительности работ. Если от данного события к исходному идут не, -мальную из них 1п1 = тш (^ - 11]).

Расчет резервов времени работ:

Любая из работ, не лежащая на критическом пути обладает резервом времени.

Полный резерв времени работ Яп (1-]) равен разности между поздним и ранним сроками свершения событий ] и 1 за вычетом продолжительности этой работы: Яп (1-]) = - 1р1 - 1(1-]).

Свободный резерв времени работы Ис (1-]) равен разности между ранними сроками свершения событий ] и 1 за вычетом продолжительности работы (ь|): Ис (1-]) = 1р] - 1р1 - 1(1-]). Свободный резерв является независимым резервом, т.к его использование на одной из работ не меняет величины свободных резервов времени остальных работ и показывает, насколько можно задержать выполнение или отсрочить начало данной работы, не меняя ранних сроков начала последую.

Резерв времени свершения события И равен разности между поздним и ранним сроками свершения данного события: И = Ш1 - 1р1.

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

♦ Необходимое условие: нулевые резервы событий, лежащих на его пути;

♦ Достаточное условие: нулевые полные резервы работ, лежащих на критическом пути.

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

Интервал I задается его левой 11 и правой И границами, т.е 1= [И , И]. Зададим в таблице 1 минимальное и максимальное время, за которое определенная работа может быть выполнена.

1

Исходные данные для задачи

Название работы Непосредственно предшествующие операции Длительность работы 1 = [И, И], дни

А - [3,5]

В - [5,7]

С А,В [6,8]

Б В [2,4]

Е С [3,5]

Б Б [4,6]

в Е,Б [2,4]

Теперь найдем критические пути и их длительности.

Согласно необходимому условию два полных пути модели Ь1=1,2,3,4,6,7 и Ь2=1,3,4,6,7 могут быть критическими. Проверим достаточное условие критичности для всех работ:

Яп(1,2) = 1п(2)4р(1)-1;(1,2)= [5,7]-[0,0]-[5,7] = [0,0];

Яп(1,3) = 1п(3)4р(1И(1,3)= [5,7]-[0,0]-[3,5] = [2,2];

Яп(3,4) = 1п(4)4р(3И(3,4)= [11,15]-[5,7]-[6,8] = [0,0];

Яп(2,5) = 1п(5)4р(2И(2,5)= [10,14]-[5,7]-[2,4] = [3,3];

Яп(4,6) = 1п(6)4р(4И(4,6)= [14,20]-[11,15]-[3,5] = [0,0];

Яп(5,6) = 1п(6)4р(5И(5,6)= [14,20]-[7,11]-[4,6] = [3,3];

Яп(6,7) = 1п(7)4р(6И(6,7)= [16,24]-[14,20]-[2,4] = [0,0].

Путь Ь2, начинающийся с работы (1,3) не является критическим, т.к. как первая из его работ не является критической. Работа (1,3) имеет ненулевой полный резерв, т.е. может быть задержана с выполнением, что недопустимо для критиче-. 2:

Таблица2

Название работы Длительность работы t = [tl, tr], дни Rn

A(1,3) [3,5] [2,2]

B(1,2) [5,7] [0,0] критич

C(3,4) [6,8] [0,0] критич

D(2,5) [2,4] [3,3]

E(4,6) [3,5] [0,0] критич

F(5,6) [4,6] [3,3]

G(6,7) [2,4] [0,0] критич

Сетевая модель имеет единственный критический путь Ькр=1,2,3,4,6,7 длительностью [16,24].

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. А.Кофман. Введение в теорию нечетких множеств / Пер. с франц. - М.: Радио и связь, 1982. - 432 с.

2. Jonathan L.Gross, Jay Yellen. Graph Theory and its application. Second Edition, 2006. Edited by: Chapman&Hall/CRC. Taylor&Francis Group.