我很想通过网络流方法来解决这个问题 . 希望有人在这里花时间帮助我为这个问题构建一个合适且合适的图表 . 构建的图形在求解最大流量时应该导致作业机器分配最大化给定数量的机器和作业调度的作业数量 .
给定m台机器和n个工作，约束m≤n . 使用网络流算法来解决分配，以最大化给定数量的机器的作业数量 .
每个作业 Ji 都有一个开始时间 Si 和结束时间 Fi . 所有机器都是相同的，一次最多可以完成一项工作 . 我们必须找到一项任务，以便我们可以安排最多的工作 .
方法我尝试过： - >作业和机器形成图中的节点 .
-
从源到所有Job节点的边 .
-
所有机器的边到终节点 .
-
每个作业节点的中间节点，其具有来自每个重叠作业节点的传入边缘 .
并坚持在这里如何进一步 .
我很想学习网络流程方法 .
P.S: I've worked out a solution by greedy approach. Asked the same question and was shot down with down votes without any explanation 因此，由于投票减少而重新询问上一个问题并没有得到任何关注 .
1 回答
这种方法怎么样？我认为你熟悉需求循环问题 .
考虑每个作业Ji是一个节点，如果Jj可以在Ji之后完成，那么它对Job Jj有优势，并且Ji和Jj不以任何方式重叠 . 现在考虑每台机器的节点，并将其命名为Mi.现在在这个模型中，每个Ji节点的需求为-1，每台机器的需求为0.还要添加一个节点t，需求为n，并将每个机器节点m连接到容量为n的节点 . 每个其他边缘的容量为1 .
现在通过需求流通来解决这个问题，我想你会得到答案 .