Johnson算法——两阶段流水线调度的最优解法

前言：写这个题目的时候感觉就是说任务a的时候是一定需要的，无法避免，怎么才能节约时间呢，就是进行任务a时候也进行任务b

第一个进行的任务a肯定时间越短越好，因为这样b的等待时间越短
最后一个进行的任务b的时候越短越好，因为这样结束时间越早

题目地址

import os
import sys
from functools import cmp_to_key
# 请在此输入您的代码

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

c = []
d = []
for i in range(n):
    if a[i]-b[i]<=0:
        c.append((a[i]-b[i],i))
    else:
        d.append((a[i]-b[i],i))


c.sort(key=lambda x:a[x[1]])
d.sort(key=lambda x:-b[x[1]])

e = c+d

nowa = 0
nowb = 0
for i in range(0,n):
    idx = e[i][1]
    x,y = a[idx],b[idx]
    nowa += x
    nowb = max(nowa,nowb)+y

print(nowb)

专题：Johnson算法——两阶段流水线调度的最优解法

1. 算法背景

在工业生产、计算机任务调度等领域，流水线调度问题广泛存在。典型的场景是多个任务需要依次经过两个不同的处理阶段（如加工和装配），每个任务在每个阶段的处理时间不同。如何安排任务顺序，使得所有任务的总完成时间最短？这一问题被称为 两阶段流水线调度问题。

Johnson算法 由 S. M. Johnson 于1954年提出，是解决此类问题的经典方法。其核心思想是通过任务分组与排序策略，最小化两个阶段的空闲等待时间，从而优化整体效率。

2. 算法原理

基本思想

• 任务分组：根据任务在两个阶段的时间关系，将任务分为两组：

  • 组1：阶段1时间 ≤ 阶段2时间（记为 $A_i\le B_i$）。
  • 组2：阶段1时间 > 阶段2时间（记为 $A_i>B_i$）。

• 排序规则：

  • 组1任务按阶段1时间升序排列（优先处理阶段1耗时短的任务）。
  • 组2任务按阶段2时间降序排列（优先处理阶段2耗时长但阶段1耗时更长的任务）。

• 合并顺序：先处理组1任务，再处理组2任务。

直观解释

• 组1任务：阶段1时间较短，尽早处理可以减少阶段2的等待时间。
• 组2任务：阶段2时间较长，但阶段1更耗时。按阶段2时间降序排列，可让阶段2的“长尾任务”尽早完成，避免后续任务的累积延迟。

3. 应用场景

Johnson算法适用于以下条件：

1. 两阶段流水线：每个任务必须依次经过两个阶段处理。
2. 固定处理时间：每个任务在两个阶段的处理时间已知且不变。
3. 无抢占：任务一旦开始处理，不能被中断。

典型场景：

• 工厂生产线（加工+检测）。
• 密码破译与传输（如用户问题中的场景）。
• 计算机任务调度（编译+测试）。

5. 复杂度分析

• 时间复杂度：O(N log N)，主要由排序操作决定。
• 空间复杂度：O(N)，用于存储分组后的任务列表。

总结

Johnson算法通过巧妙的分类和排序策略，在两阶段流水线调度中实现了时间最优。其核心在于平衡两个阶段的处理时间，减少空闲等待。掌握该算法不仅有助于解决竞赛题目，更能为实际工程中的调度问题提供理论指导。