Приближенный алгоритм

[myf]

Условие: Имеется m-процессорная система (процессоры не обязательно одинаковые, производительность их указывается). Необходимо выполнить n-работ (работы не обязательно одинаковые, время их работы указывается для процессора единичной производительности). Необходимо так распределить работы, чтобы наиболее загруженный процессор закончил выполнение как можно раньше.
Приближенный алгоритм вроде ясен (отсортировать работы и давать тому, кто раньше сможет закончить её выполнение). Вот только проблема с гарантированной оценкой алгоритма. Вроде как получается 4/3 (точно также , если бы процессоры были одинаковы), но как это доказать (или может не 4/3).

[maxal]

Оценка не может быть константой, так как легко привести пример, когда она зависит от параметров задачи.

Рассмотрим случай двух процессоров с производительностью 1 и p>1 и двух задач со временем работы 1 и 2.
По алгоритму задача 2 отдается на выполнение второму процессору и ее выполнение потребует 2/p времени, вторая задача отдается первому процессору и ее выполнение потребует 1 времени.
Если же обе задачи отдать второму процессору, то потребуется (1+2)/p=3/p времени. Поэтому оценка алгоритма не меньше (1+2/p)/(3/p) = (p+1)/3, что растет с ростом p.

[myf]

maxal
Алгоритм я думал следующий: работа отдается тому, кто после её выполнения затратит наименьшее время в сумме. Если есть 2 процессора 1 и p>1 и две задачи со временем работы 1 и 2 (задачи потом осртируме по не возрастанию). p может быть таким большим, что 2/p+1/p<1,т.е. обе работы пойдут второму процессору. Или вы имеете в виду другой алгоритм какой-то? При моем алгоритме оценка не доходит даже до 2-х (если на примерах смотреть). Но в таком я случае я не знаю, как это доказать для случая m-процессоров.

[maxal]

Да, я просто сначала не понял вашего алгоритма.

На $m$ процессорах можно получить оценку снизу $\frac{2m-1}{m}.$ Для этого достаточно запустить алгоритм на $m$ одинаковых процессорах (производительности 1) $m(m-1)$ задач сложности 1 и одну задачу сложности $m.$ Алгоритм сначала распределит простые задачи по $m-1$ на каждый процессор, а затем на одном из них в довесок запустит сложную задачу. Затраченное время равно $2m-1.$ В оптимальном варианте надо запустить сложную задачу на одном процессоре, а простые распределить поровну между остальными, это потребует $m$ времени.

[myf]

Задачи ведь отсортированы по не возрастанию. Значит мой алгоритм сначала даст одному процессору сложную задачу, а потом только простыми займется. В таком случае оценка 4/3 будет. А вот если процессоры разные... Оценка мне кажется 2, но как это доказать...

[maxal]

См. статью Approximation algorithms for scheduling unrelated parallel machines.