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

Question

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

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

A: 4 B: 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 не могут быть назначены никакие задания - он уже на пределе. Кроме того, тот факт, что С не имеет ничего общего, не означает, что ему гарантированно дадут новую работу (скорее всего).

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

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

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