Планирование с наибольшим временем обработки в первую очередь

Алгоритм планирования работ

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

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

Шаг 2 алгоритма по сути является алгоритмом планирования списков (LS). Разница в том, что LS циклически проходит по заданиям в произвольном порядке, тогда как LPT предварительно упорядочивает их по убыванию времени обработки.

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

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

Примеры

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

Характеристики

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

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

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

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

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

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

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

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

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

• ${\displaystyle 2m-1,m,m}$
• ${\displaystyle 2m-1,m}$
• ${\displaystyle 2m-2,m+1}$
• ${\displaystyle 2m-2,m+1}$,
• ...
• ${\displaystyle 3m/2,3m/2-1}$
• ${\displaystyle 3m/2,3m/2-1}$

с максимумом , но оптимальное разбиение: ${\displaystyle 4m-1}$

• ${\displaystyle m,m,m}$
• ${\displaystyle 2m-1,m+1}$
• ${\displaystyle 2m-1,m+1}$
• ${\displaystyle 2m-2,m+2}$
• ${\displaystyle 2m-2,m+2}$
• ...
• ${\displaystyle 3m/2,3m/2}$

с максимальным значением . ${\displaystyle 3m}$

Входное рассмотрение

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

1. В каждой части жадного разбиения j -е наибольшее число не превышает . ^[5] ${\displaystyle OPT/j}$
2. Предположим, что в жадной части P с максимальной суммой имеется L входов. Тогда коэффициент аппроксимации жадного алгоритма равен . ^[4] Он плотный для L≥ 3 (для L =3 мы получаем общий множитель ). Доказательство . ^[5] Обозначим числа в 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/ m )*OPT/ L . Таким образом, отношение не превышает (1 + 1/ L - 1/ Lm ). ${\displaystyle {\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}}$ ${\displaystyle {\frac {4}{3}}-{\frac {1}{3m}}}$

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

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

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

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

• Минимальная сумма в оптимальном разбиении равна 4, а минимальная сумма в жадном разбиении меньше 3 (это просто нормализация — без потери общности).
• Максимальная сумма в жадном разбиении больше 4 (так как общая сумма в обоих разбиениях одинакова и составляет не менее 4 m ).
• Если sum(P _i )≥3 для некоторого жадного контейнера P _i , то P _i не доминируется никаким оптимальным контейнером Q _j . Доказательство : если P _i доминируется Q _j , то мы можем построить меньший контрпример, уменьшив m до m -1 и удалив элементы из P _i . Минимальная сумма в жадном разбиении остается меньше 3. В оптимальном разбиении элементы в P _i можно заменить их доминирующими элементами в Q _j , поэтому минимальная сумма остается не менее 4.
• Если sum(P _i )≥3 для некоторого жадного контейнера P _i , то P _i содержит по крайней мере два числа. Доказательство : если P _i содержит только одно число x, то он доминируется оптимальным контейнером Q _j , который содержит x. Допустим, что некоторый вход x равен по крайней мере 3, и жадный алгоритм помещает его в некоторый P _i . Тогда, поскольку существует набор с суммой меньше 3, жадный алгоритм не поместит никакой другой вход в P _i , что противоречит предыдущей лемме.
• Каждый жадный контейнер P _i содержит не более одного входа, слабо большего, чем 3/2. Доказательство : Пусть P _i будет первым жадным контейнером, которому назначены два таких входа. Поскольку входы назначаются в порядке убывания, P _i является первым жадным контейнером, которому назначены два входа. Это означает, что он должен содержать два наименьших входа из числа наибольших m + 1 входов. Более того, поскольку сумма этих двух элементов составляет не менее 3/2 + 3/2 = 3, P _i не назначается никаких других входов. С другой стороны, по принципу ящика должен быть некоторый оптимальный контейнер Q _j , который содержит некоторые два входа из числа наибольших m + 1 входов; поэтому P _i доминируется Q _j .
• Во время работы жадного алгоритма сумма в каждой ячейке P _i становится по крайней мере 8/3 до того, как сумма любой ячейки превысит 4. Доказательство : Пусть y будет первым входом, добавленным к некоторой ячейке P _i , что сделало ее сумму больше 4. До того, как y был добавлен, P _i имел наименьшую сумму, которая по предположению была меньше 8/3; это означает, что y>4/3. Пусть T обозначает множество всех входов от первого до y ; все эти входы также больше 4/3. Поскольку P _i был меньше 8/3, он содержал ровно один элемент x из T. Так что теперь P _i содержит ровно 2 элемента {x,y} и остается с этими 2 элементами до конца алгоритма. Пусть 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. Это, очевидно, не уменьшает оптимальную минимальную сумму. Мы показываем, что это не меняет жадную минимальную сумму. Мы знаем, что некоторый жадный пакет P _i имеет конечную сумму больше 4. До того, как последний вход был добавлен в P _i , его сумма была меньше 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). Набор малых элементов в P _i обозначается как S _i . Обратите внимание, что когда алгоритм начинает обрабатывать малые элементы, сумма во всех наборах составляет не менее 8/3.

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

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

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

• Если x≥2, то w(x)=8/3. Доказательство : x большой. Предположим, что он находится в P _i . Если P _{i содержит другой большой элемент y, то x+y≥3, так что в P i} нет других элементов . Более того, x>y, так как существует не более одного элемента, большего 3/2. Поэтому w(x)=8/3.
• Если x<1/3, то w(x) > 2x. Доказательство : x мало. Предположим, что оно находится в P _i .
  • Если 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.
  • Если сумма(P _i )<3, то сумма(S _i ) < 3-8/3=1/3, поэтому w(x) = 2x/(3 сумма(S _i )) > 2x.
• Вес каждого жадного контейнера P _i не более 4, а вес хотя бы одного жадного контейнера не более 10/3. Доказательство :
  • Если все входы в P _i большие, то он содержит либо один вход с весом 8/3, либо два входа с весами 8/3+4/3, либо три входа с весами 4/3+4/3+4/3.
  • Если некоторые входы в P _i малы, то их общий вес не более 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. В противном случае x>5/3. Итак, x был первым входом в некоторой жадной ячейке P _m . Пусть z будет вторым входом, добавленным в P _{m . Если x+z≥3, то в P m} больше нет входов , поэтому w(x)=8/3, и мы закончили. В противном случае x+z<3. Пусть v будет наименьшим входом в некоторой жадной ячейке, сумма которого превышает 4. Поскольку x<8/3, z должен был быть обработан до v, поэтому z≥v. Теперь рассмотрим любой маленький элемент t в Q _j и предположим, что он находится в некоторой жадной ячейке P _i .
    • Если sum(P _i )<3, то тот факт, что v не было помещено в P _{i ,} подразумевает, что v > 4-sum(large-items-in-P _i ) > 1+sum(small-items-in-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(small-items-in-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 не было помещено в P _{i ,} подразумевает, что v > 4-sum(large-items-in-P _i ) > 1+sum(small-items-in-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 м. Следовательно, контрпримера не существует.

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

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

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

Вышеуказанное соотношение является жестким. ^[6]

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

Средняя максимальная сумма

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

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

Общие цели

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

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

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

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

Важным особым случаем является то, что размеры элементов образуют делимую последовательность (также называемую факторизованной ). Особый случай делимых размеров элементов возникает при распределении памяти в компьютерных системах, где все размеры элементов являются степенями 2. Если размеры элементов делимы, и, кроме того, наибольший размер элемента делит размер ячейки, то LPT всегда находит планирование, которое минимизирует максимальный размер, ^{[14] : Теория 4} и максимизирует минимальный размер. ^{[14] : Теория 5}

Адаптация к другим условиям

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

Единообразные машины

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

• Гонсалес, Ибарра и Сахни ^[15] показывают, что отношение аппроксимации LPT с m однородными машинами не превышает . Оно не является точным, но существует асимптотическая нижняя граница 1,5, когда m стремится к бесконечности. Для особого случая m = 2 машин отношение аппроксимации не превышает , и оно является точным. ${\displaystyle 2m/(m+1)}$ ${\displaystyle (1+{\sqrt {17}})/4\approx 1.281}$
• Миро, Орлин и Вохра ^[16] изучают установку с двумя машинами, в которой одна машина в q раз быстрее другой. Они вычисляют отношение аппроксимации LPT как функцию q . Когда q = 1, их результат совпадает с фактором 7/6, известным для идентичных машин.
• Куламас и Кипарисис ^[17] представляют модификацию LPT, в которой три самых длинных задания планируются оптимально, а оставшиеся задания планируются на основе правила LPT. Коэффициент аппроксимации для двух машин составляет и он жесткий. ${\displaystyle {\sqrt {1.5}}\approx 1.2247}$

Ограничения мощности

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

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

Другим ограничением является то, что число заданий на всех машинах должно быть округлено либо вверх, либо вниз. В адаптации LPT, называемой ограниченным LPT или RLPT , входы назначаются парами — по одному на каждую машину (для m = 2 машин). ^[10] Результирующее разделение сбалансировано по замыслу. ${\displaystyle n/m}$

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

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

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

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

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

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

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

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

Реализации

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

Смотрите также

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

Примечания

1. Доказательство . Нормализуем входные элементы так, чтобы OPT=1. Это означает, что сумма всех элементов не превышает m. Разобьем элементы на большие (более 2/3), средние (от 1/3 до 2/3) и маленькие (менее 1/3). Пусть их числа будут nL, nM и nS. В каждом оптимальном разбиении каждая часть содержит не более одного большого элемента, поэтому nL ≤ m. Более того, каждая оптимальная часть не может содержать одновременно большой и средний элемент или три средних элемента; поэтому nM ≤ 2(m-nL). Работа жадного алгоритма может быть разделена на три фазы: 1. Распределение больших элементов, каждый из которых помещается в отдельную ячейку. Поскольку nL ≤ m, по завершении этой фазы каждая ячейка содержит не более одного элемента, поэтому максимальная сумма не превышает 1. 2. Распределение средних элементов. Первые m-nL помещаются в пустые ячейки, а следующие m-nL (если есть) добавляются в те же ячейки. Поскольку nM ≤ 2(m-nL), по завершении этой фазы каждая ячейка содержит либо один большой элемент — с суммой не более 1, либо не более двух средних элементов — с суммой не более 4/3. 3. Распределение мелких элементов. Каждый элемент добавляется в ячейку с наименьшей суммой. Наименьшая сумма не превышает среднюю сумму, которая не более 1. Следовательно, как только добавляется небольшой элемент, новая сумма становится не более 4/3.
2. Доказательство. Предыдущее доказательство можно усовершенствовать двумя способами. Во-первых, можно доказать, что после распределения всех больших и средних элементов сумма в каждой ячейке не превышает 1. Если имеется не более m-nL средних элементов, то каждый большой и средний элемент помещается в отдельную ячейку, так что сумма, очевидно, не превышает 1. В противном случае обозначим первые m-nL средних элементов как верхние-средние элементы, а остальные (не более m-nL) как нижние-средние элементы. Предположим сначала, что элемент #m больше 1/2. Это означает, что элементы #1,...,#m все больше 1/2, поэтому каждый должен находиться в другой оптимальной части. Каждый из нижних-средних элементов (элементы #m+1,...#nM) должен вписываться в оптимальную часть ровно с одним из элементов #1,...,#m. Назовем два элемента сопоставляемыми, если их сумма не превышает 1, так что они могут вписаться в одну и ту же оптимальную часть. По теореме Холла каждое подмножество из k нижних-средних элементов должно быть сопоставимо по крайней мере с k элементами #1,...,#m. В частности, элемент #m+1 должен быть сопоставим с элементом #m; элементы #m+1 и #m+2 должны быть сопоставимы с элементом #m-1; и в общем случае элемент #m+k должен быть сопоставим с элементом #'m-k+1. LPT действительно помещает элемент #m+k в тот же контейнер, что и #'m-k+1, поэтому сумма каждого контейнера не превышает 1. Во-вторых, можно доказать, что при распределении малых входов сумма каждого нового контейнера не превышает 4/3-1/(3m). Есть два случая: 1. Если текущая наименьшая сумма не превышает 1-1/(3m), то новая сумма — после добавления одного малого входа — не превышает 1-1/(3m)+1/3 = 4/3-1/(3m). 2. В противном случае все суммы больше 1-1/(3m), поэтому сумма m-1 самых больших ячеек больше m-1-1/3+1/(3m) = m-(4/3-1/(3m)). Поскольку общая сумма всех входных данных не превышает m, новая сумма должна быть меньше 4/3-1/(3m).

Ссылки

1. Graham, RL (март 1969). «Границы аномалий многопроцессорной синхронизации». Журнал SIAM по прикладной математике . 17 (2): 416–429. CiteSeerX  10.1.1.90.8131 . doi :10.1137/0117039. JSTOR  2099572. NAID  30006801878 ProQuest  917998761.
2. Segal-Halevi, Erel (2021-10-17), О монотонности алгоритмов разбиения чисел, arXiv : 2110.08886 , получено 2024-02-22
3. Сяо, Синь (2017-04-01). "Прямое доказательство границы 4/3 правила планирования LPT". Труды 5-й Международной конференции 2017 года по передовым рубежам производственной науки и измерительной техники (FMSMT 2017) . Atlantis Press. стр. 486–489. doi : 10.2991/fmsmt-17.2017.102 . ISBN 978-94-6252-331-9.
4. Coffman, EG; Sethi, Ravi (1976-03-29). "Обобщенная граница последовательности LPT". Труды конференции ACM SIGMETRICS 1976 года по измерению и оценке моделирования производительности компьютеров - SIGMETRICS '76 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 306–310. doi :10.1145/800200.806205. ISBN 978-1-4503-7497-2. S2CID  16980306.
5. Chen, Bo (1993-10-01). «Заметка о планировании LPT». Operations Research Letters . 14 (3): 139–142. doi :10.1016/0167-6377(93)90024-B. ISSN  0167-6377.
6. Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (июнь 1982 г.). «Планирование для максимизации минимального времени завершения работы процессора в многопроцессорной системе». Журнал SIAM по алгебраическим и дискретным методам . 3 (2): 190–196. doi :10.1137/0603019.
7. Чирик, Янош; Келлерер, Ханс; Вёгингер, Герхард (июнь 1992 г.). «Точная граница LPT для максимизации минимального времени завершения». Operations Research Letters . 11 (5): 281–287. doi :10.1016/0167-6377(92)90004-M.
8. Wu, Bang Ye (декабрь 2005 г.). «Анализ алгоритма LPT для задач разделения max–min и min–ratio». Теоретическая информатика . 349 (3): 407–419. doi : 10.1016/j.tcs.2005.08.032 .
9. Уолтер, Рико (2013-01-01). «Сравнение минимального времени завершения двух эвристик планирования с наибольшим первым». Central European Journal of Operations Research . 21 (1): 125–139. doi :10.1007/s10100-011-0217-4. ISSN  1613-9178. S2CID  254144745.
10. Коффман, EG; Фредериксон, GN; Люкер, GS (1984-05-01). "Заметка об ожидаемых интервалах выполнения для последовательностей независимых задач с наибольшим первым значением на двух процессорах". Математика исследования операций . 9 (2): 260–266. doi :10.1287/moor.9.2.260. ISSN  0364-765X.
11. Frenk, JBG; Kan, AHGRinnooy (июнь 1986). "Скорость сходимости к оптимальности правила LPT". Discrete Applied Mathematics . 14 (2): 187–197. doi :10.1016/0166-218X(86)90060-0. hdl : 1765/11698 .
12. Frenk, JBG; Rinnooy Kan, AHG (1987-05-01). "Асимптотическая оптимальность правила LPT". Математика исследования операций . 12 (2): 241–254. doi :10.1287/moor.12.2.241. ISSN  0364-765X. S2CID  31770203.
13. Алон, Нога; Азар, Йосси; Вёгингер, Герхард Дж.; Ядид, Тал (1998). «Аппроксимационные схемы для планирования на параллельных машинах». Журнал планирования . 1 (1): 55–66. doi :10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J. ISSN  1099-1425.
14. Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). «Упаковка контейнеров с делимыми размерами предметов». Journal of Complexity . 3 (4): 406–428. doi :10.1016/0885-064X(87)90009-4. ISSN  0885-064X.
15. Гонсалес, Теофило; Ибарра, Оскар Х.; Сахни, Сартай (1977-03-01). «Границы для LPT-расписаний на однородных процессорах». SIAM Journal on Computing . 6 (1): 155–166. doi :10.1137/0206013. ISSN  0097-5397.
16. Миро, Пол; Орлин, Джеймс Б.; Вохра, Ракеш В. (1997-02-01). «Параметрический анализ наихудшего случая эвристики LPT для двух однородных машин». Исследование операций . 45 (1): 116–125. doi :10.1287/opre.45.1.116. ISSN  0030-364X.
17. Куламас, Христос; Кипарисис, Джордж Дж. (2009-07-01). «Модифицированный алгоритм LPT для задачи минимизации производительности двух однородных параллельных машин». Европейский журнал операционных исследований . 196 (1): 61–68. doi :10.1016/j.ejor.2008.02.008. ISSN  0377-2217.
18. Келлерер, Ганс; Вёгингер, Герхард (1993-09-07). "Жесткая граница для 3-разбиения". Дискретная прикладная математика . 45 (3): 249–259. doi : 10.1016/0166-218X(93)90013-E . ISSN  0166-218X.
19. Бабель, Луитпольд; Келлерер, Ганс; Котов, Владимир (1998-02-01). «Проблема m-разбиения». Математические методы исследования операций . 47 (1): 59–82. doi :10.1007/BF01193837. ISSN  1432-5217. S2CID  5594197.
20. Делл'Амико, Мауро; Мартелло, Сильвано (2001). «Границы для проблемы P∥Cmax с ограничением по кардинальности». Журнал планирования . 4 (3): 123–138. doi :10.1002/jos.68. ISSN  1099-1425.
21. Чэнь, Ши Пин; Хэ, Юн; Линь, Гохуэй (2002-03-01). «Задачи 3-разбиения для максимизации минимальной нагрузки». Журнал комбинаторной оптимизации . 6 (1): 67–80. doi :10.1023/A:1013370208101. ISSN  1573-2886. S2CID  9053629.
22. Цай, Ли-Хуэй (1 февраля 1992 г.). «Асимптотический анализ алгоритма сбалансированного параллельного планирования процессоров». Журнал SIAM по вычислениям . 21 (1): 59–64. doi :10.1137/0221007. ISSN  0097-5397.
23. Чэнь, С. -П.; Хэ, И.; Яо, Э. -И. (1996-09-01). "Трехразбиение, содержащее ядра: сложность и эвристика". Computing . 57 (3): 255–271. doi :10.1007/BF02247409. ISSN  1436-5057. S2CID  21935917.
24. Ли, Чунг-Йи (1991-01-07). «Планирование параллельных машин с неодновременным временем доступности машин». Дискретная прикладная математика . 30 (1): 53–61. doi : 10.1016/0166-218X(91)90013-M . ISSN  0166-218X.
25. Линь, Го-Хуэй; Яо, Эн-Ю; Хэ, Юн (1998-03-01). «Параллельное планирование машин для максимизации минимальной загрузки при неодновременном времени доступности машин». Operations Research Letters . 22 (2): 75–81. doi :10.1016/S0167-6377(97)00053-9. ISSN  0167-6377.
26. Шэнь, Лисинь; Ван, Дан; Ван, Сяо-Юань (2013-04-01). «Планирование параллельной работы машин с неодновременным временем доступности машин». Прикладное математическое моделирование . 37 (7): 5227–5232. doi :10.1016/j.apm.2012.09.053. ISSN  0307-904X.
27. Чен, Бо; Вестженс, Арьен ПА (1 ноября 1997 г.). «Планирование на идентичных машинах: насколько хорош LPT в онлайн-режиме?» (PDF) . Operations Research Letters . 21 (4): 165–169. doi :10.1016/S0167-6377(97)00040-0.