Сетевое планирование в условиях нечетких ограниченных ресурсов
На правах рукописи
Князева Маргарита Владимировна
СЕТЕВОЕ ПЛАНИРОВАНИЕ В УСЛОВИЯХ НЕЧЕТКИХ ОГРАНИЧЕННЫХ РЕСУРСОВ
Специальность: 05.13.17- Теоретические основы информатики
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Таганрог – 2012
Работа выполнена в Технологическом институте Федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет»
| Научный руководитель: | доктор технических наук, профессор Берштейн Леонид Самойлович |
| Официальные оппоненты: | доктор технических наук, профессор Ковалев Сергей Михайлович доктор технических наук, профессор Ромм Яков Евсеевич |
| Ведущая организация: | Институт проблем информатики Российской академии наук (ИПИ РАН), г. Москва |
Защита диссертации состоится «16» марта 2012 г. в 14-20 на заседании диссертационного совета Д 212.208.21 при Южном федеральном университете по адресу:
347928, ГСП-17А, Ростовская область, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.
С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148
Автореферат разослан «__» _________2012 г.
Ученый секретарь
диссертационного совета
д.т.н., профессор Чернов Н.И.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Для задач сетевого планирования и управления актуальной является проблема планирования проекта в условиях ограниченных ресурсов, выделенных для осуществления проекта, таким образом, чтобы удовлетворить ограничениям, накладываемым на задачу в том или ином случае. В ходе планирования необходимо организовать работы в условиях частичной или полной неточности информации так, чтобы они были выполнены в сжатые сроки с наименьшими затратами и наилучшим распределением выделенных ресурсов. При этом для процесса управления сложными проектами при всем их многообразии характерны некоторые виды неточности информации. Она, как правило, связана с оценкой некоторых параметров сетевой модели. В связи с тем, что возникающие на практике задачи сетевого планирования имеют многокритериальный характер, в работе предлагается рассматривать различные задачи сетевого планирования, которые часто возникают на практике и для каждой из них разработать способ решения в условиях нечетко заданных параметров модели.
При решении данных задач используются элементы теории графов, нечетких множеств, исследования операций, методов оптимизации, представленные работами Л. Заде, Г. Вагнера, Л.С. Берштейна, А.Н. Борисова, Н. Кристофидеса, А. Кофмана и других авторов. Работы перечисленных ученых относятся к ряду фундаментальных работ по теории графов, исследования операций и теории нечетких множеств, положенных в основу исследований, проводимых в данной работе.
Целью диссертационной работы является разработка методов и алгоритмов решения различных оптимизационных задач сетевого планирования в условиях нечетких ограниченных ресурсов. Поставленная цель определяет основные задачи диссертационного исследования:
1. Рассмотреть задачу минимизации времени выполнения проекта при условии заданного уровня использования ресурсов одного типа и временных параметров модели, заданных в нечетком виде. Выбрать и обосновать метод решения задачи для оптимального распределения выделенных ресурсов в течение заданного горизонта планирования с целью минимизации времени выполнения проекта.
2. Разработать метод решения задачи сетевого планирования с несколькими способами выполнения работ, несколькими типами ресурсов, максимальными (минимальными) временными промежутками между работами в условиях нечетко заданных параметров модели.
3. Разработать эвристический алгоритм планирования проектов на основе правил приоритета для нечетко заданных параметров модели. Описать возможные трудности при использовании нечетких чисел и способы их преодоления.
4. Рассмотреть задачу сетевого планирования нечеткого компромисса типа «время-затраты», предложить метод решения и способ представления оптимального решения поставленной задачи.
Методы исследования опираются на точные и эвристические методы оптимизации, теорию нечетких множеств при задании параметров модели.
Научная новизна диссертационной работы заключаются в следующем:
1. Разработан метод нахождения оптимальных решений задачи минимизации времени выполнения проекта при условии ограниченных ресурсов возобновимого типа, а также временных параметров модели, заданных с помощью нечетких чисел. Метод отличается от аналогов, включая метод ветвей и границ, способом построения дерева поиска решений на основе планирования альтернатив, что в целом позволяет сокращать пространство поиска для комбинаторной задачи сетевого планирования и наряду с оптимальным находить все локально оптимальные решения задачи.
2. Разработан метод решения задачи сетевого планирования с несколькими способами выполнения работ, несколькими типами ресурсов, максимальными (минимальными) временными промежутками между работами в условиях нечетко заданных параметров модели, отличающийся от аналогов обобщенной постановкой задачи и построением, что позволяет определять способ выполнения и нечеткие начальные сроки для каждой работы проекта при условии определенных технологических промежутков между работами и минимизировать нечеткую длительность выполнения проекта.
3.Синтезирован алгоритм нечеткого эвристического поиска оптимальных и приемлемых решений на основе правил приоритета при нечетко заданных параметрах модели, который позволяет эффективно планировать крупные проекты и мульти-проекты при условии задания параметров модели с помощью нечеткой кусочно-линейной функции принадлежности на трех 
-срезах.
4. Предложен метод получения кусочно-линейной зависимости затрат проекта от времени его выполнения с помощью поточного алгоритма Фалкерсона для задачи нечеткого компромисса типа «время-затраты». Метод позволяет уменьшать длительность выполнения проекта за счет увеличения общих затрат, выражая кусочно-линейную зависимость общих затрат проекта как функцию длительности его выполнения.
Основные положения, выносимые на защиту
1. Метод, позволяющий находить оптимальные решения для задачи сетевого планирования с ограниченными ресурсами и нечетко заданными параметрами модели с помощью дерева поиска и способа планирования альтернатив.
2. Метод решения задачи сетевого планирования с несколькими способами выполнения работ, а также максимальными и минимальными временными промежутками между ними с помощью метода ветвей и границ.
3. Алгоритм эвристического поиска с нечетко заданными параметрами модели в виде кусочно-линейной функции принадлежности на трех -срезах на основе правил приоритета.
4. Метод решения задачи нечеткого компромисса типа «время-затраты» с помощью поточного алгоритма и алгоритма расстановки меток.
Достоверность полученных в диссертации результатов вытекает из математического обоснования предложенных алгоритмов поиска и подтверждается результатами программного моделирования и численного эксперимента, результатами практического внедрения, апробацией на международных и всероссийских конференциях.
Практическая значимость диссертации заключается в прикладном характере разработанных алгоритмов и способе оценки параметров сетевой модели. Все предложенные алгоритмы решения и подходы ориентированы на компьютерную реализацию и актуальны для решения различных задач сетевого планирования, часто встающих на практике. В частности, решение задачи оптимального распределения работ с имеющимися ограничениями на использование ресурсов и минимизации времени выполнения работ в условиях нескольких способов выполнения работ и неопределенности, возникающей при задании параметров, или задачи нахождения нечеткого компромисса типа «время-затраты», позволяет лицам, принимающим решения эффективно управлять даже нестандартными сетевыми проектами.
Внедрение и использование результатов работы. Результаты диссертации внедрены в ФГУП «Федеральный Кадастровый Центр «Земля» Филиал по Южному ФО», в учебном процессе кафедры Прикладной информатики Технологического Института Южного федерального университета в г. Таганроге в курсах «Математические методы исследования операций» и «Системный анализ», что подтверждено соответствующими актами об использовании, приведенными в приложении 1 к диссертационной работе. Результаты диссертационной работы также использованы при выполнении научно-исследовательских работ, в том числе при выполнении гранта РФФИ № 11-01-00011а.
Апробация работы. Основные результаты работы представлены на 4-й Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные Технологии, Системный анализ и Управление» (Таганрог, 2006 г.), на научно-практической конференции «Управление Созданием и Развитием Систем, Сетей и Устройств Телекоммуникаций» (Санкт-Петербург, 2008 г.), на «Девятом Всероссийском Симпозиуме по Прикладной и Промышленной Математике» (Кисловодск, 2008 г.), на 10-й Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2010 г.), на 6-ой Ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН (Ростов-на-Дону, 2010 г.), на 
East-West Zittau Fuzzy Colloquium (Циттау, Германия, 2010 г.)
Публикации. Результаты диссертации отражены в 10 печатных работах, в том числе в 5 работах, опубликованных в изданиях, рекомендованных ВАК.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, выводов по главам, заключения, библиографического списка и приложения. Работа выполнена на 177 страницах машинописного текста, содержит 56 рисунков и 13 таблиц. Библиографический список включает 73 наименования.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертационной работы, описаны основные задачи сетевого планирования, сформулированы цели и задачи исследования, охарактеризованы научная новизна работы, ее практическая ценность, реализация и апробация результатов работы, дано краткое содержание структуры диссертации.
В первой главе рассматривается задача минимизации времени выполнения проекта с ограниченными ресурсами, нечетко заданными параметрами модели. В качестве целевой функции в простейшем случае выступает время выполнения проекта. Каждая работа i имеет длительность выполнения, определенную как количество единиц, выраженных с помощью нечетких чисел при учете двух видов ограничений. Ограничения на предшествования требуют, чтобы каждая работа i была спланирована только после окончания непосредственно предшествующих ей работ, включенных в группу планируемых работ 
. Кроме того, для выполнения каждой работы i требуется 
единиц четко-заданного ресурса 
в течение каждого момента выполнения. Ограничения на ресурсы ограничивают количество единиц ресурса 
, доступного в каждый момент горизонта планирования. Рассматривается задача сетевого планирования в условиях нечетких ограниченных ресурсов, которая концептуально может быть представленная следующим образом:
Min 
, (1)
при условии
для всех (i,j) 
A, (2)
, (3)
для k=1,…,m и t=1,…,
. (4)
Переменная решения 
обозначает нечеткие конечные сроки выполнения различных работ, а 
обозначает нечеткие длительности каждой из работ, 
- наличие и возможность использования k-го типа ресурса, 
- необходимость работы i в ресурсе типа k. Группа 
в выражении (4) обозначает набор работ, которые выполняются в момент t. Целевая функция (1) минимизирует конечное нечеткое время выполнения конечной фиктивной работы. Выражение (2) определяет отношения предшествования, а выражение (3) показывает, что конечный срок первой фиктивной работы равен 0. И, наконец, выражение (4) показывает, что ни в один момент времени в течение периода выполнения проекта наличие и доступность использования ресурсов не может быть превышена. Для решения представленной задачи разработан алгоритм для формирования дерева решения, каждый узел которого представлен с помощью, так называемых, альтернатив, в которых рассматривается одновременно несколько работ, подходящих для планирования в определенный момент времени таким образом, что не будут превышены совокупные требования в данном ресурсе этой группой рассматриваемых работ. Для того чтобы формально описать процедуру построения дерева решений, введем следующие обозначения. Процедура ветвления начинается с планирования фиктивной начальной работы в момент времени 0. Каждый уровень g дерева решения связан с определенной точкой решения 
, набором работ 
в процессе выполнения, набором 
законченных работ, и набором 
работ, пригодных для планирования. И введем так называемый «способ планирования альтернатив 
», который определяет способ представления работ, входящих в альтернативу, при построении расписания работ. Затем мы расширяем текущее частичное расписание путем планирования подгруппы пригодных (допустимых) работ в точке решения с учетом ограничений на ресурсы. Более точно, альтернатива 
– это подгруппа набора 
, для которой 
для каждого возобновимого ресурса 
и 
если 
=. 
- уровень наличия ресурса, 
- длительность выполнения работы j.
На текущем уровне g дерева поиска мы выполняем следующее: определяем новую точку решения 
и вычисляем набор пригодных для планирования работ. Затем мы определяем набор способов 
планирования альтернатив 
для пригодных работ, которые не являлись пригодными до этого, то есть не рассмотренных до этого. Способы планирования каждой конкретной альтернативы зависят от работ, входящих в эту альтернативу, а именно их длительностей и количества ресурсов, которые они требуют для своего выполнения. Так, например, важен даже порядок, в котором работы планируются в альтернативе, поскольку от этого зависит наличие ресурсов в тот или иной момент времени. После выбора способа планирования 
из набора способов, определяем и планируем альтернативу 
путем планирования входящих в нее работ, вычисляем приемлемый начальный срок для данных работ (или отдельной работы в альтернативе), который не должен быть меньше начального срока работ, входящих в альтернативу предыдущего уровня дерева поиска. Это условие является неотъемлемой частью алгоритма и обеспечивается тем, что при построении расписания (очередности следования работ) начальный срок (сроки) планируемых работ вычисляются как начальный срок работ в предыдущем узле + длительность работ предыдущего узла. Таким образом, данное условие будет всегда обеспечивать увеличение значения нижней границы lb при прохождении вниз по дереву поиска.
Кроме того, была разработана точная процедура поиска для задачи сетевого планирования, в которой доступны несколько способов выполнения отдельных работ, а также введены максимальные и минимальные нечетко заданные временные промежутки, которые могут иметь место между отдельными работами. Целью при этом является определение способа выполнения каждой из работ проекта, а также нечетких начальных сроков для каждой из работ таким образом, чтобы удовлетворить всем ограничениям и минимизировать нечеткую длительность выполнения проекта. Процедура поиска основана на методе ветвей и границ с помощью поиска в глубину. Это имеет смысл для стратегии ветвления тогда, когда правило ветвления выбирается динамически. Представленный подход является интеграцией приемов, при которых способы выполнения для работ и их начальные сроки выбираются одновременно. Пусть проект состоит из конечного набора работ 
. Фиктивная работа 0 представляет собой начало проекта, фиктивная работа 
завершает проект. Для каждой работы 
набор 
представляет собой набор возможных способов выполнения работы. Работы 0 и 
могут быть выполнены только одним способом: 
. Каждая работа 
должна быть выполнена только одним способом 
. Нечеткое время выполнения работы 
, исполняемой с помощью способа 
обозначим как 
. Время выполнения работ 0 и 
равны 0 и обозначаются как: 
.
Параметры 
и 
обозначают нечеткие начальный и конечный сроки выполнения работы
, соответственно. Если величина 
, тогда величина 
будет обозначать длительность выполнения всего проекта. Если работа 
начинается в момент 
с помощью способа 
, и будет выполняться в каждый нечеткий момент времени 
. Между началом 
работы 
, которая выполняется с помощью способа 
, и началом 
работы 
(
), которая выполняется с помощью способа 
, возможен минимальный нечеткий временной промежуток 
или максимальный нечеткий временной промежуток 
. Отметим, что временной промежуток между работами 
и 
зависит от способа выполнения 
или способа 
.
Обозначим через 
набор работ, выполняющихся в момент времени 
для расписания 
, тогда задача сетевого планирования с несколькими способами выполнения работ, максимальными и минимальными временными промежутками может быть представлена следующим образом:
Min 
, (5)
при условии:
, 
, (6)
, (
;
), (7)
, (
), (8)
, (
), (9)
, (
), (10)
. (11)
Целью является определение такого расписания 
, которое бы удовлетворяло условиям нечетких временных промежутков (6), ограничениям на возобновимые ресурсы (7), невозобновимые ресурсы (8) и минимизировалась целевая функция – нечеткая длительность выполнения проекта (5). Такое расписание будем считать оптимальным. Расписание 
, удовлетворяющее (6)-(8), будем считать приемлемым.
Ветвление для построения дерева поиска решений методом ветвей и границ основано на одновременной оценке решений, необходимых для приписывания работе способа выполнения (разрешения способов выполнения) и разрешении конфликта ресурсов (разрешения ресурсов), необходимых для нахождения приемлемого расписания. Для временного анализа модели были разработаны две процедуры для вычисления вектора нечетких ранних сроков начала работ 
. 
является нечеткой нижней границей, основанной на минимальной длительности выполнения проекта, и необходимой для оценки альтернатив. Обе процедуры основываются на специальных релаксациях задачи, основанных на ресурсах, и используют верхнюю границу 
, основанную на минимальной длительности выполнения проекта. Они могут приписывать фиктивные способы выполнения работам, отраженные в 
, дизъюнктивные отношения предшествования, отраженные с помощью 
. Первый алгоритм опирается на текущую сеть 
, в то время как второй алгоритм основывается на расширении текущей сети 
.
Алгоритм 1.
FOR 
DO 
stop:= FALSE
WHILE NOT stop DO
stop:= TRUE
FOR 
DO
IF 
THEN
stop:=FALSE;
FOR 
DO 
IF 
THEN stop:=TRUE
RETURN 
Временная сложность алгоритма 1 составляет 
.
В главе 1 также приводится алгоритм 2 для временного анализа модели, позволяющий определять вектор 
ранних нечетких начальных сроков, основанный на расширении текущей сети 
на сеть 
, а также приводится алгоритм поиска с помощью метода ветвей и границ. Временная сложность алгоритма 2 составляет 
. Следует отметить, что оценка эффективности работы предложенных алгоритмов временного анализа и алгоритма построения дерева поиска была проведена с помощью статистического анализа количества задач, при решении которых был получено оптимальное/приемлемое расписание. В таблице 1 каждой комбинации количества работ 
проектов и способов их выполнения 
показано процентное соотношение приемлемых и оптимальных решений, полученных применяя алгоритм метода ветвей и границ. Общее количество задач, рассматриваемых для каждой комбинации условий, равно 5.
Таблица 1
Результаты вычислительного эксперимента для алгоритма решения методом ветвей и границ.
 / | 2 | 3 | |
| 5 | - 100% | - 100% | Приемлемое Оптимальное |
| 10 | 20% 80% | 40% 60% | Приемлемое Оптимальное |
| 20 | 40% 60% | 60% 40% | Приемлемое Оптимальное |
| 40 | 40% 60% | 60% 40% | Приемлемое Оптимальное |
Итого было рассмотрено 40 задач с различными условиями, оптимальное решение было получено для 27 случаев. Остальные 13 случаев дали решение, отличающееся от оптимального, не более чем на 22%. Как видно из таблицы 1, алгоритм эффективно работает с небольшим массивом данных и количеством способов выполнения для каждой работы, не превышающим 
. Эффект, полученный от применения правил сокращения пространства поиска и двух алгоритмов для временного анализа показан в таблице 2, где приведено соотношение приемлемого и оптимального решений, полученных после применения правил сокращения и временных алгоритмов, применяемых по-отдельности для задачи с 
и 
, где B&B – метод ветвей и границ, PR0 – не применяется никакого правила сокращения, PRi – применение правила сокращения (i =1,..,3), Ti – применение алгоритма временного анализа (i =1,2). Для каждого случая было рассмотрено по 5 задач.
Таблица 2.
Соотношение приемлемых и оптимальных решений, полученных при применении правил сокращения пространства поиска и различных алгоритмов временного анализа.
  | B&B | PR0 | PR1 | PR2 | PR3 | T1 | T2 | |
| 20% 80% | 80% 20% | 60% 40% | 40% 60% | 80% 20% | 40% 60% | 20% 80% | Приемлемое Оптимальное |
Как видно из таблицы 2, применяя единственное правило сокращения PR2 алгоритм находит оптимальное решение в 60% случаев, применение правила PR3 не дал никакого результата по сравнению с PR0, когда правила сокращения не применялись вообще. С точки зрения применения алгоритмов временного анализа, если вычислительное время ограничено, и допускается наличие приемлемого решения, то следует использовать алгоритм T1, если вычислительное время для работы алгоритма существенно не ограничено, и нас интересует получение максимально-возможного количества оптимальных решений (80%), то следует применять алгоритм T2.
Кроме того, в главе 1 рассматривается возможность планирования нескольких проектов одновременно, разделяющих общие ресурсы, предлагается способ объединения сетевых графов по общей работе.
Во второй главе разрабатывается процедура эвристического поиска с нечетко заданными параметрами модели, заданными в виде нечеткого шестиугольного числа, представляющего собой кусочно-линейную функцию принадлежности на трех 
-срезах. В главе рассматриваются различные правила приоритета, осуществляется выбор нескольких из них для планирования как одного единственного проекта, так и нескольких проектов одновременно. Правило приоритета осуществляет выбор очередной работы для планирования из списка всех работ. Осуществляется выбор параллельной схемы планирования, которая состоит из набора шагов, каждый из которых связан с определенным моментом планирования, является время-ориентированной и позволяет осуществлять планирование нескольких проектов одновременно.
Предлагается задавать временные параметры модели в виде нечеткого шестиугольного числа, представляющего собой кусочно-линейную функцию на трех 
-срезах. Описываются операции сложения, вычитания и сравнения нечетких шестиугольных чисел с учетом специфики сетевого планирования и специфических ограничений. Вводится сильное и слабое правила сравнения нечетких чисел. Приводится алгоритм для осуществления процедуры эвристического поиска с нечетко заданными временными параметрами модели на основе правил приоритета и параллельной схемы планирования (алгоритм 3):
Алгоритм 3:
повторяем
Составляем набор Q(
) тех работ, которые не были еще спланированы, и чьи непосредственные предшественники были завершены к моменту 
.
для каждой работы 
из группы Q(
), в порядке списка приоритета, выполняем
начало
если 
-ое требование в ресурсе наличия ресурса, тогда
если 
, тогда
начало
-й начальный срок: 
-й конечный срок: 
перемещаем 
из группы Q(
)
назначаем требуемые ресурсы работе 
помещаем 
в группу T
конец
в противном случае
помещаем 
в группу T
конец
если 
тогда
обновляем уровень наличия ресурсов,
перемещаем 
из группы T
до тех пор пока все работы из списка приоритета не будут завершены.
Процедура начинается в нечеткий момент времени 
. Для этого момента времени, а также для следующего 
, процедура повторяется, пока не будут выполнены все работы. Группа 
состоит из работ, которые еще не были спланированы, но чьи непосредственные предшественники были завершены к моменту времени 
. Для каждой работы из группы 
процедура проверяет, имеются ли в наличии требуемые для выполнения работы ресурсы. Если работа достигла своего срока выполнения к моменту 
, то она планируется в этот момент, а затем удаляется из группы 
, требуемые ресурсы распределены, а конечный нечеткий срок работы помещается в группу Т таких событий, при которых выбирается следующая для планирования работа. Если работа не достигла своего срока выполнения к моменту 
, то нечеткий срок выполнения помещается в группу Т. Далее, для того чтобы обеспечить приемлемость последовательности нечетких моментов времени, нечеткий момент 
вычисляется как максимум среди текущего момента 
и наименьшим значением 
из группы Т (в контексте слабого правила сравнения). Если этим значением является конечный срок любой работы, то уровень наличия ресурсов обновляется.
Приводится численный пример и оценка эффективности работы алгоритма на основании вычислительного эксперимента и статистического анализа. На основании вычислительного эксперимента и статистического анализа можно сделать вывод, что решения, вырабатываемые алгоритмом, в среднем отличаются не более чем на 9,92% от эталонных. Среднеквадратичное отклонение равно 3,38%, следовательно, отличие решений более чем на значение 
- маловероятно.
Приводится программная реализация представленного подхода, реализующая функции эвристического поиска с нечетко заданными временными параметрами модели, и дающая возможность: задания временных параметров модели в нечетком виде с помощью различных видов нечетких чисел (треугольных, трапециевидных, шеститочечное представление), возможность работы с любыми из них; задания отношений предшествования в виде таблицы, отражающей список из тех работ, которые могут быть выполнены после данной; задания уровня требований в ресурсе для каждой из работ проекта; расчета нечетких начальных и конечных сроков выполнения для каждой работы и проекта вцелом с учетом максимально-возможного для использования уровня ресурсов и правила приоритета для работ; вывода полученных данных в отдельную форму; построение трехмерной диаграммы Гантта и двухмерной диаграммы распределения ресурсов в течение времени выполнения проекта; сохранения файла проекта с возможностью последующего доступа к нему и работы с ним.
В третьей главе разработан метод нахождения нечеткого непрерывного компромисса между временем выполнения проекта и общими затратами проекта, выраженными в нечетком виде. Наглядно данный тип компромисса может быть проиллюстрирован с помощью выпуклой нечеткой кусочно-линейной кривой общих затрат проекта, как функции нечеткой длительности выполнения проекта (рис.1). В главе 3 была предложена и описана процедура решения поставленной задачи с помощью потока на дугах и пропускной способности каждой из них. Предложен алгоритм расстановки меток, как способ нахождения решения задачи таким образом, что начиная с максимально-возможной длительности выполнения работ, алгоритм уменьшает эту длительность, одновременно вычисляя общие затраты проекта на сокращение длительности выполнения проекта. Приведен численный пример работы алгоритма.
Рис.1. Кривая компромисса типа «время-затраты» на 
-срезе.
Заключение. В соответствии с поставленной целью в диссертационной работе были разработаны методы и алгоритмы решения различных оптимизационных задач сетевого планирования в условиях нечетких ограниченных ресурсов. Эти методы и алгоритмы основываются на точных и эвристических методах оптимизации, таких как метод ветвей и границ, параллельный эвристический поиск, потоковые алгоритмы, и обеспечивают возможность решать различные задачи сетевого планирования в условиях неопределенности, возникающие на практике, эффективным образом. В работе приведены оценки эффективности работы алгоритмов на основании вычислительного эксперимента и, в некоторых случаях, на основании статистического анализа, которые выявляют несомненный положительный эффект от применения предложенных алгоритмов. В главе 2 произведена программная реализация предложенного параллельного эвристического алгоритма поиска на основании правил приоритета.
Основной результат диссертационной работы заключается в разработанных методах и алгоритмах для нахождения допустимых и оптимальных решений задач сетевого планирования в условиях нечетких ограниченных ресурсов.
В приложении 1 приведены документы о внедрении научных результатов.
В приложении 2 приведен листинг программного кода, осуществляющего программную реализацию нечеткого параллельного эвристического поиска на основе правила приоритета, изложенного в главе 2 диссертационной работы.
Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ
1. Берштейн Л.С., Князева М.В. Разработка алгоритма расстановки меток для решения задачи сетевого планирования в условиях компромисса типа «время-затраты» // Известия ЮФУ. Технические науки. – Таганрог: Изд-во ТТИ ЮФУ, 2011, №7 (120) - с. 121-125.
2. Князева М.В. Использование нечетких данных для задания параметров сетевой модели // Обозрение прикладной и промышленной математики. М.: ОП и ПМ, Том 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 M. 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] – разработан алгоритм расстановки меток для решения поточной задачи сетевого планирования в условиях нечеткого компромисса типа «время-затраты».
Соискатель Князева М.В.
Тип. ТТИ ЮФУ Заказ № тир. экз.
