当前位置：首页 > news >正文

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

news 来源：原创 2025/8/28 11:22:24

前言：写这个题目的时候感觉就是说任务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+dnowa = 0
nowb = 0
for i in range(0,n):idx = e[i][1]x,y = a[idx],b[idx]nowa += xnowb = max(nowa,nowb)+yprint(nowb)

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

1. 算法背景

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

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

2. 算法原理

基本思想

任务分组：根据任务在两个阶段的时间关系，将任务分为两组：
- 组1：阶段1时间 ≤ 阶段2时间（记为 $A_i \leq 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算法适用于以下条件：

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

典型场景：

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

5. 复杂度分析

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

总结

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