algorithm - 没有前瞻性的桶之间的加权分布

Question

我有 N 个工作人员需要处理传入的数据批处理。每个工作人员都经过配置，使其知道自己是“N 中的工作人员 X”。

每批传入的数据都有一个随机唯一的ID(随机，均匀分布)，并且大小不一；处理时间与大小成正比。尺寸可能相差很大。

当一批新数据可用时，所有 N 个工作人员都可以立即看到它，但我希望只有一个工作人员实际处理它，他们之间没有协调。现在，每个工作人员计算 ID % N == X，这是真的，工作人员自行分配批处理，而其他工作人员则跳过它。这可以正常工作，并确保每个工作人员平均处理相同数量的批处理。不幸的是，它没有考虑批处理大小，因此一些工作人员可以比其他工作人员更晚完成处理，因为他们可能碰巧自行分配非常大的工作。

我如何更改算法，以便每个工作人员以也考虑批处理大小的方式自行分配批处理，以便平均而言，每个工作人员将自行分配相同的总工作量(来自不同批处理)？

Answer 1

//Using a queue to store the workers
//This way we can dequeue and reenqueue workers when they accept jobs
var _queue = new Queue<Worker>[numOfWorkers];

void Setup() {
  for (int i = 0;i<numOfWorkers -1;i++) {
      _queue.Enqueue(new Worker());
  }
}

//Assigns the job to the next worker in line and puts it at the end of queue
void AcceptJob(Job j) {
    var w = FindNextAvailableWorker();
    w.AssignNewJob(j);
    _queue.Enqueue(_queue.RemoveAt(_queue.PositionOf(w)));
}

//Finds the first free worker or returns the front of queue
Worker FindNextAvailableWorker() {
    var w = _queue.front();

    while (int i=0;i<_queue.length-1<i++) {
        if (_queue[i].isWorking==false){
            w = _queue[i];
            exit loop;
        }  
    }

    return w; 
}