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

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

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

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

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

Примеры Если входное множество равно 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. Однако, его субоптимальность ограничена как в худшем, так и в среднем случае; см. Performance guarantees ниже.

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

Алгоритм LPT является монотонным в том смысле, что при увеличении одного из входных чисел целевая функция (наибольшая или наименьшая сумма подмножества в результате) слабо увеличивается. Это отличает его от алгоритма .

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

Максимальная сумма в наихудшем случае В худшем случае наибольшая сумма в жадном разбиении не более чем в раз превосходит оптимальную (минимальную) сумму. Доказательство можно найти в статье Xiao Xin.

Более детальный анализ показывает, что отношение к оптимальной (минимальной) наибольшей сумме составляет (например, если m =2, отношение равно )

Коэффициент является точным. Предположим, что имеется входных значений (где m чётно): . В этом случае жадный алгоритм выдаст следующее:

, ...

с максимумом , но оптимальное разбиение таково:

...

с максимумом .

Входные данные Более детальный анализ учитывает количество входов в части.

В каждой части жадного разбиения j-е по величине число не превышает . Предположим, что в жадной части P с максимальной суммой имеется L входных данных. Тогда коэффициент аппроксимации жадного алгоритма равен . Это значение является точным для L≥3 (для L=3 мы получаем общий коэффициент ).

Минимальная сумма в худшем случае В худшем случае, наименьшая сумма в полученном разбиении составляет не менее оптимальной (максимальной) наименьшей суммы.

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

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

Ожидаемое значение наибольшей суммы для m=2 машин составляет не менее и не более , где n — количество входных данных. Наибольшая сумма почти достоверно не превышает оптимальную более чем в , а в среднем ожидается не более чем в раз, где n — количество входных данных. Разница между наибольшей суммой по LPT и оптимальной наибольшей суммой почти достоверно составляет не более (для равномерного или отрицательного экспоненциального распределений), а в среднем ожидается не более (для однородного распределения). Эти результаты применимы также для машин с разной производительностью.

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

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

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

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

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

Гонзалез, Ибарра и Сани показали, что коэффициент аппроксимации LPT с m однородными машинами не превосходит . Значение не точное, но имеется асимптотическое нижнее значение 1,5 при стремлении m к бесконечности. Для частного случая m=2 машин, коэффициент аппроксимации не превосходит и значение точное. Миро, Орлин и Вохра изучали сценарий с двумя машинами, в которой одна машина в q раз быстрее, чем другая. Они вычислили коэффициент аппроксимации LPT как функцию от q. Если q=1, их результат совпадает с коэффициентом 7/6, известном для одинаковых машин. Куламас и Кипарисис представили модификацию LPT алгоритма, в котором три наиболее длинные задания планируются оптимально, а остальные задания планируются на основе правила LPT. Коэффициент аппроксимации для двух машин равен и является точным.

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

Келлерер и Вёгингер изучали вариант, в котором имеется не более 3*m заданий и каждая машина должна содержать не более 3 заданий (это можно рассматривать как обобщение ). Они показали, что MLPT достигает не более от минимальной наибольшей суммы, что является тем же коэффициентом аппроксимации, который LPT достигает для не имеющей ограничений задачи. Граница является точной для MLPT. Было сделано предположение, что MLPT имеет тот же коэффициент аппроксимации для более общих ограничений размера (c>3). На сегодняшний день известно, что коэффициент аппроксимации MLPT для общего случая c>3 не больше 2. Чен, Хэ и Лин показали, что для той же задачи MLPT достигает по меньшей мере максимальной наименьшей суммы, что опять является тем же коэффициентом аппроксимации, который LPT достигает для не имеющей ограничений задачи. Ещё одно ограничение заключается в том, что количество заданий на всех машинах должно быть равно значению , округлённому либо в большую, либо в меньшую сторону. В адаптации LPT, называемой ограниченным LPT или RLPT, входные данные назначаются парами — по одному на каждую машину (для m=2 машин).

Коффман, Фредериксон и Люкер показали, что математическое ожидание наибольшей суммы RLPT при равномерно распределенных случайных входных данных равно в точности . Математическое ожидание разности между наибольшей и наименьшей суммами равно .

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

Простой эвристический алгоритм, называемый SLPT назначает каждое предварительное задание различным элементам разбиения, а затем запускает алгоритм LPT.

Ли доказал, что эта эвристика имеет точный коэффициент аппроксимации для минимума наибольшей суммы. Затем он предлагает на втором шаге запустить модифицированную версию LPT и доказывает, что она достигает приближённого отношения . Линь, Яо и Хэ доказывают, что эта эвристика имеет точный коэффициент аппроксимации для максимальной наименьшей суммы. Шэнь, Ван и Ван изучают различные целевые функции для этой задачи и представляют алгоритмы полиномиального времени.

Работа в онлайн условиях Часто входные данные приходят и их размер становится известным только когда они все прибудут. В этом случае нет возможности их отсортировать заранее. является похожим алгоритмом, который принимает список в любом порядке, не обязательно отсортированный. Коэффициент аппроксимации этого алгоритма равен .

Более сложная адаптация LPT к онлайн-среде достигает коэффициента аппроксимации 3/2.

Реализации

Python: имеется реализация LPT ("жадная") в пакете numberpartitioning, а также в пакете prtpy.

См. также – обобщение LPT для for для задачи многопозиционного разбиения чисел..

Примечания

Категория:Оптимальные расписания