有n个作业（编号为1～n）要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi（1≤i≤n）。 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。可以假定任何作业一旦开始加工，就不允许被中断，直到该作业被完成，即非优先调度。 输入格式：输入包含若干个用例。每个用例第一行是作业数n（1≤n≤1000），接下来n行，每行两个非负整数，第i行的两个整数分别表示在第i个作业在第一台机器和第二台机器上加工时间。以输入n=0结束。 输出格式：每个用例输出一行，表示采用最优调度所用的总时间，即从第一台机器开始到第二台机器结束的时间。 输入样例： 4 5 6 12 2 4 14 8 7 0 输出样例： 33

流水作业调度问题的Johnson算法： （1）N1={i|t[i,1]=t[i,2]}; （2）将N1 中作业依t[i,1]的非减序排列；将N2中作业依t[i,2]的非增序排列； 问题分析： 当输入的作业数目为4时： 每个作业在M1上执行的时间为t[i,1]，在M2上执行的时间为t[i,2]，输入的数据为： 算法按照t[i,1] int i,j,k,n; int a[N]={0},b[N]={0}; int best[N];//最优调度序列 node c[N]; scanf(“%d”,&n); for(i=0;i if(c[i].group) { //第一组，从i=0开始放入到best[]中 best[j++]=c[i].index;//将排过序的数组c，取其中作业序号属于N1的从前面进入，实现N1的非减序排序 } else { best[k–]=c[i].index;//将排过序的数组c，取其中作业序号属于N2的从后面进入，实现N2的非增序排序 } } j=a[best[0]];//最优调度序列下的消耗总时间，第一个选取M1上的工作时间最少的 k=j+b[best[0]]; for(i=1;i printf(“%d “,best[i]+1); //输出最优序列 } printf(”\n”); return 0; }

算法的主要计算时间在对作业集的排序上，在本算法中，我们使用冒泡排序法(sort)，因此，在最坏情况下算法所需要计算的时间为O(nlogn)。所需要的空间为O(n)。