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

УДК 004.896(06) Интеллектуальные системы и технологии


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

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


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


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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


В. В. Емельянов, В. М. Курейчик, В. В. Курейчик Теория и практика эволюционного моделирования. М.: Физматлит, 2003. 432 c.

И.П. Норенков Генетические методы структурного синтеза проектных решений // Журнал «Информационные технологии» №1, 1998.

Д.И. Батищев, Э.Д. Гудман, И.П. Норенков, М.Х. Прилуцкий Метод декомпозиции для решения комбинаторных задач упорядочения и распределения ресурсов // Журнал «Наука в образовании: электронное научное издание» №9, 2004.




ISBN 978-5-7262-0883-1. НАУЧНАЯ СЕССИЯ МИФИ-2008. Том 10