作业车间调度

作业车间调度（job-shop scheduling）为多件作业的工序安排机器与时间。每道工序要在指定机器上连续完成，同一作业的工序有规定顺序；不同作业可以有不同机器路线。经典目标是使全部作业尽早完成，同时每台机器至多加工一道工序。

两件作业的工艺为：A先在机器一加工三小时，再到机器二加工两小时；B先在机器二加工四小时，再到机器一加工一小时。机器在零时都可使用，不考虑换线、运输和故障。若强迫A和B完全串行，要十小时；允许不同机器并行后，A第一道与B第一道可以同时开始。

工艺边与机器二选一

记工序 $o$ 的开始为 $s_o\ge 0$、时长为 $p_o>0$。同一作业的相邻工序 $o\to q$ 满足 $s_q\ge s_o+p_o$。若 $o,q$ 使用同一机器，必须满足二者之一： $$s_q\ge s_o+p_o\text{或}{s}_o\ge s_q+p_q.$$ 它表达的是完整不重叠，而非只要求开始时间不同。给每台机器确定加工顺序后，二选一约束变成有向边，工艺边保持不变。

六小时排程及机器下界

安排A第一道零至三，B第一道零至四；然后A第二道四至六，B第二道四至五。机器一在三至四可空闲，机器二从零至六连续加工。A须等待机器二，这段等待不是在加工。

每条横行代表一台机器，块长代表工时；上下两行允许并行。同色块的含义由工序标签确定。

机器二必须加工B的四小时与A的两小时，总工作量六，所以任何排程总工期至少为六。上述方案达到这个下界，故为全局最优。单件作业最长工艺链只有五小时，并没有识别机器二的共同瓶颈。

固定顺序后的最长路

若合成有向图出现环，将环上的先后不等式相加，会得到 $0\ge \sum _{o\in \text{环}}{p}_o>0$，矛盾，因此该机器顺序不可行。若无环，可按拓扑序计算 $$s_o=max(0,\underset{q\to o}{max}(s_q+p_q)).$$ 每道工序在所有前驱结束后立即开始，得到合法安排。任何其他合法方案在第一层不能更早，逐层归纳也不能比这些时刻更早，所以它是给定机器顺序下的最早排程。

下面把工序标为 (作业编号, 工序编号)，输入每件作业的机器与工时、每台机器的完整工序顺序，输出总工期与各工序开始时间。该函数只评价指定机器顺序，不能把一次评价当成搜索全部顺序。

Python 3

from collections import defaultdict, deque

def fixed_jobshop(jobs, machine_order):
    jobs = tuple(tuple(job) for job in jobs)
    duration, machine = {}, {}
    for j, job in enumerate(jobs):
        for k, (m, p) in enumerate(job):
            if type(p) is not int or p <= 0:
                raise ValueError("positive integer processing times required")
            duration[j,k], machine[j,k] = p, m
    edges = set()
    for j, job in enumerate(jobs):
        edges.update(((j,k-1),(j,k)) for k in range(1,len(job)))
    expected = defaultdict(set)
    for o,m in machine.items():
        expected[m].add(o)
    if set(machine_order) != set(expected):
        raise ValueError("one complete order per machine required")
    for m, order in machine_order.items():
        order = tuple(order)
        if len(set(order)) != len(order) or set(order) != expected[m]:
            raise ValueError("each operation must appear once on its machine")
        edges.update(zip(order,order[1:]))
    successor = {o:[] for o in duration}
    indegree = dict.fromkeys(duration,0)
    for a,b in edges:
        successor[a].append(b); indegree[b] += 1
    queue = deque(o for o in duration if indegree[o] == 0)
    start, seen = dict.fromkeys(duration,0), 0
    while queue:
        a = queue.popleft(); seen += 1
        for b in successor[a]:
            start[b] = max(start[b],start[a]+duration[a])
            indegree[b] -= 1
            if indegree[b] == 0:
                queue.append(b)
    if seen != len(duration):
        raise ValueError("cyclic machine and job orders")
    return max((start[o]+duration[o] for o in duration),default=0), start

jobs = [[("M1",3),("M2",2)], [("M2",4),("M1",1)]]
order = {"M1":[(0,0),(1,1)], "M2":[(1,0),(0,1)]}
value, start = fixed_jobshop(jobs,order)
print(value, sorted(start.items()))
# 6 [((0, 0), 0), ((0, 1), 4), ((1, 0), 0), ((1, 1), 4)]

拓扑扫描中，一个工序出队时其全部前驱已处理，故当前值已是最长前驱路径；有剩余未出队工序即说明存在有向环。工序数 $N$、边数 $E$ 时，构图和计算的期望时间、空间均为 $O(N+E)$（采用散列表）。困难在于选择机器顺序，不在于这个固定顺序后的最长路计算。

变式。 若B改为也先机器一四小时、再机器二一小时，两作业共用相同机器路线。A先时机器一完成时刻三、七，机器二A在三至五、B在七至八，总工期八；B先时则完成九。因此最优为八。两机共同路线的特殊结构可进一步用流水车间调度的Johnson规则处理；一般作业车间不能直接套用该规则。