流水线调度问题
流水线作业调度问题的初等分析

1 问题的描述

有个作业需要在2台机器和组成的流水线上完成加工。每个作业都必须先在 M1 上加工，然后在 M2 上加工。 M1 和 M2 加工作业 i 所需的时间分别记作 ai 和 bi ，每台机器同一时间最多只能执行一个作业。
请确定这 n 个作业的最优加工顺序（即1~n 的一个全排列），使得从第一个作业在机器 M1 上开始加工，到最后一个作业在机器 M2 上加工完成所需的时间最少。

2 解析

• 把全部 和 放到一个序列，升序排列；
• 如果序列中下一个数是 且 还没调度，那么在还没使用的最左位置调度 ；如果序列中下一个数是 且 还没调度，那么在还没使用的最右位置调度 ；如果已经调度 ，则转到该序列的下一个数

3 例

3.1 例1

3.2 例2