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

Вид материала

Документы

Подобный материал:

• Уктуре генетических алгоритмов, рассмотрю один из примеров использования алгоритмов,, 101.45kb.
• Задачи : Определить наличие алгоритмов в школьных предметах: география, математика,, 99.61kb.
• М. А. Жужа Ключевые слова: олимпиадные задачи по физике, приёмы составления задач,, 94.17kb.
• Доклады по секции «Приложения методов оптимизации», 22.26kb.
• Секция “Краевые задачи в физике и химии твердого тела”, 31.36kb.
• Рабочая программа учебной дисциплины (модуля) Программная реализация экспертных систем, 94.38kb.
• «Применение ит в молекулярной генетике», 325.87kb.
• Сведения для составления расписания по кафедре прикладной математики и информатики, 96.49kb.
• Белая Холуница Кировская область Описание проекта Название проекта Алгоритмы и основы, 179.54kb.
• В. Е. Латов Тульский государственный университет mibo@klax tula ru Эволюционное моделирование, 65.56kb.

O.В. КОКШАГИНА

Московский государственный технический университет им Н.Э. Баумана


МОДИФИЦИРОВАННЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ ПРОЕКТА


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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дополнительным ограничением могут стать календари ресурсов и работ. При планировании проекта каждому ресурсу можно назначить календарь, в соответствии с которым будут определяться его рабочие часы, и вычисляться длительность его работы [2, 3].


Список литературы

1. 
   В. В. Емельянов, В. М. Курейчик, В. В. Курейчик Теория и практика эволюционного моделирования. М.: Физматлит, 2003. 432 c.
   
2. И.П. Норенков Генетические методы структурного синтеза проектных решений // Журнал «Информационные технологии» №1, 1998.
   
3. Д.И. Батищев, Э.Д. Гудман, И.П. Норенков, М.Х. Прилуцкий Метод декомпозиции для решения комбинаторных задач упорядочения и распределения ресурсов // Журнал «Наука в образовании: электронное научное издание» №9, 2004.