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

工作执行最优顺序?

  •  
  •   ballshapesdsd · 2019-01-21 11:50:48 +08:00 · 2915 次点击
    这是一个创建于 2133 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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