Взвешенный алгоритм планирования ресурсов с балансировкой нагрузки

Question

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

Допустим, есть пять пользователей со следующим количеством задач:

А:4 б:5 c:0 D:7 E:9

Я хочу расставить приоритеты пользователей для следующей задачи в порядке CABDE, где C с наибольшей вероятностью получит задание, а E — с наименьшей вероятностью.Здесь следует отметить две важные вещи:

• Количество пользователей может варьироваться от 2 до десятков.
• Количество задач, назначенных каждому пользователю, может варьироваться от 1 до сотни.

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

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

Я пробовал порыться в сети, но безуспешно.Может ли кто-нибудь дать мне краткое описание алгоритма, который будет хорошо работать?Мне не нужна реальная реализация — я сделаю эту часть — просто хорошее описание.Альтернатива: есть ли хороший веб-сайт, к которому есть бесплатный доступ?

Кроме того, хотя я, безусловно, ценю качество, оно не обязательно должно быть статистически идеальным.Так что, если вы можете придумать хорошую, но не отличную технику, мне интересно!

Answer 1

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

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

Имея дополнительную информацию, мы могли бы дать конкретные рекомендации по функциям, которые могут вам подойти.

Редактировать:примеры функций балансировки нагрузки

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

Если использовать пример из вопроса: в настоящее время назначено 4 + 5 + 0 + 7 + 9 = 25 рабочих мест.Вы хотите выбрать, кто получит работу 26.

1) Простая ферма задач. Для каждого задания всегда выбирайте работника с наименьшим количеством незавершенных заданий.Быстрые работники успевают сделать больше, но все заканчивают примерно в одно и то же время.

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

3) Базовая линейная нормализация. Выберите максимальное количество рабочих мест, которое может иметь каждый работник.Рабочая нагрузка каждого работника нормируется по этому числу.Например, если максимальное количество заданий на одного работника равно 15, то до достижения емкости можно добавить еще 50 заданий.Таким образом, для каждого работника вероятность назначения на следующую работу равна

P(A) = (15 - 4)/50 = 0.22  
P(B) = (15 - 5)/50 = 0.2  
P(C) = (15 - 0)/50 = 0.3  
P(D) = (15 - 7)/50 = 0.16  
P(E) = (15 - 9)/50 = 0.12

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

P(A) = (9 - 4)/20 = 0.25  
P(B) = (9 - 5)/20 = 0.2  
P(C) = (9 - 0)/20 = 0.45 
P(D) = (9 - 7)/20 = 0.1  
P(E) = (9 - 9)/20 = 0

Обратите внимание, что в этом случае нормализация гарантирует, что работнику E не может быть назначена никакая работа — он уже на пределе.Кроме того, то, что C нечего делать, не означает, что ему гарантированно дадут новую работу (просто это более вероятно).

Вы можете легко реализовать функцию выбора, сгенерировав случайное число. р между 0 и 1 и сравниваем его с этими границами.Так что если р < 0,25, А получает работу, 0,25 < р < 0,45, B получает работу и т. д.

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

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