Содержание к диссертации
Введение
1 Анализ методов и алгоритмов составления расписаний проекта 11
1.1 Анализ существующих моделей и методов составления расписания проекта при ограниченных ресурсах 11
1.1.1 Детерминированное планирование с ограниченными ресурсами 16
1.1.2 Недетерминированное планирование с ограниченными ресурсами 21
1.2 Применяемые процедуры составления расписания проекта 27
1.3 Анализ существующих подходов для робастного распределения ресурсов 35
1.3.1 Алгоритмы для робастного распределения ресурсов 36
1.4 Постановка задач диссертационного исследования 43
2 Модели составления расписания проекта в условиях неопределённости 45
2.1 Задача составления расписания проекта при ограниченных ресурсах и возможном варьировании длительностей работ 45
2.2 Базовый алгоритм-РЧП 46
2.3 Алгоритмическая модель улучшенного алгоритма-РЧП 51
2.4 Алгоритмическая модель алгоритма-РЧП-2 63
2.5 Модель динамического составления расписаний проекта при возникновении новой работы 68
2.6 Модель двухкритериального эволюционного алгоритма 83
Выводы по второй главе 93
3 Практическое применение результатов моделирования 95
Выводы по третьей главе 108
Заключение 114
Литература 116
Приложение акты о внедрении 126
- Недетерминированное планирование с ограниченными ресурсами
- Анализ существующих подходов для робастного распределения ресурсов
- Модель динамического составления расписаний проекта при возникновении новой работы
- Практическое применение результатов моделирования
Введение к работе
Актуальность работы. В реальных строительных проектах расписание проектных работ должно составляться при наличии ограничений на имеющиеся ресурсы, такие как ограниченная численность бригад, количество оборудования и количество материалов. Задачи составления расписания при ограниченных ресурсах интенсивно изучались в области исследования операций. Были предложены различные аналитические и эвристические методы и алгоритмы решения задач. Их можно подразделить на два класса - детерминированные и недетерминированные. Большинство предложенных моделей и алгоритмов относится к классу детерминированных. Классическим подходом, как в области искусственного интеллекта, так и в теории исследования операций, является оптимизация заданной целевой функции (например, минимизация продолжительности проекта). Этот подход основан на гипотезе, что все аспекты задачи могут быть учтены априорно. На практике на ход выполнения проекта динамически влияет множество неопределённых переменных. Примерами таких переменных являются климатические условия, пространственные ограничения, скорость выполнения работы и т. д. Таким образом, усилия, направленные на оптимизацию классической целевой функции, становятся малополезными. Поэтому общей тенденцией в решении задач управления строительством является использование недетерминированного календарно-сетевого планирования в связи с множеством неопределённых переменных, включённых в строительные операции. Именно поэтому актуальным является получение «гибких» решений, которые могли бы быть полезными в условиях неопределённости. Такие решения должны обеспечивать быстрое реагирование на внешние и/или внутренние изменения, обеспечивая применимость к задачам, для которых невозможен априорный контроль выполнения.
«Гибкость» расписания должна заключаться в том, что оно представляет не единственное, а множество решений, обеспечивая возможность реагирования на ряд случайностей без нарушений, приводящих к разрушению расписания и последующей необходимости составления нового. Разумеется, через определённые промежутки времени и/или в ряде ситуаций всё равно потребуется получение нового расписания для ещё не выполненных работ, которое могло бы лучше учесть уже имеющие место отклонения в ходе реализации проекта. В этом нет ничего удивительного, поскольку даже если бы в момент времени t было найдено оптимальное решение по рассматриваемым критериям, то в условиях неопределённости (динамически меняющегося окружения проекта) нельзя гарантировать, что оно останется оптимальным в некоторый следующий момент времени t + T.
В основе «хрупкости» расписания лежит классическая формулировка задачи составления расписания с фиксированными временами старта работ. Рассматривая вместо этого модификацию сетевой постановки задачи составления расписания, в которой сеть рассматривается как транспортная для потоков ресурсов, а работы, претендующие на одни и те же ресурсы, упорядочены с помощью простых («финиш-старт») ограничений предшествования, возможно получение расписаний, сохраняющих временную гибкость в рамках ограничений задачи. Такие расписания содержат в себе целый ряд классических расписаний с фиксированными временами старта работ.
Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ:
- федеральная комплексная программа «Исследования и разработки по приоритетным направлениям науки и техники гражданского назначения»;
-госбюджетная научно-исследовательская работа «Разработка и совершенствование моделей и механизмов внутрифирменного планирования».
Цель и постановка задач исследования. Целью диссертации является получение расписаний, которые обладали бы робастностью в динамически меняющемся окружении проекта, позволяя повысить эффективность процессов управления проектами в условиях неопределённости.
Достижение цели работы потребовало решения следующих основных задач:
1. Анализ существующих подходов в области составления расписаний при ограниченных ресурсах в условиях неопределённости.
2. Разработка модели и решение задачи трансформации допустимого расписания с фиксированными временами старта работ в расписание с дополнительными ограничениями предшествования, отражающими ресурсные зависимости (расписание частичного порядка - РЧП) на основе базового эвристического алгоритма.
3. Разработка более сложных алгоритмических моделей построения
робастных расписаний, обладающих улучшенными оценками робастности
относительно используемой меры за счёт возможного увеличения времени
выполнения реализующего алгоритма.
4. Разработка модели динамического составления расписаний,
учитывающей возможность возникновения новых работ во время выполнения
проекта.
5. Построение модели для оптимизации по двум критериям, один из
которых является продолжительностью проекта и минимизируется, а другой
представлен мерой для оценки робастности полученного расписания.
Методы исследования. В работе использованы методы математического моделирования, теории эволюционного моделирования, теории графов, теории исследования операций.
Научная новизна и значимость результатов диссертационной работы состоит в следующем:
1. Построена модель трансформации допустимого расписания с фиксированными временами старта работ в расписание с дополнительными ограничениями предшествования, отражающими ресурсные зависимости (расписание частичного порядка - РЧП), и на основе модели разработан базовый алгоритм-РЧП. Получаемые расписания обладают свойством робастности, позволяющим адаптироваться к некоторым изменениям стартовых времён работ.
2. Разработаны модели получения расписаний частичного порядка и построены соответствующие им алгоритмы нахождения решения -улучшенный алгоритм-РЧП и алгоритм-РЧП-2, которые не уступают базовому алгоритму по числу пар работ, которые не упорядочены друг относительно друга с помощью отношений предшествования (если применяются к РЧП, полученному базовым алгоритмом). Для улучшенного алгоритма-РЧП проведена оценка временной сложности выполнения. Алгоритм-РЧП-2 отличается тем, что между работами вводятся только необходимые дополнительные ресурсные ограничения предшествования.
3. Предложена модель динамического составления расписаний, учитывающая возможность возникновения новых работ во время выполнения проекта. При её выполнении оценивается конечное число позиций вставки работы (среди которых есть оптимальная по минимизации увеличения продолжительности текущего расписания), после чего применяется алгоритм-РЧП-2.
4. Разработана модель двухкритериального эволюционного алгоритма для оптимизации по двум критериям, один из которых является продолжительностью проекта и минимизируется, а другой представлен мерой для оценки робастности полученного расписания.
Достоверность научных результатов. Сформулированные в
диссертационной работе научные положения, теоретические выводы и
практические рекомендации подтверждаются математическими
доказательствами, использованием аппарата математического моделирования, теории эволюционного моделирования, теории графов, теории исследования операций. Они также подтверждены производственными экспериментами и многократной проверкой при внедрении в практику управления.
Практическая значимость и результаты внедрения. Главным недостатком расписаний при их практическом использовании является «хрупкость», проявляющаяся в том, что работы не могут выполняться, как запланировано. Выполненные автором исследования позволили предложить алгоритмы, способствующие повышению робастности используемых расписаний.
Разработанные модели, алгоритмы и методики используются в практике управления проектами в ООО УК «Жилпроект» и 000 «Стройинвест».
Разработанные модели, алгоритмы и процедуры включены в состав лабораторного практикума «Исследование операций в экономике», используемого в Воронежском государственном архитектурно-строительном университете.
Апробация работы.
Основные результаты исследования и научных разработок докладывались и обсуждались на следующих конференциях: Современные проблемы прикладной математики и математического моделирования (Воронеж, 2005), 60-63 научно-технические конференции по проблемам архитектуры и строительных наук (Воронеж, ВГАСУ, 2004-2007).
Публикации. По теме диссертации опубликовано 10 печатных работ, в том числе 3 работы, опубликованные в изданиях, определённых ВАК РФ.
Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем:
в работах [9, 10, 12] автору принадлежат модели и соответствующие им алгоритмы для робастного составления расписаний, в которых продолжительность проекта является монотонной и непрерывной функцией, зависящей от продолжительностей работ, а также модель генетического алгоритма для минимизации продолжительности проекта при нечётких продолжительностях работ; в работах [13, 41] автору принадлежат модели, касающиеся анализа свободных и полных резервов событий в проектных сетях с нечёткими продолжительностями операций и неограниченными ресурсами, а в [64] были доказаны утверждения, позволившие предложить новый алгоритм вычисления критического пути в случае нечётких продолжительностей работ; в [7, 58] было предложено для нахождения функции стоимости работ по разрозненным статистическим данным воспользоваться нечётким регрессионным алгоритмом, а в [65] приведена процедура, позволяющая уменьшить вычислительную сложность эволюционного алгоритма для многокритериальной оптимизации. Модели, алгоритмы и процедуры, разработанные в диссертационном исследовании включены в состав лабораторного практикума [8].
Объём и структура работы. Диссертация состоит из введения, трёх глав, заключения, списка литературы и приложений. Она содержит 130 страниц: 111 страниц машинописного текста, 27 рисунков, 5 таблиц и приложения, библиография включает 130 наименований.
Краткое содержание работы В первой главе отмечается, что модели составления расписания в случае ограниченных ресурсов могут быть разделены на два класса, как относящиеся к:
- детерминированному календарно-сетевому планированию (ДКСП),
» - недетерминированному календарно-сетевому планированию (НКСП).
Как детерминированная задача составления расписания проекта при ограниченных ресурсах (ДЗСРПОР, между работами отношения предшествования заданы как «финиш-старт»), так и обобщённая ДЗСРПОР (возможны все четыре типа отношений предшествования) является NP-трудной, что делает точные методы малоэффективными при решении задач, характерных для реальных приложений.
В большинстве исследований по ДЗСРПОР усилия сосредоточены на разработке точных и эвристических алгоритмов для получения рабочего базового расписания, предполагающего полноту информации и детерминированные условия окружающей среды. Однако во время выполнения проекта могут возникнуть несколько типов нарушений, таких как: более длительное выполнение работы, чем ожидалось; изменение ресурсных требований или доступных количеств ресурсов; появление новых работ и т. д. (сразу отметим, что в дальнейшем будет рассматриваться неопределённость, связанная с изменением продолжительности работ или возникновением новой работы). В этом случае требуется изменение базового расписания.
В диссертационной работе исследуется вопрос получения робастного базового расписания посредством надлежащего распределения ресурсов. Для этого может быть использован некоторый алгоритм построения расписаний частичного порядка. В таких расписаниях каждая работа имеет множество возможных стартовых времён, выбор которых обеспечивает основу для адаптации к неожиданным нарушениям хода выполнения проекта.
Во второй главе рассматриваются: три алгоритма получения РЧП по некоторому допустимому расписанию для обобщённой задачи составления расписания проекта при ограниченных ресурсах; модель динамического составления расписаний, учитывающая возможность появления новой работы; модель двухкритериального эволюционного алгоритма, в которой для повышения качества получаемого расписания предлагается модель задачи составления расписания проекта при ограниченных ресурсах с двумя целевыми функциями - минимизации продолжительности проекта и максимизации робастности.
В третьей главе на реальном примере показано, что расписания с правильно идентифицированными ресурсными зависимостями помогают повысить эффективность управления проектами при варьировании длительностей работ и являются робастными для некоторых изменений стартовых времён работ.
В заключении приведены основные выводы и результаты работы.
Недетерминированное планирование с ограниченными ресурсами
Общей тенденцией в решении задач управления строительством стало использование НКСП в связи с множеством неопределённых переменных, включённых в строительные операции. В жизненном цикле каждого расписания можно выделить две главные стадии: - предварительная - на этой стадии получают первоначальное расписание, которое становится основой для дальнейшей реализации проекта. В вычислениях используются текущие знания о задаче; - выполнение в реальном времени. Происходит управление выполнением проекта с учётом непредвиденных событий, возникающих из-за недостатка необходимой информации о проекте или из-за непредсказуемости внешнего окружения. Различные методологии для составления расписаний в условиях неопределённости могут быть разделены на следующие классы: - синтез робастных расписаний: подходы, которые попадают в эту категорию, используют знания о возможных и неопределённых событиях для получения расписаний, способных абсорбировать некоторое количество непредсказуемости при выполнении, то есть способных отреагировать на некоторые динамические изменения задачи без возникновения конфликтов и разрушения расписания; -частично определённые расписания: эти подходы обычно определяют частичный порядок для рассматриваемых работ и используют введённую таким образом гибкость для защиты против непредвиденных событий. В этом случае не используется никаких знаний о неопределённости; -изменение расписаний: в этом случае текущее расписание может изменяться при выполнении, как только возникнет неожиданное событие, не позволяющее его дальнейшее выполнение. Среди этих подходов можно провести дальнейшее разделение на методы, которые пытаются выполнить восстанавливающие действия как можно более локально для сохранения стабильности решения, и теми, которые исследуют возможность более глобальных действий по восстановлению расписания для улучшения его качества; -динамическое составление расписаний: в этом случае нет базового расписания. В каждом временном интервале во время реализации проекта выбирается (согласно некоторым стратегиям и/или приоритетам) следующее множество работ для выполнения. Надо отметить, что концепция устойчивости решений в сфере составления расписаний остаётся пока достаточно грубой и не очень хорошо определённой. Фактически, анализ литературы, относящейся к составлению расписаний в условиях неопределённости, показывает существование различных определений робастности, соответствующих принимаемым во внимание аспектам задачи. На рис. 1.1 показана качественная классификация вышеприведённых методологий согласно двум стадиям существования расписания.
Модели НКСП с ограниченными ресурсами могут быть также разделены на классы по используемой теории неопределённости.
Стохастические модели составления расписания. При составлении расписания используется вся доступная информация о потенциальных изменениях в ходе выполнения проекта.
В [84] рассматривается два типа расписаний- предварительные (proactive) и реагирующие (reactive). Предварительные или базовые расписания составляются до старта проекта. При этом с целью повышения робастности используются знания о возможных неопределённостях, основанные на статистических данных. Расписание считается робастным, если оно может абсорбировать ожидаемые нарушения, не повлияв на запланированные внешние работы [119]. Для построения такого расписания могут применяться подходы, связанные с использованием теории вероятностей, теории возможностей или добавлением в расписание избыточности.
К сожалению, независимо от того, сколько усилий было затрачено на построение предварительного расписания, все возможные нарушения учесть нельзя.
В случае, когда работа задерживается из-за непредвиденного недостатка ресурсов или возрастания продолжительности одной из предшествующих работ, расписание может стать недопустимым. После этого для восстановления расписания должна быть использована процедура, реагирующая на нарушение. "Реагирующее" составление расписаний может быть использовано самостоятельно или как средство для восстановления предварительного расписания. В первом случае не строится никакого базового расписания, а для динамического выбора работы, которая будет выполняться в рассматриваемый момент, используется стратегия составления расписания [124]. Доводы в пользу необходимости построения базового расписания можно найти в [77, 112, 128, 119].
В [126] проводилось различие между двумя понятиями: качественной робастностыо (quality robustness) и робастностыо решения (solution robustness). Качественная робастность определялась как вероятность того, что проект завершится не позже заданного срока выполнения, в то время как робастность решения (или стабильность) измерялась как: Y, wi I E(Si ) si\ - сумма взвешенных абсолютных отклонений между і математическим ожиданием реального стартового времени Sj и планируемым стартовым временем Sj. Сравнимые с данным определения робастности решения были использованы в [73, 106, 119]. В недавних исследованиях [107, 126] такое определение робастности решений использовалось при формировании целевой функции в задаче составления расписания проекта со стохастическими продолжительностями работ. В [98] разработана эвристическая процедура для ЗСРПОР со стохастическими продолжительностями работ, в которой целевой функцией является минимизация ожидаемой продолжительности проекта. Решение о выполнении следующей работы основывается на отношениях предшествования и доступности ресурсов. Если несколько работ конкурируют за одни и те же ресурсы, то для выбора работы для выполнения решается задача о рюкзаке с несколькими ограничениями. В этой задаче целевая функция представляет максимальный общий вклад выбранных работ в ожидаемую продолжительность проекта. Индивидуальный вклад каждой работы вычисляется как произведение средней продолжительности работы на вероятность того, что работа при выполнении проекта окажется принадлежащей критическому пути. Для аппроксимации значений вероятности использовались значения частот, полученные с помощью симуляции.
Анализ существующих подходов для робастного распределения ресурсов
Допустимое для детерминированной ЗСРПОР расписание, полученное на основе точных или эвристических процедур, определяет предварительное расписание работ, которое служит базовым при выполнении проекта.
Как уже упоминалось ранее, в большинстве исследований по ЗСРПОР усилия сосредоточены на разработке точных и эвристических алгоритмов для получения рабочего базового расписания, предполагающего полноту информации и детерминированные условия окружающей среды. Однако во время выполнения проекта могут возникнуть несколько типов нарушений, таких как: более длительное выполнение работы, чем ожидалось; изменение ресурсных требований или доступных количеств ресурсов; появление новых работ и т. д. (сразу отметим, что в дальнейшем будет рассматриваться неопределённость, связанная с изменением продолжительности работ или возникновением новой работы). В этом случае требуется изменение базового расписания.
В данной работе исследуется вопрос получения робастности базового расписания посредством надлежащего распределения ресурсов. Рассматривается концепция робастности, которая связана с выполнением расписания в реальном времени. Решение задачи составления расписания считается робастным, если оно обладает двумя основными свойствами: способностью "амортизировать" внешние и/или непредвиденные события без потери согласованности (то есть без возникновения конфликтов и разрушения расписания); способностью "идти в ногу" с реализацией проекта, обеспечивая незамедлительное реагирование на различные события.
Замечание: согласно данной концепции робастности, рассмотренные в предыдущем параграфе стратегии составления расписания с монотонно возрастающими и непрерывными по каждому аргументу функциями П, являются робастными относительно варьирования длительностей работ.
Перейдём теперь к описанию различных процедур, используемых для достижения робастного распределения ресурсов. Построение допустимых ресурсных потоков. В [76] для получения допустимого распределения ресурсных потоков F использовалась параллельная схема составления расписания, в которую интегрирована итеративная процедура расчёта потоков.
Интеграция осуществляется следующим образом: F инициализируется так, что начальная работа 0 посылает все свои ресурсные единицы в сток -финальную работу п+1. Затем, каждый раз, когда некоторая работа j выбирается для старта в параллельной схеме, поток изменяется: единицы ресурса, требующиеся j, берутся из входного потока работы п+1, и затем все эти единицы пересылаются от j к п+1. Детализированное описание алгоритмов инициализации INIT и изменения UPDATE приведено ниже. INIT имеет временную сложность 0{п2т), в то время как UPDATE - временную сложность 0{пт) (т - число дуг сети).
Этот алгоритм строит сеть с допустимыми ресурсными потоками и не имеет своей целью максимизации робастности расписания или любой другой меры выполнения проекта.
Метод ветвей и границ. В [107] для распределения ресурсов в проектах с меняющимися продолжительностями работ предложена модель, основанная на использовании метода ветвей и границ. Распределение ресурсов должно было быть согласовано с детерминированным базовым расписанием, а в качестве целевой функции выступала взвешенная сумма ожидаемого отклонения между планируемыми и реализующимися стартовыми временами работ: где М - математическое ожидание; s , - планируемое стартовое время. Авторы получили вычислительные результаты на множестве случайно сгенерированных сетей. Однако они ограничились рассмотрением единственного ресурса и не ограничили изменение длительности работы. Расписания частичного порядка, представленные в форме ресурсных цепочек. В [121, 122] рассматривался подход, состоящий из двух стадий: на первой стадии генерировалось допустимое расписание раннего старта, затем на второй стадии применялась процедура, трансформирующая его в расписание частичного порядка (РЧП), представленное в форме цепочек. ЗСРП соответствует граф G(V,E), где множество вершин V = {0,\,-.,п,п+\} содержит все исходные работы и две искусственно добавленные работы с нулевой продолжительностью, представляющие начало (0-я работа) и финиш (n+1-я работа) расписания, а множество Е содержит дуги, соответствующие ограничениям предшествования между парами работ. В частности, для каждого ограничения sj st + dtj существует дуга (/, j)eE с меткой dtj. Решение ЗСРПОР может быть представлено как расширение G -G = (V,EvEA), где ЕА задаёт множество простых ограничений предшествования i j, которые были добавлены, чтобы разрешить все возможные ресурсные конфликты. Пусть, например, ZXQV - любое подмножество независимых работ такое, что в некоторый момент времени / выполняется rjk Rk хотя бы для одного ресурса. Тогда Zx называется множеством запрета, и минимальное множество запрета (или ресурсный конфликт, или минимальное критическое множество) - это множество ZcZx, такое, что ни одно из его подмножеств не является множеством запрета. Любое такое Z разрешается относительно ресурсного конфликта, если будет добавлено простое ограничение предшествования между любой парой работ из Z. Эти дополнительные ограничения становятся элементами ЕА. Напомним, что расписанием проекта, удовлетворяющим временным ограничениям, называется расписание, удовлетворяющее ограничениям Sj S; + dy V(/,j)eE, и допустимым называется расписание, для которого выполняются одновременно и ресурсные и временные ограничения. В дальнейшем будет использоваться следующее определение [121]: Расписанием частичного порядка (РЧП), соответствующим ЗСРПОР, называется граф POS(V,EvEA), такой, что любое расписание, удовлетворяющее временным ограничениям, также является допустимым.
Модель динамического составления расписаний проекта при возникновении новой работы
Предполагается, что проект состоит из ряда работ V = {l,...,n}, для которых должно быть составлено расписание, учитывающее потребление имеющихся возобновимых ресурсов R = {1,...,К}. Для каждого ресурса к є R задано максимальное количество, которое может быть использовано при реализации проекта - R . Считается, что работа j при выполнении использует неотрицательные количества г каждого ресурса к и имеет продолжительность d;. Ограничения предшествования между работами заданы множеством дуг Е, таким, что (i,j) єЕ означает, что выполнение работы j должно начинаться только после завершения работы і. Задача составления расписания проекта при ограниченных ресурсах (ЗСРПОР) состоит в нахождении вектора стартовых времён работ s = (sj,...,sn), минимизирующего продолжительность проекта, обозначаемую как Mmax. Каждый ресурс к может быть представлен в задаче как объединение R единиц ресурса. Ясно, что в любом допустимом расписании (для которого выполняются ресурсные ограничения и ограничения предшествования) ресурсная единица, выделенная работе і, после завершения і - ой работы передаётся некоторой работе j. Количество единиц ресурса к, передаваемых от работы і работе j, обозначим как fljj . Таким образом, для ЗСРПОР может быть определена транспортная модель. Прежде чем представить её, введём ряд дополнительных обозначений. Пусть 0 и п+1 - это искусственные работы, связывающие все работы є V в один проект. Они добавляются в множество V. Для них rg = гп+і = О Vk = 1, К, dg = dn+i = 0, а в множество Е добавляются дуги (0, j) и (j, n +1) для Vj є V. Кроме того, задаётся достаточно большое число М.
Тогда транспортная модель для ЗСРПОР может быть записана следующим образом: где (2.13) - это целевая функция рассматриваемой задачи; ограничения (2.14) - (2.15) являются выражением требования о том, чтобы входящие и исходящие потоки ресурсов для каждой работы совпадали с её потребностями в ресурсах; (2.16) предотвращает одновременное выполнение работ, связанных протекающим между ними ресурсным потоком; (2.17) описывает связь между переменными flj и XJ;: как только хотя бы для одного ресурса lq поток Ар становится больше 0 (Ацк, 0) переменная XJ; должна принять значение 1; ограничение (2.18) определяет продолжительность проекта; ограничения (2.19) - (2.20) задают допустимые области значений для переменных задачи; ограничение (2.21) задаёт отношения предшествования проекта. Каждой допустимой точке задачи (2.13) - (2.21) можно поставить в соответствие транспортную сеть G, в которой все работы, принадлежащие множеству V, представлены вершинами, а все дуги могут быть разделены на два множества: дуги принадлежащие Е (то есть присутствовавшие в первоначальном проекте) и "ресурсные" дуги, связывающие две работы i, j в том случае, если 31q є {1,...К}, такой, что fly 0. Ресурсные дуги помещаются в множество Ед. Вес дуги (i,j) равен dj, кроме того, ей соответствует вектор потока (fljji,fljj2,.--,ilijK)- Такой граф может быть использован для вычисления временных параметров работ, таких как ранний, поздний сроки начала работы, полный резерв времени и т. д. [37, 46]. Предлагаемая ниже процедура INSET состоит из двух шагов. На первом шаге используется процедура вставки, модифицирующая и расширяющая предложенную в [76]. Для её описания будет введён ряд определений и проведены необходимые доказательства. Базовому расписанию соответствует допустимая точка задачи (2.13) -(2.21) с транспортной сетью G. Рассматривается задача вставки новой работы х с продолжительностью dx и ресурсными требованиями гх , \/к = \,К в существующую транспортную сеть G таким образом, чтобы минимизировать увеличение продолжительности проекта. Для работы х может быть определён отрезок времени [ES LF " ] на основе множеств V и Vx работ, предшествующих и следующих за работой х согласно проекту (ES = max(ESj +dj), LFX = min LS[). Предполагается, что все ранее определённые ресурсные ограничения предшествования остаются неизменными. Ясно, что при этом вставка выполняется только за счёт того, что некоторое количество единиц каждого ресурса, первоначально передающееся от работы і работе j, начинает передаваться сначала от работы і работе х, а затем от работы х работе j. Пусть Р - это работы, предшествующие работе х по ресурсным ограничениям предшествования, a S - это работы, следующие за работой х после вставки. Тогда увеличение продолжительности проекта ЛМтах может быть вычислено по следующей формуле
Практическое применение результатов моделирования
Рассматривается два примера строительного проекта. Все отношения предшествования между работами заданы как «финиш-старт», и при расчёте параметров сетевых графиков используется непрерывный календарь, не предусматривающий праздников и выходных дней. Пример 3.1. Для иллюстрации алгоритмов, изложенных в диссертационном исследовании, используется расписание проекта строительства склада. В табл. 3.1 приводятся первоначальные характеристики работ. Для каждого из трёх типов ресурсов максимальное доступное количество равно 4. Сетевой график данного проекта представлен на рис. 3.1 (работы представлены вершинами). Расписание без ресурсных ограничений, полученное в системе Primavera Project Planner с помощью метода критического пути, приведено на рис. 3.2. Его продолжительность составляет 27 дней, а периоды использования количества ресурсов, превышающего максимально допустимое, можно посмотреть в ресурсной таблице, расположенное в нижней части рис. 3.2. После применения процедуры выравнивания использования ресурсов в Primavera Project Planner получено 30-ти дневное расписание, показанное на рис. 3.3, в котором в каждый из дней используется только разрешённое количество ресурсов каждого вида. Однако на рисунке видно, что критический путь разорван из-за неучёта возникающих ресурсных отношений предшествования (только последние два действия критические). Ясно, что полные резервы работ при этом также рассчитаны неправильно.
Расписание с учётом ресурсных ограничений Получение расписания с ресурсными отношениями предшествования между работами (РЧП). К расписанию с выровненным ресурсным потреблением, полученным Primavera Project Planner, применим алгоритм-РЧП-2 для идентификации и создания ресурсных отношений предшествования. Сеть с добавленными ресурсными дугами изображена на рис. 3.4 (расписание частичного порядка), а на рис. 3.5 приведено расписание, полученное для данной сети в Primavera Project Planner без выравнивания ресурсов. При этом, поскольку учтены все отношения предшествования (как технологические, так и ресурсные), на рисунке видно, что критический путь не прерывается от старта до окончания проекта. Ясно, что величины полных и свободных резервов верны. Primavera Project Planner предоставляет для исследования только одно расписание (набор стартовых времён), по которому могут быть построены ресурсные отношения предшествования. На самом деле, конечно, существуют альтернативные расписания, по которым может быть построено другое РЧП. Так, например, если в расписании работа 4 будет получать ресурсы после начала работы 5, но до начала работ 16, 17, то её выполнение будет происходить в интервале времени [13;14]. При этом, в зависимости от приоритета работ в получении ресурсов, либо работа 16, либо работа 17 будут задержаны, поскольку выполняется 4. Изменение продолжительностей работ. Допустим, что во время выполнения работ заказчик информировал подрядчика, что некоторые (ещё не выполненные) работы должны быть выполнены по-другому. При этом сама сеть не меняется, происходит лишь изменение продолжительности работ 3, 7, 8 и 29, а их ежедневные ресурсные требования остаются прежними. В табл. 3.2 приведены приросты длительностей работ по сравнению с первоначальной. Рассмотрим оценку увеличения продолжительности проекта, и меняется ли порядок выполнения работ. Оценка увеличения продолжительности проекта. Будем использовать для оценки времени выполнения проекта три расписания: 1) расписание, построенное в Primavera Project Planner по методу критического пути (ресурсные ограничения игнорируются); 2) расписание, построенное в Primavera Project Planner для случая выравнивания потребления ресурсов; 3) полученное по алгоритму-РЧП-2 расписание частичного порядка. Посмотрим, что происходит, если найти продолжительность проекта после изменения длительностей работ, пользуясь только полными резервами и не проверяя величин ежедневного потребления ресурсов.
В табл. 3.3, в столбце 3 записан полный резерв работы, посчитанный до изменения продолжительностей работ. Столбцы 6, 7, 8 показывают первоначальное время завершения проекта, оценку этой же величины, полученную на основе полных резервов, и величину продолжительности проекта после нового, с учётом изменений, составления расписания. Если сравнить столбцы 6 и 7 табл. 3.3, то можно сделать следующие выводы: -при игнорировании ресурсных ограничений, оценка времени до изменения продолжительностей работ и после не изменилась и осталась равной 27 дням; -использование расписаний, выровненных по ресурсам, но без созданных ресурсных отношений предшествования, ведёт к тому, что из-за неправильной величины полных резервов оценка продолжительности выполнения проекта увеличивается только на 6 дней. Без пересоставления расписания возникшие ресурсные конфликты остаются незамеченными; - учёт ресурсных ограничений предшествования приводит к увеличению оценки продолжительности проекта на 22 дня по сравнению с первоначальной величиной. Анализ результатов вычислений в столбцах 7 и 8 табл. 3.3, показывает, что: -при игнорировании ресурсных ограничений продолжительность проекта не изменилась при новом составлении расписания; -рассмотрение ресурсных ограничений с игнорированием ресурсных ограничений предшествования между работами привело к тому, что после нового составления расписания, продолжительность проекта непредсказуемо выросла. Вместо 36 дней она составила 50 дней. Это произошло потому, что при составлении расписания заново, система Primavera Project Planner обнаружила ресурсные конфликты, которые были разрешены посредством выравнивания ресурсов. По целому ряду причин подобные скачки в оценке времени выполнения проекта неприемлемы, так как приводят к недоразумениям между заказчиком и подрядчиком. Например, сразу возникает вопрос, почему заказчику ещё до возникновения изменений в продолжительностях работ, было представлено расписание, в котором неправильно вычислены полные резервы. Это вводит в заблуждение по поводу возможности внесения некоторых изменений в план проекта, которые согласно имеющимся резервам не должны оказывать влияние на время окончания проекта. К тому же, без введения ресурсных ограничений предшествования, трудно (а иногда и невозможно) ответить на вопрос, какое влияние на продолжительность проекта окажет изменение продолжительности одной или нескольких работ; - понятно, что для расписания частичного порядка значения посчитанных полных резервов являются настоящими, поэтому оценки продолжительности проекта в столбцах 7 и 8 совпадают.
