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

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

     这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都对应于一个已安排的作业集。以该节点为根的子树中所含叶节点的完成时间和可表示为：

     设|M|=r，且L是以节点E为根的子树中的叶节点，相应的作业调度为{pk,k=1,2,……n}，其中pk是第k个安排的作业。如果从节点E到叶节点L的路上，每一个作业pk在机器1上完成处理后都能立即在机器2上开始处理，即从p

r+1开始，机器1没有空闲时间，则对于该叶节点L有：
注：(n-k+1)t1pk,因为是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上t1pk。
     如果不能做到上面这一点，则s1只会增加，从而有：。
     类似地，如果从节点E开始到节点L的路上，从作业pr+1开始，机器2没有空闲时间，则：

     同理可知，s2是的下界。由此得到在节点E处相应子树中叶节点完成时间和的下界是：

     注意到如果选择Pk，使t1pk在k>=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。 

     这可以作为优先队列式分支限界法中的限界函数。 
     算法描述
      算法中用最小堆表示活节点优先队列。最小堆中元素类型是MinHeapNode。每一个MinHeapNode类型的节点包含域x,用来表示节点所相应的作业调度。s表示该作业已安排的作业时x[1:s]。f1表示当前已安排的作业在机器1上的最后完成时间；f2表示当前已安排作业在机器2上的完成时间；sf2表示当前已安排的作业在机器2上的完成时间和；bb表示当前完成时间和下界。二维数组M表示所给的n个作业在机器1和机器2所需的处理时间。在类Flowshop中用二维数组b存储排好序的作业处理时间。数组a表示数组M和b的对应关系。算法Sort实现对各作业在机器1和2上所需时间排序。函数Bound用于计算完成时间和下界。
     函数BBFlow中while循环完成对排列树内部结点的有序扩展。在while循环体内算法依次从活结点优先队列中取出具有最小bb值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。 算法将当前扩展节点E分两种情形处理：
　1)首先考虑E.s=n的情形，当前扩展结点E是排列树中的叶结点。E.sf2是相应于该叶结点的完成时间和。当E.sf2 < bestc时更新当前最优值bestc和相应的当前最优解bestx。 

    2)当E.s<n时，算法依次产生当前扩展结点E的所有儿子结点。对于当前扩展结点的每一个儿子结点node，计算出其相应的完成时间和的下界bb。当bb < bestc时，将该儿子结点插入到活结点优先队列中。而当bb³ bestc时，可将结点node舍去。 
    算法具体实现如下：
1. #include <iostream>  
2.   
3. template<class Type>  
4. class Graph;  
5.   
6. template<class T>   
7. class MinHeap   
8. {   
9.     template<class Type>  
10.     friend class Graph;  
11.     public:   
12.         MinHeap(int maxheapsize = 10);   
13.         ~MinHeap(){delete []heap;}   
14.   
15.         int Size() const{return currentsize;}   
16.         T Max(){if(currentsize) return heap[1];}   
17.   
18.         MinHeap<T>& Insert(const T& x);   
19.         MinHeap<T>& DeleteMin(T &x);   
20.   
21.         void Initialize(T x[], int size, int ArraySize);   
22.         void Deactivate();   
23.         void output(T a[],int n);  
24.     private:   
25.         int currentsize, maxsize;   
26.         T *heap;   
27. };   
28.   
29. template <class T>   
30. void MinHeap<T>::output(T a[],int n)   
31. {   
32.     for(int i = 1; i <= n; i++)   
33.     cout << a[i] << " ";   

34.     cout << endl;   
35. }   
36.   
37. template <class T>   
38. MinHeap<T>::MinHeap(int maxheapsize)   
39. {   
40.     maxsize = maxheapsize;   
41.     heap = new T[maxsize + 1];   
42.     currentsize = 0;   
43. }   
44.   
45. template<class T>   
46. MinHeap<T>& MinHeap<T>::Insert(const T& x)   
47. {   
48.     if(currentsize == maxsize)   
49.     {   
50.         return *this;   
51.     }   
52.     int i = ++currentsize;   
53.     while(i != 1 && x < heap[i/2])   
54.     {   
55.         heap[i] = heap[i/2];   
56.         i /= 2;   
57.     }   
58.   
59.     heap[i] = x;   
60.     return *this;   
61. }   
62.   
63. template<class T>   
64. MinHeap<T>& MinHeap<T>::DeleteMin(T& x)   
65. {   
66.     if(currentsize == 0)   
67.     {   
68.         cout<<"Empty heap!"<<endl;   
69.         return *this;   
70.     }   
71.   
72.     x = heap[1];   
73.   
74.     T y = heap[currentsize--];   
75.     int i = 1, ci = 2;   
76.     while(ci <= currentsize)   
77.     {   

78.         if(ci < currentsize && heap[ci] > heap[ci + 1])   
79.         {   
80.             ci++;   
81.         }   
82.   
83.         if(y <= heap[ci])   
84.         {   
85.             break;   
86.         }   
87.         heap[i] = heap[ci];   
88.         i = ci;   
89.         ci *= 2;   
90.     }   
91.   
92.     heap[i] = y;   
93.     return *this;   
94. }   
95.   
96. template<class T>   
97. void MinHeap<T>::Initialize(T x[], int size, int ArraySize)   
98. {   
99.     delete []heap;   
100.     heap = x;   
101.     currentsize = size;   
102.     maxsize = ArraySize;   
103.   
104.     for(int i = currentsize / 2; i >= 1; i--)   
105.     {   
106.         T y = heap[i];   
107.         int c = 2 * i;   
108.         while(c <= currentsize)   
109.         {   
110.             if(c < currentsize && heap[c] > heap[c + 1])   
111.                 c++;   
112.             if(y <= heap[c])   
113.                 break;   
114.             heap[c / 2] = heap[c];   
115.             c *= 2;   
116.         }   
117.         heap[c / 2] = y;   
118.     }   
119. }   
120.   
121. template<class T>   

122. void MinHeap<T>::Deactivate()   
123. {   
124.     heap = 0;   
125. }   
    2、6d9.cpp
[cpp] view plain copy
1. //批作业调度问题 优先队列分支限界法求解   
2. #include "stdafx.h"  
3. #include "MinHeap2.h"  
4. #include <iostream>  
5. using namespace std;  
6.   
7. class Flowshop;  
8. class MinHeapNode  
9. {  
10.     friend Flowshop;  
11.     public:  
12.         operator int() const  
13.         {  
14.             return bb;  
15.         }  
16.     private:      
17.         void Init(int);  
18.         void NewNode(MinHeapNode,int,int,int,int);  
19.         int s,          //已安排作业数  
20.             f1,         //机器1上最后完成时间  
21.             f2,         //机器2上最后完成时间  
22.             sf2,        //当前机器2上完成时间和  
23.             bb,         //当前完成时间和下界  
24.             *x;         //当前作业调度  
25. };  
26.   
27. class Flowshop  
28. {  
29.     friend int main(void);  
30.     public:  
31.         int BBFlow(void);  
32.     private:  
33.         int Bound(MinHeapNode E,int &f1,int &f2,bool **y);  
34.         void Sort(void);  
35.         int n,          //作业数  
36.             ** M,       //各作业所需的处理时间数组  
37.             **b,        //各作业所需的处理时间排序数组  

38.             **a,        //数组M和b的对应关系数组  
39.             *bestx,     //最优解  
40.             bestc;      //最小完成时间和  
41.         bool **y;       //工作数组  
42. };  
43.   
44. template <class Type>  
45. inline void Swap(Type &a, Type &b);  
46.   
47. int main()  
48. {  
49.     int n=3,bf;  
50.     int M1[3][2]={{2,1},{3,1},{2,3}};  
51.   
52.     int **M = new int*[n];  
53.     int **b = new int*[n];  
54.     int **a = new int*[n];  
55.     bool **y = new bool*[n];  
56.     int *bestx = new int[n];    
57.   
58.     for(int i=0;i<=n;i++)  
59.     {  
60.         M[i] = new int[2];  
61.         b[i] = new int[2];  
62.         a[i] = new int[2];  
63.         y[i] = new bool[2];  
64.     }  
65.     cout<<"各作业所需要的时间处理数组M(i,j)值如下："<<endl;  
66.   
67.     for(int i=0;i<n;i++)  
68.     {  
69.         for(int j=0;j<2;j++)  
70.         {  
71.             M[i][j]=M1[i][j];  
72.         }  
73.     }  
74.   
75.     for(int i=0;i<n;i++)  
76.     {  
77.         cout<<"(";  
78.         for(int j=0;j<2;j++)  
79.         cout<<M[i][j]<<" ";  
80.         cout<<")";  
81.     }  

82.     cout<<endl;  
83.   
84.     Flowshop flow;  
85.     flow.n = n;  
86.     flow.M = M;  
87.     flow.b = b;  
88.     flow.a = a;  
89.     flow.y = y;  
90.     flow.bestx = bestx;  
91.     flow.bestc = 1000;//给初值  
92.   
93.     flow.BBFlow();  
94.   
95.     cout<<"最优值是："<<flow.bestc<<endl;  
96.     cout<<"最优调度是：";  
97.   
98.     for(int i=0;i<n;i++)  
99.     {  
100.         cout<<(flow.bestx[i]+1)<<" ";  
101.     }  
102.     cout<<endl;  
103.   
104.     for(int i=0;i<n;i++)  
105.     {  
106.         delete[] M[i];  
107.         delete[] b[i];  
108.         delete[] a[i];  
109.         delete[] y[i];        
110.     }  
111.     return 0;  
112. }  
113.   
114. //最小堆节点初始化  
115. void MinHeapNode::Init(int n)  
116. {  
117.     x = new int[n];  
118.     for(int i=0; i<n; i++)  
119.     {  
120.         x[i] = i;  
121.     }  
122.     s = 0;  
123.     f1 = 0;  
124.     f2 = 0;  
125.     sf2 = 0;  

126.     bb = 0;  
127. }  
128.   
129. //最小堆新节点  
130. void MinHeapNode::NewNode(MinHeapNode E,int Ef1,int Ef2,int Ebb,int n)  
131. {  
132.     x = new int[n];  
133.     for(int i=0; i<n; i++)  
134.     {  
135.         x[i] = E.x[i];  
136.     }  
137.     f1 = Ef1;  
138.     f2 = Ef2;  
139.     sf2 = E.sf2 + f2;  
140.     bb = Ebb;  
141.     s =  E.s + 1;  
142. }  
143.   
144. //对各作业在机器1和2上所需时间排序  
145. void Flowshop::Sort(void)  
146. {  
147.     int *c = new int[n];  
148.     for(int j=0; j<2; j++)  
149.     {  
150.         for(int i=0; i<n; i++)  
151.         {  
152.             b[i][j] = M[i][j];  
153.             c[i] = i;  
154.         }  
155.   
156.         for(int i=0; i<n-1; i++)  
157.         {  
158.             for(int k=n-1; k>i; k--)  
159.             {  
160.                 if(b[k][j]<b[k-1][j])  
161.                 {  
162.                     Swap(b[k][j],b[k-1][j]);  
163.                     Swap(c[k],c[k-1]);  
164.                 }  
165.             }  
166.         }     
167.   
168.         for(int i=0; i<n; i++)  
169.         {  

170.             a[c[i]][j] = i;  
171.         }  
172.     }  
173.   
174.     delete []c;  
175. }  
176.   
177. //计算完成时间和下界  
178. int Flowshop::Bound(MinHeapNode E,int &f1,int &f2,bool **y)  
179. {  
180.     for(int k=0; k<n; k++)  
181.     {  
182.         for(int j=0; j<2; j++)  
183.         {     
184.             y[k][j] = false;  
185.         }  
186.     }  
187.   
188.     for(int k=0; k<=E.s; k++)  
189.     {  
190.         for(int j=0; j<2; j++)  
191.         {  
192.             y[a[E.x[k]][j]][j] = true;  
193.         }  
194.     }  
195.   
196.     f1 = E.f1 + M[E.x[E.s]][0];  
197.     f2 = ((f1>E.f2)?f1:E.f2)+M[E.x[E.s]][1];  
198.     int sf2 = E.sf2 + f2;  
199.     int s1 = 0,s2 = 0,k1 = n-E.s,k2 = n-E.s,f3 = f2;  
200.   
201.     //计算s1的值  
202.     for(int j=0; j<n; j++)  
203.     {  
204.         if(!y[j][0])  
205.         {  
206.             k1--;  
207.             if(k1 == n-E.s-1)  
208.             {  
209.                 f3 = (f2>f1+b[j][0])?f2:f1+b[j][0];  
210.             }  
211.             s1 += f1+k1*b[j][0];  
212.         }  
213.     }  

214.   
215.     //计算s2的值  
216.     for(int j=0; j<n; j++)  
217.     {     
218.         if(!y[j][1])  
219.         {  
220.             k2--;  
221.             s1 += b[j][1];  
222.             s2 += f3 + k2*b[j][1];  
223.         }  
224.     }  
225.   
226.     //返回完成时间和下界  
227.     return sf2 +((s1>s2)?s1:s2);  
228. }  
229.   
230. //解批处理作业调度问题的优先队列式分支限界法  
231. int Flowshop::BBFlow(void)  
232. {  
233.     Sort();//对各作业在机器1和2上所需时间排序  
234.     MinHeap<MinHeapNode> H(1000);  
235.   
236.     MinHeapNode E;  
237.     //初始化  
238.     E.Init(n);  
239.     //搜索排列空间树  
240.     while(E.s<=n)  
241.     {  
242.         //叶节点  
243.         if(E.s == n)  
244.         {  
245.             if(E.sf2<bestc)  
246.             {  
247.                 bestc = E.sf2;  
248.                 for(int i=0; i<n; i++)  
249.                 {  
250.                     bestx[i] = E.x[i];  
251.                 }  
252.             }  
253.             delete []E.x;  
254.         }  
255.         else//产生当前扩展节点的儿子节点  
256.         {  
257.             for(int i=E.s; i<n; i++)  

258.             {  
259.                 Swap(E.x[E.s],E.x[i]);  
260.                 int f1,f2;  
261.                 int bb = Bound(E,f1,f2,y);  
262.                 if(bb<bestc)  
263.                 {  
264.                     //子树可能含有最优解  
265.                     //节点插入最小堆  
266.                     MinHeapNode N;  
267.                     N.NewNode(E,f1,f2,bb,n);  
268.                     H.Insert(N);  
269.                 }  
270.                 Swap(E.x[E.s],E.x[i]);  
271.             }  
272.             delete []E.x;//完成节点扩展  
273.         }  
274.         if(H.Size() == 0)  
275.         {  
276.             break;  
277.         }  
278.         H.DeleteMin(E);//取下一扩展节点  
279.     }  
280.     return bestc;  
281. }  
282.   
283. template <class Type>  
284. inline void Swap(Type &a, Type &b)  
285. {   
286.     Type temp=a;   
287.     a=b;   
288.     b=temp;  
289. }  
     程序运行结果如图：

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）