最优流水调度问题

声明：本文转载自WsHunTer

问题描述：

       设有n个作业，每一个作业i均被分解为m项任务: T_i1, T_i2, ┅ , T_im(1≤i≤n，故共有n*m个任务)，要把这些任务安排到m台机器上进行加工。

       现在有三条限定：

       1、  每个作业i的第j项任务T_ij (1≤i≤n, 1≤j≤m)只能安排在机器P_j上进行加工；

       2、  作业i的第j项任务T_ij(1≤i≤n, 2≤j≤m)的开始加工时间均安排在第j-1项任务T_i,j-1加工完毕之后；

       3、  任何一台机器在任何一个时刻最多只能承担一项任务。

       最优流水作业调度：设任务T_ij在机器P_j上进行加工需要的时间为t_ij。如果所有的t_ij(1≤i≤n, 1≤j≤m)均已给出，要找出一种安排任务的方法，使得完成这n个作业的加工时间为最少。已经证明，当机器数(或称工序数)m≥3时，流水作业调度问题是一个NP-hard问题。

       这里就考虑n个作业对于2个机器（P₁，P₂）的调度。现在问题就是：给定n个作业T，每个作业可以分成两项任务A，B；其中A任务在P₁处理，B任务在P₂上处理。如何给出一个使得这个n个作业的加工时间最短？

问题解决：

分析：

       首先考虑最优流水调度的性质：

       1、 在所确定的最优调度的排列中去掉第一个执行作业后，剩下的作业排列仍然还是一个最优调度，即该问题具有最优子结构的性质。

       2、 在计算规模为n的作业集合的最优调度时，需多次使用该作业集合的子集合的最优调度，即该问题亦具有高度重复性。

       So… 考虑用动态规划求解这个问题咯~

 

       设N={1，2，┅，n}是全部作业的集合，作业集S是N的子集S∈N。记为g(S,t)。

       现选定作业i为S中第一个加工作业之后，在机器P₂上开始对S-{i}中的作业进行加工之前，所需要的等待时间为b_i+max{t-a_i,0}。这是因为，若P₂在开始加工S中的作业之前需等待t个时间单位且t > a_i，则作业i在P₁上加工完毕（需时a_i）之后，还要再等t-a_i个时间单位才能开始在P₂上加工；若t≤a_i，则作业i在P₁上加工完毕之后，立即可以在P₂上加工，等待时间为0。故P2在开始对S-{i}中的作业进行加工之前，所需要的等待时间为t’= b_i+max{t-a_i,0}。（b_i是作业i在P2上加工所需的时间）。所以，假定ai为已知的使得g(S,t)值最小的第一个执行的作业，可以得到

               g(S,t)= a_i+ g(S-{i},b_i+max{t-a_i,0})                                   （1）

       将以上结论推广，现在我们安排首先执行作业i，再执行作业j，P₂需等待t个时间单位以后才可以用于S中的作业加工。则由（1）式的g(S,t)可写为

               g(S,t)=a_i+g(S-{i}, t’)=a_i+a_j+g(S-{i,j}, b_j+max{t’-a_j,0})。    （2）

 

       关于max{}运算有这个性质：x+ max{y₁, y₂,…,y_n}= max{x+y₁,x+y₂,…,x+y_n}。

       所以，

               b_j+max{t’-a_j,0}

               = b_j + max{b_i+max{t-a_i,0}-a_j, 0}

               = b_j + b_i - a_j+ max{max{t-a_i,0},a_j-b_i}

               = b_j + b_i - a_j + max{t-a_i, 0, a_j-b_i}

               = b_j+ b_i - a_j - a_i + max{t, a_i, a_i+a_j-b_i}。

               记t_ij= b_j+ b_i - a_j- a_i +max{t, a_i, a_i+a_j-b_i}，则g(S,t)= a_i+a_j+g(S-{i,j}, t_ij)。

       还记得之前我们的安排了吗？我们约定先调度作业i再调度作业j，有没有发现，我们推到了半天没有什么实质性结果啊，因为现在我们还根本不知道i和j是什么啊，如何确定？

       因此，既然说先i后j是最优的，凭什么？将j和i对调下，那就不是最优的咯，那对调后不是最优的根源处在哪儿呢？我们试试。

       若是先调度j作业再调度i作业，我们可以得到g’(S,t)=a_i+a_j+g(S-{i,j}, t_ji)。

       比较g(S,t)与g’(S,t)两式，显然，就是比较t_ij和t_ji。

              t_ij= b_j+ b_i - a_j - a_i +max{t, a_i, a_i+a_j-b_i}，

              t_ji= b_j+ b_i - a_j - a_i + max{t, a_j, a_i+a_j-b_j}，

              故t_ij-t_ji= max{t, a_i, a_i+a_j-b_i} - max{t, a_j, a_i+a_j-b_j}。

       因此我们只要比较max{t, a_i, a_i+a_j-b_i}与max{t, a_j, a_i+a_j-b_j}的大小就可以了,即tij≦ tji当且仅当max{t, a_i, a_i+a_j-b_i} ≤max{t, a_j, a_i+a_j-b_j}。

              由于max{t, a_i, a_i+a_j-b_i}≤ max{t, a_j, a_i+a_j-b_j}

                      对任何t≧ 0成立，当且仅当

                         max{a_i, a_i+a_j-b_i}≤ max{a_j, a_i+a_j-b_j}成立，当且仅当

                        a_i+a_j+max{-a_j, -b_i}≦a_i+a_j+max{-a_i, -b_j}成立，当且仅当

                        max{-a_j, -b_i}≦ max{-a_i, -b_j}成立，当且仅当

                        min{a_j, b_i}≧ min{a_i, b_j}成立（此式称为Johnson不等式）。

                        当min{ a_i , a_j , b_i , b_j}为a_i或者b_j时，有t_ij≤ t_ji，此时把i排在前j排在后的调度用时较少；

                        反之，若min{ a_i , a_j , b_i, b_j}为a_j或者b_i时，则j排在前i排在后的调度用时较少。

        将此情况推广到一般。

        当min{ a₁, a₂,┅, a_n , b₁, b₂,┅, b_n }=a_k时，则对任何i≠k，都有min{a_i, b_k}  min{a_k, b_i}成立，故此时应将作业k安排在最前面，作为最优调度的第一个执行的作业；

        当min{ a₁, a₂,┅, a_n , b₁, b₂,┅, b_n}= b_k时，则对任何i≠k，也都有min{a_k, b_i}min{a_i, b_k}成立，故此时应将作业k安排在最后面，作为最优调度的最后一个执行的作业。

算法描述：

       1.    建立长为2n的数组C，

              将a₁, a₂,┅, a_n依次放入C[1]~ C[n]中，

              b₁, b₂,┅, b_n依次放入C[n+1]~ C[2n]中。    /* O(n),下面将对这2n个数进行排序*/

       2.    对长为2n的数组D进行初始化：

               D[1]~D[n]中依次放1,2,┅,n，

               D[n+1]~D[2n]中依次放-1,-2,┅,-n。     /* O(n),分别对应于a1, a2,┅, an和b1, b2,┅, bn的下标*/

       3.    对数组C进行排序，

               D[k]始终保持与C[k]的对应关系。（O(n log n)，若C[i]与C[j]对换，则D[i]也与D[j]对换。） 

               当a₁, a₂,┅, a_n及b₁, b₂,┅, b_n按从小到大排好序之后，D[1]~ D[2n]也就按从小到大的次序记录了这些a_i和b_j的下标即作业号（b_j的下标前有一负号以区别于a_i））。

        4.    将E[1]~ E[n]全部置为“No”。/* O(n)，表示所有任务均尚未被安排*/

        5.    下标变量初始化：i←1；j←n；k←1；  /*O(1)，*/

               /*i指向当前最左空位F[i]，*/

               /*放当前应最先安排的作业号;*/

               /* j指向当前最右空位F[j]，*/

               /*放当前应最后安排的作业号;*/

               /* k从1开始逐次增1，D[k]（或-D[k]）*/

               /*按a_i和b_j从小到大的次序依次给出作业号。*/

         6.    while i ≤ j do

                {     /* 作业尚未安排完毕，i从小到大, j从大到小*/

                     if D[k]>0 then   /*D[k]>0即D[k]中放的是ai下标*/

                         {  if E[D[k]]为“No”then  /*作业D[k]尚未安排*/

                                { F[i]←D[k]; i增1; E[D[k]] 置为“Yes”}

                          }/*作业D[k]放在当前最左空位*/

                     else         /*D[k]<0，则–D[k]是bj下标*/

                         {  if E[–D[k]]为“No”then /*作业–D[k]尚未安排*/

                                { F[j]←–D[k]; j减1; E[–D[k]] 置为“Yes”}

                          } /*作业–D[k]放在当前最右空位*/

                      k增1; /*准备检查下一个D[k]以便后续作业安排*/

                  }

实现

    #include <stdio.h>  
    #include <stdlib.h>  
      
    #define     MAX_LEN     128  
      
    void heap_adjust(int *array,int *index,int n,int loc)  
    {  
        int tmp,i,j,k;  
        tmp=array[loc];  
        k=index[loc];  
        for(i=loc;2*i<n;i=j)  
        {  
            j=2*i;  
            if(j+1<n && array[j]<array[j+1]) j++;  
            if(tmp < array[j]) {  
                array[i]=array[j];  
                index[i]=index[j];  
            }  
            else break;  
        }  
        array[i]=tmp;  
        index[i]=k;  
    }  
      
    void heap_sort(int *array,int *index,int n)  
    {  
        int i,j,tmp;  
        for(i=n/2;i>0;i--)  
            heap_adjust(array,index,n,i);  
      
        for(i=n;i>1;i--)  
        {  
            tmp=array[i];  
            array[i]=array[1];  
            array[1]=tmp;  
              
            j=index[i];  
            index[i]=index[1];  
            index[1]=j;  
      
            heap_adjust(array,index,i,1);  
        }  
    }  
      
      
    int main()  
    {  
        int n,i,j,k;  
        int A[MAX_LEN],B[MAX_LEN],C[MAX_LEN*2],D[MAX_LEN*2],E[MAX_LEN],F[MAX_LEN];  
        while(1==scanf("%d",&n)){  
            if(n > 0 && n < MAX_LEN){  
                for(i=1;i<=n;i++)  
                    scanf("%d%d",A+i,B+i);  
                break;  
            }  
            printf("invalid n
");  
        }  
      
        //initial tabs  
        for(i=1;i<=2*n;i++){  
            if(i<=n){  
                C[i]=A[i];  
                D[i]=i;  
                E[i]=0;  
            }  
            else{  
                C[i]=B[i-n];  
                D[i]=-(i-n);  
            }  
        }  
      
        //sort it!  
        heap_sort(C,D,2*n);  
      
        //dp find  
        for(k=1,i=1,j=n;i<=j;k++){  
            if(D[k] > 0){  
                if(E[D[k]] == 0){  
                    F[i++]=D[k];  
                    E[D[k]]=1;  
                }  
            }  
            else{  
                if(E[-D[k]] == 0){  
                    F[j--]=-D[k];  
                    E[-D[k]]=1;  
                }  
            }  
        }  
      
      
        printf("scheduled tasks:");  
        for(i=1;i<=n;i++)  
            printf("%-3d",F[i]);  
        printf("
");  
      
        return 0;  
    }