转自:https://blog.csdn.net/hlk_1135/article/details/53872064

n个作业{0,1,2,…,n}在2台机器上M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，后在M2上加工。在两台机器上加工的时间分别为ai和bi。  目标：确定这n个作业的加工顺序，使得从第一台作业开始加工，到最后一个作业完成加工所需要的时间最少。  题目类型：动态规划  算法描述：  流水作业调度问题的Johnson算法：  （1） 令   （2）将N1 中作业依t[i,1]的非减序排列；将N2中作业依t[i,2]的非增序排列；  问题分析：  当输入的作业数目为6时：  每个作业在M1上执行的时间为t[i,1]，在M2上执行的时间为t[i,2]，输入的数据为：

算法按照先执行的作业,保证M2机器上没有等待，本例中作业1、4、5满足条件，被选择先执行。当选择第一个作业时，算法选择让M2第一次等待时间最少的那个，本例中作业1的t[i,1]最小，这样就可以让M2第一次等待最少。所以在的集合中,t[i,1]越小越靠前执行。  当执行的作业时，要保证最后一个作业在M2上的执行时间最短，所以作业2，6，3是按照t[i,2]非增序排列，保证了作业3的t[i,2]是它们三个当中最小的一个。  算法在计算执行时间的过程如下图所示： 

作业执行次序为：1，4，5，2，6，3

1)执行1时：M1上运行2个时间后交给M2，这时M2空闲了2个时间并开始工作。  所以此时要想将1做完需要7（2+5）个时间。  2)执行4时：M1上运行4个时间后，M2还在继续运行1，并没有结束。M1结束时间为6，而M2结束1的时间为7，即。  所以此时要想把1，4做完，需要14（7+7）个时间。  3)执行5时：M1上运行6个时间后，M2还在继续运行4，并没有结束。M1的结束时间为12，而M2结束4的时间为14，即  所以此时要想把1，4，5做完，需要23（14+9）个时间。  4)执行2时：M1上运行7个时间后，M2还在继续运行5，并没有结束。M1的结束时间为19，而M2结束5的时间为23，即.  所以此时要想把1，4，5，2做完，需要26（23+3）个时间。  5)执行6时：M1上运行8个时间后，M2已经不在继续运行2。M1的结束时间为27，而M2结束2的时间为26，即此时M2已经空闲了一个时间，即.  所以此时要想把1，4，5，2，6完成，需要29（27+2）个时间。  6)执行3时：M1上运行6个时间后，M2已经不在继续运行6。M1的结束时间为33，而M2结束6的时间为29，即此时M2已经空闲了3个时间，即.  所以此时要把1，4，5，2，6，3完成，需要35（33+2）个时间。

所以，根据运行结果，作业执行时间为35.

代码如下：

/* 1)先执行t[i,1]=t[i,2]时，要保证最后一个作业在M2上执行时间最短，所以按照减序排列  */ #include #include #include  #define N 100 using namespace std;

struct node {     int time;//执行时间      int index;//作业序号     bool group;//1代表第一个机器，0代表第二个机器  };

bool cmp(node a,node b) {//升序排序      return a.time