Введение к работе
Актуальность темы. Для задач сетевого планирования и управления актуальной является проблема планирования проекта в условиях ограниченных ресурсов, выделенных для осуществления проекта, таким образом, чтобы удовлетворить ограничениям, накладываемым на задачу в том или ином случае. В ходе планирования необходимо организовать работы в условиях частичной или полной неточности информации так, чтобы они были выполнены в сжатые сроки с наименьшими затратами и наилучшим распределением выделенных ресурсов. При этом для процесса управления сложными проектами при всем их многообразии характерны некоторые виды неточности информации. Она, как правило, связана с оценкой некоторых параметров сетевой модели. В связи с тем, что возникающие на практике задачи сетевого планирования имеют многокритериальный характер, в работе предлагается рассматривать различные задачи сетевого планирования, которые часто возникают на практике и для каждой из них разработать способ решения в условиях нечетко заданных параметров модели.
При решении данных задач используются элементы теории графов, нечетких множеств, исследования операций, методов оптимизации, представленные работами Л. Заде, Г. Вагнера, Л.С. Берштейна, А.Н. Борисова, Н. Кристофидеса, А. Кофмана и других авторов. Работы перечисленных ученых относятся к ряду фундаментальных работ по теории графов, исследования операций и теории нечетких множеств, положенных в основу исследований, проводимых в данной работе.
Целью диссертационной работы является разработка методов и алгоритмов решения различных оптимизационных задач сетевого планирования в условиях нечетких ограниченных ресурсов. Поставленная цель определяет основные задачи диссертационного исследования:
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 наименования.
