双机调度(Johnson 法则)

What · 是什么

双机流水作业调度（two-machine flow shop scheduling）：n 个作业都需先在第一台机器加工 a_i 分钟、再在第二台机器加工 b_i 分钟（加工顺序两机一致），求使总完工时间（makespan）最小的作业排列。Johnson 法则：若 min(a_i, b_i) < min(a_j, b_j)，则 i 应排在 j 之前。实现：把所有作业按 min(a_i,b_i) 排序；a_i < b_i 的作业放前面（按 a 升序），其余放后面（按 b 降序）。正确性由相邻交换证明（交换相邻两作业，空闲时间不增 ⟺ min(a_i,b_{i+1}) ≤ min(b_i,a_{i+1})）。复杂度 O(n log n)。当机器数≥3 时问题变为 NP-hard。

Why · 为什么

How · 实现

伪代码

# Johnson 法则
for 每个作业: 记 (a, b, id)
sort 作业 by min(a,b)
A = []  # 收集 a < b 的作业 (放前面)
B = []  # 收集 a >= b 的作业 (放后面)
for job in sorted:
    if job.a < job.b: A.append(job)
    else: B.append(job)
order = A + reversed(B)   # B 部分反转
# 计算完工时间:
t1 = t2 = 0
for job in order:
    t1 += job.a
    t2 = max(t2, t1) + job.b
makespan = t2

Python 实现

def johnson(jobs):
    """Johnson 法则求双机调度最优顺序.
    jobs: list of (a, b, id). 返回最优顺序的 id 列表.
    """
    sorted_by_min = sorted(range(len(jobs)), key=lambda i: min(jobs[i][0], jobs[i][1]))
    A, B = [], []
    for i in sorted_by_min:
        a, b, _ = jobs[i]
        (A if a < b else B).append(i)
    order = A + list(reversed(B))
    return order


def makespan(jobs, order):
    """给定顺序的双机完工时间"""
    t1 = t2 = 0
    for i in order:
        a, b, _ = jobs[i]
        t1 += a
        t2 = max(t2, t1) + b
    return t2


if __name__ == "__main__":
    import itertools, random
    random.seed(0)

    def brute(jobs):
        return min(itertools.permutations(range(len(jobs))),
                   key=lambda o: makespan(jobs, o))

    # 经典样例 (来自 CP-Alg 中文题解): 应使完工时间最小
    jobs1 = [(3, 2, 0), (5, 1, 1), (2, 4, 2), (1, 3, 3)]
    o = johnson(jobs1)
    assert makespan(jobs1, o) == makespan(jobs1, brute(jobs1))

    # 随机对拍
    for _ in range(300):
        n = random.randrange(1, 8)
        js = [(random.randrange(1, 8), random.randrange(1, 8), i) for i in range(n)]
        o = johnson(js)
        assert makespan(js, o) == makespan(js, brute(js)), js

    # 单作业边界
    assert johnson([(5, 3, 7)]) == [0]

    print("schedule-two-machines tests passed")

易错点

• a==b 时归入哪组都行，但实现要一致（通常 a<b 一组，a>=b 另一组再反转）
• B 组必须反转（按 b 降序）才能匹配比较器
• 完工时间计算用 t2=max(t2,t1)+b，漏掉 max 会算错空闲
• 三机及以上不能直接套 Johnson
• 比较器 min(a_i,b_{i+1}) ≤ min(b_i,a_{i+1}) 的等价分组别记反

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/schedules/schedule_two_machines.html
• Wikipedia✓ https://en.wikipedia.org/wiki/Job_shop_scheduling