автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.10, диссертация на тему:Моделирование процессов управления проектами в условиях неопределённости на основе робастных расписаний

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

ФЕДОРОВА ИРИНА ВЛАДИМИРОВНА

МОДЕЛИРОВАНИЕ ПРОЦЕССОВ УПРАВЛЕНИЯ ПРОЕКТАМИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ НА ОСНОВЕ РОБАСТНЫХ РАСПИСАНИЙ

Специальность 05.13.10 - управление в социальных и экономических системах

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

ООУи<

Воронеж - 2007

003070929

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

Научный руководитель - доктор технических наук, профессор

Баркалов Сергей Алексеевич

Официальные оппоненты:

доктор физико-математических наук, профессор Головинский Павел Абрамович

доктор технических наук, профессор Леденева Татьяна Михайловна

Ведущая организация - Липецкий государственный технический

Защита диссертации состоится «24» мая 2007 г. в 14 00 часов на заседании диссертационного совета К 212.033.01 при Воронежском государственном архитектурно-строительном университете по адресу:

394006, г. Воронеж, ул. 20-летия Октября, 84, ауд. 20, корп. 3.

С диссертацией можно ознакомиться в библиотеке Воронежского государственного архитектурно-строительного университета.

Автореферат разослан «2,3» апреля 2007 г.

университет

Ученый секретарь диссертационного совета

/

Чертов В.А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Именно поэтому актуальным является получение «гибких» решений, которые могли бы быть полезными в условиях неопределенности Такие решения должны обеспечивать быстрое реагирование на внешние и/или внутренние изменения, обеспечивая применимость к задачам, для которых невозможен априорный контроль выполнения

«Гибкость» расписания должна заключаться в том, что оно представляет не единственное, а множество решений, обеспечивая возможность реагирования на ряд случайностей без нарушений, приводящих к разрушению расписания и последующей необходимости составления нового Разумеется, через определенные промежутки времени и/или в ряде ситуаций все равно потребуется получение нового расписания для еще не выполненных работ, которое могло бы лучше учесть уже имеющие место отклонения в ходе реализации проекта В этом нет ничего удивительного, поскотьку даже если бы в момент времени г было найдено оптимальное решение по рассматриваемым критериям, то в условиях неопредетенности (динамически меняющегося окружения проекта) нельзя гарантировать, что оно останется оптимальным и некоторый следующий момент времени I + г

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

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

Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ

- федеральная комплексная программа «Исследования и разработки по приоритетным направлениям науки и техники гражданского назначения»,

-госбюджетная научно-исследовательская работа «Разработка и совершенствование моделей и механизмов внутрифирменного планирования»

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

Достижение цели работы потребовало решения следующих основных

задач

1 Анализ существующих подходов в области составления расписаний при ограниченных ресурсах в условиях неопределенности

2 Разработка модели и решение задачи трансформации допустимого расписания с фиксированными временами старта работ в расписание с дополнительными ограничениями предшествования, отражающими ресурсные зависимости (расписание частичного порядка - РЧП) на основе базового эвристического алгоритма

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

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

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

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

Научная новизна и значимость результатов диссертационной работы состоит в следующем

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

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

2 Разработаны модели получения расписаний частичного порядка и построены соответствующие им алгоритмы нахождения решения -улучшенный алгоритм-РЧП и алгоритм-РЧП-2, которые не уступают базовому алгоритму по числу пар работ, которые не упорядочены друг относительно друга с помощью отношений предшествования (если применяются к РЧП, полученному базовым алгоритмом) Для улучшенного алгоритма-РЧП проведена оценка временной сложности выполнения Алгоригм-РЧГ1-2 отличается тем, что между работами вводятся только необходимые дополнительные ресурсные ограничения предшествования

3 Предложена модель динамического составления расписаний, учитывающая возможность возникновения новых работ во время выполнения проекта При ее выполнении оценивается конечное число позиций вставки работы (среди которых есть оптимальная по минимизации увеличения продолжительности текущего расписания), после чего применяется алгоритм-РЧП-2

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

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

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

Разработанные модели, алгоритмы и методики используются в практике управления проектами в ООО УК «Жилпроект» и ООО «Стройинвест»

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

На защиту выносятся:

I Модель задачи трансформации допустимого расписания с фиксированными временами старта работ в расписание с дополнительными ограничениями предшествования, отражающими ресурсные зависимости (расписаииь частичного порядка -.РЧП)

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

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

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

Апробация работы.

Основные результаты исследования и научных разработок докладывались и обсуждались на следующих конференциях Современные проблемы прикладной математики и математического моделирования (Воронеж, 2005), 60-63 научно-технические конференции по проблемам архитектуры и строительных наук (Воронеж, ВГАСУ, 2004-2007)

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

Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем

в работах [1], [3], [6] автору принадпежат модели и соответствующие им алгоритмы для робастного составления расписаний, в которых продолжительность проекта является монотонной и непрерывной функцией, зависящей от продолжительностей работ, а также модель генетического алгоритма для минимизации продолжительности проекта при нечетких продолжительностях работ, в работах [2], [7] автору принадлежат модели, касающиеся анализа свободных и полных резервов событий в проектных сетях с нечеткими продолжительностями операций и неограниченными ресурсами, а в [9] были доказаны утверждения, позволившие предложить новый алгоритм вычисления критического пути в случае нечетких продолжительностей работ, в [4], [5] было предложено для нахождения функции стоимости работ по разрозненным статистическим данным воспользоваться нечетким регрессионным алгоритмом, а в [8] приведена процедура, позволяющая уменьшить вычислительную сложность эволюционного алгоритма для мноюкритериальной оптимизации, в работах [10], [11] приведен ряд моделей, позволяющих оценить начальные параметры проекта Модели, алгоритмы и процедуры, разработанные в диссертационном исследовании включены в состав лабораторного практикума [ 12]

Объём и структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложений Она содержит 130 страниц 111 страниц машинописного текста, 27 рисунков, 5 таблиц и приложения, библиография включает 130 наименований

Содержание работы

Во введении обосновывается актуальность, описываются цели и задачи исследования, научная новизна и практическая значимость

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

1) детерминированному календарно-сетевому планированию (ДКСП),

2) недетерминированному календарно-сегевому планированию (НКСП) Как детерминированная задача составления расписания проекта при

ограниченных ресурсах (ДЗСРПОР, между работами отношения предшествования заданы как «финиш-старт»), так и обобщенная ДЗСРПОР (возможны все четыре типа отношений предшествования) является ЬГР-трудной, что делает точные методы малоэффективными при решении задач, характерных для реальных приложений

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

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

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

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

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

Допустимое для ДЗСРПОР расписание, полученное на основе точных или эвристических процедур, определяет предварительное расписание работ, которое служит базовым при выполнении проекта

Задаче составления расписания проекта соответствует граф 0(У, Ь), где множество вершин V = {0,1, ,п,п + 1}, а множество Е содержит дуги, соответствующие ограничениям предшествования между парами работ В частности, для каждого ограничения +<1^ существует дуга с

меткой (1 у

Решение задачи составления расписания проекта с ограниченными ресурсами может быть представлено как расширение О - в = (V, Е Е д ), где Ед задает множество простых («финиш-старт») ограничений предшествования которые были добавлены, чтобы разрешить все возможные ресурсные конфликты Пусть, например, г, сК - любое подмножество работ, такое, что в некоторый момент времени г выполняется Х^к > К-к хотя бы для одного

ресурса (г - это фиксированное количество ресурса к , к — 1, К , требующееся для выполнения работы у, - максимальное количество ресурса к, sJ -стартовое, - финишное время работы )) Тогда Ъ^ называется множеством

запрета (или ресурсным пиком) Минимальное множество запрета (или ресурсный конфликт, или минимальное критическое множество) - это множество 7с2х, такое, что ни одно из его подмножеств не является множеством запрета Любое такое Ъ разрешается относительно ресурсного конфликта, если будет добавлено простое ограничение предшествования между любой парой работ из Z Эти дополнительные ограничения становятся элементами Ед

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

Расписанием частичного порядка (РЧП), соответствующим задаче составления расписания проекта при ограниченных ресурсах, называется граф Р05(У,ЕиЕд), такой, что любое расписание, удовлетворяющее временным ограничениям, также является допустимым

Для каждой дуги Оо) задано количество ресурсных единиц ресурса

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

оценки используются следующие меры 1) первая состоит в подсчете числа пар работ, которые не упорядочены друг относительно друга с помощью простых отношений предшествования в РЧП, 2) взвешенная сумма полных резервов работ Чем больше риск задержки работы, тем больше ее весовой коэффициент

Во второй главе рассматриваются три алгоритма получения РЧП по некоторому допустимому расписанию для обобщенной задачи составления расписания проекта при ограниченных ресурсах, описание которой приведено ниже

Проект состоит из п работ, пронумерованных о г 1 до п Порядок выполнения работ определен заранее Фиктивные работы 0 - начальная и п+! -конечная связывают все работы в один проект Стартовое время работы ; обозначается как s, и время ее завершения как /, Продолжительность известна заранее и она равна d, = /, - s. Продолжительность фиктивных операций равна 0 с/о = = 0 Таким образом, их стартовые и финишные времена эквивалентны sg = /о и s„+i = fn+j Целью является нахождение вектора времен старта s - (s\, ,s„) для того, чтобы оптимизировать целевую функцию J(s)

Есть четыре возможных отношения предшествования между предшествующей i и последующей j работами

- «финиш - к - старту» FStJ ,

- «старт - к - старту» SSy ,

- «финиш - к - финишу» FF,j ,

- «старт - к- финишу» SFtJ

Они определяют желательные минимальные временные промежутки между предшествующей и последующей работами (называемые в дальнейшем лагами) То есть в случае отношения предшествования «старт - к - старту», последующая работа j не должна стартовать раньше, чем лаг размера SSIJt добавленный к стартовому времени st предшествующей работы i Из-за того, что продолжительность dt каждой операции ; известна заранее, все лаги из отношений предшествования могут быть скомбинированы с использованием следующей формулы

FS; = тах{ SStJ - d,, S'F,-d,-dr FS:J .FF^-dJ (1)

В этом случае обобщенная ДЗСРПОР формулируется следующим образом

оптимизировать J(s) (2)

[so — t0 при прямом проходе

относительно < , (3)

[/л+] =/е при обратном

s^l+fSl V(i,y)e£, (4)

s, V/ = 77«, (5)

/, <А, V/ = Ли, (6)

XV ' = ./,* = /* (7)

Ограничения (6) могут отсутствовать в задаче

Направление составления расписания может быть прямым (слева -направо) и обратным (справа - налево) Стартовое время первой фиктивной работы фиксировано как /„ Соответственно, при обратном проходе зафиксировано как /Е время завершения /п+1 последней фиктивной работы Ограничения предшествования (4) устанавливают, что стартовое время последующей работы ] должно быть больше, чем финишное время / предшествующей работы / плюс преобразованный временной лаг РБ' между

работами / и ] Е указывает множество всех пар работ / и у, между которыми существует отношение предшествования Согласно ограничениям времени готовности и обязательного времени завершения (5) и (6), работа ) не может стартовать раньше времени готовности gJ и финишировать после

обязательного времени завершения hJ Временная шкала разбита на постоянные интервалы Л1 = - , начиная с времени Для удобства временной интервал Л1 рассматривается как единица времени, а стартовое время ¡п соответствует началу координат 0 Есть К возобновимых ресурсов (трудовых или машин) и работа у требует для своего выполнения фиксированное количество г]к ресурса к, к = /,К В (7) отражено требование, что во временном интервале /7 - Л // не может быть превышено доступное количество Як1 ресурсов каждого вида 5, обозначает множество работ, выполняющихся во временном интервале [¡-1,1] В рассматриваемой формулировке работы не могут быть прерваны и продолжены вновь позже

Первый алгоритм, называемый базовым алгоритмом-РЧП, является самым простым, распределяя для некоторого допустимого для задачи (2)-(7) расписания Б ресурсные потоки между работами по заданной эвристической схеме Показано, что по рассматриваемым мерам робастности данный ал1 оритм в среднем превосходит ранее предложенные алгоритмы для построения РЧП

Дальше рассматриваются два алгоритма, использующие более сложное распределение ресурсных потоков - улучшенный алгоритм-РЧП и алгоритм-РЧП-2 В работе показано, что оба этих алгоритма не хуже по первой мере, чем базовый алгоритм-РЧП, если начинают выполнение с построенной базовым алгоритмом ресурсной транспортной сети В обоих алгоритмах делается попытка удаления из текущей ресурсной транспортной сети избыточных ресурсных дуг, не изменяя оригинальных технологических ограничений предшес гвования

Для улучшенного алгоргпма-РЧП рассмотрены два варианта реализации Предполагается, что алгоритм начинает выполнение с ресурсной транспортной сети, полученной базовым алгоритмом-РЧП Тогда для варианта А в моменты

времени Г|, Г2, ,тс начала работ в базовом расписании S, фиксируется ресурсный поток (для варианта В это не так), получаемый работой, принадлежащей S(rg) (множество работ, начинающихся в момент времени

Tg), от работ, не принадлежащих множеству (множество работ

завершившихся в промежуток времени (rg_j,rg]) И только после этого, через

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

S(rg)

Улучшенный алгоритм-РЧП для варианта А не хуже базового алгоритма-РЧП по первой мере, оценивающей качество полученного расписания, поскольку в каждый момент времени rg может происходить удаление

некоторых ограничений предшествования

Для варианта В улучшенного алгоритма-РЧП были исследованы некоторые свойства получаемых расписаний

При доказательстве нижеприведенных утверждении неявно предполагалось, что для нахождения максимального потока в сети используется алгоритм Форда - Фулкерсона

Для каждого момента времени rg начала S(rg) работ в базовом

расписании алгоритм рассматривает К двудольных графов Вк с разделяющимися множествами вершин F(rg)vj{/} и S(rg), неотрицательными весами вершин г^ для V/€) и следующей (ст, г)-сетью N(Bfc) добавим новые вершины а и г в В^, проведем дуги (cr,u) с максимальной пропускной способностью для uef(r;) и дуги (v,г) с максимальной пропускной способностью для veS(rg) Все дуги (u,v), ueF(Tg), veS(Tg) имеют неограниченную пропускную способность Здесь S(fg) - количество уже рассмотренных работ, F(Tg) - работы eF(rg), для каждой из которых существует хотя бы одна дуга, связывающая с работой eS(rg) I - искусственная работа, для которой г= rr/c(Tg), где ^(г^) - это свободный поток ресурсов в момент времени rg (наличие этих ресурсов не связано с окончанием ни одной из работ е F(rg))

Известна следующая теорема, обозначения которой иереформупированы согласно рассматриваемому графу Ести (S,T) - минимальный разрез в

двудольном графе N( В^), а е S, тогда (Sri(f'(rg)u/))u(?(r;,)n7") -максимально взвешенное множество независимых вершин в В^

Замечание №1 Если (S,T) - минимальный разрез в (<т, г)- сети N(Bk) двудольного графа В^, creS, в котором все дуги (u,v), ueF(rg)KjI,

veS(tg) имеют неограниченную пропускную способность, то не существует ни одной дуги (с, 1), cef(rg)u/, leS(rg) такой, что выпочняется ceS,

I еТ или с еТ, I е S

Следствие Непосредственно из замечания №1 следует, что выполняются равенства

Z flclk = X flclk

ceTn(F(rg )и/),/б5(гг) ceF( rg )и/,/бГп5(гг)

^¡L, flclk ~ ILflclk (flclk ' это количество единиц

ресурса k, передаваемых от работы с работе 1)

Лемма №1: Если все работы v с; S(t!; ) в сети N(Bk) получили необходимое количество ресурсов, то есть ßmaxk = 2rvjfc > то вес максимально

V

взвешенного множества независимых вершин равен Rк

Лемма №2: Каждому отношению предшествования (qj), введенному после выполнения улучшенного алгоритма-РЧП, соответствует некоторое минимальное множество запрета, содержащее работы q и j

При доказательстве лемм № 1 и № 2, фактически была доказана следующая теорема 1 Если для Vk = 1, К при удалении дуги (u,v) величина максимального потока в сети A^(Sfc) не меняется, то простое ограничение предшествования и < V может быть удалено как избыточное В противном случае дуга (u,v) не может быть удалена из графа

Анализ временной сложности улучшенного алгоритма-РЧП После предварительного доказательства ряда вспомогательных утверждений (рассмотрение ведется для варианта В) можно получить следующее утверждение

Временная сложность улучшенного алгоритма-РЧП составляет К 2

0(2mn^Uk +4Кп ), где m - это общее количество дуг (включая исходные), *=1

введенных за все время работы улучшенного алгоритма-РЧП, а

Uk =maxi/i(r„), Uk(Tg)= шах r]k rg jzS(rg)

Для алгоритма-РЧП-2 рассмотрены два варианта реализации Предполагается, что алгоритм начинает выполнение с ресурсной транспортной сети, полученной базовым алгоритмом-РЧП Тогда для всех моментов времени Г], Г2, ,тс начала работ в базовом расписании S для каждой работы, принадлежащей S(rg) (множество работ, начинающихся в момент времени rg), решается задача нахождения минимального потока в N^ (V", Е") -

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

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

технологических ограничений предшествования Расщепление вершин означает, что в сети Г-^к (V",С) каждой работе 1 соответствует две вершины /], 12, связанные дугой (/].'2) с минимальной пропускной способность ,

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

Если для Ук=1,К при удалении дуги (и2^[) величина минимального потока в сети Ы^С*/", Е") не превосходит К^, то ограничение предшествования и -< V может быть удалено как избыточное В противном случае дуга (и 2, V ]) не может быть удалена из графа

Модель динамического составления расписаний, учитывающая возможность появления новой работы Рассматривается появление новой работы в задаче (2)-(4), (7), = 0 при критерии минимизации

продолжительности проекта Каждый ресурс к может быть представлен в задаче как объединение единиц ресурса Ясно, что в любом допустимом расписании (для которого выполняются ресурсные ограничении и ограничения предшествования) ресурсная единица, выделенная работе 1, после завершения 1-ой работы, передается некоторой работе J Как и раньше, количество единиц ресурса к, передаваемых от работы 1 работе ^ обозначается как Я,^, а (1,^ е Е

означает, что выполнение работы ) должно начинаться только после завершения работы 1 М - достаточно большое число, Мтах продолжительность проекта При этом для задачи составления расписания проекта при ограниченных ресурсах может быть определена транспортная

модель

Мтах -> тт (8)

X % = 1пя+1=кк^к = ис (9)

I Яцк= Е^.к^к^еУ, Ук = 17к, (10)

я^МО-Ху)^, +с1,, У1бУ\{п + 1}, V) е V \ {0}, (11)

Пук <Мху, У1еУ\{п + 1},^еУ\{0}, Ук = 1Д, (12)

мтах=5п+1 03)

х„ е {0,1}, У1еУ\{п + 1},^б V \ {0} (14)

Пук еЫ, VI б У\{п + 1},У]е У\{0}, = (15)

х„ =1, (16)

Здесь (8) - это целевая функция рассматриваемой задачи, ограничения (9)-(10) являются выражением требования о том, чтобы входящие и исходящие потоки ресурсов для каждой работы совпадали с ее потребностями в ресурсах Ограничение (16) задает отношения предшествования проекта, (11) предотвращает одновременное выполнение работ, связанных протекающим между ними ресурсным потоком (12) описывает связь между переменными Пук и х„ как только хотя бы для одного ресурса к] поток становится

больше 0 (Ацк, >0), переменная хц должна принять значение 1 Ограничение

(13) определяет продолжительность проекта, а ограничения (14) - (15) задают допустимые области значений для переменных задачи

Базовому расписанию соответствует допустимая точка задачи (8)-(16) с транспортной сетью в

Рассматривается задача вставки новой работы х с продолжительностью йх и ресурсными требованиями \/к = \,К в существующую транспортную сеть О таким образом, чтобы минимизировать увеличение продолжительности проекта Для работы х может быть определен отрезок времени [Е5Х,ЬГХ] на основе множеств V" и V* работ, предшествующих и следующих за работой х

согласно проекту (£57 = тах(£5, + с!,), ЬЕХ = тт ¿5,)

/ек;

Предполагается, что все ранее определенные ресурсные ограничения предшествования остаются неизменными Ясно, что при этом вставка выполняется только за счет того, что некоторое количество единиц каждого ресурса, первоначально передающееся от работы 1 работе ^ начинает передаваться сначала от работы 1 работе х, а затем от работы х работе J

Пусть Р - это работы, предшествующие работе х по ресурсным ограничениям предшествования, а Б - это работы, следующие за работой х

после вставки Кроме того, будем считать, что в сети в нет пути из Ух ^ Б в

Тогда для позиции вставки (Р,Б) рассмотрим следующие К задач

ХЛ>->тах, (17)

X АЬ]к= (18)

уеК\{0} J£V\{n + \}

I Л>= ХЛ),к=Пк> VíGK\{0,«+l}, (19)

Аук еЫ, VI е У\{п + 1},^еУ\{0} (20)

Здесь Р1 - это множество работ, предшествующих, а - множество работ, спедующих за работой ;еК\{0,«+1} в транзитивном замыкании транспортной сети С{У,Е^ЕА) (ЕА - дуги, соответствующие ресурсным ограничениям предшествования)

Оптимальное значение целевой функции задач (17)-(20) обозначим как

FimaxC.S), =

Определение №1 позиция вставки (P,S) называется допустимой, если выполняются следующие условия

1 В сети G нет пути из vjS в l'x kj Р,

2 Vk = VC,F¿mm(P,S)*rxk

При появлении новой работы перенумеровывается конечное число максимальных позиций вставки (максимальной позиции вставки соответствует пара множеств (P,S) />сС \ j« + l}, ScK\{0¡, таких, что вектор общего потока, передающегося от всех работ множества Р всем работам множества S, равен (R],R2, ,Rk)) Из каждой максимальной позиции вставки получают ряд допустимых позиций вставки для работы х по алгоритму, рассмотренному в работе Было доказано, что среди рассматриваемых допустимых позиций вставки содержится оптимальная Поэтому все они просматриваются и среди них выбирается одна по критерию минимизации увеличения продолжительности проекта ЛМтах Для каждого допустимого разреза вставки (P,S), ¿lMmax = max{0, шах EF, + dx - rmn LS¡}

В предлагаемом алгоритме вставки новой работы INSERI на первом шаге для каждого допустимого разреза вставки считается увеличение продолжительности проекта и находится оптимальный разрез вставки На втором шаге для допустимого разреза вставки и новой работы х выполняется алгоритм-РЧП-2

Пример 1. На рис 1 изображено расписание проекта В порядке неубывания стартовых времен работы были занесены в список Л = (1,2,3,4,5,6,7,8,9) В результате применения базового алгоритма РЧП была получена транспортная сеть, представленная на рис 2 Ресурсные дуги показаны пунктирной линией, над дугами указано количество передаваемого по ним ресурса (в задаче используется топько один ресурс) На рисунке нет проектных дуг, исходящих из вершины 0, или входящих в вершину п+1, поток по которым равен О Максимальное количество ресурса равно 5 После применения алгоритма-РЧП-2 были удалены избыточные ресурсные ограничения предшествования и получена сеть, изображенная на рис 3 Для каждой вершины i данной сети в табл 1 приведены значения ES, LS, и EF, LF-(LF, = LS, +d,), то есть ранние и поздние сроки начала и завершения работы

Предполагается, что возникает новая работа х, для которой Vx = {5}, Vx = {9}, dx =4, rx =2

Таблица 1 - Ранние и поздние сроки начала и завершения работ

Работы ЕБ, ¿5, ЕРг ¡.Г,

0 0 0 0 0

1 0 0 1 1

2 1 1 5 5

3 1 4 2 5

4 5 5 8 8

5 8 10 10 12

6 8 8 12 12

7 10 13 12 15

8 12 12 13 13

9 13 13 15 15

10 15 15 15 15

Рисунок 1-Расписание проекта Рисунок 2- Ресурсная транспортная

сеть

транспортная сеть добавленной работой х

Посте применения первого шага алгоритма INSERT, было найдено, что оптимальным является разрез вставки ( P,S) = ({1,2 3,4,5 }, { 7 9,10 ,')

В данном случае для оптимального разреза вставки и новой работы х базовый алгоритм РЧП и алгоритм-РЧП-2 дали один и тот же результат, так как из множества вершин {1,2,3,4,5} в множество вершин {7,9,10} ведет одна единственная дуга (5,7), для которой П57 = 2 Транспортная сеть после вставки новой работы х изображена на рис 4

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

Для измерения робастности полученных расписаний использовалась

п

взвешенная сумма полных резервов работ Fj = Вторым критерием

i=l

являлось время выполнения последней работы /"2 = max /,

1=1, п

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

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

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

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

Основные результаты работы

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

2 Построены модели получения расписаний частичного порядка и реализующие их алгоритмы - улучшенный алгоритм-РЧП и алгоритм-РЧП-2 Они дают то же или большее значение меры робастности по сравнению с базовым алгоритмом-РЧП, позволяя улучшить полученное им расписание Робастность оценивается по числу пар работ, которые не упорядочены друг относительно друга с помощью отношений предшествования Для улучшенного алгоритма-РЧП дан анализ временной сложности выполнения и исследованы свойства получаемых расписаний Алгоритм-РЧП-2 отличается тем, что между работами вводятся только необходимые дополнительные ресурсные ограничения предшествования За счет идентификации ресурсных ограничений предшествования выявляются скрытые зависимости между работами, что позволяет правильно оценивать полные резервы работ

3 Разработана модель динамического составления расписаний Она предусматривает возможность возникновения новой работы во время выполнения проекта и ее включение в текущее расписание В процессе решения задачи среди конечного числа позиций вставки работы в расписание ищется позиция, оптимальная по критерию минимизации увеличения продолжительности проекта Затем, после обновления расписания (добавления новой работы), применяется алгоритм-РЧП-2 для удаления избыточных ресурсных ограничений предшествования

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

Основные публикации по теме диссертации Статьи, опубликованные в изданиях, определенных ВАК РФ

1 Баркалов С А , Котенко А М , Федорова И В Задача календарного планирования с ограниченными ресурсами при нечетких продолжительностях работ//Системы управления и информационные технологии -2005 -№ 4(2!) -С 37-40 (Лично автором выполнено 2,5 с )

2 Курочка П Н , Потапенко А М , Федорова И В Критичность в сетях с нечеткими продолжительностями операций // Системы управления и

информационные технологии -2005 -№ 4 (21), -С 43-46 (Лично автором выполнено 2,5 с )

3 Баркалов С А , Михнн П В , Федорова И В Стратегия составления расписания для нечеткой задачи минимизации продолжительности проекта // Системы управления и информационные технологии -№ 1 1 (23) -Москва-Воронеж, 2006 -С 115-120 (Лично автором выполнено4с)

Статьи, материалы конференций

4 Федорова И В , Потапенко A M Нечеткий регрессионный алгоритм функции стоимости ресурсной задачи // Оптимизация и моделирование в автоматизированных системах Межвуз сб науч тр / Воронеж гос тех ун-т -Воронеж, 2003 -С 99-108 (Лично автором выполнено 8 с )

5 Баркалов С А , Котенко A M , Федорова И В Моделирование функции стоимости ресурсной задачи с помощью нечеткого регрессионного алгоритма // Современные сложные системы управления Известия ТулГУ Сер Строительство, архитектура и реставрация Вып 8 / Тульск гос ун-т -Тула, 2005 - С 102- 109 (Лично автором выполнено 6 с )

6 Баркалов С А, Федорова И В Модель составления расписания проекта, основанная на представлении продолжительностей работ в виде нечетких чисел // Современные проблемы прикладной математики и математического моделирования Матер междунар науч конф -Воронеж, 2005 - С 18 (Лично автором выполнено 0,5 с )

7 Баркалов С А, Федорова И В Модель минимизации продолжительности проекта при ограниченных ресурсах и нечетких продолжительное!ях работ II Современные проблемы прикладной математики и математического моделирования Матер междунар науч конф -Воронеж,

2005 -С 19 (Лично автором выполнено 0,5 с )

8 Федорова И В Повышение эффективности алгоритма NSGA-II для многокритериальной оптимизации // Научный вестник ВГАСУ /Воронеж гос арх-строит ун-т Вып №2 -Воронеж, 2006 - С 91-98

9 Федорова И В Алгоритм вычисления нечеткого критического пути // Управление большими системами Сб тр -Вып 7/ ИПУ РАН -М , 2004 - С 93-100

10 Половинкина АИ, Федорова ИВ Обоснование принятия экономических решений при выборе вариантов Методические указания для проведения практических занятий / Воронеж гос арх -строит ун-т -Воронеж, 2004 - 42 с (Лично автором выполнено 20 с )

11 Половинкина А И , Федорова И В Применение метода экспертных оценок в задачах принятия решений Методические указания для проведения практических занятий / Воронеж гос арх -строит ун-т -Воронеж, 2004 - 42 с (Лично автором выполнено 20 с )

12 Баркалов С А , Курочка П H , Федорова И В Исследование операций в экономике Лаб практикум / / Воронеж гос арх -строит ун-т -Воронеж,

2006 -244 с (Лично автором выполнено 75 с )

Подписано в печать 20 04 2007 Формат 60x84 1/16 Уч - изд л 1,0 Уел-печ 1,1л Бумага писчая Тираж ЮОэкз Заказ № ¿•'■У

Отпечатано в отделе оперативной полиграфии Воронежского государственного архитектурно-строительного университета 394006, Воронеж, ул 20-летия Октября, 84

ВВЕДЕНИЕ.

1 АНАЛИЗ МЕТОДОВ И АЛГОРИТМОВ СОСТАВЛЕНИЯ РАСПИСАНИЙ ПРОЕКТА.

1.1 Анализ существующих моделей и методов составления расписания проекта при ограниченных ресурсах.

1.1.1 Детерминированное планирование с ограниченными ресурсами.

1.1.2 Недетерминированное планирование с ограниченными ресурсами.

1.2 Применяемые процедуры составления расписания проекта.

1.3 Анализ существующих подходов для робастного распределения ресурсов.

1.3.1 Алгоритмы для робастного распределения ресурсов.

1.4 Постановка задач диссертационного исследования.

2 МОДЕЛИ СОСТАВЛЕНИЯ РАСПИСАНИЯ ПРОЕКТА В УСЛОВИЯХ НЕОПРЕДЕЛЁННОСТИ.

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

2.2 Базовый алгоритм-РЧП.

2.3 Алгоритмическая модель улучшенного алгоритма-РЧП.

2.4 Алгоритмическая модель алгоритма-РЧП-2.

2.5 Модель динамического составления расписаний проекта при возникновении новой работы.

2.6 Модель двухкритериального эволюционного алгоритма.

Выводы по второй главе.

3 ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ РЕЗУЛЬТАТОВ

МОДЕЛИРОВАНИЯ.

Выводы по третьей главе.

Актуальность работы. В реальных строительных проектах расписание проектных работ должно составляться при наличии ограничений на имеющиеся ресурсы, такие как ограниченная численность бригад, количество оборудования и количество материалов. Задачи составления расписания при ограниченных ресурсах интенсивно изучались в области исследования операций. Были предложены различные аналитические и эвристические методы и алгоритмы решения задач. Их можно подразделить на два класса - детерминированные и недетерминированные. Большинство предложенных моделей и алгоритмов относится к классу детерминированных. Классическим подходом, как в области искусственного интеллекта, так и в теории исследования операций, является оптимизация заданной целевой функции (например, минимизация продолжительности проекта). Этот подход основан на гипотезе, что все аспекты задачи могут быть учтены априорно. На практике на ход выполнения проекта динамически влияет множество неопределённых переменных. Примерами таких переменных являются климатические условия, пространственные ограничения, скорость выполнения работы и т. д. Таким образом, усилия, направленные на оптимизацию классической целевой функции, становятся малополезными. Поэтому общей тенденцией в решении задач управления строительством является использование недетерминированного календарно-сетевого планирования в связи с множеством неопределённых переменных, включённых в строительные операции.

Именно поэтому актуальным является получение «гибких» решений, которые могли бы быть полезными в условиях неопределённости. Такие решения должны обеспечивать быстрое реагирование на внешние и/или внутренние изменения, обеспечивая применимость к задачам, для которых невозможен априорный контроль выполнения.

Гибкость» расписания должна заключаться в том, что оно представляет не единственное, а множество решений, обеспечивая возможность реагирования на ряд случайностей без нарушений, приводящих к разрушению расписания и последующей необходимости составления нового. Разумеется, через определённые промежутки времени и/или в ряде ситуаций всё равно потребуется получение нового расписания для ещё не выполненных работ, которое могло бы лучше учесть уже имеющие место отклонения в ходе реализации проекта. В этом нет ничего удивительного, поскольку даже если бы в момент времени t было найдено оптимальное решение по рассматриваемым критериям, то в условиях неопределённости (динамически меняющегося окружения проекта) нельзя гарантировать, что оно останется оптимальным в некоторый следующий момент времени t + т.

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

Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ:

- федеральная комплексная программа «Исследования и разработки по приоритетным направлениям науки и техники гражданского назначения»;

- госбюджетная научно-исследовательская работа «Разработка и совершенствование моделей и механизмов внутрифирменного планирования».

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

Достижение цели работы потребовало решения следующих основных задач:

1. Анализ существующих подходов в области составления расписаний при ограниченных ресурсах в условиях неопределённости.

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

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

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

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

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

Научная новизна и значимость результатов диссертационной работы состоит в следующем:

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

2. Разработаны модели получения расписаний частичного порядка и построены соответствующие им алгоритмы нахождения решения -улучшенный алгоритм-РЧП и алгоритм-РЧП-2, которые не уступают базовому алгоритму по числу пар работ, которые не упорядочены друг относительно друга с помощью отношений предшествования (если применяются к РЧП, полученному базовым алгоритмом). Для улучшенного алгоритма-РЧП проведена оценка временной сложности выполнения. Алгоритм-РЧП-2 отличается тем, что между работами вводятся только необходимые дополнительные ресурсные ограничения предшествования.

3. Предложена модель динамического составления расписаний, учитывающая возможность возникновения новых работ во время выполнения проекта. При её выполнении оценивается конечное число позиций вставки работы (среди которых есть оптимальная по минимизации увеличения продолжительности текущего расписания), после чего применяется алгоритм-РЧП-2.

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

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

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

Разработанные модели, алгоритмы и методики используются в практике управления проектами в ООО УК «Жилпроект» и ООО «Стройинвест».

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

Апробация работы.

Основные результаты исследования и научных разработок докладывались и обсуждались на следующих конференциях: Современные проблемы прикладной математики и математического моделирования (Воронеж, 2005), 60-63 научно-технические конференции по проблемам архитектуры и строительных наук (Воронеж, ВГАСУ, 2004-2007).

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

Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: в работах [9, 10, 12] автору принадлежат модели и соответствующие им алгоритмы для робастного составления расписаний, в которых продолжительность проекта является монотонной и непрерывной функцией, зависящей от продолжительностей работ, а также модель генетического алгоритма для минимизации продолжительности проекта при нечётких продолжительностях работ; в работах [13, 41] автору принадлежат модели, касающиеся анализа свободных и полных резервов событий в проектных сетях с нечёткими продолжительностями операций и неограниченными ресурсами, а в [64] были доказаны утверждения, позволившие предложить новый алгоритм вычисления критического пути в случае нечётких продолжительностей работ; в [7, 58] было предложено для нахождения функции стоимости работ по разрозненным статистическим данным воспользоваться нечётким регрессионным алгоритмом, а в [65] приведена процедура, позволяющая уменьшить вычислительную сложность эволюционного алгоритма для многокритериальной оптимизации. Модели, алгоритмы и процедуры, разработанные в диссертационном исследовании включены в состав лабораторного практикума [8].

Объём и структура работы. Диссертация состоит из введения, трёх глав, заключения, списка литературы и приложений. Она содержит 130 страниц: 111 страниц машинописного текста, 27 рисунков, 5 таблиц и приложения, библиография включает 130 наименований.

Основные результаты диссертационной работы состоят в следующем:

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

2. Построены модели получения расписаний частичного порядка и реализующие их алгоритмы - улучшенный алгоритм-РЧП и алгоритм-РЧП-2. Они дают то же или большее значение меры робастности по сравнению с базовым алгоритмом-РЧП, позволяя улучшить полученное им расписание. Робастность оценивается по числу пар работ, которые не упорядочены друг относительно друга с помощью отношений предшествования. Для улучшенного алгоритма-РЧП дан анализ временной сложности выполнения и исследованы свойства получаемых расписаний. Алгоритм-РЧП-2 отличается тем, что между работами вводятся только необходимые дополнительные ресурсные ограничения предшествования. За счёт идентификации ресурсных ограничений предшествования выявляются скрытые зависимости между работами, что позволяет правильно оценивать полные резервы работ.

3. Разработана модель динамического составления расписаний. Она предусматривает возможность возникновения новой работы во время выполнения проекта и её включение в текущее расписание. В процессе решения задачи среди конечного числа позиций вставки работы в расписание ищется позиция, оптимальная по критерию минимизации увеличения продолжительности проекта. Затем, после обновления расписания (добавления новой работы), применяется алгоритм-РЧП-2 для удаления избыточных ресурсных ограничений предшествования.

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

5. Разработанные модели, алгоритмы и методики прошли апробацию и внедрение в практику управления проектами в ООО УК «Жилпроект» и ООО «Стройинвеет» и включены в состав лабораторного практикума «Исследование операций в экономике», используемого в Воронежском государственном архитектурно-строительном университете.

116

ЗАКЛЮЧЕНИЕ

1. А. Оперативное планирование в целевых программах. -Одесса: Маяк, 1990. - 136 с.

2. Алиев Р. А. и др. Управление производством при нечеткой исходной информации / Р. А. Алиев, А. Э. Церковный, Г. А. Мамедова. М.: Энергоатомиздат, 1991. - 240 с.

3. Андрейчиков А.В., Андрейчикова О.Н. Анализ, синтез, планирование решений в экономике. М.: Финансы и статистика, 2000. - 368 с.

4. Афанасьев В. А. Поточная организация строительства. Л.: Стройиз-дат, 1990.- 160 с.

5. Багриновский К. А., Егорова Н. Е. Имитационные системы в планировании экономических объектов. М.: Наука, 1980. - 250 с.

6. Баркалов С. А. Теория и практика календарного планирования строительного производства.- Воронеж., ВГАСУ, 1999.-216 с.

7. Баркалов С. А., Курочка П. Н., Фёдорова И. В. Исследование операций в экономике. Лаб. практикум / Воронеж, ВГАСУ, 2006. 244 с.

8. Баркалов С. А., Михин П. В., Фёдорова И. В. Стратегия составления расписания для нечёткой задачи минимизации продолжительности проекта // Системы управления и информационные технологии, н. т. журнал №1.1 (23) Москва-Воронеж, 2006.-е. 115-120.

9. Баркалов С.А., Котенко A.M., Федорова И.В. Задача календарного планирования с ограниченными ресурсами при нечётких продолжительно-стях работ // Системы управления и информационные технологии. -2005.-N4(21). -с. 37-40.

10. Баркалов С.А., Курочка П. Н. , Мищенко В. Я. Моделирование и автоматизация организационно-технологического проектирования строительного производства. Воронеж, 1997.- 120 с.

11. Берж К. Теория графов и ее применения. М.: Изд-во иностранной литературы, 1962. - 319 с.

12. Блишун А. Ф. Сравнительный анализ методов измерения нечеткости // Техническая кибернетика. 1988. - № 5, с. 152-173.

13. Борисов В. В., Круглов В. В., Федулов А. С. Нечеткие модели и сети. -М: Горячая линия Телеком, 2007. - 284 с.

14. Бурков В.Н., Новиков Д.А. Как управлять проектами: Научно-практическое издание. Серия "Информатизация России на пороге XXI века". СИНТЕГ-ГЕО, 1997. - 188 с.

15. Вайнторг В. Л., Голуб J1. Г. Сбалансированное планирование в строительных организациях. М.: Стройиздат, 1985. - 134 с.

16. Васильев Д. К., Заложнев А. Ю., Новиков Д. А., Цветков А. В. Типовые решения в управлении проектами. М.: ИЛУ РАН (научное издание), 2003.-73 с.

17. Воропаев В. И. Модели и методы календарного планирования в автоматизированных системах управления строительством. М.: Стройиздат, 1975.-231 с.

18. Воропаев В. И. Управление проектами в России. М.: Алане, 1995. -225 с.

19. Воропаев В. И., Методические рекомендации по построению и использованию сетевых моделей в строительстве. М.: ЦНИИЭУС, 1990. -150 с.

20. Гладков J1. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы / Под ред. В. М. Курейчика. 2-е изд., испр. и доп. - М: ФИЗМАТ-ЛИТ, 2006.-320 с.

21. Голенко Д. И. Статистические методы сетевого планирования и управ25