algorithm - 如何获得一个作品序列的最短时间？

Question

我正在针对流程管理问题进行编程。假设有一系列工作需要一个接一个地完成，您必须在每个项目的工作 2 之前完成工作 1。使用以下示例:

work1   8   6   2   4
work2   3   1   3   12

我们需要用 8 小时来完成第一列的工作 1，然后再用 3 小时，但是如果我们先完成第 4 列，在接下来的 12 小时内，我们有一些时间来完成第 3 列和第 2 列。它最好将此列放在第一步。

我的直觉，work2是瓶颈，也就是说，我们至少需要用到3+1+3+12=20才能完成这笔交易。也就是说，尽可能让work2进程一直处于working状态。我的算法:反向排序 work2 和排序 work1，因为我们想让 work2 进程尽可能忙。

这是我的算法，看起来可行:

class Solution(object):
    def least_time(self, intervals):
        intervals.sort(key = lambda x: (-x[1], x[0]))
        time1 = time2 = 0 
        print intervals
        for inv in intervals:
            item1, item2 = inv
            if time1 + item1 <= time2 + item2:
                time1 += item1 
                time2 += item2
            else:
                time1 += item1
                time2 = time1 + item2

        return time2


if __name__ == "__main__":
    s = Solution()
    invs = [(8,3), (6,1), (2,3), (4,12)]
    print(s.least_time(invs))




>>>[(4, 12), (2, 3), (8, 3), (6, 1)]
>>>21

能够在21小时内完成以上顺序的事情。

我的问题是:1.我的算法正确吗？2.如何将这个问题扩展到n个作品？ (work1 -> work2 -> work3 ->...->workn)

Answer 1

我在下面举了一个例子，但我认为网络搜索可以找到您真正想要的答案。

对于两台机器的情况，问题可以用约翰逊规则(https://en.wikipedia.org/wiki/Job_shop_scheduling#Jobs_consisting_of_multiple_operations)解决(https://en.wikipedia.org/wiki/Johnson%27s_rule)。

由于第一个引用文献谈到了使用 Johnson 规则来处理多于两台机器的情况，我认为对于这种情况没有其他更令人满意的解决方案。

假设您兼有两种工作。一个人走 A 两步，然后 B 走三步。另一个让 A 走三步，然后 B 走两步。一种似乎有效的模式是交替执行这两项工作。 A忙了两步，B空闲了。然后 B 在该工作上工作三个步骤，而 A 则从事另一种工作。在那段时间结束时，A 交给 B 一份工作，B 分三步完成，而 A 接手第一种工作。

因此，两者都一直忙于在每个工作的两步和三步之间交替。

我认为这不会来自您的预排序算法。

一种通用的(但计算量很大)算法是使用带有启发式的 A* 搜索，该算法表示从特定状态完成的时间为最大值(如果 A 持续忙碌所花费的时间，如果 B 所花费的时间一直忙)。有大量关于调度问题的文献，不幸的是我脑子里没有——我只知道它存在，而且大多数不平凡的问题结果都是 NP 完全问题。