Надежные решения о распределении ресурсов в условиях ограниченных ресурсов проекты *
РЕЗЮМЕ
Известные детерминированные с ограниченными ресурсами проблема планирования проектов предусматривает определение интеллектуального график (базовый график или досрочное) от деятельности по проектам, что удовлетворяет соотношениям закончить запуска приоритет и возобновляемых нехватки ресурсов в соответствии с целью сведения к минимуму проекта продолжительность. Этот базовый график служит основой для реализации проекта. Во время исполнения, однако, проект может быть несколько типов нарушений, которые могут нарушить базовому плану. Управление должно затем полагаться на реактивной процедуры планирования для их пересмотра или reoptimizing базовому плану. Цель нашего исследования состоит в разработке процедур выделения средств на деятельность данной базовому плану в целях обеспечения максимальной стабильности в присутствии деятельности изменчивость продолжительности. Мы предлагаем три целочисленного программирования основе эвристик и одна конструктивная процедура распределения ресурсов. Получены нижние оценки устойчивости расписание и представить доклад о вычислительных результатов, полученных на ряд тестовых задач.
Предметные области: Эвристический, Integer программирование, управление проектами, ограниченными ресурсами проекта Планирование.
ВВЕДЕНИЕ
Исследования с ограниченными ресурсами планирования проектов значительно возросла за последние несколько десятилетий. Подавляющее большинство этих научно-исследовательских работ основное внимание уделяется разработке точных и эвристических процедур для создания работоспособной график исходных данных (или досрочного интеллектуального график), предполагая полную информацию и статические и детерминированной окружающей среды. Такие базовому плану, как правило, построены решения так называемых ограниченных ресурсов задача календарного планирования (RCPSP). RCPSP также известен как проблема м, 1 \ минуту \ C ^ югу тах в обозначениях Herroelen Де Reyck и Demeulemeester (2000). м, 1 указывает, что имеем т возобновляемых видов ресурсов, для которых наличие определяется за период продолжительностью единицы; CPM означает, что приоритет имеют отношения с нулевой задержкой закончить запуска типа, а к югу C ^ тах обозначает минимальный makespan цели. Эта проблема заключается в определении графика, который устраивал и с нулевой задержкой ограничений закончить запуска приоритет между мероприятиями и возобновляемых нехватки ресурсов в соответствии с целью сведения к минимуму продолжительность проекта. По отзывам, мы ссылаемся на Herroelen Де Reyck и Demeulemeester (1998); Brucker, Drex1, M 2002) ..
Базовому плану служит ряд важных функций в области оказания помощи по проектам, принимающих решения, такие, как содействие распределению ресурсов, что обеспечивает основу для планирования внешней деятельности (например, мероприятия, которые будут выполняться субподрядчиками) и визуализации будущей работы для сотрудников (Мехта
Во время исполнения, однако, проект может быть значительной неопределенности, которая может привести к многочисленным нарушения графика. Многие виды нарушения были выявлены в литературе (речь идет о Ван (2005) и Чжу, Бард, Ю. (2005), обзор нескольких типов нарушения графика). Деятельность может занять больше времени, чем ожидалось, потребности в ресурсах и ассортимент могут различаться (Lambrechts, Demeulemeester,
Когда происходят сбои в графике выполнения, согласно базовому плану должно быть перенесено. Если мы хотим изучить вышеупомянутый координации и планирования в целях базовому плану по наилучшей степени желательно, чтобы фактическим началом каждого вида деятельности происходит как можно ближе к первоначальной времени начала. Кроме того, как будет указано в следующем разделе, отклонения от запланированной деятельности, начиная раз может привести к многочисленным видам расходов, таких, как затраты на хранение, организационные расходы, и так далее. Базовый с курьерской ожидании сбоев, который защищен от некоторых нежелательных последствий реструктуризации, называется устойчивым. Ван де Вон Demeulemeester, Herroelen и Леус (2005) различают два вида надежности: надежность и качество решения надежности. Качество надежность определяется как вероятность того, что по завершении проекта в рамках проекта сроки. Решение надежности, также известный, как стабильность, определяется как качество планирования окружающей среды, когда есть маленькие отклонения от исходных условий и выполнение графика. Вариант, который мы рассмотрим в этой статье, чтобы ввести стабильности в базовому плану по надлежащее распределение ресурсов (для получения дополнительной информации по решению надежную проекта планирования, мы ссылаемся на Herroelen и Леус (2004a, б), и Herroelen Леус (2004) и Herroelen и Леус (2005)) ..
Мы предлагаем реактивной политики планирования в присутствии деятельности изменчивость продолжительности, что требует выделения ресурсов остаются неизменными. Это означает, что, учитывая определенный график базового уровня, мы будем определять для каждой единицы ресурса последовательность действий, которые будут использовать данную единицу ресурсов. Как следствие, преимущество отношения возникают между деятельности с использованием той же единицы ресурса (ов). Когда деятельность дольше, чем ожидалось, график может быть пересмотрен лишь расчета новых раннего начала график, учитывая приоритет отношений индуцированных решения о распределении ресурсов. Мы разрабатываем три целочисленного программирования основе эвристик и одна конструктивная процедура для принятия решения о распределении ресурсов таким образом, что график стабильность достигнута.
Надежная распределения ресурсов решения проблемы, описанной в этой статье, встречается в различных средах, в том числе разработка новой продукции, коммерческого судостроения, строительства и разработки программного обеспечения, например, когда проектные планы должны быть разработаны при условии предшествования и ресурсные ограничения, но затем должны быть Изменения во время исполнения в связи с изменением масштаба, в недооценке продолжительность деятельности по проекту, и другие отклонения от первоначального графика базового уровня.
Хотя потребность в планировании неопределенности в условиях ограниченных ресурсов графиков проекта привело к появлению новых методик планирования, таких как критическая цепь методологии разработан Goldratt (1997), доказательства, которые теперь доступны буферизации методов, применяемых в данной методике осуществляемые путем поддержки программ- может overprotect makespan проекта и может привести к неоправданно высоких проекта сроки и процедуры могут создавать неустойчивые графики вызвано тем, что питание буфера механизм может не препятствовать прохождению график сбоев во базовому плану. Herroelen и Леус (2001); Elmaghraby, Herroelen и Леус (2003) и Ван де дали и др.. (2005) провели оценку критической методологии цепочку с помощью вычислительного эксперимента на обширный набор тестовых экземпляров, достигнув к парадоксальному заключению, что критическая цепь планирования процедуры самочувствие существенно планирования процедуры, которая пытается защитить проект makespan-трудно защитить, особенно для тех проектов, где сроки выполнения заказов считается важным.
Структура статьи заключается в следующем. В следующем разделе вводятся основные определения и понятия сетей потока ресурсов, используемых для представления решения о распределении ресурсов. Он заключает с официальным заявлением проблемы ведется расследование. Тогда мы предлагаем обзор литературы, а затем распределение ресурсов эвристики, разработанные в этой статье. В следующем разделе мы приводим ниже оценки в соответствии с графиком стабильности, которые могут быть использованы для проверки наших вычислений. После этого мы приводим результаты расчетов, полученных на ряд тестовых задач. Мы сравним производительность наших алгоритмов для некоторых ранее разработанных процедур, а в последнем разделе мы предоставляем выводы.
РАСПРЕДЕЛЕНИЕ РЕСУРСОВ И СЕТИ приток ресурсов
Основные определения и обозначения
Мы предполагаем, проект сети, состоящей из множества N п 1 деятельность в деятельности-на-узлов представление с одной нулевой длительности манекена запуска узла 0 и один нулевой длительности манекена конечного узла Н. Деятельность в рамках проекта J (J = 1, 2 ,..., п - 1), стохастические продолжительность деятельности г ^ к югу J ^, подлежат нулевой задержкой ограничений закончить запуска приоритет, и требуют целого за этот период составляет г ^ к югу JK ^ одной или нескольких возобновляемых ресурсов типа K (K Возобновляемых видов ресурсов (например, труд или оборудование) постоянное наличие свободных мест за период ^ ^ А к югу. Фиктивной деятельности имеют нулевую длительность и нулевой использования ресурсов. Мы предполагаем, приоритет и ресурсов возможно базовому плану S был создан с помощью детерминированных продолжительность деятельности D ^ J ^ к югу. Этот график предусматривает начало деятельности запланировано раз S ^ югу J ^, у = 0 ,..., n.
Рисунок 1 (а) приведен пример проекта. Выше номер узла означает соответствующей детерминированной продолжительности активности, а ниже номер обозначает узел за период требованием для одного типа возобновляемых ресурсов. Ресурс типа за период наличие 10 единиц. Рисунок 1 (б) показывает минимальный базовый график продолжительности проекта порожденных ветвей и границ процедуры Demeulemeester и Herroelen (1992, 1997). Мы определим На примере сети, мы имеем Эта проблема экземпляр будет использоваться в качестве показательного примера по всей статье.
Из-за стохастический характер проектов и проектной деятельности, нарушения могут возникнуть в ходе проекта, в результате чего на самом деле понял, раз деятельность начала с ^ к югу J ^ отличаться от запланированного начала деятельности раза S ^ J ^ к югу. Менеджер проекта должен пытаться уважать базовому плану по максимально возможной степени, чтобы избежать нервозности системы и постоянной реструктуризации ресурсов, другими словами, для поддержания стабильности системы и сокращению расходов нарушения. Таким образом, мы выбрать так называемый режим железнодорожных исполнения никогда не начала деятельность раньше, чем их досрочного время старта в базовому плану. Фактически, базовый время начала стать даты релиза для исполнения расписания. Такого рода ограничение присуще планирование курса, спортивных расписаний, и ж / д и авиа планирования. В рамках проекта, установка, деятельность исполнения не может начаться до необходимые материалы были доставлены на наш сайт (Смит-Дэниелс
После Леус (2003), Herroelen и Леус (2004a, б), и Леус и Herroelen (2004), мы принимаем в качестве меры досрочного стабильности ожидаемых взвешенных отклонение времени старта в фактическом графике от тех, в базовому плану. Иными словами, мы стремимся свести к минимуму , которая является предельной стоимости, начиная деятельности J позже, чем планировалось в базовому плану. Это может включать непредвиденные расходы на хранение, дополнительные организационные расходы, расходы, связанные с соглашениями с субподрядчиками, или только с точки зрения затрат, которая выражает недовольство сотрудников с графиком изменения. Эти расходы могут включать также сбои в графиках других проектов в области окружающей среды комбинированная (Бок
Сети ресурсов потока
Рис 2 () показывает возможные возможности сетевых потоков ресурсов на примере графика на рисунке 1 (б). Твердых дуги представляют собой подлинные отношения приоритет, а пунктирные дуги показывают отношения дополнительные преимущества введенной сетевых потоков ресурсов. Например проект только требует использования одного типа ресурсов, с тем, в целях упрощения записи мы опускаем индексом k. Позитивные потоков F ^ ^ т к югу указаны рядом с каждой стрелки, соответствующие деятельности пары (I, J). Ненулевых потоков: п ^ к югу 0,1 = 5; е ^ к югу 0,2 = 3; е ^ к югу 0,3 = 2; е ^ к югу 1,4 = 1, е ^ 1 к югу, 5 = 3; е ^ к югу 1,6 = 1, е ^ к югу 2,6 = 3; е ^ к югу 3,7 = 2; е ^ к югу 4,8 = 3; е ^ 4 к югу, 10 = 1, е ^ к югу 5,4 = 3; е ^ к югу 6,9 = 4, е ^ к югу 7,9 = 1, е ^ к югу 7,10 = 1, е ^ 8 к югу, 10 = 3; е ^ к югу 9,10 = 5. Представление ресурсов профиля на рисунке 2 (б) содержит ту же информацию, сетью представительств на рисунке 2 (а). Профиль ресурсов можно рассматривать как состоящий из 10 горизонтальных полос (не обращается здесь), по одному для каждой единицы доступных ресурсов. Каждый единицы ресурса передается между мероприятий выделено в соответствующие группы. Например, горизонтальные полосы, соответствующей десятой единицы ресурса на рисунке 2 (б) показывает, что единицы ресурса будет переведен из фиктивной деятельности начала деятельности 3, то из деятельности от 3 до 7 деятельности и, наконец, от деятельности, от 7 до фиктивной деятельности конца.
Сетевого ресурса потока на рисунке 2 (а) и профиль ресурсов показано на рисунке 2 (б) показывают, что 5 из доступных единиц ресурса, переносятся с конца фиктивной деятельности старт к началу деятельности 1. Кроме того, 3 и 2 единицы переносятся с конца фиктивной деятельности старт к началу мероприятия 2 и 3, соответственно. В момент / = 2, 2 единицы ресурса выпустили по видам деятельности 3 и переданы в начале своего непосредственного преемника, деятельность 7. В момент / = 4, активность 1-релизы своих ресурсов. Три единицы ресурса передается в начале его преемника, деятельность 5. Из оставшихся двух единиц ресурса, 1 единица передается начала деятельности 6, а другой начала деятельности 4. Эти потоки ресурсов F ^ югу 1,4 = 1 и / ^ к югу 1,6 = 1 наложить два дополнительных дуг ресурсов указано пунктирной дуги (1, 4) и (1, 6). Эти дуги вызвать дополнительные нулевой задержкой закончить запуска приоритет ограничений, которых не было в первоначальном проекте сети. Таким же образом, потоки ресурсов F ^ югу 5,4 = 3 и / ^ к югу 7,9 = 1 наложить два дополнительных отношений приоритет (5, 4) и (7, 9). Обратите внимание, что приток ресурсов F ^ югу 4,10 = 1 не приводит к дополнительным ограничением приоритет.
Действительно, деятельность 10 (фиктивный конец деятельности) уже транзитивных преемника деятельности 4 в исходной сети проекта. Кроме того, приоритет дуги (0, 4) и (5, 10) не используется для передачи каких-либо ресурсов ..
Рисунок 3 показывает альтернативную сеть потока и, как следствие, альтернативного распределения ресурсов по той же минимальной график makespan показано на рисунке 1 (б). В этом транспортная сеть, ресурс дуги (7, 9) исчезла и заменена дуги (4, 9), проведение потока / ^ к югу 4,9 = 1.
Нарушения деятельности и стабильности
Всем должно быть ясно, что часто можно делать различные решения о распределении ресурсов по тому же графику базового уровня, каждый из которых представлен различных сетевых потоков ресурсов. Возможность создания различных ресурсах на тот же график Исходные условия могут иметь серьезные последствия для устойчивости соответствующих реактивной процедуры планирования.
В этой статье мы предполагаем, что неопределенность связана с деятельностью изменчивость продолжительности. Когда информация становится известно о длительности D ^ J ^ к югу, что взять на себя реализацию отличается от D ^ J ^ к югу, график, возможно, придется пересмотреть. В рамках этого процесса пересмотра графика, мы требуем, распределения ресурсов будут оставаться постоянными, то есть, в одном потоке ресурсов сохраняется. Такие реактивной политики рекомендуется использовать, если специалист ресурсов (например, эксперт персонал) не могут быть переданы между деятельностью в короткие сроки, например, в комбинированная среда, в которой это необходимо заказать ключевых сотрудников или дефицитного оборудования с высокими требованиями к обучению (Аш-
Обратитесь снова к приток ресурсов сети показано на рисунках 2 и 3. Руководитель проекта может получить только четыре из пяти единиц необходимых ресурсов от деятельности 9 непосредственный предшественник, деятельность 6. На рисунке 2, деятельность 9 получает пятый блок ресурсов от деятельности 7, а на рисунке 3 она получает от деятельности 4. Поскольку деятельность 7 планируется завершить в момент / = 4, а деятельность 4 планируется завершить в момент / = 8, сетевой ресурс потока на рисунке 2, вероятно, лучший выбор. Действительно, деятельность 7 должна пройти задержки по меньшей мере шесть единиц времени (мы называем это число с плавающей точкой между активностью и деятельностью 7 9), прежде чем оно повлияет на начало деятельности 9, в то время задержки 2 единицы времени на конец деятельности 4 достаточно задержки начала деятельности 9.
Формальные Постановка задачи
Целевая функция в уравнении (3) состоит в максимизации график стабильности, то есть, чтобы свести к минимуму отклонения взвешенного ожидается между запланированными и понял, раз начала деятельности. Уравнения (4) и (5), было показано ранее как уравнения (1) и (2), являются потока возможности ограничений на возможности сетевых потоков ресурсов. Уравнение (6) определяет железнодорожного планирования реактивной политики: к югу S ^ J ^, понял, времени начала деятельности J, должны быть более запланированного времени начала S ^ J ^ к югу в базовый график и максимальное время окончания Пред предшественников ^ J ^ югу деятельности / в сети G (N, A Уравнение (7) налагает на целостность потока переменных.
Проблема P1 было показано, что обычно NP-близко Леус (2003), ни одного случая нарушения (за дополнительную доказательства NP-твердость количество машин задач календарного планирования со стабильностью цели, мы ссылаемся на Леус и Herroelen (2005)).
АЛГОРИТМЫ STABLE РАСПРЕДЕЛЕНИЕ РЕСУРСОВ
Обзор литературы
Создание возможные потоки ресурсов
Artigues и др.. (2003) представляет простой способ для получения возможности поток ресурсов за счет расширения параллельной схеме поколения график вывода потоков в ходе планирования. Алгоритм итеративно перенаправляет поток до величины допустимого общего потока получается. Распределение обычных может быть легко отделена от графика поколения. Для всех типов ресурсов А, поток / ^ ^ к югу 0nk инициализируется со значением ^ ^ к югу, в то время как все другие потоки имеют значение 0. Напомним, что Остальные этапы процедуры, описанные в алгоритме 1. Этот алгоритм попытки создать возможности сетевых потоков ресурсов, не пытаясь максимизировать стабильность график или любой другой мерой измерения производительности. Он будет использоваться как в наихудшем случае эталоном вычислительного эксперимента описаны в дальнейшем.
Ветвей и границ
Леус (2003) и Леус и Herroelen (2004) предложить отрасли и границ модели распределения ресурсов на проекты с переменной длительности деятельности. Распределение должны быть совместимы с детерминированной график исходных условий и задача заключается в стабильности цели, заданной уравнением (3). Ограничение распространения применяется в процессе поиска для ускорения алгоритма. Авторы получить результаты вычислений на множестве случайно сгенерированных сетей. Тем не менее, они ограничивают свое внимание на одном типе ресурсов и взять на себя экспоненциальной длины нарушение деятельности. Распространение на несколько типов ресурсов потребует пересмотра ветвления решений, принятых отраслевых и границ порядок и последовательность испытаний, участвующих в ограничении распространения.
Связанные форме частичного порядка графики
Policella (2005) (см. также Policella, Одди, Смит,
Цепочки процедуры для генерации прикованный POS представлена в алгоритме 2. Первый шаг сорта всех видов деятельности в порядке возрастания, начиная раз базовому плану. Тогда деятельность постепенно выделенных на реализацию различных цепей. Если деятельность требует более 1 единицы одного или нескольких типов ресурсов, она будет направлена на число цепей равно общее количество требуемых единиц ресурса.
SelectChain функции (J, K) является основной процедуры. В своей основной форме цепочки, которые он выбирает для каждого вида деятельности первых доступных цепочки из необходимых к тип ресурса (с учетом деятельности J, цепи м доступна, если в конце время последнего мероприятия выделено на него, последний (т), не больше времени начала деятельности J).
Предполагая, что график на рис 1 (б) (повторяется здесь как показано на рисунке 4 (а)) берется в качестве входных данных, сортировка шаг даст последовательность действий, представленных в таблице 1. Процедура занимает 1 деятельности, как деятельность первых в списке, и случайным образом выбирает пять цепей для выполнения своих потребностей в ресурсах. Только сети доступны, относящихся к деятельности 0 (фиктивный начала), так что пять сети будут созданы: эти сети с 6 по 10 на рисунке 4 (б). Деятельность 1 затем последних действиях в эти цепи. Следующие два мероприятия в списке, мероприятия 2 и 3, рассматриваются аналогичным образом. Деятельность 2 присваивается сети от 1 до 3, 3 и деятельности возлагается на цепи 4 и 5. Для деятельности 7, следующей деятельности в списке, только две сети, имеют право: цепи 4 и 5. Добавление деятельности 7 этих сетей, мы получаем две цепочки. Процедура продолжается таким образом, добавив к деятельности случайных право цепи, наконец, уступая прикованный POS показано на рисунке 4 (б). Обратите внимание, что приток ресурсов сети и приковали кассы связаны понятия: сетевой ресурс потока определяется глобально для всех типов ресурсов А, тогда как в сети Policella рассчитываются отдельно для каждого типа ресурса К.
Давайте внимательнее посмотрим на рисунке 4 (б). Из-за случайности в основной цепочки процедуры, деятельность 6 выделяется на цепи, принадлежащих к трем различным видам деятельности (деятельность 1, 2 и 7). Это позволит связать воедино исполнение деятельности 1 и 6, и деятельности 7 и 6, 2 пары, ранее не связанных видов деятельности. Такая взаимозависимость, или синхронизации точек, как правило, ухудшает стабильность графику. Чтобы уменьшить количество таких точек синхронизации Policella и др.. (2004) разрабатывать два дополнительных эвристики, ISH и ISH2.
ISH пытается пользу распределения деятельности по общей сети путем выделения деятельности в соответствии с J следующих четырех этапов:
1. Первоначальный м цепи случайным образом выбирается из числа тех, для деятельности / и ограничения последних (м)
2. Если деятельность J требуется более 1 единицы ресурса, то оставшиеся множества доступных сетей делится на два подмножества: множество цепей, которые последний (м), а последний элемент C ^ югу Последнее (т) ^, а множество цепей, которые не, C ^ SUP - ^ ^ к югу Последнее (т) ^ 3. Для удовлетворения всех остальных потребностей в ресурсах, активность J выделяется первая в цепи, принадлежащих к первой подмножество,
4. В случае, если этот набор не является достаточным, а оставшиеся единицы активности J затем рандомизировали в первую доступных сетей, м'', из второго подмножества, м''
Предположим, что ISH при принятии решения по распределению деятельности 6 в задаче экземпляр Рисунок 1 (б) (повторяется здесь как показано на рисунке 5 (а)) случайным образом выбирает седьмой цепи введения ограничений 1
Хотя ISH процедура привела к уменьшению числа ресурсов предшественников деятельности от 6 1:57, второй тип синхронизации точки выходит на рисунке 5 (б). Деятельность 2 и 6 выделяются на различные сети, но их преимущество отношению делает выполнение цепочки 4 зависеть от выполнения цепочки 3. ISH ^ 2 ^ SUP старается свести к минимуму такого рода взаимозависимости путем замены первого шага ISH с более осознанный выбор, который принимает во внимание существующие заказ отношения с теми, мероприятия, которые уже выделены в цепочки процесса. Точнее, шаг 1 из ISH заменяется следующей последовательности шагов:
1,1. М цепи, для которых их последний элемент последней (м) уже отсортированы по отношению к деятельности J собраны из множества P ^ югу J ^;
1,2. Если P ^ J ^ югу
1,3. Последнее ограничение (м)
Применение ISH2 по проблеме например на рисунке 1 (б) (повторяется здесь как показано на рисунке 6 (а)), могут поступить следующим образом. Во-первых, деятельность 1, 2 и 3 будет выделено доступных сетей. Деятельность 7 будут направлены на цепи 4 и 5, потому что нет другого выбора. Следующее мероприятие в нашем списке есть деятельность 5. P ^ ^ 5 подпункта состоит из цепи с 6 по 10 (1 время деятельности предшественника деятельности 5), поэтому случайные цепочки будут выбираться из этого набора, а также ограничение 1
Второй метрических взят из Aloulou и Portmann (2003) и называется гибкость, Flex. Эта мера подсчитывает количество пар деятельности в растворе, которые не связаны простым ограничений приоритета. Обоснование этой меры является то, что, когда два мероприятия не связаны, можно перейти на одну, не двигаясь другой. Чем выше значение гибкого меньше степень взаимодействия между деятельностью. Сетей в цифрах 5 (б) и 6 (б) обе имеют гибкие = 22.
Policella и др.. (2004) прямо не оптимизировать fldt и гибкости. Они применяются итерационные поиск отбора проб, в которых они выполняют цепочки оператора выше число раз из той же первоначальный график и выбрать лучшие решения по fldt или согнуть.
Сокращение сложности задачи
График на рисунке 1 (б) требует неизбежного дуги ресурсов от деятельности к деятельности 5 4. На момент S ^ к югу 4 = 6 6 единственный вид деятельности, ведется с г подпункта 6 = 4. Потому что с ^ ^ к югу 5 г ^ к югу 5 = S ^ ^ 4 к югу, Z, очевидно, силы, и левая часть уравнения (9) в результате обработки 10 - 4 - 3 = 3, что меньше, чем г ^ подпункт 4 = 4. Дуги (5, 4) Таким образом, следует добавить к югу ^ U ^. Давайте проверим, все ли деятельность 6, входящих дуг неизбежным ресурсов. В S ^ югу 6 = 5, только деятельность 5 активен, с г к югу 5 = 3. Множество Z деятельности г с з ^ ^ 1 подпункта г ^ ^ 1 к югу
IP-основе алгоритмов
Как уже упоминалось ранее, проблемы P1 является NP-трудной задачей. В этом разделе мы описываем 3 эвристические алгоритмы, основанные на альтернативных линейного целочисленного программирования формулировки, которые направлены на предотвращение использования случайных величин.
Сведите к минимуму количество дополнительных дуг
Увеличить сумму попарно поплавки
Введем некоторые обозначения. С учетом проекта сети G (N, A), мы определим для всех пар деятельности (I, J) с с ^ ^ к югу я г ^ ^ к югу я Разница во времени между началом деятельности у и прекращение деятельности я: PF ^ югу т = S ^ к югу J ^ - (S ^ ^ к югу я D ^ ^ я к югу). Затем мы определим MSPF ^ ^ т к югу, как минимальная сумма попарно плывет на всех путей из деятельности я с деятельностью j. Это дает нам максимальное количество времени (возможно, нулевой), в которой в конце деятельности я может быть отложено без задержки начала деятельности J (если нет других нарушений место). Например, в сети ресурсов потока представлены на рисунке 3, Есть три пути от активности от 1 до 9 деятельности. Существует путь 1-6-9 с суммой попарно равных плывет к югу PF ^ 16 ^ ^ PF подпункта 69 = 1 +0 = 1, то путь 1-4-9 с суммой попарно плывет равно PF ^ подпункт 14 ^ ^ к югу PF 49 ^ = 2 1 = 3, и путь 1-5-4-9 с суммой попарно поплавки, равным 1. Таким образом, к югу MSPF ^ 19 ^ = тт (1, 3, 1) = 1. Это означает, что прекращение деятельности 1 может быть отложено на 1 единицу времени без ущерба для начала деятельности 9. Очевидно, что высокие MSPF ^ ^ т к югу значения приведет к более стабильной сети потока ресурсов.
Целевая функция (16) максимально минимальная сумма попарно плывет по всем парам деятельности (I, J), удовлетворяющих неравенству S ^ югу я ^ D ^ ^ к югу я Уравнения (17) - (19), поток и дополнительные дуги трудности, которые мы уже объяснили в предыдущем разделе. В уравнениях (20) - (23) вычислить минимальную сумму попарно плавает в рекурсивных образом. Уравнение (20) отделяется один дуги (I, K), где к деятельности либо прямым наследником деятельности я, или неизбежным преемником ресурс деятельности I. Остальные попарно поплавок MSPF ^ ^ к югу кДж рассчитывается рекурсивно. Уравнение (21) делает то же самое, но в настоящее время деятельность К возможным преемником дополнительных деятельности я (т. е. (я, Ь) Если возможные дополнительные дуги (I, K) не присутствует в текущем решении, переменная х ^ ^ ик югу будет равна нулю, а соответствующие уравнения (21) не будет обязательным (M снова быть большое целое число). Если по одной паре деятельности / и / все MSPF ^ ^ т к югу ограничения не носят обязательного характера, то эти виды деятельности как приоритет и независимых ресурсов в текущем сетевых потоков ресурсов, а также к югу MSPF ^ т ^ переменная получения максимального значения C, как насильственные уравнением (23), C время положительная постоянная.
Высокие значения C приведет подход, в котором мы стараемся максимально увеличить количество ресурсов и приоритет независимой деятельности. Низкие значения C приведет подход, в котором мы готовы принести в жертву независимость пару деятельности, если это приводит к общему увеличению других MSPF югу ^ т ^ ценностей. Это увеличение должно то по крайней мере равным C. В наших экспериментах мы поставили C = 10. Наконец, уравнения (22) дает определенные рекурсия заканчивается, и уравнения (24) - (26), двойных и целостность ограничений ..
Чтобы увидеть, как целевой функции (16) оценивает различных сетей потока ресурсов, давайте еще раз взглянуть на цифры 2 и 3. Обратите внимание, что к югу MSPF ^ 39 ^ ^ MSPF подпункта 79 ^ ^ MSPF подпункта 59 ^ и ^ MSPF подпункта 49 ^ будет иметь разные значения в обеих сетях приток ресурсов, в то время как стоимость всех других MSPF югу ^ ^ т переменных быть одинаковыми. На рисунке 2, подпункт MSPF ^ 39 ^ ^ = MSPF подпункта 79 = 5, а 9 деятельности требует значительных ресурсов (и старшинство), независимо от деятельности 5 и 4, уступая MSPF югу ^ 59 ^ ^ = MSPF подпункта 49 = C. В Рис 3, 9 деятельности требует значительных ресурсов и приоритет независимо от видов деятельности 3 и 7. Таким образом, к югу MSPF ^ 39 ^ ^ = MSPF подпункта 79 = C. Тем не менее, деятельность 9 в настоящее время ресурсов зависит от деятельности 5 и 4, и только одна единица времени отделяет конец деятельности 4 с самого начала деятельности 9, так что мы получить MSPF ^ югу = 59 ^ MSPF подпункта 49 = 1. Потому что 5 5 2C> 1 +1 2C, сетевой ресурс потока на рисунке 2 будет предпочтительнее, чем к сетевому ресурсу, поток на рисунке 3. Это логический выбор, потому что поплавок 5 единиц времени будет достаточно, чтобы поглотить большую (если не все) нарушение в результате деятельности ближайшие 3 и 7, в то время как единое целое время плавать, не всегда достаточно для покрытия нарушения ближайшие 5 от деятельности и 4. Это уже шаг вперед по сравнению предыдущей модели, которая была не в состоянии различать между сетями на рисунках 2 и 3 (обе сети, имеющие равное число дополнительных дуг) ..
Минимизировать нарушение оценкам
Предыдущий эвристический, направленных на создание надежной распределения ресурсов за счет максимального сумму попарно плывет по всем парам деятельности (I, J), удовлетворяющих ^ югу я ^ D ^ ^ к югу я Эвристические, описанные в этом разделе сделана попытка свести к минимуму влияние распространения предполагаемых нарушений в настоящее время более избирательны в выборе попарно поплавки. Мероприятия, для которых базовым начиная время близко к проекту makespan будет выше вероятность того, нарушается, чем мероприятия, которые запланированы ближе к началу проекта, потому что нарушения будут распространяться и накопленный в рамках всей сети, что привело к своего рода эффект снежного кома. Поэтому мы должны уделять повышенное значение плавать, происходящих в конце графика, по сравнению с равным количеством листового происходит в начале график, потому что первый поплавок, скорее всего, использоваться задержки деятельности.
Чтобы получить этот выбор более информированным попарно плавает, мы упрощаем нашей исходной задачи P1 и решить эту проблему упрощенной оптимальности. Упрощенная версия P1 использует следующие два предположения:
Успенский 1: Только одна деятельности продолжительность нарушения D ^ ^ я к югу
Успенский 2: Каждое мероприятие имеет равную вероятность стать жертвой этого нарушения.
Поскольку деятельность, начиная с базового времена, близкие к проекту makespan будут прерваны более чем сценарии мероприятий, начиная с первого периода времени базового графика, разработка автоматически подчеркнуть сохранение дополнительных плавают между видами деятельности, начиная в более поздние периоды времени в базовом график. Кроме того, при наших предыдущих эвристики оптимизированы некоторые характерные надежных сетей потока ресурсов, целевая функция (27) напоминает первоначальную цель стабильности (3) более подробно. Кроме того, целевая функция (27) позволяет очень естественной интеграции деятельности веса. Мы надеемся, что все это приведет к более точной аппроксимацией стабильности цели.
Конструктивные процедуры распределения ресурсов
В этом разделе мы представляем конструктивную процедуру распределения ресурсов, которые мы называем Мабо (близорукий активности основе оптимизации). Процедура близоруким, потому что мы не смотрим на другие виды деятельности при принятии решений относительно наилучшего распределения ресурсов для деятельности. В отличие от большинства действующих процедур распределения ресурсов, Мабо является деятельность на основе ресурсов, а не основаны. Мабо состоит из трех шагов, которые необходимо выполнить для каждого вида деятельности j. Шаг 1 проверяет является ли текущий предшественников деятельности J может освободить достаточное единиц ресурсов с целью удовлетворения потребностей в ресурсах на деятельность j. Если нет, то дополнительные предшественников, будут добавлены в следующий этап с минимальными последствиями для стабильности. Шаг 3 затем определяет потоки ресурсов F ^ ^ IJK к югу от предшественника деятельности я с деятельностью j. Подробные инструкции о процедуре представлены в Алгоритм 3.
В инициализации шаг, множество ресурсов дуг ^ югу R ^ инициализируется множество неизбежных дуг ^ U ^ к югу. Для каждого типа К ресурсов, число единиц ресурсов Alloc ^ ^ к югу 0k, которые могут быть перенесены из фиктивной деятельности начать 0 инициализируется наличия ресурсов ^ ^ А к югу. Деятельности по проектам, помещаются в список в порядке возрастания их запланированного времени начала использования уменьшением предполагаемого взноса, стоимости стабильности с ^ ^ я к югу, как тай-брейк правила. Эти значения с ^ ^ к югу я рассчитываются следующим образом. Для каждого вида деятельности я, мы вычисляем среднюю задержку . Затем мы применяем политики железнодорожного исполнения всех транзитивных преемников деятельности я в сети G (N, A С учетом этих понял, время начала, то мы устанавливаем значение с ^ ^ я к югу, чтобы сумма всех взвешенных время начала отклонения переходных преемников деятельности I. Это значение с ^ ^ я к югу дает нам меру вклада деятельности общей стабильности стоимости ..
На шаге 1 Мабо, мы рассчитываем количество единиц ресурса Свободна ^ югу JK ^ (A Если это количество доступных единиц ресурса не является достаточным для любого й тип ресурса, мы должны найти дополнительные источники для данного типа ресурсов, в результате чего новые ограничения приоритета, которые должны быть добавлены к югу ^ R ^. Это то, что мы делаем в Шаг 2. Мы определим множество H ^ J ^ к югу от всех возможных дуги между возможным источником ресурсов ч тока / активности и / себя. При решении проблемы стрелкового рекурсии мы можем найти подмножество H * ^ к югу J ^ Н югу ^ J ^, что составляет недостающие потребности в ресурсах у, для любого й тип ресурса как минимум стабильности стоимости Stability_cost (A
Стабильность стоимости Stability_cost (A вычисляется путем имитации казни 100 (частично) график, сохраняя фиксированный потоков ресурсов и соблюдения дополнительных ограничений приоритета (подпункт ^ R ^ Множество дуг ^ H * J ^ югу добавляется к югу ^ R ^ такой, что обновленный Свободна ^ югу JK ^ (A деятельности решается близоруко.
На шаге 3, мы выделим фактические потоки ресурсов F ^ ^ к югу IJK на предшественников / в (A Если Свободна ^ югу JK ^ (A Мы стараемся делать это в разумный путь, потому что жадный алгоритм даже укрепить близорукий характер Мабо введены в Шаг 2. Предшественников, я отсортирован по увеличению числа их еще не начали преемников л с подпунктом г ^ LK ^> 0, так как эти наследники могут рассчитывать на эти средства должны быть доступными. Два тай-брейка правила: снижение закончить раз и уменьшение разницы продолжительности деятельности. Принцип заключается в том, что предшественники в начале отсортированного списка обычно имеют более высокую вероятность сорвать будущей деятельности. Желательно, чтобы потреблять все единиц ресурса они выпускают как можно больше таких, что их возможные большое влияние на позднее мероприятий нейтрализованы. Это процедура выделения переделано для каждого типа К ресурсов самостоятельно.
После всего этого мы перезагрузить три шага процедуры следующей деятельности в списке, пока мы не получили полной возможности распределения ресурсов в конце списка. Процедура использует оптимальный алгоритм рекурсии для каждого вида деятельности, но не обязательно оптимальным в отношении всех мероприятий.
В качестве примера, мы столкнемся с Мабо процедуры по минимальной makespan график на рис 1. Этот проект имеет только один тип ресурса, поэтому мы будем опускать индекс К. Начнем с того, сортировка nondummy деятельности в соответствии с увеличением времени старта, уступая список (1, 2, 3, 7, 5, 6, 4, 8, 9). Все имеющиеся единиц ресурсов, выделяемых на фиктивной деятельности старт (Alloc ^ югу 0 = 10).
Деятельность 1 стоит на первом месте в списке. Эта деятельность имеет только один предшественник, такие, что к югу Свободна ^ 1 = ^ Alloc югу 0 = 10, что является достаточным для выполнения потребностей в ресурсах г, к югу 1 = 5. Положим F ^ югу = 0,1 мин (Alloc югу ^ ^ 0, г \ к югу 1 ^ - Alloc югу ^ 1) = 5, Alloc ^ югу 0 = 5, и к югу Alloc ^ 1 = 5.
Деятельность 2 и 3 рассматриваются таким же образом. И принять их ресурсы от предшественника лишь, активность 0. Это истощает ассигнования на деятельность 0: Alloc югу ^ 0 = 0.
Следующее мероприятие в списке деятельности 7. Свободна ^ югу 7 = ^ Alloc югу 3 = 2, что достаточно для выполнения требования подпункта г ^ 7 = 2. Положим F ^ югу = 3,7 мин (Alloc югу ^ ^ 3, г, к югу 7 ^ - Alloc югу ^ 7) = 2, к югу Alloc ^ 3 = 0, а к югу Alloc ^ 7 = 2.
Деятельность 5 создает каких-либо проблем. Мы рассчитываем Свободна югу ^ 5 = ^ Alloc подпункта 1 = 5> г ^ 5 ^ к югу. Положим F ^ югу 1,5 = 3, Alloc ^ югу 1 = 5 - 3 = 2, а к югу Alloc ^ 5 = 3.
Выделения ресурсов для деятельности 6, следующий деятельности в списке, является более сложной. Мы Свободна ^ югу 6 = ^ Alloc югу 2 = 3, что меньше, чем потребности в ресурсах деятельности 6, г, к югу 6 = 4. Мы должны получить еще одну единицу ресурсов с одного из мероприятий, которые уже закончили. Приемлемыми видами деятельности являются мероприятия 7 и 1, поэтому мы поставили H ^ подпункт 6 = ((7,6), (1,6)). Два подмножества должны быть оценены, а именно ((7,6)) и ((1,6)). Моделирование показывает, что оба подмножества имеют нестабильности стоимость 0,11 (это означает, что, в среднем, в начале деятельности 6 может быть отложено на 0,11 единиц времени в результате дополнительных отношении преимущество), так что мы произвольно выбрать первый подмножества: H * ^ к югу 6 = ((7,6)) и добавьте эту дугу ^ югу R ^. Мы приходим к шаг 3 процедуры Мабо, с множеством предшественников должен быть отсортирован равна (2,7). Деятельность 2 не имеет наследников, начиная позднее с ^ ^ к югу 6 = 5, и единственным наследником деятельности 7 является фиктивной конца, поэтому мы вынуждены прибегать к нашей первой тай-брейк. Деятельность 2 заканчивается позднее 7 деятельности в базовых график, так что деятельность 2 появится первый в списке, и мы приходим на шаге (3.2) с отсортированный список предшественников равно (2,7). Сначала пройти через это время цикла приводит к югу F ^ 2,6 = 3, Alloc ^ к югу 2 = 0, а к югу Alloc ^ 6 = 3.
Мы проходим в то время как цикл второй раз, и множество / ^ к югу = 7,6 мин (2, 4 - 3) = 1, подпункт Alloc ^ 7 = 2 - 1 = 1, а к югу Alloc ^ 6 = 3 +1 = 4, завершение выделения ресурсов для деятельности 6. Затем процедура продолжается до полной возможности выделения ресурсов не найдено. График представления полной сетевой поток ресурсов порожденных процедуры Мабо это показано на рисунке 7 ..
Нижние границы ГРАФИК РАСХОДОВ СТАБИЛЬНОСТЬ
В этом разделе, получим нижнюю границу стоимости график стабильности для данного графика. Получение жесткой нижняя граница важна, поскольку она позволяет нам оценить работы наших алгоритмов в связи с нашей работой меры. Нижняя граница расчетов определить стабильность стоимости взносов, которые являются необходимыми. К ним относятся стабильность стоимости взносов в связи с первоначальным отношений приоритет и неизбежное ресурсов дуг ^ U ^ к югу. Stability_cost (A Мы будем называть этот слабый нижней границы к югу, как LB ^ ^ 0.
Алгоритм 4 представляет собой жесткий нижней границы, которое может быть найдено путем сосредоточения внимания на решения о распределении ресурсов, которые не решены, принимая во внимание неизбежные дуги A Мы рассчитываем по каждому виду деятельности J лучшем случае для решения проблемы близоруких распределения ресурсов. Начнем с расчета минимального количества ресурсов пунктов Alloc ^ ^ ик югу выделено на момент S ^ J ^ к югу к каждому виду деятельности я с с ^ ^ я к югу
Как и в шаге 1 процедуры Мабо, нам необходимо знать количество единиц ресурсов, которые выделяются на предшественников деятельности / в Мы не знаем, неизвестным происхождение Alloc югу ^ ^ х единиц предшественников деятельности /, либо нет. В любом случае, Есть не более Свободна югу JK ^ ^ ^ = Alloc югу х ^ ^ выделено предшественникам / на время S ^ J ^ к югу. Если существует А, для которых Свободна ^ ^ к югу JK
После этого для каждой деятельности мы определяем деятельность * ^, который является самым дорогостоящим по урегулированию и вычислить Stability_cost (H * ^ к югу у * ^ Результирующая стоимость стабильность жесткие нижняя граница стоимости стабильности графику. Мы будем называть усовершенствованной нижней границы к югу, как LB ^ 1 ^.
Проиллюстрируем расчет этот обновленный нижняя граница деятельности 9 из нашего примера график на рис 1. Начнем с расчета Alloc югу ^ я ^ 'ы во время S ^ югу 9 = 9. Очевидно, что к югу Alloc ^ 6 = 4 и Alloc югу ^ 8 = 3, так как не деятельность начал после их окончания раза, то есть к югу Z ^ 6 = Z ^ подпункт 8 = (). Для деятельности 4, мы Alloc ^ к югу 4 = тах (0, г \ к югу 4 ^ - г ^ ^ к югу 8) = 1. Для всех других видов деятельности я, можно убедиться, что к югу Alloc ^ я = 0. Это приводит к югу Alloc ^ х = 10 - (4 3 1) = 2 единиц ресурса неизвестного происхождения. Все это означает, мы уверены, что по крайней мере один блок ресурсов по-прежнему, выделяемых на деятельность 4. Аналогичным образом, по крайней мере 4 и 3 единицы ресурсов, выделяемых на деятельность, 6 и 8 соответственно. Это оставляет нас с 2 единиц ресурса, для которого мы не знаем, в какой деятельности они распределены. В нашей нижней границы, мы делаем предположение, что эти единиц ресурса выделены предшественникам деятельности 9, и мы получаем Свободна ^ югу 9 = Alloc ^ ^ 6 югу Alloc ^ югу х = 6, что больше, чем г ^ к югу 9 ^, так что никаких дополнительных расходов, понесенных устойчивости для решения проблемы распределения ресурсов для деятельности 9.
При расчете нижняя граница LB югу ^ 1 ^, мы можем столкнуться с некоторыми деятельности, для которых проблема распределения ресурсов не может быть решена без дополнительных затрат стабильности, то есть Stability_cost (H * ^ к югу J ^ ^)> LB ^ ^ к югу 0 для некоторых видов деятельности j. Если это число стабильности стоимости расширением деятельности, по крайней мере два, мы можем ужесточить нижняя граница LB ^ ^ 1 к югу еще, глядя на совместное действие решения проблемы распределения ресурсов для каждого из этих видов деятельности. Подробные инструкции этого ужесточили нижняя граница LB ^ 2 ^ к югу представлены в алгоритме 5. Процедура состоит из двух этапов. Первый этап очень похож на расчет LB югу ^ 1 ^: мы определяем все стабильности стоимости расширением деятельности, добавьте их в набор I, и хранить подмножества дуг в состоянии решить свои проблемы распределения ресурсов. На втором этапе, мы рассчитываем стоимость стабильности для всех возможных комбинаций этих подмножеств. Как мы уверены, что одна из этих комбинаций подмножеств появится в сети оптимального потока ресурсов (WRT стабильности график), сочетание подмножества с минимальными затратами стабильности дает нам ужесточили снизу.
Результаты расчетов
Мы провели вычислительный эксперимент, в котором мы оценили эффективность нашего ресурса процедур выделения земельных участков от выполнения процедуры, которые уже описаны в литературе. Показатели деятельности, используемые в нашей вычислительного эксперимента стоит график стабильности Процедуры были проверены на J30, J60 и J120 например наборы PSPLIB (Колиш
Для каждого вида деятельности фактического моделируемых понял продолжительность деятельности исходит из правой перекос бета-распределение с параметрами 2 и 5, и ожидается, равное продолжительности детерминированной деятельности. Минимальные и максимальные значения этого распределения равной 0,5 раза и 2,25 раза ожидаемой продолжительности активности соответственно. Для каждого экземпляра и порядок (как точные и эвристические), 100 работает моделирования Были приняты меры для оценки устойчивости цели.
Результаты, полученные на экземпляре J30 набора приведены в таблице 3. Второй столбец с заголовком "Стабильность" приведены средние расходы стабильности для каждого из 480 J30-задачи случаев PSPLIB. Потому что ни Artigues и др.. (2003), ни Policella и др.. (2004) принимать во внимание деятельность весов W ^ J ^ к югу в принятии решений, распределение ресурсов, мы также покажем в третьей колонке средняя стоимость стабильности результатов, полученных с деятельностью всех весов W ^ J ^ югу установлен в 1, то есть, В пятой колонке указывается количество экземпляров, которые могут быть решены путем доказали оптимальность решатель MIP в заданное время. Очевидно, что этот столбец имеет значение только для эвристики целочисленного программирования.
Основной цепочки процедура показывает худшие производительности для обеспечения устойчивости мер. Это в соответствии с ожиданиями, поскольку процедура выделяет средства на деятельность в совершенно случайным образом. Одна вещь, которая обращает на себя внимание тот факт, что процедура Artigues и др.. (2003), который только ставит своей целью получение возможности сетевых потоков ресурсов без какой-либо стабильности цели, превосходит основные цепочки процедуры, а также к югу ISH ^ ^ гибкие процедуры. Причина этого заключается в том, что процедура Artigues всегда принимали во внимание деятельность, которые поставляют ресурсы для данного вида деятельности в том же порядке (то есть, увеличение времени начала). Таким образом, ресурс поставщиков для определенного вида деятельности, более вероятно, будет одинакова для различных типов ресурсов. В отличие от основной цепочки и IHS ^ ^ к югу гибкие процедуры выбора первого поставщика ресурсов на данный вид деятельности и тип ресурса случайным образом, что в целом приведет-когда несколько типов ресурсов, считаются более-ресурсов зависимостей между различными мероприятиями. ISH ^ югу гибкие процедуры ^ является единственной процедурой, разработанной Policella, которое превосходит процедуры Artigues именно по этой причине: случайность сократить за счет использования политики, где предшественники предпочитали в качестве консультантов поставщиков на данный вид деятельности.
Из эвристики, разработанные в этой статье, минных выполняет из лучших на этом случае набор, а затем Мабо и MaxPF, отметить, что результаты добытого за невзвешенных цель стабильности довольно близко к нижней границе LB ^ ^ два подпункта, отметив, что в результате притока ресурсов сети является очень хорошим решением в связи с невзвешенное цель стабильности, наконец, эвристический MinEA не выполняет очень хорошо по сравнению с заминированы, MaxPF и Mabo, но все же дает лучшие результаты, чем процедуры, разработанные Artigues и Policella . Причина этого умеренной производительности эвристического MinEA можно найти в грубой аппроксимации стабильности цели, и в том, что эвристический не в состоянии сделать осознанный выбор между двумя сетями потоков ресурсов с равным количеством дополнительных дуг.
Как раз для расчета, мы видим, что IP эвристики есть среднее время вычисления (более или менее) за одну секунду. Кроме того, почти все проблемы могут быть решены к оптимальности, в рамках отведенного срока. Наконец, отметим, что процедура Мабо получает результаты об устойчивости цели, которые немного лучше, чем эвристический MaxPF, а его расчет времени в среднем в 25 раз короче.
Чтобы определить, что эти выводы справедливы и для больших случаев проблемы, рассмотрим таблицу 4, представляя результаты по 480 проблемам J60 например набор PSPLIB. Прежде всего заметим, что нижняя граница рассчитывается здесь не нижняя граница LB ^ 2 ^ к югу, представленные в предыдущем разделе, но слабый вариант. Потому что число сочетаний из подмножества L ^ ^ к югу JK может стать очень большой, мы ограничиваем число стабильности стоимости расширением деятельности таким образом, что не более 10000 подмножество комбинации должны быть оценены. Конечно, это серьезно уменьшает плотность снизу.
Заметим, что ни один из эвристических Policella в превзойти процедуры Artigues этого экземпляра набора. Опять же, это можно объяснить тот факт, что алгоритмы Policella иногда делают очень разные решения о распределении ресурсов между различными видами ресурсов. Если посмотреть на время вычислений, мы видим, что IP эвристики требуется гораздо больше времени, чем на экземпляре J30 множество. Среднее время вычисления для этих эвристик настоящее время составляет около 40 секунд проблемы и ряд проблем, мы смогли решить к оптимальности снижается до менее половины случаев. Как следствие, производительность IP эвристики деградирует, и наши Мабо процедуры в настоящее время получает результаты, которые весьма схожи с теми из наших лучших IP эвристические, заминирован. Тем не менее, если мы предоставим заминированных модели с выходом процедуры Мабо в качестве отправной решения, результаты представлены для весовых стабильность может быть улучшен с 737,72 до 729,77, а невзвешенное стабильности может быть снижена с 149,17 до 147,25. Кроме того, в среднем времени вычисления капель от 39 до 37 секунд. Таким образом, мы можем применить заминированных модель в качестве своего рода улучшения процедуры в верхней части процедуры Мабо.
Результаты, полученные на 600 проблемы J120 например набор представлены в таблице 5. Эвристический Заминированный не нашел целое решение в рамках отведенного срока, так что никаких результатов представлены здесь. Кроме того, заминированных модель не может быть использована как улучшению процедуры на верхней части процедуры Мабо, а никаких улучшений были обнаружены в пределах срока. Эвристический MaxPF нашел целых решений, но и для небольшого набора связанных с этим проблем заняло больше времени, чем 60 секунд. В этом случае, решать MIP было разрешено превышать заданное время, прерывание с первым решением целого нашли. Это находит отражение в среднем времени вычисления 155 секунд. Результаты об устойчивости цель показать, что Мабо является явным победителем. Кроме того, она требует только около половины второго на проблемы, в среднем. По сравнению с IP эвристики, время работы процедуры Мабо не взрывается, когда ряд мероприятий возрастает.
ВЫВОДЫ
Мы описали реактивной процедуры планирования для RCPSP в присутствии деятельности изменчивость продолжительности. Эта процедура требует, чтобы определить сетевой ресурс поток, который показывает, каким образом ресурсы передаются от одного вида деятельности к другому. Мы сформулировали задачи определения сетевого ресурса потока такова, что стоимость график устойчивости (определяется как сумма взвешенных отклонений от запланированного начала деятельности раза базовому плану и фактически реализованы раз начала деятельности во время выполнения проекта) сведена к минимуму. Наш обзор литературы показал, что научно-исследовательских работ в этой области все еще находятся в начальной стадии.
Мы представили три новых эвристик на основе суррогатных MIP формулировки основных сильно W-трудной задачей. Эвристический MinEA свести к минимуму дополнительные отношений приоритет введенных решения о распределении ресурсов; MaxPF эвристический максимальную сумму попарно плавает в сети G (N, ^ АУА югу R ^), а также сводит к минимуму минных эвристического приближения взвешенной стоимости стабильности . Кроме того, мы разработали близоруких распределения ресурсов называемый эвристический Мабо, одним пройти процедуру, которая пытается построить надежную сеть потока ресурсов, глядя на один активность во время и в решении его проблемы распределения ресурсов, а также возможно. Мы также получены нижние границы в соответствии с графиком стоимость стабильности.
Выступления MinEA, MaxPF, добыл и Мабо были оценены в отношении четырех ранее разработанных процедур набор случайно сгенерированных тестовых задач. Все эвристики, разработанные в этой статье доказал свое превосходство над существующими алгоритмами. Заминированный модели получить максимальную производительность от стабильности задача о проблемах с 30 или 60 видов деятельности. Тем не менее, он не нашел возможным решением о проблемах с 120 мероприятий в течение срока, 60 секунд. Процедура Мабо обеспечивает очень хорошие результаты в целом по стабильности цели в течение короткого времени вычислений. Наконец, модели MinEA MaxPF и не получить лучшие результаты, чем процедуры Мабо, требуя более длительное время вычислений.
В этой статье мы описали простой реактивный подход планирования для проектов с неопределенной длительности деятельности. Он требует от руководителя проекта для поддержания фиксированного потока ресурсов между видами деятельности, во исполнение данного проекта. Эвристики и алгоритмы, предложенные в этой статье дают нам эффективную процедуру график ремонта, способны спасти от многих видов расходов (затраты на хранение, организационные расходы ,..., т.д.) в результате задержек в деятельности, начиная раз.
Процедуры, разработанные в этой статье обещание провести иметь сильные управленческие воздействия. Они обеспечивают первоначальное доказательство практического средства для разработки проекта базовых таблицах, которые являются надежной в отношении нарушений, которые могут возникнуть во время выполнения проекта. Это резко контрастирует с "принять или оставить его" одним графиком подхода, содержащиеся в существующих коммерческих пакетов без каких-либо положения для планирования качества надежности и стабильности. Наши процедуры определить возможные средства для оценки стабильности и относительные затраты на изменение графика. Развертывание подходов, описанных в этой статье, могут уменьшить сбоев и задержек, связанных с прерываниями в нескольких проектов установки (Бок
Процедуры, разработанные в данной статье, предполагается, что неопределенность заключается в деятельности продолжительность и устойчивость базовому плану может быть повышена за счет надлежащего распределения ресурсов. Исследования по генерации стабильного базового графика при условии нарушения возобновляемых ресурсов просто новых (Lambrechts и др.., 2006a, б). Управление проектом может также рассчитывать на альтернативные процедуры для создания надежных графиков исходных условий, например, путем включения времени буферов (Ван де Вондер и др.., 2005, 2006). Наше будущее исследовательские усилия направлены на расширение нашей активной / реактивной методологии планирования, в соответствии с общими ограничениями приоритет и с учетом различных типов времени, ресурсов, стоимости и сферы неопределенности и ее интеграции в глобальную процедуру управления рисками (Schatteman, Herroelen, Ван де Вондер,
* Это исследование было поддержано проекта OT/03/14 Научно-исследовательского фонда KULeuven проекта 06163 и при поддержке Национального банка Бельгии.
Ссылки
Aloulou, М.,
Artigues, C., Michelon П.,
Artigues, C.,
Эш Р.,
Айтуг, H., Лола, М., Мак-Кей К. Мохан, S.,
Бок, Д. Б.,
Бауэрс, J. (1995). Критичности в условиях ограниченных ресурсов сети. Журнал Оперативного общества исследований, 46, 80-91.
Brucker П., Дрексл А., M
Cesta А., Одди, А.,
Debels Д.,
Demeulemeester Е.,
Demeulemeester Е.,
Demeulemeester Е.,
Elmaghraby, С. Е. Е., Herroelen, W.,
Goldratt, Е. (1997). Критическая цепь. Great Barrington, М.: Удмуртский госуниверситет.
Herroelen, В. Де Reyck, B.,
Herroelen, В. Де Reyck, B.,
Herroelen, W.,
Herroelen, W.,
Herroelen, W.,
Herroelen, W.,
Igelmund Г.
Igelmund Г.
Колиш Р.,
Колиш Р.,
Колиш Р.,
Lambrechts О., Demeulemeester Е.,
Lambrechts О., Demeulemeester Е.,
Леус, R. (2003). Генерации стабильных планов проекта. Диссертация, факультет прикладной экономики, Бельгия: Католический Левен Universiteit.
Леус, Р.,
Леус, Р.,
Мехта, S.,
Policella, Н. (2005). Планирование в условиях неопределенности-активный подход с помощью частичной графики заказа. Диссертация, Италия: Studi Университете дельи-ди-Рома "La Sapienza".
Policella, N., Одди, А. Смит, С.,
Schatteman Д., Herroelen У., Ван де Вондер, S.,
Смит-Дэниелс, Д. Е.,
Ван де Вондер, S., Demeulemeester Е., Herroelen, W.,
Ван де Вондер, S., Demeulemeester Е., Herroelen, W.,
Wang, J. (2005). Ограничение основе графика ремонта проекты по разработке продукта с ограниченными по времени ограничений. Международный научный журнал "Экономика производства, 95, 399-414.
Чжу, Г., Барда, J,
Филипп Deblaere [кинжал]
Научно-исследовательский центр по управлению операциями, KULeuven, Naamsestraat 69,3000 Leuven,
Бельгия, адрес электронной почты: filip.deblaere <a href="mailto:filip.deblaere@econ.kuleuven.be"> @ econ.kuleuven.be </ A>
Эрик Demeulemeester
Научно-исследовательский центр по управлению операциями, KULeuven, Naamsestraat 69,3000 Leuven,
Бельгия, адрес электронной почты: erik.demeulemeester <a href="mailto:erik.demeulemeester@econ.kuleuven.be"> @ econ.kuleuven.be </ A>
Вилли Herroelen
Научно-исследовательский центр по управлению операциями, KULeuven, Naamsestraat 69,3000 Leuven,
Бельгия, адрес электронной почты: willy.herroelen <a href="mailto:willy.herroelen@econ.kuleuven.be"> @ econ.kuleuven.be </ A>
Stijn Ван де Йондер
Научно-исследовательский центр по управлению операциями, KULeuven, Naamsestraat 69,3000 Leuven,
Бельгия, адрес электронной почты: stijn.vandevonder <a href="mailto:stijn.vandevonder@econ.kuleuven.be"> @ econ.kuleuven.be </ A>
[Кинжал] корреспондент автора.
Филипп Deblaere является научным сотрудником и аспирантом научно-исследовательского центра по управлению операциями факультета экономики и прикладной экономики KULeuven (Бельгия). Он получил степень магистра в области информатики и степень магистра в области управления от KULeuven (Бельгия). Его исследования направлены на активную / реактивной планирования проекта.
Эрик Demeulemeester профессор по управлению операциями в Научно-исследовательский центр по управлению операциями факультета экономики и прикладной экономики KULeuven (Бельгия). Д-р Demeulemeester Имеет многочисленные публикации в планировании проекта и здравоохранения уходу управления. Он является соавтором книги, планирование проекта-исследования Справочник опубликованы в Международном серии в области исследования операций
Вилли Herroelen профессор по управлению операциями в Научно-исследовательский центр по управлению операциями факультета экономики и прикладной экономики KULeuven (Бельгия). Д-р Herroelen опубликовала широко в области планирования проекта. Он является соавтором книги, планирование проекта-исследования Справочник опубликованы в Международном серии в области исследования операций
Stijn Ван де Вондер получил степень магистра в области управления информатики из KULeuven (Бельгия) и получил степень доктора прикладной экономики в научно-исследовательский центр по управлению операциями факультета экономики и прикладной экономики KULeuven (Бельгия). Он опубликовал в международном журнале производства исследований, Международный научный журнал "Экономика производства, а также различные материалы конференций.
Сделка-анализа эффективности интернет Цепочка поставок в розничной Music CD промышленности *
Количественное сравнение приближенного решения множества проблем Bi-критерии оптимизации *
