流水线作业调度问题-动态规划(运用Johnson算法)

问题描述

• n个作业{1，2，…，n},要在由机器M1和M2组成的流水线上完成加工。
• 每个作业加工的顺序都是先在M1上加工，然后在M2上加工。
• M1和M2加工作业i所需的时间分别为ai和bi。

  要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

问题分析

• 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。
• 在一般情况下，机器M2上会有机器空闲和作业积压两种情况
  
  
  
• 设全部作业的集合为N={1，2，…，n}。S $\subseteq$ N是N的作业子集。
• 通常，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。
• 将这种情况下完成S中作业所需的最短时间记为T(S, t)。
• 流水作业调度问题的最优值为T(N, 0)。

最优子结构性质

 最优子结构性质：问题最优解，是否包含了子问题的最优解。

 调度问题最优子结构性质：设π是所给n个流水作业（N={1，2，…，n}）的一个最优调度，最优调度序列是π(1) ，π(2)， π(3)，…，π(n) ，π是否是调度π(2)， π(3)，…， π(n)的一个最优调度？若是，最优子结构性质成立。证明如下：

1. 把π调度n个作业所需的加工时间分成两部分： $a_{\pi (1)}$(1) 和T’。 其中，T’是机器M1和M2加工作业{π(2)，…，π(n)}所需的时间。因此，π调度n个流水作业需要的总时间为$a_{\pi (1)}$(1) 和T’
2. 令作业子集S=N – {π(1)} ，即：S={π(2)， π(3)，…，π(n)}。
3. 假设π不是实现加工作业子集S所需时间最短（最优）的调度，设π’是M1和M2加工作业子集S所需时间最短的一个最优调度, 则按π’加工作业子集S的最短时间为 T(S,$b_{\pi (1)}$ )

4. 因此π(1)， π’(2)，…， π’(n)是完成N ={1，2，…，n}作业 的一个调度，且该调度完成n个作业所需的时间 a_π(1)+T(S,b_π(1))
5. 由于 π’是加工π(2)，…，π(n)的最优调度，则T(S,bπ(1))是最短 时间，则T(S,$b_{\pi (1)}$)≤ T’，因此， $a_{\pi (1)}$+T(S,$b_{\pi (1)}$) ≤ $a_{\pi (1)}$+T’.
6. 由此，按照π(1)， π’(2)，…， π’(n)调度顺序完成n个作业所需的时间，小于按照π(1)， π(2) ，…， π(n) 调度完成n个作业所需时间aπ(1)+T’，这与π是N的最优调度矛盾，
7. 因此，π’是完成π(2)，…，π(n)的最优调度假设不成立，因此，π是完成π(2)，…，π(n)作业的最优调度。即：作业调度问题最优子结构性质成立。

递归计算最优值

 由流水作业调度问题的最优子结构性质可知:

流水作业调度的Johnson法则

• 所有满足Johnson法则的调度均为最优调度,且具有相同的加工时间。
• 从而，将流水作业调度问题转化为求满足Johnson法则的调度问题。

分析问题

• 当min{ $a_1$, $a_2$,┅, $a_n$ , $b_1$, $b_2$,┅, $b_n$ }=$a_k$时，则对任何i≠k，都有min{
  $b_k$, $a_i$} ≥ min{
  $b_i$,$a_k$}成立，故此时应将作业k安排在最前面，作为最优调度的第一个执行的作业；
• 当min{ $a_1$, $a_2$,┅, $a_n$ , $b_1$, $b_2$,┅, $b_n$ }=$b_k$时，则对任何i≠k，也都有min{
  $b_i$, $a_k$} ≥ min{
  $b_k$,$a_i$}成立，故此时应将作业k安排在最后面，作为最优调度的最后一个执行的作业。
• n个作业中首先开工（或最后开工）的作业确定之后，对剩下的n-1个作业采用相同方法可再确定其中的一个作业,应作为n-1个作业中最先或最后执行的作业；反复使用这个方法直到最后只剩一个作业为止，最优调度就确定了 。

  
  
  

计算作业加工顺序的步骤

1. 将{ $a_1$, $a_2$,┅, $a_n$ , $b_1$, $b_2$,┅, $b_n$ }排成非递减序列；
2. 依次从序列中抽出最小元素m，如果m ＝ $a_j$且作业j还没有排入调度表，则把作业 j 安排在调度表可达的最左边一项空位上（设n个作业的调度表有n项，开始全部为空）。
3. 如果m = bj且作业j还没有排入调度表，则把作业j安排在调度表可达的最右边一项空位上。
4. 如果作业j已排在调度表中，则取序列的下一个最小元素m，继续按上述方法调度，直到元素取完为止。
5. 最后得到的调度表中的作业的顺序就是各作业的加工顺序。

例子

流水作业调度问题的Johnson算法

1. 令 $N_1$ = { i | $a_i$ < $b_i$}，$N_2$ = { i | $a_i$ ＞ $b_i$}
2. 将$N_1$中作业依ai的非减序排序；将$N_2$中作业依$b_i$的非增序排序；
3. $N_1$中作业接$N_2$中作业构成满足Johnson法则的最优调度π。
   
   
   

• 红线左侧满足 $a_{\pi (i)}$ ≤ $b_{\pi (i)}$ 和 $a_{\pi (i)}$ ≤ $a_{\pi (i+1)}$ ，符合johnson不等式: min{
  $b_{\pi (i)}$,$a_{\pi (i+1)}$}≥min{
  $b_{\pi (i+1)}$,$a_{\pi (i)}$} ，N1中作业调度顺序最优；
• 红线右侧满足$b_{\pi (i+1)}$ ≤ $a_{\pi (i+1)}$ 和 $b_{\pi (i+1)}$ ≤ $b_{\pi (i)}$，符合johnson不等式: min{
  $b_{\pi (i)}$,$a_{\pi (i+1)}$}≥min{
  $b_{\pi (i+1)}$,$a_{\pi (i)}$} ，N2中作业调度顺序最优；
• 中间过渡部分横向比较，左侧 $a_{\pi (i)}$ ≤ $b_{\pi (i)}$,右侧$b_{\pi (i+1)}$ ≤ $a_{\pi (i+1)}$，符合johnson不等式: min{
  $b_{\pi (i)}$,$a_{\pi (i+1)}$}≥min{
  $b_{\pi (i+1)}$,$a_{\pi (i)}$} ，其作业调度顺序最优；
    若$a_{\pi (i)}$ ≤ $b_{\pi (i+1)}$ , 则$a_{\pi (i)}$ ≤ $b_{\pi (i+1)}$ ≤ $a_{\pi (i+1)}$ ，又$a_{\pi (i)}$ ≤ $b_{\pi (i)}$ ， 成立。
    若$a_{\pi (i)}$ ≥ $b_{\pi (i+1)}$ , 则$b_{\pi (i+1)}$ ≤ $a_{\pi (i)}$ ≤ $b_{\pi (i)}$ ，又$b_{\pi (i+1)}$ ≤ $a_{\pi (i+1)}$ ， 成立。

  
  
  
  

算法复杂度分析

  算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。

作业调度的最短时间计算

两个作业调度

三个作业调度

核心代码

 ? 参照上面的计算步骤进行分析,有些许不同。

class Jobtype { 
              public: int key, index; // key保存ai和bi二者较小的值； index保存作业号i  bool job; ///将满足条件ai 
              
              int operator 
              <= 
              (Jobtype a 
              ) 
              const 
              { 
                
              return 
              (key 
              <=a 
              .key 
              ) 
              ; 
              } 
              } 
              ; 
              int 
              FlowShop 
              ( 
              int n 
              , 
              int a 
              [ 
              ] 
              , 
              int b 
              [ 
              ] 
              , 
              int c 
              [ 
              ] 
              ) 
              { 
                Jobtype 
              *d 
              = 
              new 
              Jobtype 
              [n 
              ] 
              ; 
              for 
              ( 
              int i 
              = 
              0 
              ; i 
              <n 
              ; i 
              ++ 
              ) 
              { 
                d 
              [i 
              ] 
              .key 
              = a 
              [i 
              ] 
              >b 
              [i 
              ] 
              ? b 
              [i 
              ] 
              :a 
              [i 
              ] 
              ; 
              //分别取b[i]和a[i]值较小的作为关键字  d 
              [i 
              ] 
              .job 
              = a 
              [i 
              ] 
              <=b 
              [i 
              ] 
              ; 
              //将满足a[i] 
               
                 d 
                [i 
                ] 
                .index 
                = i 
                ; 
                //将当前作业号i赋值给index 
                } 
                Sort 
                (d 
                , n 
                ) 
                ; 
                //对数组d按关键字key升序进行排序 
                int j 
                = 
                0 
                , k 
                = n 
                - 
                1 
                ; 
                //指向数组c的两个指针，j指向最前面，k指向最后面 
                for 
                ( 
                int i 
                = 
                0 
                ; i 
                <n 
                ; i 
                ++ 
                ) 
                { 
                  
                if 
                (d 
                [i 
                ] 
                .job 
                ) c 
                [j 
                ++ 
                ] 
                = d 
                [i 
                ] 
                .index 
                ; 
                //将排过序的数组d，取N1中作业号,放到数组c的前面  
                else c 
                [k 
                -- 
                ] 
                = d 
                [i 
                ] 
                .index 
                ; 
                //将d中属于N2的作业号, 放到数组c的后面，从而实现N1的非减序排序，N2的非增序排序 
                } j 
                = a 
                [c 
                [ 
                0 
                ] 
                ] 
                ; 
                //第一个作业a完成的时间 k 
                = j 
                +b 
                [c 
                [ 
                0 
                ] 
                ] 
                ; 
                //第一个作业a+b完成的时间 
                for 
                ( 
                int i 
                = 
                1 
                ; i 
                <n 
                ; i 
                ++ 
                ) 
                { 
                  j 
                += a 
                [c 
                [i 
                ] 
                ] 
                ; 
                //M1在执行c[i]作业的同时，M2在执行c[i-1]号作业，最短执行时间取决于M1与M2谁后执行完 k 
                = j 
                <k 
                ? k 
                +b 
                [c 
                [i 
                ] 
                ] 
                : j 
                +b 
                [c 
                [i 
                ] 
                ] 
                ; 
                //计算最优加工时间 
                } delete d 
                ; 
                return k 
                ; 
                } 
                
             

完整代码

 #include 
               
                 #include 
                
                  #include 
                 
                   #define n 6 //6个作业 using namespace std; int M1[n]={2,7,6,4,6,8}; int M2[n]={5,3,2,7,9,2}; int c[n]={0}; //存放次序，注意：c[m]=k,意思是第m+1个执行的作业是k class Node{ public: int time; //时间 int index; //来自第几个作业 int position; //是先行工序还是后行工序 }; bool cmp(Node a,Node b){ return a.time 
                  
                    M2[i]){ node[i].time=M2[i]; node[i].position=2; //后行工序 } else{ node[i].time=M1[i]; node[i].position=1; //先行工序 } } //虽然把n个作业都赋值到了Node型结构体中， //但是大小交错，没有顺序， //所以需要排序 sort(node,node+n,cmp); //排完序后，把原本顺序都乱了，先行、后行工作虽然交错，但都已经从小到大排列了 //需要用c数组记录执行顺序，先行工序从前往后放，后行工序从后往前放 for(int i=0;i 
                   
                     time2?time1+M2[c[i]]:time2+M2[c[i]]; } cout<<"次序："< 
                     
                    
                   
                  
                 
               

测试样例

输入

输出
次序：
1 4 5 2 6 3
35