分支限界法批处理调度问题.docx
- 文档编号:9411451
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:20
- 大小:121.09KB
分支限界法批处理调度问题.docx
《分支限界法批处理调度问题.docx》由会员分享,可在线阅读,更多相关《分支限界法批处理调度问题.docx(20页珍藏版)》请在冰点文库上搜索。
分支限界法批处理调度问题
【分支限界法】批处理作业调度问题
问题描述
给定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上开始处理,即从pr+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 2)当E.s 对于当前扩展结点的每一个儿子结点node,计算出其相应的完成时间和的下界bb。 当bb 而当bbbestc时,可将结点node舍去。 算法具体实现如下: 1.#include 2. 3.template 4.class Graph; 5. 6.template 7.class MinHeap 8.{ 9. template 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 19. MinHeap 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 30.void MinHeap : 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 38.MinHeap : MinHeap(int maxheapsize) 39.{ 40. maxsize = maxheapsize; 41. heap = new T[maxsize + 1]; 42. currentsize = 0; 43.} 44. 45.template 46.MinHeap : 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 64.MinHeap : DeleteMin(T& x) 65.{ 66. if(currentsize == 0) 67. { 68. cout<<"Empty heap! "< 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 97.void MinHeap : 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 122.void MinHeap : Deactivate() 123.{ 124. heap = 0; 125.} 2、6d9.cpp [cpp] viewplain copy 1.//批作业调度问题 优先队列分支限界法求解 2.#include "stdafx.h" 3.#include "MinHeap2.h" 4.#include 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 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)值如下: "< 66. 67. for(int i=0;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 76. { 77. cout<<"("; 78. for(int j=0;j<2;j++) 79. cout< 80. cout<<")"; 81. } 82. cout< 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<<"最优值是: "< 96. cout<<"最优调度是: "; 97. 98. for(int i=0;i 99. { 100. cout<<(flow.bestx[i]+1)<<" "; 101. } 102. cout< 103. 104. for(int i=0;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 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 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 151. { 152. b[i][j] = M[i][j]; 153. c[i] = i; 154. } 155. 156. for(int i=0; i 157. { 158. for(int k=n-1; k>i; k--) 159. { 160. if(b[k][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 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 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]; 19
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分支 限界 批处理 调度 问题