Алгоритм «самое долгое время обработки первым»

Алгоритм «самое долгое время обработки первым» (англ. Longest Processing Time, LPT) — это жадный алгоритм для решения задачи оптимального планирования работ. На вход алгоритма поступает набор заданий, каждое из которых характеризуется определённым временем обработки, а также число m, задающее количество доступных машин. Алгоритм LPT функционирует в два этапа:

1. Задания сортируются в порядке убывания времени обработки, так что самое продолжительное задание оказывается первым в списке. 2. Каждое задание из отсортированной последовательности назначается на машину, имеющую на данный момент наименьшую суммарную загрузку (т.е. минимальное общее время уже назначенных ей заданий).

Второй шаг по своей сути представляет собой алгоритм «список первым» (англ. List Scheduling, LS). Ключевое отличие заключается в том, что LS обрабатывает задания в произвольном порядке, тогда как LPT предварительно упорядочивает их по убыванию длительности.

Алгоритм LPT был впервые исследован Рональдом Грэмом в 1960-х годах в контексте задачи планирования на идентичных машинах. Впоследствии он нашёл применение и во многих других вариантах данной проблемы.

LPT также можно описать в более абстрактной формулировке как алгоритм для разбиения множества чисел. Входными данными служат множество чисел S и целое положительное число m. Результатом работы является разбиение S на m подмножеств. Алгоритм упорядочивает входные числа от наибольшего к наименьшему и последовательно помещает каждое число в ту часть, сумма элементов которой на текущий момент является наименьшей.

Примеры[править | править код]

Если входное множество равно S = {4, 5, 6, 7, 8} и m = 2, то результирующее разбиение будет {8, 5, 4} и {7, 6}. При m = 3 разбиение примет вид {8}, {7, 4} и {6, 5}.

Свойства[править | править код]

Алгоритм LPT не всегда находит оптимальное разбиение. Например, в приведённом выше случае оптимальным разбиением для двух машин является {8, 7} и {6, 5, 4}, где суммы равны 15. Однако степень его субоптимальности ограничена как в худшем, так и в среднем случае (см. раздел #Гарантии производительности).

Время работы алгоритма определяется этапом сортировки и составляет O(n log n), где n — количество входных чисел.

Алгоритм LPT является монотонным: увеличение одного из входных чисел приводит к слабому возрастанию целевой функции (максимальной или минимальной суммы в полученном разбиении). Это отличает его от алгоритма «самое короткое время обработки первым».

Гарантии производительности: одинаковые машины[править | править код]

При использовании для задачи планирования на идентичных машинах алгоритм LPT обеспечивает следующие гарантии аппроксимации.

Максимальная сумма в наихудшем случае[править | править код]

В худшем случае максимальная сумма в разбиении, полученном с помощью LPT, не более чем в $\frac{4}{3}$ раза превышает оптимальную (минимально возможную) максимальную сумму. Доказательство этого факта приведено в работе Сяо Синя.

Более детальный анализ показывает, что отношение максимальной суммы к оптимальной составляет $\frac{4 m - 1}{3 m} = \frac{4}{3} - \frac{1}{3 m}$ (например, при m = 2 отношение равно $7 / 6 \approx 1, 167$ ).

Коэффициент $\frac{4 m - 1}{3 m}$ является точным. Рассмотрим пример с $2 m + 1$ входными значениями (где m чётно): $2 m - 1, 2 m - 1, 2 m - 2, 2 m - 2, \dots, m + 1, m + 1, m, m, m$ . В этом случае жадный алгоритм выдаст следующее разбиение:

$2 m - 1, m, m$
$2 m - 1, m$
$2 m - 2, m + 1$
$2 m - 2, m + 1$ ,
...
$3 m / 2, 3 m / 2 - 1$
$3 m / 2, 3 m / 2 - 1$

с максимальной суммой $4 m - 1$ . Однако оптимальное разбиение таково:

$m, m, m$
$2 m - 1, m + 1$
$2 m - 1, m + 1$
$2 m - 2, m + 2$
$2 m - 2, m + 2$
...
$3 m / 2, 3 m / 2$

с максимальной суммой $3 m$ .

Анализ входных данных[править | править код]

Более глубокий анализ учитывает количество элементов в частях разбиения.

В каждой части жадного разбиения j-й по величине элемент не превышает $O P T / j$ , где OPT — оптимальная максимальная сумма.
Предположим, что в части P с максимальной суммой содержится L элементов. Тогда коэффициент аппроксимации жадного алгоритма равен $\frac{L + 1}{L} - \frac{1}{L m} = 1 + \frac{1}{L} - \frac{1}{L m}$ . Это значение является точным для L ≥ 3 (при L=3 получается общий коэффициент $\frac{4}{3} - \frac{1}{3 m}$ ). Обозначим элементы P как x₁,...,x_L. До момента добавления x_L в P её сумма была наименьшей. Следовательно, средняя сумма по всем частям составляет не менее суммы x₁+...+x_L-1 + x_L/m. Оптимальная максимальная сумма должна быть не меньше этой средней. В то же время, сумма в части P равна x₁+...+x_L-1+x_L. Таким образом, разница не превышает (1-1/m)x_L, что согласно пункту (1) не более (1-1/m)*OPT/L. Следовательно, отношение не превышает (1 + 1/L - 1/Lm).

Минимальная сумма в худшем случае[править | править код]

В худшем случае минимальная сумма в полученном разбиении составляет не менее $\frac{3}{4}$ от оптимальной (максимально возможной) минимальной суммы.

Доказательство[править | править код]

Доказательство от противного можно найти в соответствующей литературе.

Верхняя граница отношения[править | править код]

Более тщательный анализ показывает, что это отношение не превышает $\frac{3 m - 1}{4 m - 2}$ (например, при m=2 отношение равно 5/6).

Точность и пример[править | править код]

Указанное отношение является точным.

Рассмотрим пример с 3m-1 входными значениями (где m чётно). Первые 2m значений: 2m-1, 2m-1, 2m-2, 2m-2, ..., m, m. Оставшиеся m-1 значений равны m. В этом случае жадный алгоритм выдаст:

2m-1, m, m
2m-1, m, m
2m-2, m+1, m
2m-2, m+1, m
...
3 m/2, 3 m/2-1, m
3 m/2, 3 m/2-1

с минимальной суммой 3m-1. Однако оптимальное разбиение таково:

2m-1, 2m-1
2m-2, m, m
2m-2, m, m
2m-3, m+1, m
2m-3, m+1, m
...
3 m/2, 3 m/2-2, m
3 m/2, 3 m/2-2, m
3 m/2-1, 3 m/2-1, m

с минимальной суммой 4m-2.

Ограниченный алгоритм LPT[править | править код]

Существует разновидность алгоритма под названием Restricted-LPT (RLPT), в которой входные данные делятся на группы размера m, называемые рангами (ранг 1 содержит m наибольших значений, ранг 2 — следующие m по величине и т.д.). Элементы каждого ранга должны быть распределены по m различным частям разбиения: сначала ранг 1, затем ранг 2 и так далее. Минимальная сумма в разбиении RLPT не превышает минимальную сумму в LPT. Коэффициент аппроксимации RLPT для максимизации минимальной суммы не превышает m.

Максимальная сумма в среднем[править | править код]

Если числа распределены равномерно на отрезке [0,1], то максимальная сумма в расписании LPT обладает следующими свойствами:

Математическое ожидание максимальной суммы для m=2 машин лежит в диапазоне от $\frac{n}{4} + \frac{1}{4 n + 4}$ до $\frac{n}{4} + \frac{e}{2 n + 2}$ , где n — количество входных данных.
Максимальная сумма почти наверняка не превышает оптимальную более чем в $1 + O (\log \log n / n)$ раз, а в среднем ожидается превышение не более чем в $1 + O (1 / n)$ раз.
Разница между максимальной суммой по LPT и оптимальной максимальной суммой почти наверняка составляет не более $O (\log n / n)$ (для равномерного или экспоненциального распределений), а её математическое ожидание не превышает $O (m^{2} / n)$ (для равномерного распределения). Эти результаты применимы также для задачи планирования на однородных машинах.

Целевая функция общего вида[править | править код]

Пусть C_i (для i от 1 до m) обозначает сумму подмножества i в заданном разбиении. Вместо минимизации целевой функции max(C_i) можно минимизировать функцию max(f(C_i</sub)), где f — произвольная функция. Аналогично, можно минимизировать целевую функцию sum(f(C_i</sub)). Алон, Азар, Вёгингер и Ядид доказали, что если f удовлетворяет следующим условиям:

1. Условие строгой непрерывности (Условие F*): для любого ε>0 существует δ>0, такое что, если |y-x|<δx, то |f(y)-f(x)|<εf(x). 2. f является выпуклой функцией, то правило LPT имеет конечный коэффициент аппроксимации для минимизации sum(f(C_i</sub)).

Производительность при делимых размерах элементов[править | править код]

Важным частным случаем является ситуация, когда размеры элементов образуют делимую последовательность. Такой случай встречается, например, при выделении памяти в компьютерных системах, где размеры объектов являются степенями двойки. Если размеры элементов делимы, и, кроме того, наибольший размер элемента делит размер контейнера, то алгоритм LPT всегда находит расписание, которое минимизирует максимальную сумму и максимизирует минимальную сумму.

Адаптации к другим сценариям[править | править код]

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

Однородные машины[править | править код]

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

Гонзалез, Ибарра и Сани показали, что коэффициент аппроксимации LPT для m однородных машин не превосходит $2 m / (m + 1)$ . Эта граница не является точной; существует асимптотическая нижняя оценка 1,5 при стремлении m к бесконечности. Для частного случая m=2 коэффициент аппроксимации не превышает $(1 + \sqrt{17}) / 4 \approx 1, 281$ , и эта оценка точна.
Миро, Орлин и Вохра исследовали сценарий с двумя машинами, одна из которых в q раз быстрее другой. Они вычислили коэффициент аппроксимации LPT как функцию от q. При q=1 их результат совпадает с известным коэффициентом 7/6 для идентичных машин.
Куламас и Кипарисис предложили модификацию LPT, в которой три самых длинных задания планируются оптимально, а остальные — по правилу LPT. Коэффициент аппроксимации для двух машин в этом случае равен $\sqrt{1, 5} \approx 1, 2247$ , и эта оценка точна.

Ограничение на количество заданий[править | править код]

В некоторых постановках существует ограничение на количество заданий, которые могут быть назначены каждой машине. Простым ограничением является условие, что любая машина не может выполнить более c заданий. Модифицированное правило LPT (MLPT) назначает каждое задание машине с наименьшей загрузкой среди тех, на которых назначено менее c работ.

Келлерер и Вёгингер исследовали вариант, в котором имеется не более 3*m заданий и каждая машина может содержать не более 3 заданий (это можно рассматривать как обобщение задачи упаковки в контейнеры). Они показали, что MLPT обеспечивает отношение максимальной суммы к оптимальной не более $(4 m - 1) / (3 m)$ , что совпадает с коэффициентом аппроксимации LPT для задачи без ограничений. Эта граница точна для MLPT. Высказано предположение, что MLPT имеет тот же коэффициент аппроксимации и для более общего ограничения на мощность множества (c>3). На сегодняшний день известно, что коэффициент аппроксимации MLPT для общего случая c>3 не превышает 2.
Чен, Хэ и Лин показали, что для той же задачи MLPT обеспечивает отношение минимальной суммы к оптимальной не менее $(3 m - 1) / (4 m - 2)$ , что также совпадает с гарантией LPT для задачи без ограничений.

Ещё одно ограничение требует, чтобы количество заданий на всех машинах было равно значению $n / m$ , округлённому в большую или меньшую сторону. В адаптации LPT, называемой ограниченным LPT (RLPT), входные данные назначаются парами — по одному на каждую машину (для m=2 машин).

Коффман, Фредериксон и Люкер показали, что математическое ожидание максимальной суммы в RLPT при равномерно распределённых случайных входных данных в точности равно $\frac{n}{4} + \frac{1}{2 n + 2}$ . Математическое ожидание разности между максимальной и минимальной суммами составляет $Θ (1 / n)$ .

Неодновременная доступность машин[править | править код]

В задаче корневого разделения имеется m предварительных заданий, каждое из которых должно быть распределено на единственную машину. Эквивалентная задача — планирование работ, когда машины становятся доступными в разное время — машина i доступна начиная с

Ссылки[править | править код]