我有一个任务/工作调度问题,希望找到高效的算法来解决它。
假设有一些工人,每个工人能够完成不同的一组任务/工作。以下示例可能会让问题更加清晰明了:
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
因为这里没有等待时间。
现在假设我知道工人任务矩阵(哪个工人可以做哪些任务)。任务一个接一个地到来,但是不知道接下来会是什么任务。我被要求设计一个调度程序,自动为每个任务找到空闲的工人。当最后所有任务完成时,会有最小的等待时间。
因此,我需要一个算法来实现这个调度程序。如果已经存在完美的解决方案,我就不想重复造轮子。请问有人可以帮忙吗?
谢谢。