如何获得一系列工作的最短时间？

Question

我正在处理一个进程管理问题。假设有一系列需要按顺序完成的工作，每个项目都必须在进行工作2之前先完成工作1。请看以下示例：

work1   8   6   2   4
work2   3   1   3   12

我们需要用8小时完成第一列的工作1，还需要3个小时，但如果我们先完成第4列，在接下来的12小时内，我们有时间做第3列和第2列。最好将这一列放在第一步。

我的直觉是，工作2是瓶颈，也就是说，我们至少需要使用3+1+3+12=20个小时来完成这笔交易。也就是说，始终让工作2的流程尽可能忙碌。我的算法：反向排序工作2并排序工作1，因为我们希望保持工作2流程尽可能忙碌。

这是我的算法，看起来很有效:

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个任务？（任务1 -> 任务2 -> 任务3 -> ...-> 任务n）

- Pythoner

---

你只有两个处理器吗？而且处理器1只能处理work1任务，处理器2只能处理work2任务吗？ - slider

@slider 是的，让我们这样假设。 - Pythoner

Answer 1

我在下面放了一个例子，但我认为通过网络搜索可以找到你实际想要的答案。

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

由于第一篇参考文献谈到了如何处理超过两台机器的情况，我推测在这种情况下没有其他更令人满意的解决方案。

假设你有两种类型的工作。其中一种需要A进行两个步骤，然后B进行三个步骤。另一种需要A进行三个步骤，然后B进行两个步骤。似乎有效的一种模式是交替进行这两种工作。A忙于进行两个步骤，B空闲。然后B在三个步骤中完成该任务，同时A接管另一种工作。在此期间结束时，A将需要三个步骤才能完成的工作交给B，而A则接手第一种工作。

因此，两者都在不断地忙碌，交替进行每个工作的两个或三个步骤。

我认为这不会从您的预排序算法中获得。

一种通用（但计算成本非常高）的算法是使用A*搜索，其中启发式表明从特定状态完成所需的时间是max（A连续忙碌时所需的时间，B连续忙碌时所需的时间）。有大量关于调度问题的文献，可惜我没有记在脑子里 - 我只知道它的存在，并且大多数非平凡问题都被证明是NP完全的。

- mcdowella