工作执行最优顺序？

2019-01-21 11:50:48 +08:00
 ballshapesdsd

问题： 给定有 n 个工作需要执行，每个工作需要耗费不同的时间，并且不同的工作之间有依赖关系（使用一个有向图表示），同时可以执行的工作数是给定的常数 m，那么如何安排工作顺序使得总时间最小？

感觉是一个经典的问题，有没有一个成熟的算法呢？

2800 次点击
所在节点    算法
13 条回复
xiaohuamao
2019-01-21 11:58:26 +08:00
稳如分布式
ballshapesdsd
2019-01-21 12:06:05 +08:00
@xiaohuamao #1 就是分布式编译
Fulcrum
2019-01-21 12:12:51 +08:00
找本管理运筹学 排序与统筹方法 随便看下
fyyz
2019-01-21 12:14:36 +08:00
APS 排程软件了解一下
takato
2019-01-21 12:26:28 +08:00
最短 Hamilton 路径？
ballshapesdsd
2019-01-21 15:54:54 +08:00
@takato #5 好像不是吧。。。
alfchin
2019-01-21 16:04:45 +08:00
我觉得楼主需要修运筹学。。。然后整理一个自己的算法
quinoa42
2019-01-21 16:12:08 +08:00
一个简单的贪心思路就是，先画出有向图，然后倒推或者顺推每个节点到最终目标还需要的时间
然后决定顺序的每一轮就是选择执行当前预计耗费时间最久的可执行节点
quinoa42
2019-01-21 16:13:19 +08:00
@quinoa42
第二句有点没太说清楚，我的意思是选择当前预计到最终目标需要的时间最久的可执行且未执行节点
ballshapesdsd
2019-01-21 16:20:19 +08:00
@quinoa42 #9 没太懂，能不能详细说说，或者给我发一个能参考的链接
quinoa42
2019-01-21 16:29:13 +08:00
@ballshapesdsd https://en.wikipedia.org/wiki/Critical_path_method
ballshapesdsd
2019-01-21 16:31:08 +08:00
@quinoa42 #11 谢谢了
behanga
2019-01-21 17:41:52 +08:00
实际情况是最先执行 BOSS 安排的工作,其他都靠边

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/529055

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX