автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Сетевое планирование в условиях нечетких ограниченных ресурсов

На правах рукописи

Князева Маргарита Владимировна

СЕТЕВОЕ ПЛАНИРОВАНИЕ В УСЛОВИЯХ НЕЧЕТКИХ ОГРАНИЧЕННЫХ РЕСУРСОВ

Специальность: 05.13.17-Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Таганрог-2012

005053362

005053362

Работа выполнена в Технологическом институте Федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет»

Научный руководитель: доктор технических наук, профессор,

Заслуженный деятель науки и техники РФ Берштейн Леонид Самойлович

Официальные оппоненты: доктор технических наук, профессор

Ковалев Сергей Михайлович, профессор кафедры Автоматики и телемеханики ФГБОУ ВПО Ростовского государственного

университета путей сообщения (РГУПС)

доктор технических наук, профессор Ромм Яков Евсеевич, заведующий кафедрой информатики Таганрогского государственного педагогического института (ФГБОУ ВПО «ТГПИ имени А.П. Чехова»)

Ведущая организация: Институт проблем информатики

Российской академии наук (ИЛИ РАН), г. Москва

Защита диссертации состоится ¡МОЖСи 2012 г. в на заседании диссертационного совета Д 212.208.21 ЮжАого федерального университета по адресу:

347928, ГСП-17А, Ростовская область, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального унивещц^а^по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148

Автореферат разе

,д НА)

й^^КОЕ оерЛ

.і ■■' * ї- сУ

Ученый секрета| диссертационног д.т.н., профессор

ао^ а ?

О

ЩМ'гг*

Щі ~

Чернов Н.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

При решении данных задач использовались элементы теории графов, нечетких множеств, исследования операций, методов оптимизации, представленных работами Л. Заде, Г. Вагнера, Л.С. Берштейна, А.Н. Борисова, Н. Кристофидеса, А. Кофмана и других авторов. Работы перечисленных ученых относятся к ряду фундаментальных работ по теории графов, исследования операций и теории нечетких множеств, положенных в основу исследований, проведенных в данной работе.

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

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

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

3. Разработать эвристический алгоритм планирования проектов на основе правил приоритета для нечетко заданных параметров модели. Описать возможные трудности при использовании нечетких чисел и способы их преодоления.

4. Рассмотреть задачу сетевого планирования нечеткого компромисса типа «время-затраты», предложить метод решения и способ представления оптимального решения поставленной задачи.

Методы исследования опираются на точные и эвристические методы оптимизации, теорию нечетких множеств при задании параметров модели.

Научная новизна диссертационной работы заключаются в следующем:

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

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

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

4. Предложен метод получения кусочно-линейной зависимости затрат проекта от времени его выполнения с помощью поточного алгоритма Фалкерсона для задачи нечеткого компромисса типа «время-затраты». Метод позволяет уменьшать длительность выполнения проекта за счет увеличения общих затрат, выражая кусочно-линейную зависимость общих затрат проекта как функцию длительности его выполнения.

Основные положения, выносимые на защиту

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

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

3. Алгоритм эвристического поиска с нечетко заданными параметрами модели в виде кусочно-линейной функции принадлежности на трех а-срезах на основе правил приоритета.

4. Метод решения задачи нечеткого компромисса типа «время-затраты» с помощью поточного алгоритма и алгоритма расстановки меток.

Достоверность полученных в диссертации результатов вытекает из математического обоснования предложенных алгоритмов поиска и подтверждается результатами программного моделирования и численного

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

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

Внедрение и использование результатов работы. Результаты диссертации внедрены в ФГУП «Федеральный Кадастровый Центр «Земля» Филиал по Южному ФО», в учебном процессе кафедры Прикладной информатики Технологического Института Южного федерального университета в г. Таганроге в курсах «Математические методы исследования операций» и «Системный анализ», что подтверждено соответствующими актами об использовании, приведенными в приложении 1 к диссертационной работе. Результаты диссертационной работы также использованы при выполнении научно-исследовательских работ, в том числе при выполнении фанга РФФИ №11-01 -ООО 11 а.

Апробация работы. Основные результаты работы представлены на 4-й Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные Технологии, Системный анализ и Управление» (Таганрог, 2006 г.), на научно-практической конференции «Управление Созданием и Развитием Систем, Сетей и Устройств Телекоммуникаций» (Санкт-Петербург, 2008 г.), на «Девятом Всероссийском Симпозиуме по Прикладной и Промышленной Математике» (Кисловодск, 2008 г.), на 10-й Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2010 г.), на 6-ой Ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН (Ростов-на-Дону, 2010 г.), на 17'* East-West Zittau Fuzzy Colloquium (Цитгау, Германия, 2010 г.)

Публикации. Результаты диссертации отражены в 10 печатных работах, в том числе в 5 работах, опубликованных в изданиях, рекомендованных ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, выводов по главам, заключения, библиографического списка и приложения. Работа выполнена на 177 страницах машинописного текста, содержит 56 рисунков и 13 таблиц. Библиографический список включает 73 наименования.

СОДЕРЖАНИЕ РАБОТЫ

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

ценность, реализация и апробация результатов работы, дано краткое содержание структуры диссертации.

В первой главе рассматривается задача минимизации времени выполнения проекта с ограниченными ресурсами, нечетко заданными параметрами модели. В качестве целевой функции в простейшем случае выступает время выполнения проекта. Каждая работа / имеет длительность выполнения, определенную как количество единиц, выраженных с помощью нечетких чисел при учете двух видов ограничений. Ограничения на предшествования требуют, чтобы каждая работа /' была спланирована только после окончания непосредственно предшествующих ей работ, включенных в группу планируемых работ />. Кроме того, для выполнения

каждой работы/'требуется г.к единиц четко-заданного ресурса к е И = {\,...,К} в течение каждого момента выполнения. Ограничения на ресурсы ограничивают количество единиц ресурса £ е Л = {1,...,/С} > доступного в каждый момент горизонта

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

Переменная решения / обозначает нечеткие конечные сроки выполнения

различных работ, а обозначает нечеткие длительности каждой из работ, ак -

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

работы в ресурсе типа к. Группа в выражении (4) обозначает набор работ,

которые выполняются в момент £ Целевая функция (1) минимизирует конечное нечеткое время выполнения конечной фиктивной работы. Выражение (2) определяет отношения предшествования, а выражение (3) показывает, что конечный срок первой фиктивной работы равен 0. И, наконец, выражение (4) показывает, что ни в один момент времени в течение периода выполнения проекта наличие и доступность использования ресурсов не может быть превышена. Для решения представленной задачи разработан алгоритм для формирования дерева решения, каждый узел которого представлен с помощью, так называемых, альтернатив, в которых рассматривается одновременно несколько работ, подходящих для планирования в определенный момент времени таким образом, что не будут превышены совокупные требования в данном ресурсе этой группой рассматриваемых работ. Для того чтобы формально описать процедуру построения дерева решений, введем следующие обозначения. Процедура ветвления

Мш /„,

(1)

(2)

(3)

(4)

начинается с планирования фиктивной начальной работы, в момент времени 0. Каждый уровень g дерева решения связан с определенной точкой решения /,

набором работ лр• в процессе выполнения, набором уг/ законченных работ, и

набором работ, пригодных для планирования. И введем так называемый

«способ планирования альтернатив зл», который определяет способ

представления работ, входящих в альтернативу, при построении расписания работ. Затем мы расширяем текущее частичное расписание путем планирования подгруппы пригодных (допустимых) работ в точке решения с учетом ограничений

на ресурсы. Более точно, альтернатива А - это подгруппа набора £/ , для

« £

которой г к ^р для каждого возобновимого ресурса к с А''' и д фа если

¿^ ]к. к В

¡еЛР^А^

ЛР =0. /?■» - уровень наличия ресурса, с1 - длительность выполнения работы_/. £ * ]

На текущем уровне g дерева поиска мы выполняем следующее: определяем новую точку решения и вычисляем набор пригодных для планирования работ.

Затем мы определяем набор способов ^А планирования альтернатив д для

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

альтернативу ^ путем планирования входящих в нее работ, вычисляем

приемлемый начальный срок для данных работ (или отдельной работы в альтернативе), который не должен быть меньше начального срока работ, входящих в альтернативу предыдущего уровня дерева поиска. Это условие является неотъемлемой частью алгоритма и обеспечивается тем, что при построении расписания (очередности следования работ) начальный срок (сроки) планируемых работ вычисляются как начальный срок работ в предыдущем узле + длительность работ предыдущего узла. Таким образом, данное условие будет всегда обеспечивать увеличение значения нижней границы 1Ь при прохождении вниз по дереву поиска

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

чтобы удовлетворить всем ограничениям и минимизировать нечеткую длительность выполнения проекта. Процедура поиска основана на методе ветвей и границ с помощью поиска в глубину. Это имеет смысл для стратегии ветвления тогда, когда правило ветвления выбирается динамически. Представленный подход является интеграцией приемов, при которых способы выполнения для работ и их начальные сроки выбираются одновременно. Пусть npoeicr состоит из конечного набора работ К = {0,1,...,я,я+ 1}- Фиктивная работа 0 представляет собой начало проекта, фиктивная работа п +1 завершает проект. Для каждой работы у 6 у набор д/. = {1 _ | |} представляет собой набор возможных способов выполнения

работы. Работы 0 и п +1 могут быть выполнены только одним способом: Л/0 := Mnt] := {1} • Каждая работа j е у должна быть выполнена только одним способом MeMj- Нечеткое время выполнения работы j, исполняемой с помощью способа и обозначим как р^ е z. Время выполнения работ 0 и п + \ равны 0 и обозначаются как: ptn := р^, = о •

Параметры ^ и g обозначают нечеткие начальный и конечный сроки выполнения работы j, соответственно. Если величина s0 := (0,0,0). тогда величина будет обозначать длительность выполнения всего проекта. Если работа j начинается в момент с помощью способа р, и будет выполняться в каждый нечеткий момент времени t e[Sj,Sj + pJfl)• Между началом §. работы j, которая выполняется с помощью способа ¡j е м , и началом s, работы / (l^j), которая выполняется с помощью способа х е М,, возможен минимальный нечеткий временной промежуток d . , е Z или максимальный

min j f,'х

нечеткий временной промежуток dmiK . ^ 6 Z>0 ■ Отметим, что временной

промежуток между работами j и / зависит от способа выполнения или способа я.

Обозначим через а = (М, S, Т) := {j е V | Sj < Т < Sj + pj } набор работ,

выполняющихся в момент времени Г для расписания (M,S), тогда задача сетевого планирования с несколькими способами выполнения работ, максимальными и минимальными временными промежутками может быть предстаапеиа следующим образом:

(5)

при условии:

S.-SjZS^, ((jj)eE).

(6)

X rlmkp<Rkp. (keR>;t>Q), (7)

сю

M'

nij e Mj, (j t V), (9)

SjtO.(jcV), (10)

5.=0- (11)

Целью является определение такого расписания (M,S), которое бы удовлетворяло условиям нечетких временных промежутков (6), ограничениям на возобновимые ресурсы (7), невозобновимые ресурсы (8) и минимизировалась целевая функция - нечеткая длительность выполнения проекта (5). Такое расписание будем считать оптимальным. Расписание (М,$), удовлетворяющее (6)-(8), будем считать приемлемым.

Ветвление для построения дерева поиска решений методом ветвей и границ основано на одновременной оценке решений, необходимых доя приписывания работе способа выполнения {разрешения способов выполнения) и разрешении конфликта ресурсов (разрешения ресурсов), необходимых для нахождения приемлемого расписания. Для временного анализа модели были разработаны две процедуры для вычисления вектора нечетких ранних сроков начала работ ES-{ESj)jey• ¿i„+l является нечеткой нижней границей, основанной на

минимальной длительности выполнения проекта, и необходимой доя оценки альтернатив. Обе процедуры основываются на специальных релаксациях задачи, основанных на ресурсах, и используют верхнюю границу d, основанную на минимальной длительности выполнения проекта. Они могут приписывать фиктивные способы выполнения работам, отраженные в А7) дизъюнктивные отношения предшествования, отраженные с помощью EJ". Первый алгоритм опирается на текущую сеть NM , в то время как второй алгоритм основывается на расширении текущей сети N. Алгоритм 1. FOR JeV DO еЩ := ¿70AJ

stop:= FALSE WHILE NOT stop DO stop:= TRUE FOR (p,l)eEJ,s DO

IF f£/< mines'+t?f) THEN

siop:=FALSE;

ES! :=min76l,(£5;+,?f)

FOR jeV

DO ES/ := max {ES', ES' + d,f} IF £5„'+1 > d THEN stop:=TRUE RETURN ES]

Временная сложность алгоритма 1 составляет

C(max{| К || £ |,| V |2 •

В главе 1 также приводится алгоритм 2 для временного анализа модели, позволяющий определять вектор ES2 = ES2 (М, EJ") ранних нечетких начальных сроков, основанный на расширении текущей сети N на сеть fj _ (у^Ё-^у а также

приводится алгоритм поиска с помощью метода ветвей и границ. Временная сложность алгоритма 2 составляет 0(\V\\E\d)- Следует отметить, что оценка эффективности работы предложенных алгоритмов временного анализа и алгоритма построения дерева поиска была проведена с помощью статистического анализа количества задач, при решении которых был получено оптимальное/приемлемое расписание. В таблице 1 каждой комбинации количества работ п проектов и способов их выполнения т показано процентное соотношение приемлемых и оптимальных решений, полученных применяя алгоритм метода ветвей и границ. Общее количество задач, рассматриваемых для каждой комбинации условий, равно 5.

Таблица 1

Результаты вычислительного эксперимента для алгоритма решения

методом ветвей и границ.

п! т 2 3

5 - - Приемлемое

100% 100% Оптимальное

10 20% 40% Приемлемое

80% 60% Оптимальное

20 40% 60% Приемлемое

60% 40% Оптимальное

40 40% 60% Приемлемое

60% 40% Оптимальное

Итого было рассмотрено 40 задач с различными условиями, оптимальное решение было получено для 27 случаев. Остальные 13 случаев дали решение, отличающееся от оптимального, не более чем на 22%. Как видно из таблицы 1, алгоритм эффективно работает с небольшим массивом данных и количеством способов выполнения для каждой работы, не превышающим т = 3 ■ Эффект, полученный от применения правил сокращения пространства поиска и двух алгоритмов для временного анализа показан в таблице 2, где приведено соотношение приемлемого и оптимального решений, полученных после

применения правил сокращения и временных алгоритмов, применяемых по-отдельносги для задачи с и = 10 и m = 3 , где В&В - метод ветвей и границ, PRO -не применяется никакого правила сокращения, PR; - применение правила сокращения (/ =1,..,3), Т/- применение алгоритма временного анализа (/ =1,2). Для каждого случая было рассмотрено по 5 задач.

Таблица 2.

Соотношение приемлемых и оптимальных решений, полученных при применении правил сокращения пространства поиска и различных

/7 = 10 т = 3 В&В PRO PR1 PR2 PR3 Т1 Т2

20% 80% 80% 20% 60% 40% 40% 60% 80% 20% 40% 60% 20% 80% Приемлемое Оптимальное

Как видно из таблицы 2, применяя единственное правило сокращения PR2 алгоритм находит оптимальное решение в 60% случаев, применение правила PR3 не дал никакого результата по сравнению с PRO, когда правила сокращения не применялись вообще. С точки зрения применения алгоритмов временного анализа, если вычислительное время ограничено, и допускается наличие приемлемого решения, то следует использовать алгоритм Т1, если вычислительное время для работы алгоритма существенно не ограничено, и нас интересует получение максимально-возможного количества оптимальных решений (80%), то следует применять алгоритм Т2.

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

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

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

эвристического поиска с нечетко заданными временными параметрами модели на основе правил приоритета и параллельной схемы планирования (алгоритм 3): Алгоритм 3:

7 :=70

повторяем

Составляем набор Q(T) тех работ, которые не были еще спланированы, и чьи непосредственные предшественники были завершены к моменту 7.

для каждой работы 2, из группы (2(7), в порядке списка

приоритета, выполняем начало

если 2, -о<2 требование в ресурсе < наличия ресурса, тогда если а. «= 7 > тогда

начало

-й начальный срок: ^ ~Т

-й конечный срок: ■= + р. перемещаем х. из группы Q(7) назначаем требуемые ресурсы работе 21 помещаем /. в группу Т конец

в противном случае

помещаем а, в группу Т

конец

7 := тах(7,1) если 7 = у тогда

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

Процедура начинается в нечеткий момент времени 70 ■ Для этого момента времени, а также для следующего Г, процедура повторяется, пока не будут выполнены все работы. Группа о(7) состоит из работ, которые еще не были спланированы, но чьи непосредственные предшественники были завершены к моменту времени 7. Для каждой работы из группы 0(7) процедура проверяет, имеются ли в наличии требуемые для выполнения работы ресурсы. Если работа достигла своего срока выполнения к моменту 7, то она планируется в этот момент, а затем удаляется из группы о(7), требуемые ресурсы распределены, а

конечный нечеткий срок работы помещается в группу Т таких событий, при которых выбирается следующая для планирования работа. Если работа не достигла своего срока выполнения к моменту Г, то нечеткий срок выполнения помещается в группу Т. Далее, для того чтобы обеспечить приемлемость последовательности нечетких моментов времени, нечеткий момент 7 вычисляется как максимум среди текущего момента 7 и наименьшим значением / из группы Т (в контексте слабого правила сравнения). Если этим значением является конечный срок любой работы, то уровень наличия ресурсов обновляется.

Приводится численный пример и оценка эффективности работы алгоритма на основании вычислительного эксперимента и статистического анализа. На основании вычислительного эксперимента и статистического анализа можно сделать вывод, что решения, вырабатываемые алгоритмом, в среднем отличаются не более чем на 9,92% от эталонных. Среднеквадратичное отклонение равно 3,38%, следовательно, отличие решений более чем на значение т(Х) + 2а(Х) = 16,72 - маловероятно.

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

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

Т Т ^ Нечеткая длительность

—<* ,<г а проекта

Рис. 1. Кривая компромисса типа «время-затраты» на СС -срезе.

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

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

В приложении 1 приведены документы о внедрении научных результатов.

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

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК

РФ

1. Берштейн Л.С., Князева М.В. Разработка алгоритма расстановки меток для решения задачи сетевого планирования в условиях компромисса типа «время-затраты» // Известия ЮФУ. Технические науки. - Таганрог Изд-во ТТИ ЮФУ, 2011, №7 (120)-с. 121-125.

2. Князева M.B. Использование нечетких данных для задания параметров сетевой модели // Обозрение прикладной и промышленной математики. М.: ОП и ПМ, Том 15, Выпуск 3,2008, с. 494-495.

3. Князева М.В. Планирование мультипроектов в условиях нечетких ограниченных ресурсов // Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2010, № 4(105), с. 216-223.

4. Князева М.В. Метод ветвей и границ для решения задачи сетевого планирования с ограниченными ресурсами // Известия ЮФУ. Технические науки». -Таганрог Изд-во ТТИ ЮФУ, 2010, №7(108), с. 78-84.

5. Курмаз М.В. Нахождение критического пути в сетевом планировании в условиях лингвистического задания времени // Известия ТРТУ. - Таганрог: Изд-во ТРТУ, 2007, №2(74), с. 27-32.

Публикации по теме диссертации в других изданиях

6. Князева М.В. Сетевое планирование в условиях нечетких ограниченных ресурсов // Труды научно-практической конференции «Управление Созданием и Развитием Систем, Сетей и Устройств Телекоммуникаций». - СПб: Изд-во СПбГПУ, 2008. - с. 424-430.

7. Князева М.В. Нечеткий подход при формализации параметров сетевой модели // Сборник материалов 10-й Всероссийская научная конференция «Техническая кибернетика, радиоэлектроника и системы управления». - Таганрог: Изд-во ТТИ ЮФУ, 2010. - Т.2., с. 145-146.

8. Князева М.В. Сетевое планирование мультипроектов в условиях нечетких ограниченных ресурсов // Тезисы докладов 6-ой Ежегодной научной конференции студентов и ас пиратов базовых кафедр Южного научного центра РАН. - Ростов н/Д: Изд-во ЮНЦ РАН, 2010. - с. 146-147.

9. Курмаз М.В. Сетевое планирование в нечетких условиях //Сборник трудов 4 Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные Технологии, Системный анаше и Управление». - Таганрог: Изд-во ТРТУ, 2006. - с. 79.

10. Knyazeva М. Resource-constrained Multiproject Scheduling Problem under Fuzzy Conditions // Proceedings of East-West Fuzzy Colloquium 2010, 17-th Zittau Fuzzy Colloquium. Zittau: Hochschule Zittau\Goerlitz.2010.P.

Личный вклад автора в работах, опубликованных в соавторстве: [1] -разработан алгоритм расстановки меток для решения поточной задачи сетевого планирования в условиях нечеткого компромисса типа «время-затраты».

Соискатель

Князева М.В.

Тип. ТТИ ЮФУ Заказ № тир.

61 12-5/3499

ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ ЮЖНОГО ФЕДЕРАЛЬНОГО УНИВЕРСИТЕТА в г. Таганроге

Князева Маргарита Владимировна

СЕТЕВОЕ ПЛАНИРОВАНИЕ В УСЛОВИЯХ НЕЧЕТКИХ ОГРАНИЧЕННЫХ РЕСУРСОВ

Специальность: 05.13.17 «Теоретические основы информатики»

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н., профессор Л.С. Берштейн

На правах рукописи

Таганрог - 2011

ВВЕДЕНИЕ..........................................................................................................................5

ГЛАВА 1. СЕТЕВОЕ ПЛАНИРОВАНИЕ В УСЛОВИЯХ НЕЧЕТКИХ ОГРАНИЧЕННЫХ РЕСУРСОВ. ПОДЗАДАЧА МИНИМИЗАЦИИ ВРЕМЕНИ ВЫПОЛНЕНИЯ ПРОЕКТА ПРИ ЗАДАННОМ УРОВНЕ НАЛИЧИЯ РЕСУРСОВ. 11

Введение..........................................................................................................................11

1.1 Задача сетевого планирования в условиях нечетких ограниченных ресурсов.

Постановка задачи.........................................................................................................12

1.1.1 Краткий обзор существующих методов, выбор и обоснование выбора метода решения задачи..................................................................................................................13

1.1.2 Описание метода ветвей и границ для задачи сетевого планирования...........15

1.1.3 Нечеткое представление параметров модели (сравнение с вероятностным представлением), обоснование необходимости применения нечеткого подхода......17

1.1.4 Решение задачи сетевого планирования с помощью дерева поиска и способа планирования альтернатив...............................................................................................21

1.1.4.1 Построение дерева решений на основе альтернатив и способа планирования альтернатив. Численный пример.....................................................................................22

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

Постановка задачи.........................................................................................................31

1.2.1 Процедуры решения..............................................................................................32

1.2.2 Правила доминирования для решения задачи сетевого планирования в условиях нечеткого компромисса типа «время ресурсы» методом ветвей и границ. 36

1.2.2.1 Правило доминирования 1: избыточные комбинации способов выполнения работ....................................................................................................................................36

1.2.2.2 Правило доминирования 2: правило сдвига влево для единственного способа планирования работ............................................................................................38

1.2.2.3 Правило доминирования 3: правило доминирования для сечения...............38

1.2.2.4 Правило доминирования 4: правило сдвига влево для нескольких способов планирования работ...........................................................................................................40

1.2.3 Правила для нахождения нижних границ...........................................................43

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

нечеткими временными промежутками......................................................................46

1.3.1. Постановка задачи................................................................................................48

1.3.2 Основные понятия.................................................................................................52

1.3.3 Процедура поиска с помощью метода ветвей и границ....................................55

1.3.3.1 Стратегия ветвления..........................................................................................56

1.7.3.2 Временной анализ сети......................................................................................61

1.3.3.3 Правила сокращения пространства поиска...................................................64

1.3.3.4 Алгоритм поиска методом ветвей и границ..................................................65

1.3.4 Численный пример..............................................................................................67

1.3.5 Оценка эффективности алгоритма. Вычислительный эксперимент..............70

1.4 Планирование мульти-проектов в условиях нечетких ограниченных ресурсов.

..........................................................................................................................................75

Выводы по главе............................................................................................................82

ГЛАВА 2. РАЗРАБОТКА ПРОЦЕДУРЫ ПАРАЛЛЕЛЬНОГО ЭВРИСТИЧЕСКОГО ПОИСКА С НЕЧЕТКО-ЗАДАННЫМИ ПАРАМЕТРАМИ МОДЕЛИ НА ОСНОВЕ

ПРАВИЛ ПРИОРИТЕТА..................................................................................................84

Введение..........................................................................................................................84

2.1 Последовательная и параллельная схемы эвристического планирования. Правила приоритета при планировании единичных проектов и мульти-проектов.86

2.2 Постановка задачи сетевого планирования с ограниченными ресурсами, концептуальная модель.................................................................................................90

2.3 Нечеткое определение параметров модели, нечеткие операции, применяемые

при построении модели, сравнение нечетких чисел..................................................91

2.4 Разработка процедуры параллельного эвристического поиска с нечетко-заданными параметрами модели..................................................................................97

2.4.1 Нечеткий критический путь.................................................................................99

2.4.2 Нечетка эвристика, основанная на правилах приоритета...............................100

2.4.3 Нечеткая процедура параллельного эвристического поиска..........................101

2.5 Численный пример.................................................................................................Ю4

2.6 Оценка эффективности алгоритма. Вычислительный эксперимент................108

2.5 Разработка программного продукта, реализующего функции эвристического

поиска с нечетко-заданными параметрами модели..................................................120

Выводы по главе..........................................................................................................124

ГЛАВА 3. СЕТЕВОЕ ПЛАНИРОВАНИЕ В УСЛОВИЯХ НЕЧЕТКОГО

КОМПРОМИССА ТИПА «ВРЕМЯ - ЗАТРАТЫ».......................................................126

Введение........................................................................................................................126

3.1 Постановка задачи непрерывного нечеткого компромисса типа «время-затраты»........................................................................................................................128

3.2 Процедуры решения..............................................................................................132

3.1.3 Разработка алгоритма расстановки меток.........................................................138

3.3 Численный пример.................................................................................................141

Выводы по главе..........................................................................................................151

ЗАКЛЮЧЕНИЕ...............................................................................................................152

Библиографический список............................................................................................155

Приложение 1...................................................................................................................162

Приложение 2...................................................................................................................163

ВВЕДЕНИЕ

Актуальность темы.

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

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

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

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

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

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

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

1. Рассмотреть подзадачу минимизации времени выполнения проекта при условии заданного уровня использования ресурсов одного типа и временных

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

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

3. Предложить и обосновать метод решения задачи сетевого планирования с несколькими способами выполнения работ, несколькими типами ресурсов, максимальными (минимальными) временными промежутками между работами в условиях нечетко-заданных параметров модели.

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

5. Разработать параллельный эвристический способ планирования проектов на основе правил приоритета для нечетко-заданных параметров модели. Описать возможные трудности при использовании нечетких чисел и способы их преодоления.

6. Рассмотреть подзадачу сетевого планирования нечеткого компромисса типа «время-затраты», предложить метод решения и способ представления оптимального решения поставленной задачи.

Научная новизна данной работы заключается в следующем:

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

2. Разработан способ объединения двух и более сетевых графов для планирования нескольких проектов одновременно, разделяющих общие ограниченные ресурсы.

3. Разработана процедура параллельного эвристического поиска с нечетко-заданными параметрами модели на основе правил приоритета работ с шеститочечным нечетким представлением некоторых параметров модели.

4. Предложен метод решения подзадачи сетевого планирования в условиях компромисса типа «время-затраты» с помощью поточного алгоритма Фалкерсона; разработан алгоритм расстановки меток на сетевом графе.

Методы исследования опираются на точные и эвристические методы оптимизации, теорию нечетких множеств при задании параметров модели.

Достоверность результатов вытекает из математического обоснования предложенных алгоритмов поиска и подтверждается результатами программного моделирования и численного эксперимента.

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

1. Алгоритм для построения дерева решений на основе альтернатив и способа планирования альтернатив.

2. Способ представления неопределенных параметров модели с помощью аппарата нечетких чисел.

3. Правила доминирования для решения задачи сетевого планирования с несколькими способами выполнения работ с помощью метода ветвей и границ.

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

5. Понятия «расписания», «минимальной подзадачи», «альтернативы способа выполнения» и «конфликтной альтернативы» введенные для постановки и решения задачи сетевого планирования с несколькими способами выполнения

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

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

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

8. Методология планирования нескольких проектов одновременно, разделяющих

одни и те же ресурсы.

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

10. Программная реализация предложенного эвристического алгоритма.

11. Методология решения задачи непрерывного нечеткого компромисса типа «время-затраты» на основании поточного алгоритма расстановки меток и разрезов сети.

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

позволяет лицам, принимающим решения эффективно управлять даже нестандартными сетевыми проектами.

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

Введение.

Часто при планировании проектов доступность ресурсов ограничена или они не имеются в достаточном количес