Планирование с наибольшим временем обработки

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

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

Шаг 2 алгоритма по сути представляет собой алгоритм планирования списков (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. Однако его субоптимальность ограничена как в худшем, так и в среднем случае; см. Гарантии производительности ниже.

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

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

Гарантии производительности: идентичные машины

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

Максимальная сумма в худшем случае

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

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

Фактор ${\frac {4m-1}{3m}}$ тесно. Предположим, есть $2m+1$ входы (где m четно): $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$. Затем жадный алгоритм возвращает:

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

с максимумом $4m-1$, но оптимальный раздел:

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

с максимумом $3m$.

Входные данные

Еще более детальный анализ учитывает количество входных данных в части максимальной суммы.

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

Минимальная сумма в худшем случае

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

Доказательство

Доказательство проводится от противного. Мы рассматриваем минимальный контрпример , то есть контрпример с наименьшим m и наименьшим количеством входных чисел. Обозначим жадное разбиение через P ₁ ,...,P _m , а оптимальное разбиение через Q ₁ ,...,Q _m . Некоторые свойства минимального контрпримера:

• Минимальная сумма в оптимальном разделе равна 4, а минимальная сумма в жадном разделе меньше 3 (это просто нормализация — без потери общности).
• Максимальная сумма в жадном разделе больше 4 (поскольку общая сумма в обоих разделах одинакова и составляет не менее 4 m ).
• Если sum(P _i )≥3 для некоторого жадного интервала Pi _, то Pi _не доминируется каким-либо оптимальным интервалом Q _j . Доказательство : если в Pi _{доминирует} Qj _, то мы можем построить меньший контрпример, уменьшив m до m -1 и удалив элементы из _Pi . Минимальная сумма в жадном разделе остается меньше 3. В оптимальном разделе элементы в Pi _могут быть заменены их доминирующими элементами в Q _j , поэтому минимальная сумма остается не менее 4.
• Если sum(Pi ₎ ≥3 для некоторого жадного интервала Pi _, то Pi _{содержит} как минимум два числа. Доказательство : если Pi _{содержит} только одно число x, то в нем доминирует оптимальный интервал Qj _, который содержит x. Дайте некоторый входной x, равный по крайней мере 3, и жадный алгоритм помещает его в некоторый _Pi . Тогда, поскольку существует пакет с суммой меньше 3, жадный алгоритм не будет помещать какие-либо другие входные данные в Pi _, что противоречит предыдущей лемме.
• Каждый жадный контейнер Pi _{содержит} не более одного входного сигнала, размер которого немного больше 3/2. Доказательство . Пусть P _i — первый жадный контейнер, которому назначены два таких входа. Поскольку входы назначаются в порядке убывания, Pi _— это первый жадный интервал, которому назначены два входа. Это означает, что он должен содержать два наименьших входа из числа самых больших m +1 входов. Более того, поскольку сумма этих двух элементов равна как минимум 3/2+3/2=3, P _i не назначается никакой другой вход. С другой стороны, согласно принципу «ячейки» , должен существовать некоторый оптимальный интервал Q _j , который содержит около двух входных данных из числа наибольших m +1 входных данных; поэтому в P _i доминирует Q _j .
• Во время работы жадного алгоритма сумма в каждом интервале Pi _{становится} не менее 8/3, прежде чем сумма любого интервала превысит 4. Доказательство : пусть y будет первым входным сигналом, добавленным в некоторый интервал Pi _, что увеличило его сумму. чем 4. До y добавления _{у Pi} была наименьшая сумма, которая по предположению была меньше 8/3; это означает, что y>4/3. Пусть T обозначает набор всех входных данных от первого до y ; все эти входы тоже больше 4/3. Поскольку P _i было меньше 8/3, оно содержало ровно один элемент x из T. Итак, теперь P _i содержит ровно 2 элемента {x, y} и остается с этими двумя элементами до тех пор, пока алгоритм не завершится. Пусть m — количество элементов от первого до x. Теперь мы покажем противоречие, посчитав элементы в T двумя способами.
  • Сначала рассмотрим n оптимальных ячеек. Если любой такой контейнер содержит элемент размером не меньше x, то он не может содержать какой-либо другой элемент из T, поскольку в противном случае он доминирует над {x,y}. При этом ни в одной такой корзине не может находиться три предмета из T, так как сумма любых двух из них больше 8/3, что больше x; а третий равен как минимум y, поэтому он доминирует над {x,y}. Следовательно, количество элементов в T не превышает 1* m + 2*( n - m ) = 2 n - m .
  • Теперь рассмотрим n жадных контейнеров. Когда y добавляется к пакету, содержащему x , это пакет с наименьшей суммой. Следовательно, все элементы T , меньшие x, должны находиться в жадном контейнере хотя бы с одним другим элементом T. То же самое верно для x и y. Следовательно, количество элементов в T не менее (m-1)+2*(n-m+1) = 2 n - m +1 - противоречие.
• Мы можем предположить, без ограничения общности, что все входные данные либо меньше 1/3, либо по крайней мере 1. Доказательство : предположим, что некоторый входной сигнал x находится в (1/3,1). Заменяем x на 1. Это, очевидно, не уменьшает оптимальную минимальную сумму. Мы показываем, что это не меняет жадную минимальную сумму. Мы знаем, что некоторый жадный пакет Pi _имеет конечную сумму больше 4. До того, как последний вход был добавлен в Pi _, его сумма была меньше 3; поэтому P _i стало больше 4, когда к нему было добавлено какое-то входное значение больше 1. По предыдущей лемме в этот момент сумма всех остальных жадных расслоений была не меньше 8/3. Алгоритм впоследствии достигает точки x. Как только алгоритм добавляет x в некоторый интервал P _j , сумма P _j больше не добавляются элементы _{становится не менее 8/3+1/3=3, поэтому в P j} . Таким образом, P _j содержит только один вход размером в [1/3,1). Как только x заменяется на 1, он все равно вставляется в P _j , и его сумма все еще превышает 3. Таким образом, жадная минимальная сумма не меняется.
• Теперь мы можем разделить входные данные на маленькие (менее 1/3) и большие (минимум 1). Набор мелких предметов в _Pi обозначается _Si . Обратите внимание, что когда алгоритм начинает обрабатывать мелкие предметы, сумма во всех пакетах составляет не менее 8/3.

Доказательство того, что минимального контрпримера не существует, использует схему взвешивания . Каждому входу x присваивается вес w(x) в соответствии с его размером и жадным пакетом P _i :

• Если x — большой элемент:
  • Если x — единственный большой элемент в Pi _, то w(x)=8/3.
  • Если P _i содержит ровно два элемента {x,y} и оба они большие, x>y и sum(P _i )≥3, то w(x)=8/3.
  • В противном случае w(x)=4/3.
• Если x — небольшой предмет:
  • если sum(P _i )≥3, то w(x) = 4x/(3 sum(S _i )); поэтому w(S _i ) = 4/3.
  • если sum(P _i )<3, то w(x) = 2x/(3 sum(S _i )); поэтому w(S _i ) = 2/3.

Эта схема взвешивания имеет следующие свойства:

• Если x≥2, то w(x)=8/3. Доказательство : x велико. Предположим, что это в _Pi . Если Pi _{содержит} нет другого элемента _{другой большой элемент y, то x+y≥3, поэтому в Pi} . Более того, x>y, поскольку существует не более одного элемента больше 3/2. Итак, w(x)=8/3.
• Если x<1/3, то w(x) > 2x. Доказательство : x мало. Предположим, что это в _Pi .
  • Если sum(P _i )≥3, то, поскольку sum(P _i ) была меньше 3 до того, как к ней был добавлен x, теперь она меньше 10/3. Но когда алгоритм начал обрабатывать мелкие элементы, sum(P _i ) составляла не менее 8/3. Это означает, что sum(S _i ) < 2/3, поэтому w(x) = 4x/(3 sum(S _i )) > 2x.
  • Если sum(P _i )<3, то sum(S _i ) < 3-8/3=1/3, поэтому w(x) = 2x/(3 sum(S _i )) > 2x.
• Вес каждого жадного контейнера Pi _не превышает 4, а вес хотя бы одного жадного контейнера не превышает 10/3. Доказательство :
  • Если все входы в Pi _{большие} , то он содержит либо один вход с весом 8/3, два входа с весами 8/3+4/3 или три входа с весами 4/3+4/3+4/3. .
  • Если некоторые входы в Pi _малы , то их общий вес не превышает 4/3. Существует не более двух больших входных данных, и их веса равны либо 8/3, либо 4/3+4/3.
  • Наконец, вес жадного контейнера с суммой меньше 3 составляет не более 8/3 (если у него только большие входные данные) или 10/3 (если у него несколько маленьких входных данных).
• Вес каждого оптимального контейнера Q _j не менее 4. Доказательство :
  • Если Q _j содержит только небольшие элементы, то каждый из них удовлетворяет условию w(x) > 2x, поэтому w(Q _j ) > 2 sum(Q _j ) ≥ 8.
  • Если Q _j содержит ровно один большой элемент x, то он должен содержать несколько мелких элементов, сумма которых не менее 4-x и вес не менее 8-2x. Тогда либо x<2 и вес мелких предметов не менее 8-4=4, либо x в (2,3) и w(x)=8/3 и вес мелких предметов не менее 8-6. =2. В обоих случаях общий вес составляет не менее 4.
  • Если Q _j содержит ровно два больших элемента x>y и x≥2, то существует как минимум 8/3+4/3=4. Если x+y≤10/3, то сумма мелких предметов должна быть не менее 2/3, поэтому общий вес будет не менее 4/3+4/3+2*2/3=4. В противном случае х>5/3. Итак, x был первым входом в некоторую жадную корзину P _m . Пусть z будет вторым входом, добавленным в P _m . больше нет входных данных _{Если x+z≥3, то в Pm} , поэтому w(x)=8/3, и мы закончили. В противном случае x+z<3. Пусть v — наименьший входной сигнал в некотором жадном контейнере, сумма которого превышает 4. Поскольку x<8/3, z должен быть обработан до v, поэтому z≥v. Теперь рассмотрим любой небольшой элемент t в Qj _и предположим, что он находится в некоторой жадной корзине _Pi .
    • Если sum(P _i )<3, то тот факт, что v не был помещен в Pi _, означает, что v > 4-sum(большие элементы в P _i ) > 1+sum(маленькие элементы в P _i ). Следовательно, 1+sum(S _i )+x < v+x ≤ z+x < 3 и sum(S _i ) < 2-x. Это означает, что 2*sum(S _i ) < 4-2x ≤ 4-xy ≤ sum(small-items-in-Q _j ). Итак, w(t) = 2t/(3sum(S _i )) > 4t/(3sum(маленькие элементы в Q _j )).
    • Если sum(P _i )≥3 и sum(S _i )≤1, то w(t)=4/3, и все готово. Поскольку sum(P _i ) было меньше 3 до добавления к нему t, sum(P _i )<3+sum(S _i )/2. Тот факт, что v не был помещен в Pi _, означает, что v > 4-sum(большие элементы в P _i ) > 1+sum(маленькие элементы в P _i )/2. Как и в предыдущем абзаце, w(t) > 4t/(3sum(small-items-in-Q _j )).
    • Следовательно, общий вес всех мелких предметов в Q _j составляет не менее 4/3, поэтому общий вес Q _j составляет не менее 4/3+10/3>4.
  • Если Q _j содержит ровно три и более крупных предметов, то его общий вес не менее 4/3+4/3+4/3=4.
• Последние два утверждения противоречивы, так как первое предполагает, что вес всех входов не превышает 4 м -2/3, а второе подразумевает, что вес всех входов не менее 4 м. Следовательно, контрпримера не существует.

Верхняя граница отношения

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

Плотность и пример

Вышеупомянутое соотношение жесткое.

Предположим, что имеется 3 m -1 входов (где m четно). Первые 2 м входных данных: 2 м -1, 2 м -1, 2 м -2, 2 м -2, ..., м , м . Все последние m -1 входные данные — m . Затем жадный алгоритм возвращает:

• 2 м -1, м , м
• 2 м -1, м , м
• 2 м -2, м+1 , м
• 2 м -2, м+1 , м
• ...
• 3 м/2, 3 м/2-1, м
• 3 м/2, 3 м/2-1

с минимумом 3 м -1. Но оптимальный раздел:

• 2 м -1, 2 м -1
• 2 м -2, м , м
• 2 м -2, м , м
• 2 м -3, м +1, м
• 2 м -3, м +1, м
• ...
• 3 м/2, 3 м/2-2, м
• 3 м/2, 3 м/2-2, м
• 3 м/2-1, 3 м/2-1, м

с минимумом 4 м -2.

Ограниченный LPT

Существует вариант 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}{4n+4}}$ и самое большее ${\frac {n}{4}}+{\frac {e}{2n+2}}$, где n — количество входов.
• Самая большая сумма не превышает $1+O(\log {\log {n}}/n)$ раз оптимум почти наверняка , и $1+O(1/n)$ в ожидании, где $n$ это количество входов.
• Разница между наибольшей суммой LPT и оптимальной наибольшей суммой не превышает $O(\log {n}/n)$ почти наверняка (при равномерном или отрицательном экспоненциальном распределении) и не более $O(m^{2}/n)$ в ожидании (для равномерного распределения). Эти результаты справедливы и для машин с разными скоростями .

Общие цели

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

1. Сильное условие непрерывности, называемое условием F* : для любого ε>0 существует δ>0 такое, что если | y - x |<δ x , то |f( y )-f( x )|<ε f ( x ).
2. Выпуклость .

Тогда правило LPT имеет конечный коэффициент аппроксимации для минимизации суммы ( f ( C _i )).

Производительность с делимыми размерами предметов

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

Адаптации к другим настройкам

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

Униформные машины

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

• Гонсалес, Ибарра и Сахни показывают, что коэффициент аппроксимации LPT с m однородными машинами не превышает $2m/(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 назначает каждое задание машине с наименьшей нагрузкой из числа тех, у которых меньше c заданий. Это правило называется модифицированным LPT или MLPT .

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

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

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

Ограничения ядра — неодновременная доступность

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

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

• Ли доказывает, что эта эвристика имеет строгий коэффициент аппроксимации ${\frac {3m-1}{2m}}$ за минимальную большую сумму. Затем он предлагает на втором этапе запустить модифицированную версию LPT и доказывает, что она достигает коэффициента аппроксимации ${\frac {4}{3}}$ .
• Линь, Яо и Хэ докажите, что эта эвристика имеет строгий коэффициент аппроксимации ${\frac {2m-1}{3m-2}}$ за максимально наименьшую сумму.
• Шен, Ван и Ван изучить различные целевые функции для этой ситуации и представить алгоритмы с полиномиальным временем.

Настройки онлайн

Часто входы поступают в онлайн , и их размеры становятся известны только тогда, когда они поступают. В этом случае отсортировать их заранее невозможно. Планирование списков — это аналогичный алгоритм, который принимает список в любом порядке, не обязательно отсортированном. Его коэффициент аппроксимации равен ${\frac {2m-1}{m}}=2-{\frac {1}{m}}$.

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

Реализации

• Python : реализация LPT («жадный») есть в пакете numberpartitioning , а также в пакете prtpy .

См. также

• Жадное разделение чисел - обобщение и расширение LPT для задачи многостороннего разделения чисел.