流水车间调度

流水车间调度（flow-shop scheduling）中，每个作业按相同机器路线加工，例如都先粗加工、再精加工。虽然路线相同，工时可以因作业不同而不同；安排作业次序会影响机器等待及最后完成时刻。经典两机模型假定作业在零时全部可用、工时确定、不可中断，机器间可以等待，且没有额外的顺序相关换线时间。^[1]

三件作业A、B、C在两台机器上的工时分别为 $(3, 7), (6, 2), (4, 5)$ 小时。按A、C、B加工时，机器一结束于三、七、十三；机器二上A在三至十、C在十至十五、B在十五至十七，总工期十七。

给定顺序的最早完成时间

对排列 $π_{1}, \dots, π_{n}$ ，记第一、二台机器累计完成时刻为 $A_{k}, B_{k}$ ，工时为 $a_{i}, b_{i}$ 。有 $\begin{matrix} A_{k} & = A_{k - 1} + a_{π_{k}}, \\ B_{k} & = max {A_{k}, B_{k - 1}} + b_{π_{k}}, \\ A_{0} & = B_{0} = 0. \end{matrix}$ 第二台机器既要等该作业在第一台完成，也要等自己上一作业完成；两项取最大后，才能加当前加工时长。这个递推给定顺序的最早排程：任意可行排程都不能早于这两种前提，按位置归纳即得下界，而递推本身又能达到。

Johnson顺序A,C,B：第一机0至3、3至7、7至13；第二机3至10、10至15、15至17 — 机器二开始工作前必须等第一件流入。最后的十七包含等待与加工，并非简单取两台机器工作量的较大值。

相邻交换与Johnson规则

两机模型总存在一个最优排列排程，即两台机器采用同一作业次序。取任意可行排程，按其第二台机器的作业次序重排第一台，令第一台从零时起无空闲地依次加工。原排程中，第二台第 $k$ 个作业开始之前，次序中的前 $k$ 个作业都已在第一台完成，故这些作业第一阶段工时之和不超过该原开始时刻。新排程中，第一台完成前 $k$ 个作业的时刻恰是这项工时和，因此保持第二台原来的加工时刻仍然可行，工期不增。对原最优排程作此修改，就得到最优排列排程。此处利用了全部作业零时可用、只有两台机器与无限中间等待空间。

在一个共同前缀后，若两作业 $i, j$ 紧邻，前缀在两机结束于 $T_{1}, T_{2}$ 。令 $S = a_{i} + a_{j} + b_{i} + b_{j}$ ，将前面的递推展开，二作业在第二机全部完成的时刻为 $\begin{matrix} C_{i j} & = max {T_{2} + b_{i} + b_{j}, \\ T_{1} + S - min (a_{j}, b_{i})}, \\ C_{j i} & = max {T_{2} + b_{i} + b_{j}, \\ T_{1} + S - min (a_{i}, b_{j})} . \end{matrix}$ 因此若 $min (a_{i}, b_{j}) \leq min (a_{j}, b_{i})$ ，将 $i$ 放在 $j$ 前面不会更差。第一机的二作业总加工时长不变，第二机的结束不延后，后续最早排程也不会被延后。

Johnson顺序把 $a_{i} \leq b_{i}$ 的作业放前组，按 $a_{i}$ 递增；其余放后组，按 $b_{i}$ 递减。前组内、后组内、前后两组之间，都满足上面的两两条件：分别利用前组的 $a_{i} \leq b_{i}$ 、后组的 $b_{i} < a_{i}$ 及各自排序。任意排列若与此顺序不同，总能交换一个逆序邻对而不增大工期；有限次交换后得到Johnson顺序，故它全局最优。并列时任意固定顺序即可，不必声称最优解唯一。

主例前组A、C按三、四排序，后组只有B，因此得A、C、B。还有一个直接证书：第二机总工时十四，最早任何作业流入需至少三小时，所以任何总工期不小于 $3 + 14 = 17$ ，本方案取等。

实现与独立核对

Python 3

def johnson_two_machine(processing):
    p = tuple(tuple(row) for row in processing)
    if any(len(row) != 2 for row in p):
        raise ValueError("two processing times per job required")
    if any(type(x) is not int or x <= 0 for row in p for x in row):
        raise ValueError("positive integer durations required")
    early = sorted((i for i,(a,b) in enumerate(p) if a <= b),
                   key=lambda i:(p[i][0],i))
    late = sorted((i for i,(a,b) in enumerate(p) if a > b),
                  key=lambda i:(-p[i][1],i))
    order, first, second, schedule = early+late, 0, 0, []
    for i in order:
        a,b = p[i]
        start1 = first; first += a
        start2 = max(first,second); second = start2+b
        schedule.append((i,start1,first,start2,second))
    return tuple(order), second, schedule

order, value, _ = johnson_two_machine([(3,7),(6,2),(4,5)])
print(order,value)
# (0, 2, 1) 17

排序时间为 $O (n \log n)$ ，一次扫描计算排程为 $O (n)$ ，空间为 $O (n)$ 。空作业清单返回零工期。程序明确针对正整数工时的两机经典模型；有释放时间、阻塞、不得等待或第三台机器时，交换论证的前提会改变。

变式。 保留A、B两件作业。A先时第二机结束为十二，B先时结束为十六，Johnson仍选A、B。若要最小化平均完成时间而非最后完成时间，目标已经不同，不能沿用上述最优性结论。

参考文献

↑ Ray Butterworth，Machine Scheduling, 1.8 Serial Machines (Flowshops)，§1.8.1—1.8.3，两机排列调度、相邻交换及Johnson模型。

[1] Ray Butterworth，Machine Scheduling, 1.8 Serial Machines (Flowshops)，§1.8.1—1.8.3，两机排列调度、相邻交换及Johnson模型。

[1]