Сетевое планирование в условиях нечетких ограниченных ресурсов

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

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

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

Специальность: 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.Синтезирован алгоритм нечеткого эвристического поиска оптимальных и приемлемых решений на основе правил приоритета при нечетко заданных параметрах модели, который позволяет эффективно планировать крупные проекты и мульти-проекты при условии задания параметров модели с помощью нечеткой кусочно-линейной функции принадлежности на трех EMBED Equation.3 -срезах.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Min EMBED Equation.3 ,(1)

при условии

EMBED Equation.3 для всех (i,j) EMBED Equation.3 A,(2)

EMBED Equation.3 ,(3)

EMBED Equation.3 для k=1,…,m и t=1,…, EMBED Equation.3 .(4)

Переменная решения EMBED Equation.3 обозначает нечеткие конечные сроки выполнения различных работ, а EMBED Equation.3 обозначает нечеткие длительности каждой из работ, EMBED Equation.3 — наличие и возможность использования k-го типа ресурса, EMBED Equation.3 — необходимость работы i в ресурсе типа k. Группа EMBED Equation.3 в выражении (4) обозначает набор работ, которые выполняются в момент t. Целевая функция (1) минимизирует конечное нечеткое время выполнения конечной фиктивной работы. Выражение (2) определяет отношения предшествования, а выражение (3) показывает, что конечный срок первой фиктивной работы равен 0. И, наконец, выражение (4) показывает, что ни в один момент времени в течение периода выполнения проекта наличие и доступность использования ресурсов не может быть превышена. Для решения представленной задачи разработан алгоритм для формирования дерева решения, каждый узел которого представлен с помощью, так называемых, альтернатив, в которых рассматривается одновременно несколько работ, подходящих для планирования в определенный момент времени таким образом, что не будут превышены совокупные требования в данном ресурсе этой группой рассматриваемых работ. Для того чтобы формально описать процедуру построения дерева решений, введем следующие обозначения. Процедура ветвления начинается с планирования фиктивной начальной работы в момент времени 0. Каждый уровень g дерева решения связан с определенной точкой решения EMBED Equation.3 , набором работ EMBED Equation.3 в процессе выполнения, набором EMBED Equation.3 законченных работ, и набором EMBED Equation.3 работ, пригодных для планирования. И введем так называемый «способ планирования альтернатив EMBED Equation.3 », который определяет способ представления работ, входящих в альтернативу, при построении расписания работ. Затем мы расширяем текущее частичное расписание путем планирования подгруппы пригодных (допустимых) работ в точке решения с учетом ограничений на ресурсы. Более точно, альтернатива EMBED Equation.3 – это подгруппа набора EMBED Equation.3 , для которой EMBED Equation.3 для каждого возобновимого ресурса EMBED Equation.3 и EMBED Equation.3 ≠ø если EMBED Equation.3 =ø. EMBED Equation.3 — уровень наличия ресурса, EMBED Equation.3 — длительность выполнения работы j.

На текущем уровне g дерева поиска мы выполняем следующее: определяем новую точку решения EMBED Equation.3 и вычисляем набор пригодных для планирования работ. Затем мы определяем набор способов EMBED Equation.3 планирования альтернатив EMBED Equation.3 для пригодных работ, которые не являлись пригодными до этого, то есть не рассмотренных до этого. Способы планирования каждой конкретной альтернативы зависят от работ, входящих в эту альтернативу, а именно их длительностей и количества ресурсов, которые они требуют для своего выполнения. Так, например, важен даже порядок, в котором работы планируются в альтернативе, поскольку от этого зависит наличие ресурсов в тот или иной момент времени. После выбора способа планирования EMBED Equation.3 из набора способов, определяем и планируем альтернативу EMBED Equation.3 путем планирования входящих в нее работ, вычисляем приемлемый начальный срок для данных работ (или отдельной работы в альтернативе), который не должен быть меньше начального срока работ, входящих в альтернативу предыдущего уровня дерева поиска. Это условие является неотъемлемой частью алгоритма и обеспечивается тем, что при построении расписания (очередности следования работ) начальный срок (сроки) планируемых работ вычисляются как начальный срок работ в предыдущем узле + длительность работ предыдущего узла. Таким образом, данное условие будет всегда обеспечивать увеличение значения нижней границы lb при прохождении вниз по дереву поиска.

Кроме того, была разработана точная процедура поиска для задачи сетевого планирования, в которой доступны несколько способов выполнения отдельных работ, а также введены максимальные и минимальные нечетко заданные временные промежутки, которые могут иметь место между отдельными работами. Целью при этом является определение способа выполнения каждой из работ проекта, а также нечетких начальных сроков для каждой из работ таким образом, чтобы удовлетворить всем ограничениям и минимизировать нечеткую длительность выполнения проекта. Процедура поиска основана на методе ветвей и границ с помощью поиска в глубину. Это имеет смысл для стратегии ветвления тогда, когда правило ветвления выбирается динамически. Представленный подход является интеграцией приемов, при которых способы выполнения для работ и их начальные сроки выбираются одновременно. Пусть проект состоит из конечного набора работ EMBED Equation.3 . Фиктивная работа 0 представляет собой начало проекта, фиктивная работа EMBED Equation.3 завершает проект. Для каждой работы EMBED Equation.3 набор EMBED Equation.3 представляет собой набор возможных способов выполнения работы. Работы 0 и EMBED Equation.3 могут быть выполнены только одним способом: EMBED Equation.3 . Каждая работа EMBED Equation.3 должна быть выполнена только одним способом EMBED Equation.3 . Нечеткое время выполнения работы EMBED Equation.3 , исполняемой с помощью способа EMBED Equation.3 обозначим как EMBED Equation.3 . Время выполнения работ 0 и EMBED Equation.3 равны 0 и обозначаются как: EMBED Equation.3 .

Параметры EMBED Equation.3 и EMBED Equation.3 обозначают нечеткие начальный и конечный сроки выполнения работы EMBED Equation.3 , соответственно. Если величина EMBED Equation.3 , тогда величина EMBED Equation.3 будет обозначать длительность выполнения всего проекта. Если работа EMBED Equation.3 начинается в момент EMBED Equation.3 с помощью способа EMBED Equation.3 , и будет выполняться в каждый нечеткий момент времени EMBED Equation.3 . Между началом EMBED Equation.3 работы EMBED Equation.3 , которая выполняется с помощью способа EMBED Equation.3 , и началом EMBED Equation.3 работы EMBED Equation.3 ( EMBED Equation.3 ), которая выполняется с помощью способа EMBED Equation.3 , возможен минимальный нечеткий временной промежуток EMBED Equation.3 или максимальный нечеткий временной промежуток EMBED Equation.3 . Отметим, что временной промежуток между работами EMBED Equation.3 и EMBED Equation.3 зависит от способа выполнения EMBED Equation.3 или способа EMBED Equation.3 .

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

Min EMBED Equation.3 , (5)

при условии:

EMBED Equation.3 , EMBED Equation.3 , (6)

EMBED Equation.3 , ( EMBED Equation.3 ; EMBED Equation.3 ), (7)

EMBED Equation.3 , ( EMBED Equation.3 ), (8)

EMBED Equation.3 , ( EMBED Equation.3 ), (9)

EMBED Equation.3 , ( EMBED Equation.3 ), (10)

EMBED Equation.3 . (11)

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

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

Алгоритм 1.

FOR EMBED Equation.3 DO EMBED Equation.3

stop:= FALSE

WHILE NOT stop DO

stop:= TRUE

FOR EMBED Equation.3 DO

IF EMBED Equation.3 THEN

stop:=FALSE;

EMBED Equation.3

FOR EMBED Equation.3

DO EMBED Equation.3

IF EMBED Equation.3 THEN stop:=TRUE

RETURN EMBED Equation.3

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

В главе 1 также приводится алгоритм 2 для временного анализа модели, позволяющий определять вектор EMBED Equation.3 ранних нечетких начальных сроков, основанный на расширении текущей сети EMBED Equation.3 на сеть EMBED Equation.3 , а также приводится алгоритм поиска с помощью метода ветвей и границ. Временная сложность алгоритма 2 составляет EMBED Equation.3 . Следует отметить, что оценка эффективности работы предложенных алгоритмов временного анализа и алгоритма построения дерева поиска была проведена с помощью статистического анализа количества задач, при решении которых был получено оптимальное/приемлемое расписание. В таблице 1 каждой комбинации количества работ EMBED Equation.3 проектов и способов их выполнения EMBED Equation.3 показано процентное соотношение приемлемых и оптимальных решений, полученных применяя алгоритм метода ветвей и границ. Общее количество задач, рассматриваемых для каждой комбинации условий, равно 5.

Таблица 1

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

EMBED Equation.3 / EMBED Equation.3

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, алгоритм эффективно работает с небольшим массивом данных и количеством способов выполнения для каждой работы, не превышающим EMBED Equation.3 . Эффект, полученный от применения правил сокращения пространства поиска и двух алгоритмов для временного анализа показан в таблице 2, где приведено соотношение приемлемого и оптимального решений, полученных после применения правил сокращения и временных алгоритмов, применяемых по-отдельности для задачи с EMBED Equation.3 и EMBED Equation.3 , где B&B – метод ветвей и границ, PR0 – не применяется никакого правила сокращения, PRi – применение правила сокращения (i =1,..,3), Ti – применение алгоритма временного анализа (i =1,2). Для каждого случая было рассмотрено по 5 задач.

Таблица 2.

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

EMBED Equation.3

EMBED Equation.3 B&BPR0PR1PR2PR3T1T220%

80%80%

20%60%

40%40%

60%80%

20%40%

60%20%

80%Приемлемое

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

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

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

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

Алгоритм 3:

EMBED Equation.3

повторяем

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

для каждой работы EMBED Equation.3 из группы Q( EMBED Equation.3 ), в порядке списка приоритета, выполняем

начало

если EMBED Equation.3 -ое требование в ресурсе ≤ наличия ресурса, тогда

если EMBED Equation.3 , тогда

начало

EMBED Equation.3 -й начальный срок: EMBED Equation.3

EMBED Equation.3 -й конечный срок: EMBED Equation.3

перемещаем EMBED Equation.3 из группы Q( EMBED Equation.3 )

назначаем требуемые ресурсы работе EMBED Equation.3

помещаем EMBED Equation.3 в группу T

конец

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

помещаем EMBED Equation.3 в группу T

конец

EMBED Equation.3

если EMBED Equation.3 тогда

обновляем уровень наличия ресурсов,

перемещаем EMBED Equation.3 из группы T

до тех пор пока все работы из списка приоритета не будут завершены.

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

Приводится численный пример и оценка эффективности работы алгоритма на основании вычислительного эксперимента и статистического анализа. На основании вычислительного эксперимента и статистического анализа можно сделать вывод, что решения, вырабатываемые алгоритмом, в среднем отличаются не более чем на 9,92% от эталонных. Среднеквадратичное отклонение равно 3,38%, следовательно, отличие решений более чем на значение EMBED Equation.3 — маловероятно.

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

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

EMBED Visio.Drawing.11

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

Заключение. В соответствии с поставленной целью в диссертационной работе были разработаны методы и алгоритмы решения различных оптимизационных задач сетевого планирования в условиях нечетких ограниченных ресурсов. Эти методы и алгоритмы основываются на точных и эвристических методах оптимизации, таких как метод ветвей и границ, параллельный эвристический поиск, потоковые алгоритмы, и обеспечивают возможность решать различные задачи сетевого планирования в условиях неопределенности, возникающие на практике, эффективным образом. В работе приведены оценки эффективности работы алгоритмов на основании вычислительного эксперимента и, в некоторых случаях, на основании статистического анализа, которые выявляют несомненный положительный эффект от применения предложенных алгоритмов. В главе 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] – разработан алгоритм расстановки меток для решения поточной задачи сетевого планирования в условиях нечеткого компромисса типа «время-затраты».

Соискатель Князева М.В.



Страницы: 1 | 2 | Весь текст