问题: 给定有 n 个工作需要执行,每个工作需要耗费不同的时间,并且不同的工作之间有依赖关系(使用一个有向图表示),同时可以执行的工作数是给定的常数 m,那么如何安排工作顺序使得总时间最小?
感觉是一个经典的问题,有没有一个成熟的算法呢?
1
xiaohuamao 2019-01-21 11:58:26 +08:00
稳如分布式
|
2
ballshapesdsd OP @xiaohuamao #1 就是分布式编译
|
3
Fulcrum 2019-01-21 12:12:51 +08:00 via Android
找本管理运筹学 排序与统筹方法 随便看下
|
4
fyyz 2019-01-21 12:14:36 +08:00 via Android
APS 排程软件了解一下
|
5
takato 2019-01-21 12:26:28 +08:00
最短 Hamilton 路径?
|
6
ballshapesdsd OP @takato #5 好像不是吧。。。
|
7
alfchin 2019-01-21 16:04:45 +08:00 via Android
我觉得楼主需要修运筹学。。。然后整理一个自己的算法
|
8
quinoa42 2019-01-21 16:12:08 +08:00
一个简单的贪心思路就是,先画出有向图,然后倒推或者顺推每个节点到最终目标还需要的时间
然后决定顺序的每一轮就是选择执行当前预计耗费时间最久的可执行节点 |
10
ballshapesdsd OP @quinoa42 #9 没太懂,能不能详细说说,或者给我发一个能参考的链接
|
11
quinoa42 2019-01-21 16:29:13 +08:00
|
12
ballshapesdsd OP @quinoa42 #11 谢谢了
|
13
behanga 2019-01-21 17:41:52 +08:00
实际情况是最先执行 BOSS 安排的工作,其他都靠边
|