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

Я думаю, что алгоритм, подобный приведенному ниже, был бы полезен для вас, он делает мельчайшие изменения в вашем алгоритме RR, поэтому вам не нужно много менять:

work(Product product) {
    if (product is small)
        put in queue
    else {
        split product into independent parts
        fork new subtasks to solve each part
        join all subtasks
        compose result from subresults
    }
}

Если я правильно помню, это часть алгоритма кражи работ.

Один из способов сделать это — изменить очереди так, чтобы они были не очередями элементов, а очередями записей производителей, каждая из которых содержит очередь элементов. Таким образом, если у вас есть N производителей, каждая очередь будет иметь не более N записей. Каждая запись содержит список (очередь) заданий от этого производителя.

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

Некоторое время назад я сделал что-то очень похожее с проектом поискового робота. Это сработало очень хорошо.

По сути, то, что вы описали, - это то, как вы интерпретировали RR для своей проблемы, я бы интерпретировал это по-другому:

каждый производитель будет заполнять одну очередь за другой. Здесь все еще есть небольшая проблема, так как для вашего примера Q1 будет содержать 52 задачи (половина из N1 плюс N2+N3), а Q2 будет содержать только 50 задач, но эту разницу можно считать довольно незначительной.

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

N1 начинается с Q1, N2 начинается с Q2 и N3 снова с Q1.

Таким образом, мы получим разделение 51:51.

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