Abstract

Abstract

We consider the problem of determining resource loads in search of makespan lower bounds for resource-constrained project scheduling problem (RCPSP). For the case of two resources we propose a geometric approach to solving the problem and present two exact polynomial algorithms with time complexities O ( n 2) and O ( n log n ), where n is the initial number of jobs.

Full Text

Введение Задача построения расписания выполнения работ проекта с учетом ограничений на ресурсы (resource-constrained project scheduling problem, RCPSP) является одной из основных задач теории расписаний [1] и широко применяется в качестве математической модели при управлении циклом производства в масштабных проектах. Задача RCPSP является NP-трудной в сильном смысле [2]. В простейшей формулировке задачи RCPSP проект задается множеством работ и ограничениями доступности ресурсов, требуемых для выполнения работ. Целью является построение расписания с минимальной общей продолжительностью выполнения проекта (makespan). Большинство точных алгоритмов решения задачи RCPSP основаны на методе ветвей и границ, для применения которого необходимо знание верхних и нижних оценок общей продолжительности проекта. В работе [3] был представлен алгоритм поиска нижних оценок, основанный на определении загрузки ресурсов. Решение задачи нахождения максимальной загрузки заданной пары ресурсов и стало целью данной работы. Для решения задачи был использован геометрический подход. Работы представляются в виде векторов на плоскости. Показано, что удовлетворяющие заданным ограничениям линейные комбинации этих векторов образуют на плоскости некоторый выпуклый многоугольник, названный областью разрешимости задачи. Показано, что необходимым и достаточным условием существования оптимального плана выполнения работ является условие принадлежности точки (А, В) этому многоугольнику. Представлены два алгоритма решения задачи, имеющие вычислительные сложности O(п2) и O(п log п) операций соответственно, где п - исходное число работ. Данные алгоритмы были использованы при проведении численных экспериментов, результаты которых были представлены в работе [3]. 1. Формулировка задачи Имеются ресурсы двух видов в количестве А, В единиц и множество N = {1, ..., п} работ. На выполнение работы i N в полном объеме расходуется аi, bi единиц ресурсов. Работы могут выполняться частично: выполняемая часть i-й работы может составлять 0 ≤ xi ≤ 1 от ее полного объема, при этом будет израсходовано аixi, bixi единиц ресурсов соответственно. Требуется определить загрузки ресурсов - составить план выполнения работ, минимизирующий совокупный объем неизрасходованных ресурсов: а загрузки ресурсов А и В (максимальный возможный их расход) равны и в соответствии с данным оптимальным планом. 2. Сопутствующие задачи Задача о сумме подмножества. Имеется множество S = {si} действительных чисел мощностью n. Необходимо определить, существует ли для заданного действительного числа s непустое подмножество S' = {si}, S' S, || S || = т ≤ n, имеющее заданную сумму . Эквивалентная постановка: определить, существует ли булев вектор , такой что . Эта задача является NP-трудной и может рассматриваться как частный случай задачи о рюкзаке без повторений ({0 - 1} knapsack problem), для которой существует алгоритм с псевдополиномиальной вычислительной сложностью [5]. Задача о сумме подмножества с дроблениями. Имеется множество S = {si} действительных чисел мощностью n. Требуется определить, существует ли вектор с ограниченными вещественными компонентами 0 ≤ xi ≤ 1, такой что . Благодаря тому что компоненты вектора-решения более не являются строго булевыми, данная задача, в отличие от предыдущей, не является NP-трудной: очевидно, пока текущее значение суммы искомой линейной комбинации и очередного числа sk+1 меньше целевого значения s, можно добавлять очередное число полностью (хk+1 = 1), в противном случае . Таким образом, задача разрешима за время О(n). Задача суммирования векторов. Имеется множество n векторов S = {si} в векторном пространстве размерности k. Вводится метрика ||.|| на данном векторном пространстве (например, евклидова метрика l2). Требуется найти булев вектор X = {xi}, такой что метрика || || вектора достигает максимума. В работе [4] приводятся полиномиальные алгоритмы решения задачи суммирования векторов для случая произвольной размерности для евклидовой и полиэдральной метрик. Однако, в отличие от задачи, рассмотренной в данной работе, исследованная в статье задача не содержит ограничений на значения координат искомой линейной комбинации («ограничений на ресурсы»), а искомый вектор является строго булевым. 3. Геометрический подход Сформулируем постановку задачи в виде задачи нелинейного программирования. Дано: пара чисел А, В , множество векторов на плоскости S = {si}, si = (ai, bi) с неотрицательными вещественными координатами ai, bi , . Найти: вектор X = {xi} с ограниченными вещественными компонентами xi [0,1], , такой что , и . 3.1. Исследование математическом модели. Условие разрешимости Рассмотрим перестановки γup и γdown из n векторов из множества S, получаемые сортировкой элементов этого множества по неубыванию и по невозрастанию соотношения их координат bi/ai. Для последовательности γup Для перестановки γdown неравенство обратное. Операция деления здесь несколько «формальная»: случай деления на ноль стоит обрабатывать отдельным условным оператором. В случае, когда у каких-либо двух векторов совпадают соотношения bi/ai их координат, порядок следования этих векторов считаем несущественным. Отложим первый вектор из γup от начала координат на плоскости, второй - от конца первого и т.д. Получим некоторую ломаную (обозначим ее также γup) на плоскости. Обозначим как θi величину угла между вектором и осью абсцисс а соответственно. Поскольку сортировки производятся по величине tgθi, γup является выпуклой вверх в каждой своей точке излома. Аналогично получим ломаную γdown, выпуклую вниз в каждой своей точке излома. Назовем областью разрешимости задачи для множества S плоский многоугольник, образованный ломаными γup, γdown, отложенными от начала координат на плоскости. Очевидно, этот плоский многоугольник является выпуклым. Теорема 1. Для любого вектора , компоненты которого xi удовлетворяют ограничениям 0 ≤ xi ≤ 1 (при этом необязательно соответствует решению задачи), точка , si = (ai,bi), si S лежит в пределах (внутри или на границе) области разрешимости множества S. Доказательство. Построим на плоскости b(а) некоторую ломаную γ из векторов множества S, такую что каждая ее точка лежит не ниже любой ломаной , также состоящей из векторов множества S: , где , - кусочно-заданные функции - уравнения ломаных γ, на координатной плоскости b(a). Докажем, что ломаная γ совпадает с вышеупомянутой ломаной γup, т.е. является выпуклой вверх в каждой своей точке излома. Предположим обратное: пусть γ не является выпуклой вверх в i-й точке излома, т.е. . Тогда составим ломаную , совпадающую с γ, за исключением того, что i и i+1 векторы из γ в ней следуют в обратном порядке: . При этом является выпуклой вверх в i-й точке излома, и, очевидно, на отрезке будет лежать выше γ: < , что противоречит условию теоремы. Значит, γ совпадает с γup. Аналогично доказывается, что для произвольной ломаной ≥ . Очевидно, любая ломаная , полученная из некоторой перестановки векторов , 0 ≤ xi ≤ 1, а значит, и точка также будет лежать не выше ломаной γup и не ниже ломаной γdown, т.е. в пределах многоугольника, образованного этими ломаными - в пределах области разрешимости. Таким образом, теорема доказана. Следствие 1 (необходимое и достаточное условие разрешимости задачи). Для того чтобы задача была разрешима, необходимо и достаточно, чтобы точка (А, В) лежала в пределах области разрешимости множества S. Таким образом, мы получили способ проверить разрешимость задачи для конкретных входных данных: для этого надо отсортировать векторы из заданного множества S по соотношению их координат bi/ai, построить на плоскости область разрешимости множества S и проверить, содержит ли она точку (А, В). 4. Поиск решения. Построение алгоритмов 4.1. Алгоритм 1 Рассмотрим какое-либо фиксированное множество работ S и вектор ресурсов (А, В). Пусть соответствующая задача имеет частное решение . Заметим, что если (или 1), то решение такой задачи совпадает с решением задачи для множества работ S' = S/si с вектором ресурсов (А, В) (или (A - ai, В - bi) соответственно) с той лишь разницей, что в «пропущена» компонента xi. Таким образом, мы получаем стратегию, в соответствии с которой будем понижать множество имеющихся работ и переходить к задачам с меньшим числом работ, пока оно не станет достаточно малым (0, 1 или 2), чтобы задача свелась к решению простейшей системы линейных алгебраических уравнений. Алгоритм 1: Шаг 1. Отсортировать работы исходного множества работ S по невозрастанию соотношения bi/ai. Шаг 2. Проверить разрешимость задачи для множества S (проверить, принадлежит ли точка (А, В) области разрешимости для множества работ S), если задача неразрешима - конец алгоритма. Шаг 3. Положить i = 1. Цикл 1: а) для очередной работы построить подмножество работ ; б) проверить, является ли разрешимой задача для множества работ (см. шаг 2); если является, в ответ записать xi = 0, положить (с сохранением порядка элементов в множестве) и повторить цикл для следующей работы (перейти к началу шага 3), если таковая имеется. Шаг 4. Положить i = 1. Цикл 2: a) для каждой работы построить подмножество работ и модифицированный вектор ресурсов А' = А - ai, В' = В - bi (примечание: здесь и далее А, В не исходные количества ресурсов, а их текущие значения, полученные в процессе работы алгоритма); б) проверить, является ли разрешимой задача для множества Si' и пары ресурсов А', В'; если является, в ответ записать хi = 1, положить , , и повторить цикл для следующей работы, если таковая имеется. Шаг 5. Если множество S содержит две работы j, k, решить систему уравнений Если S содержит 1 или 0 работ, решение очевидно. Шаг 6. Конец работы алгоритма. Утверждение 1. Алгоритм 1 корректен, т.е. имеет конечное время работы, и результатом работы алгоритма является решение задачи в случае существования такового. Справедливость этого утверждения доказывается путем простого рассмотрения структуры алгоритма. Утверждение 2. Алгоритм 1 имеет вычислительную сложность О(п2) операций, где п - исходное число работ. Для доказательства достаточно последовательно рассмотреть вычислительную сложность каждого шага алгоритма. 4.2. Алгоритм 2 Рассмотрим исходное множество работ S. Построим на координатной плоскости ранее описанным способом соответствующий этому множеству работ многоугольник (область разрешимости), обозначим его М. Построим на той же координатной плоскости многоугольник М', полученный параллельным переносом М на вектор (А, В). Обозначим его М'. Поскольку М и М' - выпуклые многоугольники и переходят друг в друга при параллельным переносе на вектор соответственно, то они могут либо пересекаться не более чем в двух точках либо иметь общую грань или ее участок. Рассмотрим одну из точек пересечения (на рисунке она обозначена как С). Рис. Пояснение к алгоритму 2 Для определения индексов пересекающихся звеньев j, k необходимо для всех пар решить систему (1) относительно xj, xk и проверить, удовлетворяет ли полученное решение условию 0 ≤ xj, xk ≤ 1. Для координат хC, yC точки С и коэффициентов xj, xk имеем следующую систему уравнений: (2) Заметим, что в силу того, что А, В > 0 и ai, bi > 0, имеем j ≤ k. Исключаем из этой системы хС, уС и переносим суммы в левую часть, получаем (3) Преобразуем: (4) Обозначим α = 1 - xj, β = xk (здесь xj, xk - найденное ранее решение системы (2), удовлетворяющее условию 0 ≤ xj, xk ≤ 1). Таким образом, пересекающиеся звенья j, k многоугольников М', М соответствуют работам j, k, входящим в решение с коэффициентами 0 < α, β < 1. Тогда можно построить следующий алгоритм. Алгоритм 2: Шаг 1. Отсортировать работы исходного множества работ S по невозрастанию соотношения bi/ai. Шаг 2. Проверить разрешимость задачи для множества S (проверить, принадлежит ли точка (А, В) области разрешимости для множества работ S); если задача неразрешима, конец алгоритма. Шаг 3. Положить j = 1. Цикл: Методом дихотомии определить, существует ли такое , что решение системы (3) относительно xj, xk удовлетворяет условию 0 ≤ xk ≤ 1. Если такого k не существует, повторить цикл для следующей работы (j + 1). Если такое k существует, но при этом не выполнено условие 0 ≤ xj ≤ 1, повторить цикл для следующей работы (j + 1). Если такое k существует и при этом выполнено условие 0 ≤ xj ≤ 1, положить α = 1 - xj, β = xk, завершить цикл. Шаг 4. Положить: , , , . Шаг 5. Конец работы алгоритма. Утверждение 3. Алгоритм 2 корректен, т.е. имеет конечное время работы и результатом работы алгоритма является решение задачи в случае существования такового. Справедливость этого утверждения доказывается путем простого рассмотрения структуры алгоритма. Утверждение 4. Алгоритм 2 имеет вычислительную сложность O(п log п) операций, где п - исходное число работ. Для доказательства достаточно последовательно рассмотреть вычислительную сложность каждого шага алгоритма. Таким образом, алгоритм 1 проигрывает в вычислительной сложности и, более того, является достаточно громоздким при реализации, однако он допускает модификации для решения аналогичных задач (например, если требуется, помимо прочего, максимизировать число ненулевых компонент в ответе или если работы имеют «вес» и требуется, помимо прочего, максимизировать совокупный вес входящих в решение работ), в то время как алгоритм 2 такой особенностью не обладает. Заключение Представленные в данной работе алгоритмы решения учитывают все необходимые условия и ограничения, входящие в постановку задачи. Поскольку данные алгоритмы предоставляют точное решение и обладают полиномиальным временем работы, представляется возможным их использование на практике. Алгоритм 2 был использован в работе [3] в качестве составной части алгоритма решения задачи поиска нижней оценки общего времени выполнения работ проекта с ограниченными ресурсами. Представленный в работе [3] алгоритм поиска нижней оценки имеет вычислительную сложность O(п3r(п + т + r)H× ×log Н), где п - количество работ, r - количество ресурсов, Н - горизонт планирования, т - количество точек излома у функций емкости ресурсов. Наличие компоненты O(п3) обусловлено иной составной частью алгоритма, не содержащей алгоритм 2. В дальнейшем планируется развитие разработанного подхода для случая произвольного числа ресурсов для задач с дополнительными требованиями к входящим в решение работам (задача с весами, задача с ограничением на число небулевых компонент решения и т.д.), а также применение разработанных алгоритмов в задаче об инвестициях.