pta求解流水作业调度问题

### Johnson 法则解析

对于两台机器的流水线作业调度问题，Johnson法则提供了一种有效方法来最小化总完成时间。该法则的核心在于对所有作业按照特定条件进行排序[^1]。

具体来说：

- 如果某个作业在第一台机器上的加工时间短于或等于第二台，则将其安排到当前已知最早可用位置；
- 反之，如果某作业在第二台机器上所需的时间更少，则应尽可能推迟此任务至最后执行；

通过这种方式可以构建最优序列从而减少整个系统的完工时刻。

#### PTA 流水作业调度实现示例 (Python)

下面给出基于上述原则的一个简单 Python 实现版本:

def johnson_algorithm(jobs):
    n = len(jobs)
    
    order = [-1]*n  # 存储最终的任务顺序
    pos = [0, n-1]  # 分别指向待填入最前后的索引
    
    while jobs:
        min_job = None
        
        for job in jobs:
            if not min_job or min(job[0],job[1]) < min(min_job[0],min_job[1]):
                min_job = job
                
        if min_job[0]<=min_job[1]:
            index = 0
        else:
            index = 1
            
        i = jobs.index(min_job)
        
        order[pos[index]] = jobs.pop(i)[2]
        pos[index] -= (-1)**index*(pos[index]!=0) 

    return order


if __name__ == "__main__":
    tasks = [(3,7,'a'),(8,4,'b'),(5,9,'c')]  # 每个元组代表一项工作，在两个阶段分别所需的处理时间和名称
    result = johnson_algorithm(tasks.copy())
    print("Optimal sequence:",result)

在这个例子中，`tasks` 列表包含了三个工作任务及其各自在两台不同设备上的预计耗时。程序会输出这些工作的最佳排列方式以便达到整体效率最大化的目的。