algorithm - 具有多个分支的等待队列

Question

我目前正在做一个项目，我正在寻找一种可以解决这种情况的技术:

有人在房间里等着参加多项测试中的一项。可以为每个人分配多个测试。每项考试可在给定时间在一个或多个地点进行，但一次只能有一个人在给定地点参加考试。

只是随机分配人员进行测试并最终全部完成是相对简单的，但是我可以使用什么样的系统来使人们等待的时间相对均等？如果我只是随机分配他们，一个只需要参加其中一项测试的人可能会落后于必须参加 5 项测试的人。

我考虑过让测试次数较少的人先参加，但我还没有测试过，看来这仍然不公平。为了增加复杂性，我添加了一个允许更改优先级的功能。

需要说明的是，这不是家庭作业。这个项目还处于逻辑开发阶段，所以我还没有真正开始编程来比较不同的技术。我想到的最接近的事情是创建一个有点像线程池的系统，但我还没有找到任何详细描述线程池背后技术的东西，而且似乎需要很多时间的开销，如果我直接使用线程池，仍然会遇到问题。我也研究了 C# Queue 类，但我还没有想出一种方法来扩展它的功能。

有人有什么想法或建议吗？

Answer 1

C#(和大多数其他语言)有一个 concurrent priority queue你可以使用。将应试者放在队列中，并在有空房间时移除一个(并为其分配一个测试)；如果应试者还有更多考试要参加，则将其放回队列中。

平衡执行时间的一种方法是为“应试者”分配随机优先级，例如

testTaker.serPriority(random.Next(CONSTANT * testTaker.numberOfRemainingTests))

然后每当测试者完成测试时重置测试者的优先级。这将有利于将测试分配给要参加更多测试的应试者，而随机元素将接近公平。 CONSTANT 应该大于应试者的数量以确保足够的随机性。