求解流水作业调度问题pta

### 流水作业调度问题 PTA 解题思路

对于流水作业调度问题，在特定条件下可以采用多项式时间算法求解。当机器数量为2时，存在有效的多项式时间算法来解决问题[^1]。

#### Johnson法则的应用
Johnson法则提供了一种有效的方法用于两台机器上的流水线调度问题。该方法通过一系列规则决定任务顺序以最小化总完工时间。具体来说：

- 如果所有任务的第一阶段加工时间小于第二阶段，则这些任务应尽可能早地安排；
- 反之如果某任务的第二阶段加工时间更短，则应该推迟此任务直到最后才考虑加入序列；

基于上述原则构建的任务排列能够确保获得最优解。

#### Python代码实现

下面给出一段Python程序实现了针对两个工作中心的标准约翰逊算法:

def johnson_algorithm(jobs):
    n = len(jobs)
    
    sequence = []
    left_jobs = set(range(n))
    
    while left_jobs:
        min_time, job_index = float('inf'), None
        
        for i in left_jobs:
            if jobs[i][0] < jobs[i][1]:
                time_to_compare = jobs[i][0]
            else:
                time_to_compare = jobs[i][1]

            if time_to_compare < min_time:
                min_time = time_to_compare
                job_index = i
                
        # Add the selected job to result list based on its processing times.
        if jobs[job_index][0] <= jobs[job_index][1]:
            sequence.insert(0, job_index + 1)  # Insert at front when t1<=t2
        else:
            sequence.append(job_index + 1)     # Append at end otherwise
            
        left_jobs.remove(job_index)

    return sequence


if __name__ == "__main__":
    tasks = [(3, 7), (8, 2), (5, 6)]  # Example input as tuples of two machine's process times per task
    
    optimal_sequence = johnson_algorithm(tasks)
    print(f"The optimal order is {optimal_sequence}")

这段代码定义了一个`johnson_algorithm()`函数接收一个列表作为参数，其中每个元素都是表示单个工作项在两台设备上所需的时间元组。它返回的是按照最佳顺序排列后的索引数组。