分支限界法-批处理调度问题

1、【分支限界法】批处理作业调度问题    问题描述     给定n个作业的集合J1,J2,Jn。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。     批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。      例：设n=3，考虑以下实例：   

2、  这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。     限界函数     批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。          在作业调度问相应的排列空间树中，每一个节点E都对应于

3、一个已安排的作业集。以该节点为根的子树中所含叶节点的完成时间和可表示为：     设|M|=r，且L是以节点E为根的子树中的叶节点，相应的作业调度为pk,k=1,2,n，其中pk是第k个安排的作业。如果从节点E到叶节点L的路上，每一个作业pk在机器1上完成处理后都能立即在机器2上开始处理，即从pr+1开始，机器1没有空闲时间，则对于该叶节点L有：注：(n-k+1)t1pk,因为是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上t1pk。     如果不能做到上面这一点，则s1只会增加，从而有：。   

4、  类似地，如果从节点E开始到节点L的路上，从作业pr+1开始，机器2没有空闲时间，则：     同理可知，s2是的下界。由此得到在节点E处相应子树中叶节点完成时间和的下界是：     注意到如果选择Pk，使t1pk在k>=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。      这可以作为优先队列式分支限界法中的限界函数。      算法描述     

5、60;算法中用最小堆表示活节点优先队列。最小堆中元素类型是MinHeapNode。每一个MinHeapNode类型的节点包含域x,用来表示节点所相应的作业调度。s表示该作业已安排的作业时x1:s。f1表示当前已安排的作业在机器1上的最后完成时间；f2表示当前已安排作业在机器2上的完成时间；sf2表示当前已安排的作业在机器2上的完成时间和；bb表示当前完成时间和下界。二维数组M表示所给的n个作业在机器1和机器2所需的处理时间。在类Flowshop中用二维数组b存储排好序的作业处理时间。数组a表示数组M和b的对应关系。算法Sort实现对各作业在机器1和2上所需时间排序。函数Bound用于计算完成时

6、间和下界。     函数BBFlow中while循环完成对排列树内部结点的有序扩展。在while循环体内算法依次从活结点优先队列中取出具有最小bb值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。 算法将当前扩展节点E分两种情形处理：1)首先考虑E.s=n的情形，当前扩展结点E是排列树中的叶结点。E.sf2是相应于该叶结点的完成时间和。当E.sf2 < bestc时更新当前最优值bestc和相应的当前最优解bestx。     2)当E.s<n时，算法依次产生当前扩展结点E的所有儿子结点。对于当前扩展结点的每一个儿子

7、结点node，计算出其相应的完成时间和的下界bb。当bb < bestc时，将该儿子结点插入到活结点优先队列中。而当bb³ bestc时，可将结点node舍去。     算法具体实现如下：1. #include <iostream>  2.   3. template<class Type>  4. class Graph;  5.   6. template<class T>

8、;   7. class MinHeap   8.    9.     template<class Type>  10.     friend class Graph;  11.     public:   12.     &

9、#160;   MinHeap(int maxheapsize = 10);   13.         MinHeap()delete heap;   14.   15.         int Size() constreturn currentsize;

10、   16.         T Max()if(currentsize) return heap1;   17.   18.         MinHeap<T>& Insert(const T& x);   19.   

11、;      MinHeap<T>& DeleteMin(T &x);   20.   21.         void Initialize(T x, int size, int ArraySize);   22.     

12、60;   void Deactivate();   23.         void output(T a,int n);  24.     private:   25.         int currentsize, max

13、size;   26.         T *heap;   27. ;   28.   29. template <class T>   30. void MinHeap<T>:output(T a,int n)   31.    3

14、2.     for(int i = 1; i <= n; i+)   33.     cout << ai << " "   34.     cout << endl;   35. &#

15、160;  36.   37. template <class T>   38. MinHeap<T>:MinHeap(int maxheapsize)   39.    40.     maxsize = maxheapsize;   41.     heap = 

16、;new Tmaxsize + 1;   42.     currentsize = 0;   43.    44.   45. template<class T>   46. MinHeap<T>& MinHeap<T>:Insert(const T& x) 

17、60; 47.    48.     if(currentsize = maxsize)   49.        50.         return *this;   51.        52. 

18、0;   int i = +currentsize;   53.     while(i != 1 && x < heapi/2)   54.        55.         heapi =&

19、#160;heapi/2;   56.         i /= 2;   57.        58.   59.     heapi = x;   60.     return *this; &#

20、160; 61.    62.   63. template<class T>   64. MinHeap<T>& MinHeap<T>:DeleteMin(T& x)   65.    66.     if(currentsize = 0)   67.   

21、;     68.         cout<<"Empty heap!"<<endl;   69.         return *this;   70.        71.  &#

22、160;72.     x = heap1;   73.   74.     T y = heapcurrentsize-;   75.     int i = 1, ci = 2;   76.     while(ci

23、 <= currentsize)   77.        78.         if(ci < currentsize && heapci > heapci + 1)   79.       

24、     80.             ci+;   81.            82.   83.         if(y <= heapci) 

25、  84.            85.             break;   86.            87.        &#

26、160;heapi = heapci;   88.         i = ci;   89.         ci *= 2;   90.        91.   92.   

27、  heapi = y;   93.     return *this;   94.    95.   96. template<class T>   97. void MinHeap<T>:Initialize(T x, int size, int ArraySize)&#

28、160;  98.    99.     delete heap;   100.     heap = x;   101.     currentsize = size;   102.     maxsize = ArraySiz

29、e;   103.   104.     for(int i = currentsize / 2; i >= 1; i-)   105.        106.         T y = heapi;&

30、#160;  107.         int c = 2 * i;   108.         while(c <= currentsize)   109.           &

31、#160;110.             if(c < currentsize && heapc > heapc + 1)   111.                 c+;&#

32、160;  112.             if(y <= heapc)   113.                 break;   114.      &#

33、160;      heapc / 2 = heapc;   115.             c *= 2;   116.            117.   

34、0;     heapc / 2 = y;   118.        119.    120.   121. template<class T>   122. void MinHeap<T>:Deactivate()   123.   

35、; 124.     heap = 0;   125.        2、6d9.cppcpp view plain copy1. /批作业调度问题 优先队列分支限界法求解   2. #include "stdafx.h"  3. #include "MinHeap2.h"  4. #in

36、clude <iostream>  5. using namespace std;  6.   7. class Flowshop;  8. class MinHeapNode  9.   10.     friend Flowshop;  11.     public:  12. &#

37、160;       operator int() const  13.           14.             return bb;  15.        

38、;   16.     private:      17.         void Init(int);  18.         void NewNode(MinHeapNode,int,int,int,int);  19.  

39、0;      int s,          /已安排作业数  20.             f1,         /机器1上最后完成时间  21.   

40、          f2,         /机器2上最后完成时间  22.             sf2,        /当前机器2上完成时间和  23. 

41、0;           bb,         /当前完成时间和下界  24.             *x;         /当前作业调度  2

42、5. ;  26.   27. class Flowshop  28.   29.     friend int main(void);  30.     public:  31.         int BBFlow(void);  32.  &#

43、160;  private:  33.         int Bound(MinHeapNode E,int &f1,int &f2,bool *y);  34.         void Sort(void);  35.      

44、;   int n,          /作业数  36.             * M,       /各作业所需的处理时间数组  37.       &#

45、160;     *b,        /各作业所需的处理时间排序数组  38.             *a,        /数组M和b的对应关系数组  39.      &#

46、160;      *bestx,     /最优解  40.             bestc;      /最小完成时间和  41.         bool *y;

47、0;      /工作数组  42. ;  43.   44. template <class Type>  45. inline void Swap(Type &a, Type &b);  46.   47. int main()  48.   49.  &#

48、160;  int n=3,bf;  50.     int M132=2,1,3,1,2,3;  51.   52.     int *M = new int*n;  53.     int *b = new int*n;  54.   

49、  int *a = new int*n;  55.     bool *y = new bool*n;  56.     int *bestx = new intn;    57.   58.     for(int i=0;i

50、<=n;i+)  59.       60.         Mi = new int2;  61.         bi = new int2;  62.         

51、ai = new int2;  63.         yi = new bool2;  64.       65.     cout<<"各作业所需要的时间处理数组M(i,j)值如下："<<endl;  66.   67.  

52、;   for(int i=0;i<n;i+)  68.       69.         for(int j=0;j<2;j+)  70.           71.        &

53、#160;    Mij=M1ij;  72.           73.       74.   75.     for(int i=0;i<n;i+)  76.       77.    &

54、#160;    cout<<"("  78.         for(int j=0;j<2;j+)  79.         cout<<Mij<<" "  80.      

55、0;  cout<<")"  81.       82.     cout<<endl;  83.   84.     Flowshop flow;  85.     flow.n = n;  86.   

56、  flow.M = M;  87.     flow.b = b;  88.     flow.a = a;  89.     flow.y = y;  90.     flow.bestx = bestx;  91.

57、     flow.bestc = 1000;/给初值  92.   93.     flow.BBFlow();  94.   95.     cout<<"最优值是："<<flow.bestc<<endl;  96.     cout<<"

58、;最优调度是："  97.   98.     for(int i=0;i<n;i+)  99.       100.         cout<<(flow.bestxi+1)<<" "  101.      

59、; 102.     cout<<endl;  103.   104.     for(int i=0;i<n;i+)  105.       106.         delete Mi;  107.     

60、    delete bi;  108.         delete ai;  109.         delete yi;        110.       111.  &

61、#160;  return 0;  112.   113.   114. /最小堆节点初始化  115. void MinHeapNode:Init(int n)  116.   117.     x = new intn;  118.     for(int i=0; i<

62、;n; i+)  119.       120.         xi = i;  121.       122.     s = 0;  123.     f1 = 0; 

63、60;124.     f2 = 0;  125.     sf2 = 0;  126.     bb = 0;  127.   128.   129. /最小堆新节点  130. void MinHeapNode:NewNode(MinHeapNode E,int E

64、f1,int Ef2,int Ebb,int n)  131.   132.     x = new intn;  133.     for(int i=0; i<n; i+)  134.       135.       

65、  xi = E.xi;  136.       137.     f1 = Ef1;  138.     f2 = Ef2;  139.     sf2 = E.sf2 + f2;  140.   

66、  bb = Ebb;  141.     s =  E.s + 1;  142.   143.   144. /对各作业在机器1和2上所需时间排序  145. void Flowshop:Sort(void)  146.   147.     int *c 

67、= new intn;  148.     for(int j=0; j<2; j+)  149.       150.         for(int i=0; i<n; i+)  151.       &

68、#160;   152.             bij = Mij;  153.             ci = i;  154.          

69、60;155.   156.         for(int i=0; i<n-1; i+)  157.           158.             for(int k=n-1; k>i;

70、 k-)  159.               160.                 if(bkj<bk-1j)  161.          &#

71、160;        162.                     Swap(bkj,bk-1j);  163.                

72、     Swap(ck,ck-1);  164.                   165.               166.       &

73、#160;      167.   168.         for(int i=0; i<n; i+)  169.           170.            &#

74、160;acij = i;  171.           172.       173.   174.     delete c;  175.   176.   177. /计算完成时间和下界  178. int Flowshop:Bou

75、nd(MinHeapNode E,int &f1,int &f2,bool *y)  179.   180.     for(int k=0; k<n; k+)  181.       182.         for(int j=0; j<

76、2; j+)  183.              184.             ykj = false;  185.           186.   &

77、#160;   187.   188.     for(int k=0; k<=E.s; k+)  189.       190.         for(int j=0; j<2; j+)  191.     

78、60;     192.             yaE.xkjj = true;  193.           194.       195.   196.     

79、f1 = E.f1 + ME.xE.s0;  197.     f2 = (f1>E.f2)?f1:E.f2)+ME.xE.s1;  198.     int sf2 = E.sf2 + f2;  199.     int s1 = 0,s2 = 0,k

80、1 = n-E.s,k2 = n-E.s,f3 = f2;  200.   201.     /计算s1的值  202.     for(int j=0; j<n; j+)  203.       204.       &#

81、160; if(!yj0)  205.           206.             k1-;  207.             if(k1 = n-E.s-1) 

82、60;208.               209.                 f3 = (f2>f1+bj0)?f2:f1+bj0;  210.         &#

83、160;     211.             s1 += f1+k1*bj0;  212.           213.       214.   215.     

84、;/计算s2的值  216.     for(int j=0; j<n; j+)  217.          218.         if(!yj1)  219.           220

85、.             k2-;  221.             s1 += bj1;  222.             s2 += f3 

86、+ k2*bj1;  223.           224.       225.   226.     /返回完成时间和下界  227.     return sf2 +(s1>s2)?s1:s2);  228.   22

87、9.   230. /解批处理作业调度问题的优先队列式分支限界法  231. int Flowshop:BBFlow(void)  232.   233.     Sort();/对各作业在机器1和2上所需时间排序  234.     MinHeap<MinHeapNode> H(1000);  235.   236.   &

88、#160; MinHeapNode E;  237.     /初始化  238.     E.Init(n);  239.     /搜索排列空间树  240.     while(E.s<=n)  241.       242.  

89、0;      /叶节点  243.         if(E.s = n)  244.           245.             if(E.sf2<bestc)

90、  246.               247.                 bestc = E.sf2;  248.          

91、60;      for(int i=0; i<n; i+)  249.                   250.                &#

92、160;    bestxi = E.xi;  251.                   252.               253.             delete E.x;  254.           255.         else/产生当前扩展节点的儿子节点  256.