首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Coding
V2EX  ›  算法

工作执行最优顺序?

  •  
  •   ballshapesdsd · 325 天前 · 1019 次点击
    这是一个创建于 325 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    13 回复  |  直到 2019-01-21 17:41:52 +08:00
        1
    xiaohuamao   325 天前
    稳如分布式
        2
    ballshapesdsd   325 天前
    @xiaohuamao #1 就是分布式编译
        3
    Fulcrum   325 天前 via Android
    找本管理运筹学 排序与统筹方法 随便看下
        4
    fyyz   325 天前 via Android
    APS 排程软件了解一下
        5
    takato   325 天前
    最短 Hamilton 路径?
        6
    ballshapesdsd   325 天前
    @takato #5 好像不是吧。。。
        7
    alfchin   325 天前 via Android
    我觉得楼主需要修运筹学。。。然后整理一个自己的算法
        8
    quinoa42   325 天前
    一个简单的贪心思路就是,先画出有向图,然后倒推或者顺推每个节点到最终目标还需要的时间
    然后决定顺序的每一轮就是选择执行当前预计耗费时间最久的可执行节点
        9
    quinoa42   325 天前
    @quinoa42
    第二句有点没太说清楚,我的意思是选择当前预计到最终目标需要的时间最久的可执行且未执行节点
        10
    ballshapesdsd   325 天前
    @quinoa42 #9 没太懂,能不能详细说说,或者给我发一个能参考的链接
        12
    ballshapesdsd   325 天前
    @quinoa42 #11 谢谢了
        13
    behanga   324 天前
    实际情况是最先执行 BOSS 安排的工作,其他都靠边
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4116 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 22ms · UTC 09:16 · PVG 17:16 · LAX 01:16 · JFK 04:16
    ♥ Do have faith in what you're doing.