Содержание к диссертации
Введение
1. Задачи календарного планирования с ограниченными ресурсами 12
1.1. Постановка общей задачи календарного планирования с ограниченными ресурсами 12
1.2. Частные случаи задач календарного планирования с ограниченными ресурсами 19
1.3. Задача календарного планирования проектов с критерием чистой приведенной прибыли 22
1.4. Модель целочисленного линейного программирования 25
2. Анализ сложности задач календарного планирования со складируемыми ресурсами 28
2.1. Алгоритмическая сложность решения задач 29
2.2. О сложности задачи календарного планирования с критерием средневзвешенного времени выполнения работ 35
2.3. Сложность задачи календарного планирования с критерием чистой приведенной прибыли 41
2.4. Псевдополиномиальные алгоритмы решения задач календар ного планирования при независимых работах 46
3. Алгоритмы нахолсдения точного решения некоторых задач календарного планирования 51
3.1. Алгоритмы, основанные на методе динамического программирования 52
3.2. Алгоритмы ветвей и границ решения задач календарного планирования 62
3.3. Гибридный алгоритм решения задач календарного планирования с ограниченными ресурсами 69
4. Аппроксимационные схемы для некоторых задач календар ного планирования с возобновимыми ресурсами 77
4.1. Предварительные сведения 78
4.2. Задача календарного планирования с критерием общего времени завершения работ 80
4.3. Задача календарного планирования с критерием среднего времени завершения всех работ 84
4.4. Разномаршрутная задача теории расписаний 86
Заключение 88
Литература 90
- Частные случаи задач календарного планирования с ограниченными ресурсами
- О сложности задачи календарного планирования с критерием средневзвешенного времени выполнения работ
- Алгоритмы ветвей и границ решения задач календарного планирования
- Задача календарного планирования с критерием общего времени завершения работ
Введение к работе
Задачи календарного планирования возникают в различных сферах деятельности, в том числе при проектировании новых изделий и запуске их в производство, составлении расписаний движения транспорта, планировании графиков выпуска и доставки продукции, разведке и освоении месторождений и т. д. Разнообразие приложений делает это направление весьма актуальным в области математических моделей и методов оптимизации.
Научный подход к календарному планированию проектов предложен и применен в конце 50-х годов прошлого века. Были разработаны такие технологии как PERT (Project Evaluation and Review Technique) [46, 65| и CPM (Critical Path Method) [71, 75]. Характерной особенностью этих технологий является представление проекта в виде комплекса взаимосвязанных работ. Однако возможности указанных разработок были ограничены, так как в них не учитывались реальные ограничения на используемые ресурсы.
В дальнейшем, после создания теории сложности, было установлено, что большинство задач календарного планирования с учетом ограничений на ресурсы являются JVP-трудными. Эти задачи можно рассматривать, например, как обобщения разномаршрутной задачи теории расписаний (Job-shop) [47], задачи построения конвейерного расписания (Flow-shop)\b8\, задачи с параллельными приборами [92], задача о камнях [57] и т. д.
В настоящее время ведутся исследования структуры и вычислительной
сложности указанных задач календарного планирования, выделяются полиномиально разрешимые случаи, развиваются точные и приближенные методы их решения [7,12,16,22,28,36—38,48,50,62]. Особую актуальность эти задачи приобретают при планировании крупномасштабных проектов, требующих больших затрат ресурсов [10, 8, 9, 81].
Среди подходов к получению оптимальных решений задач календарного планирования следует выделить схему динамического программирования [2], метод ветвей и границ [8 — 10,81], различные алгоритмы комбинаторного типа [11, 14, 16, 23, 36, 37, 57, 61].
Другим перспективным направлением является сведение задач построения расписаний к задачам целочисленного линейного программирования (ЦЛП). Данный подход используется, например, в [10, 81]. В ряде известных методов решения задач ЦЛП применяется приведение исходной задачи к последовательности задач непрерывной оптимизации. На таком подходе основаны алгоритмы отсечения [4, 15, 18, 39, 42], ветвей и границ [20, 42], декомпозиции [45], перебора L-классов [19] и др.
Задачи календарного планирования с ограничениями па ресурсы можно разбить два класса. К первому относятся задачи с временными критериями (общее или средневзвешенное время завершения всех работ, штраф за нарушение директивных сроков, число невыполненных в срок работ и т. д. [47,49 — 51,59,72]). Ко второму классу - задачи с критериями, связанными с эффективным использованием ресурсов или получением прибыли, в частности, задачи минимизации общего потребления ресурсов (Resource leveling problem), сглаживания потребляемых ресурсов (Resource Investment problem), максимизации чистой приведенной прибыли (Net Present Value problem) [53, 68, 72]. В диссертации рассматриваются
задачи из обоих классов.
Ограниченные ресурсы, используемые при выполнении работ, в основном делятся на возобновимые и складируемые. Возобновимые ресурсы доступны в каждый момент времени. При этом общий расход ресурса, требуемого для выполнения всех работ в момент времени t, не должен превосходить имеющегося объема ресурса. Представителями данного типа ресурсов являются рабочая сила, оборудование, производственные мощности и т. п. Складируемые ресурсы в отличие от возобновимых ресурсов доступны на протяжении всего проекта. В период времени t невостребованный объем складируемого ресурса переходит на следующий период времени. При этом в каждый момент t должен сохраняться баланс между потребляемым и выделяемыми объемами ресурсов. Примером данного вида ресурсов могут служить материалы с длительным сроком хранения: финансы, сырье и т. д.
Наиболее изучена задача календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ. Для данной задачи в [44, 53, 68, 69, 90] предложены алгоритмы точного и приближенного решений. Однако задачи такого типа с другими критериями оптимизации исследованы относительно слабо, поэтому возникает необходимость в построении как точных, так и приближенных алгоритмов решения таких задач.
В связи со сложностью рассматриваемых задач значительное число исследований посвящено разработке приближенных алгоритмов с гарантированной оценкой точности. Особое значение имеют аппроксимационные схемы, с помощью которых за полиномиальное время от длины входа можно получить решение задач с любой наперед заданной точностью. Такой иод-
ход использовали в [5, 67, 73] и других работах. Построение аппроксимаци-онных схем решения iVP-трудных задач является одним из перспективных направлений дискретной оптимизации.
Определенные успехи достигнуты при исследовании задачи календарного планирования со складируемыми ресурсами, в которых минимизируется общее время завершения всех работ [6, 8 — 10,14,16] Было доказано, что данная задача является полиномиально разрешимой [7] и предложен алгоритм ее решения. Поэтому актуальным является исследование сложности указанных задач с другими критериями оптимизации.
Целью диссертационной работы является исследование задач календарного планирования с ограниченными ресурсами и различными критериями оптимизацрщ, построение и анализ алгоритмов решения данных задач.
Диссертация состоит из введения, четырех глав и заключения.
В первой главе описываются модели задач календарного планирования с учетом ограничений на ресурсы и различными критериями оптимизации.
В п. 1.1 приводится общая постановка задачи календарного планирования с ограниченными ресурсами. Проект состоит из множества взаимосвязанных работ, выполнение которых направлено на достижение определенной цели. Каждая работа характеризуется длительностью, некоторыми ресурсными требованиями и директивными сроками. Необходимо с учетом ограничений на ресурсы определить сроки выполнения всех работ, при которых значение целевой функции является оптимальным.
В качестве целевой функции нами рассматриваются следующие критерии минимизации: общий срок выполнения всех работ, максимальное запаздывание работ, средневзвешенное время завершения всех работ, суммарный взвешенный штраф за нарушение директивных сроков, взвешенное число
невыполненных в срок работ.
В п. 1.2 описываются частные случаи задачи календарного планирования с ограниченными ресурсами: разномаршрутная задача теории расписаний (Job-shop) [47], задача об упаковке в контейнеры [12], задача с параллельными приборами [92]. Приводится также постановка задачи календарного планирования, в которой мощность множества независимых работ ограниченна константой.
В п. 1.3 рассматривается задача календарного планирования проектов со складируемыми ресурсами и критерием чистой приведенной прибыли. Постановка данной задачи отличается от общего случая только одним видом складируемого ресурса (финансового) и наличием потока поступлений.
В п. 1.4 задача календарного планирования с учетом ограничений на ресурсы формулируется как задача целочисленного линейного программирования. ЛП-релаксация данной задачи используется для построения верхней оценки (нижней оценки) значений целевой функции в третьей главе.
Во второй главе исследуется сложность задач календарного планирования с различными критериями. В п. 2.1 приводятся положения современной теории сложности, на основе которых дастся обзор сложности изучаемых в работе задач. В п. 2.2 и п. 2.3 доказана iVP-трудность в сильном смысле задачи календарного планирования со складируемыми ресурсами и критерием средневзвешенного времени завершения всех работ. К данной задаче полиномиально сводится задача о максимальной клике. Аналогичный результат получен для задачи календарного планирования проекта с критерием чистой приведенной прибыли.
В случае, если работы выполняются независимо друг от друга, нами доказана iVP-трудность задачи со складируемыми ресурсами и критери-
ем средневзвешенного времени завершения всех работ. К рассматриваемой задаче полиномиально сводится булева задача о рюкзаке. Аналогичный результат получен для частного случая задачи календарного планирования проектов с критерием чистой приведенной прибыли и со складируемыми ресурсами.
В п. 2.4 описываются алгоритмы решения задач календарного планирования со складируемыми ресурсами и независимых работах с критериями средневзвешенного времени завершения всех работ и чистой приведенной прибыли. Для данных задач предложены алгоритмы, основанные на схеме динамического программирования. Если предположить, что горизонт планирования является параметром задачи, то рассматриваемые задачи являются псевдополиномиально разрешимыми. В этом же параграфе показана полиномиальная разрешимость задачи календарного планирования с критерием средневзвешенного времени выполнения всех работ, если весовые коэффициенты равны единице. Основные результаты данной главы опубликованы в [32 — 34,87].
Третья глава посвящена разработке и анализу точных алгоритмов решения задач календарного планирования с ограниченными ресурсами.
В п. 3.1 на основе метода динамического программирования (ДП) предложены новые алгоритмы, позволяющие решать широкий класс задач календарного планирования с различными критериями оптимизации. Основная идея заключается в переборе всевозможных состояний выполнения работ и вычисления для каждого состояния по рекуррентной формуле лучшее допустимое частичное расписание. Доказано, что если мощность максимального независимого подмножества работ ограничено константой, то задача календарного планирования с ограниченными ресурсами псевдопо-
линомиально разрешима.
В п. 3.2 предложены два алгоритма ветвей и границ решения задачи календарного планирования с ограниченными ресурсами. Первый алгоритм решает задачи календарного планирования с независимыми работами или со слабой зависимостью между ними. Второй алгоритм показал себя эффективным в объединении с алгоритмом ДП.
В п. 3.3 строится точный гибридный алгоритм, который является комбинацией алгоритмов ветвей и границ и динамического программирования, описанных в п 3.1 и п. 3.2., и позволяет расширить возможности исходных алгоритмов. Алгоритм ДП по трудоемкости доминирует алгоритм ветвей и границ. Но существенным ограничением для использования алгоритма ДП является большой объем требуемой памяти. Причем чем меньше ширина частичного порядка, тем меньше необходимо памяти для работы алгоритма. Возможности алгоритма ДП можно расширить, если в процессе применения алгоритма ветвей и границ получится уменьшить ширину частичного порядка. С другой стороны, алгоритм ветвей и границ также можно усилить, решая очередную подзадачу алгоритмом динамического программирования, если позволяет объем требуемой памяти.
Основные результаты данной главы опубликованы в [31 — 34].
В четвертой главе рассматриваются вопросы построения аппроксимаци-онных схем для двух задач календарного планирования с возобновимыми ресурсами. Дается обзор основных методов разработки аппроксимацион-ных схем. Предложены вполне полиномиальные аппроксимационные схемы для задачи календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ и для задачи с критерием среднего времени завершения всех работ. Результаты данной главы
опубликованы в [30,41,42,86 — 89].
Основные результаты диссертации опубликованы в работах [29 — 34,40,41,84 — 87,89] и докладывались на следующих конференциях и семинарах: XXIX Региональной научной студенческой конференции "Молодежь третьего тысячелетия" (Омск, 2005), XVIII International Conference of the European Chapter on Combinatorial Optimizations (Минск, 2005), I международной школе-семинаре "Проблемы оптимизации сложных систем" (Новосибирск, 2005), 12th IFAC Symposium on Information Control Problems in Manufacturing (Saint-Etienne, France, 2006), III Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2006), XIII Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2007), Всероссийской научной молодежной конференции "Под знаком " (Омск, 2007), Всероссийской конференции "Дискретная оптимизация и исследование операций" (Владивосток, 2007), International Conference of Operations Research in the Service Industry (Saarbrucken, 2007), 14-й Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2008), а также на семинарах в Омском государственном университете, Институте математики им. С.Л. Соболева СО РАН и его Омском филиале.
Частные случаи задач календарного планирования с ограниченными ресурсами
Рассмотрим некоторые важные случаи задач календарного планирования с ограниченными ресурсами.
Наиболее изучена задача календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ. Известно, что эта задача является iVP-трудной в сильном смысле [56]. Определенных успехов добились при исследовании задачи календарного планирования со складируемыми ресурсами. Обычно такая задача возникает при планировании крупномасштабных проектов, когда основным ресурсом являются финансы. В работе [7] предложен полиномиальный алгоритм для задачи календарного планирования со складируемыми ресурсами, директивными сроками и критерием общего времени завершения всех работ (1.1), (1-3)-(1.6). Однако для других критериев (например, критерий средневзвешенного времени завершения всех работ Y wj j критерий чистой приведенной прибыли NPV) эта задача не исследовалась.
Проводятся исследования задач календарного планирования в зависимости от вида частичного порядка Е. Например, при строительстве объектов линейной структуры (железные или автомобильные дороги) фронт выполняемых работ узкий. Следовательно, возникают задачи календарного планирования, в которых количество работ одновременно доступных для выполнения ограничено (мощность множества независимых работ ограниченна константой). Пример задачи календарного планирования с узким частичным порядком выполнения работ представлен в предыдущем параграфе на рис. 1.1.
В данной работе исследования задач календарного планирования с узким частичным порядком проводились как в общем случае, так и в следующей постановке.
Пусть как и ранее имеется проект, который состоит из множества взаимосвязанных работ V = {1, 2,..., N} . Взаимосвязь задается частичным порядком их выполнения Е. При выполнении работы j Є V используется М видов возобновимых ресурсов. В каждый момент времени имеется Rm единиц ресурса вида т, т = 1,2,..., М. Каждая работа j Є V характеризуется длительностью Pj Є Z+ и потребностью rmj в ресурсе вида т, т.е. ресурс потребляется равномерно. Предполагается, что все работы выполняются непрерывно.
Расписание S = (si, S2,, SJV) называется допустимым, если: где Nt = {j Є V\SJ t Sj + pj} - множество работ, выполняемых на интервале [t — l,t). В качестве критерия оптимизации рассматривались критерий общего времени завершения всех работ Стйх и критерий среднего времени завершения работ Y Cj.
Еще одним важным случаем является задача, когда частичный порядок выполнения работ является объединением цепей (chains). Для примера приведем задачу, известную в литературе как разномаршрутная задача теории расписаний (Job-shop problem). Пусть п - количество требований и L - число обслуживающих приборов. Каждое требование к = 1,2,... ,п обслуживается приборами в Процесс обслуживания требования может включать повторные обращения к одним и тем же приборам. Известны длительности операций р є Z+, к = 1,2,..., n, j = 1,2,..., ik- Прерывания выполнения операций не допускаются. Каждый прибор не может обслуживать более одного требования одновременно. Необходимо построить оптимальное по быстродействию расписание процесса обслуживания всех требований.
Разномаршрутная задача теории расписаний является частным случаем задачи календарного планирования с ограниченными ресурсами. Каждой операции в разномаршрутной задаче соответствует работа в задаче календарного планирования. Взаимосвязь работ задается п цепями, каждая из которых отвечает требованию. Следовательно, ширина частичного порядка К в данном случае равна п. Количество приборов L совпадает с числом ресурсов М. Так как имеется только один прибор каждого типа, то Rm = 1. Поскольку операция j требования к обслуживается прибором га, то вектор потребности в ресурсах для разномаршрутной задачи выглядит следующим образом (0,0,..., 1,..., 0), где единица стоит на месте rrij. Разномаршрутная задача теории расписаний является JVP-трудной в сильном смысле [74].
Рассматриваются задачи календарного планирования с независимыми работами, т.е. Е — 0. Такие задачи возникают, когда необходимо выполнить совокупность работ, не связанных технологическим порядком. Например, организация и строительство обслуживающих пунктов. В диссертационной работе рассматриваются задачи как с возобновимыми ресурсами, так и со складируемыми ресурсами.
О сложности задач календарного планирования с независимыми работами можно судить по тому факту, что ее частными случаями являются следующие задачи.
Задача об упаковке в контейнеры Постановка задачи заключается в упаковке объектов предопределённой формы в конечное число одинаковых контейнеров таким способом, чтобы число использованных контейнеров было наименьшим. Задача об упаковке в контейнеры является частным случаем задачи календарного планирования с возобновимым ресурсом и критерием общего времени выполнения всех работ: в каждый период времени в наличии имеется постоянное количество единиц возобновимого ресурса, работы имеют единичные длительности, каждая работа потребляет произвольное количество ресурса. Задача об упаковке в контейнеры является iVP-трудной в сильном смысле [12].
О сложности задачи календарного планирования с критерием средневзвешенного времени выполнения работ
В 1970 году А. Расселл [82] предложил использовать в качестве критерия значение чистой приведенной прибыли проекта. Задача была сформулирована как задача нелинейного программирования без ограничений на ресурсы. Он предложил процедуру нахождения точного решения, которая базируется на разложении критерия в ряд Тейлора и решении соответствующей задачи о перевозках.
Гринольд [60] продолжил исследования, добавив длительность проекта, и преобразовал задачу нелинейного программирования с линейными ограничениями предшествования и экспоненциальной целевой функцией к эквивалентной задаче линейного программирования, которая имеет структуру взвешенной задачи размещения. Он также доказал, что оптимальное решение всегда соответствует остовному дереву сетевой модели проекта, и использовал этот результат для того, чтобы ограничить пространство поиска только деревьями данного вида. Элмаграби и Херроэлен [54], используя модель Расселла, предложили простой точный алгоритм решения задачи без ограничений на ресурсы. Он последовательно строит деревья, используя сетевую модель задачи, и вычисляет точные интервалы смещения для них. Херроэлен и Галленс [64] модифицировали алгоритм и провели вычислительный эксперимент на 250 случайно построенных задачах. Недавно, Дэмеулемеестер (Demeulemeester) и др. [52] предложили новый точный алгоритм, который осуществляет рекурсивный поиск по частичным деревьям. В его основе лежит следующий принцип: работы приносящие доход выполняются раньше, а работы, производящие расходы, задерживаются. Вычислительный эксперимент показал лучший результат по сравнению с методом Гринольда.
Для задачи с ограничениями на ресурсы в [53] предложена модель целочисленного программирования. Она включает ограничения на капитал, то есть затраты, возникающие при выполнении работ проекта такие, что наличие капитала уменьшается на осуществленные выплаты. Целевая функция также включает платежи, осуществляемые при завершении работ, и штрафы за их задержки. Данная модель позволяла решать задачи с 15 - 25 работами. Позднее в нее были включены ограничения на используемые материалы.
Паттерсон и другими [79, 80] представили булеву модель и алгоритм с возвратом для решения ограниченной задачи с/УРУ-критерием. Уникальность алгоритма заключается в том, что он позволяет также решать задачу минимизации длительности выполнения всего проекта. Решение задачи с критерием Стах использовалось в качестве начального решения задачи с iVPy-критерием. Далее для улучшения значения критерия начальное решение изменялось при помощи сдвига работ вправо. Во время вычислительного эксперимента была просчитана серия из 91 задачи с числом работ в проекте от 10 до 500.
Следующие два параграфа посвящены исследованию сложности некоторых задач календарного планирования проектов с учетом ограничений на ресурсы.
В данном параграфе исследуется сложность задачи (1.1), (1.3), (1.5), (1.9) с произвольным частичным порядком и складируемыми ресурсами.
Теорема 2.1. Задача календарного планирования проектов со складируе-лїими ресурсами и критерием средневзвешенного времени завершения работ является NP-трудной в сильном смысле.
Доказательство. Рассмотрим задачу о клике. Дан неориентированный граф Г = (Vl\Er) и натуральное число т/о- Существует ли в Г такой полный подграф (клика) Г = (У0, 0), что V т/о? Пусть v = \VV\, а е = .7Г. Задача о клике iVP-трудна в сильном смысле [70]. Без ограничения общности будем считать, что в графе Г изолированных вершин нет.
Рассмотрим следующую задачу планирования: существует ли такое допустимое относительно графа G — (V, Е) расписание S0 выполнения работ, что Y WjCjiS0) у для заданного значения у.
Покажем, что задача о клике полиномиально сводится к задаче планирования. Используем идею сводимости, предложенную в [3].
Алгоритмы ветвей и границ решения задач календарного планирования
В параграфе исследуется сложность задачи календарного планирования проектов со складируемыми ресурсами (1.17)-(1.20). Утверждение 2.1. Задача календарного планирования проектов со складируемыми ресурсами и критерием чистой приведенной прибыли является NP-трудной в сильном смысле. Доказательство. Рассмотрим задачу о клике. Дан неориентированный граф Г = (Vr, ЕГ) и натуральное число уо. Существует ли в Г такой полный подграф (клика) Г = (V,E), что [V уо? Пусть v = Vr, а е = \ЕГ\. Без ограничения общности будем считать, что в графе Г изолированных вершин нет. Рассмотрим следующую задачу планирования проектов: существует ли такое допустимое относительно графа G = (V, Е) расписание S0 выполнения работ проекта, что NPV(S) у для заданного значения у. Покажем, что задача о клике полиномиально сводится к этой задаче. По графу Г сформируем задачу планирования проектов. Множество V зададим следующим образом. Каждой вершине j графа Г сопоставляется работа Vj, далее такие работы будем называть вершинными работами, а каждому ребру (i,j) Є Ег - работа eij, которые будем называть реберными работами. На построенном множестве V определим отношение порядка предшествования Е: V{ — e;j и Vj —» eij для всех (i,j) Є і?г. Объемы имеющегося в наличии ресурса равны д(1) = г/о, #(2) = (v — г/о) + 0 -1 и д(3) = е — Уо 2 Для каждой работы j Є V потребность в ресурсе т = 1, чистая приведенная прибыль работы NPVj = 1 и базовая процентная став-ка г0 = 1.
Положим y = yQ + \{{v - г/0) + ) + \{е - f% Очевидно, что расписание удовлетворяет условию NPV(S) у тогда и только тогда, когда выполнены следующие условия: a) в течение интервала [0,1) будут выполнены г/о вершинных работ; b) в течение интервала [1,2) - остальные г; — г/о вершинных работ и у" у реберных работ; c) в течение интервала [2,3) будут выполнены е — Уо , реберных работ. Докажем, что расписание S0, удовлетворяющее перечисленным условиям а) — с), будет допустимым тогда и только тогда, когда граф Г имеет клику, содержащую не менее т/о вершин. Предположим, что в графе Г существует клика, содержащая не менее г/о вершин. Тогда существует такая клика Г = (V ,Е), что \V \ = г/о- Рассмотрим расписание 5, при котором а) в интервале времени [0,1) выполнены г/о вершинных работ, соответствующие вершинам Г , Ь) в интервале времени [1,2) выполнены № з реберных работ, соответствующие ребрам Г и оставшиеся вершинные работы и с) в интервале времени [2,3) выполнены оставшиеся реберные работы. Поскольку выполнены ресурсные требования для вершинных и реберных работ, и все имеющиеся в наличии ресурсы были использованы, то S0 - допустимое относительно G расписание и NPV(SQ) = yQ + !((« - г/о) + Щ=) Пусть S - оптимальное расписание сформированной задачи планирования проектов, которое удовлетворяет условию: NPV(S) Уо + ({у — уо) + №(2/о- ) __ е _ УО(УО- ) _ _ Тогда в интервале времени [0,1) выполняется ровно /о вершинных работ. Обозначим множество этих вершинных работ через V0. Реберные работы выполняться в этом интервале не могут, так как любой реберной работе e j предшествует две вершинных работы vi и Uj, где (i,j) Є Ег. В интервале [1,2) выполняются Уа реберных работ.
Обозначим это множество через Е. Так же в интервале [1,2) выполняются оставшиеся вершинные работы из множества V\V. В интервале [2, 3) вершинные работы из множества V\V выполняться не могут, потому что в графе Г изолированных вершин нет. Следовательно, оставшиеся реберные работы выполняются в интервале времени [2,3). Так как расписание 5 допустимо, то реберные работы Е не связаны с вершинными работами из V\V. Но тогда реберные работы из Е связаны с вершинными работами из VQ и только с ними. Тогда имеем подграф, состоящий из вершин, соответствующих множеству У0, и ребер, соответствующих множеству i. А так как 1- 1 = Vo(y \ a V = уо, то этот подграф полный. В итоге получаем, что расписание S0, удовлетворяющее перечисленным условиям а) — с), будет допустимым тогда и только тогда, когда граф Г имеет клику, содержащую не менее уо вершин. Сведение задач является полиномиальным, так как для его реализации требуется не болееО((г)+е)2) операций. В данном параграфе рассматривается задача (1.18)-(1.20) с независимыми работами и доказывается iVP-трудность данной задачи. Идея доказательства изложена в [32]. "Утверждение 2.2. Задача календарного планирования проектов со складируемыми ресурсами и критерием чистой приведенной прибыли является NP-трудной даоїсе в случае независимых работ единичной длительности. Доказательство. Рассмотрим проект, состоящий из множества независимых работ V = {1,2,..., N}. Все работы имеют единичные длительности Pj = l,j Є V. Величина Tj задает капиталовложения, необходимые для выполнения работы j, a NPVj - получаемый доход. Без ограничения общности, будем считать, что все Tj целые, а отсчет времени ведется с нулевого момента. Пусть выполнено условие 2 т3- g(l) + q(2), которое предпола jev гает, что все работы гарантированно выполняются за два периода времени. Для работы j Є V будем полагать х3- = 1, если работа выполняется в первый период времени, и Xj = 0, если во второй. В первый период времени потребуется ресурс объемом 52 rjxj а полученная прибыль равна jev 72 NPVj-Xj. Соответственно, во второй период потребуется 52 rj (l xj) jeV jeV ресурса, а прибыль составит 52 NPVj (1 — х3). jev Общая прибыль от выполнения работ проекта будет равна:
Задача календарного планирования с критерием общего времени завершения работ
Рассматривается задача календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ (1.1), (1.3), (1.5), (1.6).
Теорема 4.1. Если ширина частичного порядка выполнения работ ограничена некоторой заданной величиной К, то для, задачи календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ существует вполне полиномиальная аппроксима-ционная схема трудоемкости 0(2ККМ( )к).
Доказательство. Для построения вполне полиномиальной аипроксимаци-онной схемы применим подход, основанный на округлении входных данных (см., например, [67]). Обозначим через/ индивидуальную задачу календарного планирования (1.1), (1.3), (1.5), (1.6). Пусть Р = maxpj. Фиксируем точность 0 є 1 и вычислим коэффициент округления Z = -. Заметим, что Z 0. Упростим задачу / следующим образом: поделим длительности pj на коэффициент Z и полученное число округлим вверх, то есть в упрощенной задаче /" длительности р
Решим упрощенную задачу Р псевдополиномиальным алгоритмом, описанным в параграфе 3.1. Сложность этого алгоритма для задачи/" составляет 0{2KKMB\B\.. .В к). Из работ, принадлежащих цепи к задачи 1%, выберем ту, у которой длительность выполнения наибольшая, и обозначим соответствующую длительность через PJj. Множество работ, принадлежащих цепи к обозначим через V . Вычислим трудоемкость решения упрощенной задачи псевдополиномиальным алгоритмом: где п/г - количество работ в /е-ой цепи, к = 1,2,..., К. Следовательно, временная сложность алгоритма для задачи Р равна 0(2ККМ(—)К), то есть при фиксированном К полиномиально зависит от длины входа и .
После того как решим упрощенную задачу Р, необходимо восстановить соответствующее решение в исходной задаче. При решении задачи Р получили расписание работ SK Оптимальное значение целевой функции для этой задачи есть ОРТ" = max с?- = maxfs,- + ?) Расписание работ в исходной задаче задается величинами Zs , то есть восстанавливаем расписание работ, полученное при решении упрощенной задачи Р. Так как pj Zpj, то при переходе к исходной задаче никаких сдвижек работ относительно друг друга не происходит. В силу этого частичный порядок выполнения работ не нарушается, и требования по ресурсам в каждый момент времени будут выполняться. То есть расписание Sj = Zs- в исходной задаче остается допустимым. Оценим значение целевой функции АРР при этом расписании:
Здесь DOPB - значение целевой функции задачи Р, соответствующее оптимуму в исходной задаче /. Расписания для DOP" и ОРТ имеют одинаковую последовательность выполнения работ. При переходе в исходной задаче от pj к Zp,, длина соответствующего расписания увеличивается не более чем на NZ, так как длина каждой работы увеличивается не более чем на Z. А длина расписания с длительностями Zm равна Z DOP11. Значит Z DOP NZ + ОРТ.
Последнее неравенство следует из того, что Р ОРТ. Таким образом, для каждого є О за время 0(2ККМ(—-)К) можно найти приближенное решение, значение целевой функции которого не превосходит (1 + є)ОРТ.
В работе [73] для задачи минимизации предложена процедура улучшения верхних и нижних границ, основанная на свойствах аппроксимационнои схемы. Введем некоторые понятия. Пусть F — оптимальное значение целевой функции задачи минимизации; є — относительная погрешность приближенного решения; G — нижняя оценка целевой функции; R — верхняя оценка целевой функции: G F R.
Обозначим через {A(G, R)} семейство приближенных алгоритмов со свойствами: 1) Для любых e,G,R и любой задачи / алгоритм Ae(G, R) находит решение с целевой функцией FA R + eG, если F R\ 2) трудоемкость алгоритма Ae(G, R) составляет 0(р(/, )) В общем случае, пусть есть некоторая задача минимизации и выполнено условие: LB F UB. Также имеем семейство приближенных алгоритмов {AE(G, R)}, удовлетворяющих свойствам 1) - 2). Если UB 3LB, то процедура "Улучшения верхних и нижних границ" найдет значение F0 такое, что F F SF0.
