2条的流水作业调度问题的贪心做法。
题目:有n个作业要在两台机器M1和M2组成的流水线上 完成加工。每个作业i都必须先花时间ai在Mi上加 工，然后花时间bi在M2上加工 确定n个作业的加工顺序，使得从作业1在机器M1 上加工开始到作业n在机器M2上加工为止所用的 总时间最短
做法：
(1)把所有作业按M1,M2的时间分为两组，a[i]≤b[i]对应组N1,a[i]>b[i]对应组N2N2。
(2)将N1的作业按a[i]递增排序，N2的作业按b[i]递减排序。
(3)按顺序先执行N1的作业，再执行N2的作业，得到的就是耗时最少的最优调度方案。
正确性:
t1=a1+a2+b1+b2-min(a2,b1)(先执行1，后执行2)
t2=a1+a2+b1+b2-min(a1,b2)(先执行2，后执行1)
所以当min(a2,b1)<min(a1,b2)时，先1后2，否则先2后1。
做法可以保证只要min(a2,b1)<min(a1,b2)就先1后2.
分类讨论
1.N1内部min(a2,b1)=a2,min(a1,b2)=a1,a1<a2.所以1该在2前面。
2.N1与N2中a1<=b1,b2<=a2,所以min(a2,b1)>min(a1,b2),所以1该在2前面
3.N2内部，a1>=b1,a2>=b2,b1>=b2,所以min(a2,b1)>min(a1,b2),所以1该在2面前。
标签：法则,Johnson,min,作业,a1,a2,b1,b2 From： https://www.cnblogs.com/storms11/p/18279692