任务/作业调度问题
我有一个任务/作业调度问题，我想找到更有效的算法来解决它。
假设有一些工人。每个工人都能够完成一组不同的任务/工作。下面的例子可以清楚地说明：
Worker A (can do): T2, T3
Worker B : T1, T3, T4
Worker C : T3, T5
现在我们有一个必须完成的任务列表。例如，列表类似于： T1、T3、T5
有一些限制：
- 每个任务必须由一个工作人员执行
- 多个任务可以同时执行
- 但一个工作人员只能同时执行一项任务。 （他/她在完成任务之前才可用）
对于上面的例子，我们可能有这样的时间表：
T1 --> Worker B
T3 --> Worker C T5 --> Worker C
正如您可能注意到的，上面的时间表并不是最佳的。因为T5必须等待工人C完成T3。以下解决方案更好：
T1 --> Worker B
T3 --> Worker A
T5 --> Worker C
因为无需等待。
现在假设我知道工人任务矩阵（哪些工人可以执行哪些任务）。 任务会一个接一个地到来，但不知道会是什么。我被要求设计一个调度程序，自动为每个即将到来的任务找到一个空闲的工作人员。当所有任务最终完成时，等待时间最短。
所以我需要一个用于这个调度程序的算法。如果完美的轮子已经存在，我不想重新发明轮子。有人可以帮忙吗？
谢谢。
I have a task/job scheduling problem and I would like to find preferably efficient algorithms to solve it.
Let's say there are some workers. Every worker is able to do a different set of tasks/jobs. The following example may make it clear:
Worker A (can do): T2, T3
Worker B : T1, T3, T4
Worker C : T3, T5
Now we have a list of tasks which must be done. For example, the list is something like: T1, T3, T5
There's some constraints:
- Each task must be taken by one worker
- Several tasks can be taken concurrently
- But a worker can do only one task at the same time. (He/she is not available until finish the task)
For the above example, we may have a schedule like this:
T1 --> Worker B
T3 --> Worker C T5 --> Worker C
As you may noticed, the above schedule is not optimal. Because T5 has to wait worker C to finish T3. The following solution is better:
T1 --> Worker B
T3 --> Worker A
T5 --> Worker C
Because there's no wait.
Now suppose that I know the the worker-tasks matrix (what worker can do what tasks). The tasks will come one by one, but don't know what it will be. I am asked to design a scheduler that automatically find an idle worker for every coming task. And when finally all the tasks are done, there's a minimum waiting time.
So I need an algorithm for this scheduler. I don't want to reinvent the wheel if the perfect wheel already exists. Can any one help?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对预先未知但“随时”输入的输入进行操作的算法称为在线算法< /a>.当然，它们只是次优的。它们是通过比最佳算法差不超过一个常数因子来衡量的（例如，如果最佳解决方案（不是在线的，即预先有整个输入）需要 X 步，那么您的在线解决方案应该不采取超过 k*X 步，当然 k 越小越好）。
在您的情况下，要求不明确 - “最短等待时间”与什么相比？
一个可能对您有帮助的想法是选择一个具有最小任务列表的可用工作人员，为未来的任务保留更多“多样化”的工作人员。
Algorithms operating on input that is not known upfront but is coming in "as you go" are called on-line algorithms. They are only sub-optimal, naturally. They are measured by being worse than the optimal algorithm not more than by a constant factor (e.g. if the best solution (which is not on-line, i.e. has the whole input upfront) takes X steps, your on-line one should take not more than k*X steps, the smaller the k the better of course).
In your case the requirement is not clear - "minimum waiting time" compared to what?
One idea that may help you is to pick up an available worker with the smallest task list, saving the more "diverse" workers for future tasks.
听起来您正在寻找“Bin Packing”算法 -
http://en.wikipedia.org/ wiki/Bin_packing
一般装箱问题与您所说的非常相似，是 NP 困难的，因此如果您的输入大小非常小，您可能会忘记最佳解决方案。
你能找到的是一个保证不会与最佳解决方案相差太远的解决方案，通常是我的一些因素。维基百科的这篇文章是一个很好的起点。
It sounds like you're looking for a "Bin Packing" algorithm -
http://en.wikipedia.org/wiki/Bin_packing
The general bin packing problem, very similar to what you phrased, is NP-Hard so you can forget about an optimal solution if your input size is more than trivial.
What you can find is a solution that is guaranteed not to be too far from the optimal solution, usually my some factor. That wikipedia article is a good place to start.