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

1、.【分支限界法】批处理作业调度问题 问题描述 给定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。易见，最佳调度方

2、案是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,因为

3、是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上t1pk。 如果不能做到上面这一点，则s1只会增加，从而有：。 类似地，如果从节点E开始到节点L的路上，从作业pr+1开始，机器2没有空闲时间，则： 同理可知，s2是的下界。由此得到在节点E处相应子树中叶节点完成时间和的下界是： 注意到如果选择Pk，使t1pk在k=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。 这可以作为优先队列式分支限界法中的限界函数。 算法描述 算法中用最小堆表示活节点优先队列。最小堆中元素类型是MinHeapNode。每一个MinHeapNode类型的节点

4、包含域x,用来表示节点所相应的作业调度。s表示该作业已安排的作业时x1:s。f1表示当前已安排的作业在机器1上的最后完成时间；f2表示当前已安排作业在机器2上的完成时间；sf2表示当前已安排的作业在机器2上的完成时间和；bb表示当前完成时间和下界。二维数组M表示所给的n个作业在机器1和机器2所需的处理时间。在类Flowshop中用二维数组b存储排好序的作业处理时间。数组a表示数组M和b的对应关系。算法Sort实现对各作业在机器1和2上所需时间排序。函数Bound用于计算完成时间和下界。 函数BBFlow中while循环完成对排列树内部结点的有序扩展。在while循环体内算法依次从活结点优先队列

5、中取出具有最小bb值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。 算法将当前扩展节点E分两种情形处理：1)首先考虑E.s=n的情形，当前扩展结点E是排列树中的叶结点。E.sf2是相应于该叶结点的完成时间和。当E.sf2 bestc时更新当前最优值bestc和相应的当前最优解bestx。 2)当E.sn时，算法依次产生当前扩展结点E的所有儿子结点。对于当前扩展结点的每一个儿子结点node，计算出其相应的完成时间和的下界bb。当bb bestc时，将该儿子结点插入到活结点优先队列中。而当bb bestc时，可将结点node舍去。 算法具体实现如下：1. #include2. 3. tem

6、plate4. classGraph;5. 6. template7. classMinHeap8. 9. template10. friendclassGraph;11. public:12. MinHeap(intmaxheapsize=10);13. MinHeap()deleteheap;14. 15. intSize()constreturncurrentsize;16. TMax()if(currentsize)returnheap1;17. 18. MinHeap&Insert(constT&x);19. MinHeap&DeleteMin(T&x);20. 21. voidIn

7、itialize(Tx,intsize,intArraySize);22. voidDeactivate();23. voidoutput(Ta,intn);24. private:25. intcurrentsize,maxsize;26. T*heap;27. ;28. 29. template30. voidMinHeap:output(Ta,intn)31. 32. for(inti=1;i=n;i+)33. coutai;34. coutendl;35. 36. 37. template38. MinHeap:MinHeap(intmaxheapsize)39. 40. maxsiz

8、e=maxheapsize;41. heap=newTmaxsize+1;42. currentsize=0;43. 44. 45. template46. MinHeap&MinHeap:Insert(constT&x)47. 48. if(currentsize=maxsize)49. 50. return*this;51. 52. inti=+currentsize;53. while(i!=1&xheapi/2)54. 55. heapi=heapi/2;56. i/=2;57. 58. 59. heapi=x;60. return*this;61. 62. 63. template6

9、4. MinHeap&MinHeap:DeleteMin(T&x)65. 66. if(currentsize=0)67. 68. coutEmptyheap!endl;69. return*this;70. 71. 72. x=heap1;73. 74. Ty=heapcurrentsize-;75. inti=1,ci=2;76. while(ci=currentsize)77. 78. if(ciheapci+1)79. 80. ci+;81. 82. 83. if(y=heapci)84. 85. break;86. 87. heapi=heapci;88. i=ci;89. ci*=

10、2;90. 91. 92. heapi=y;93. return*this;94. 95. 96. template97. voidMinHeap:Initialize(Tx,intsize,intArraySize)98. 99. deleteheap;100. heap=x;101. currentsize=size;102. maxsize=ArraySize;103. 104. for(inti=currentsize/2;i=1;i-)105. 106. Ty=heapi;107. intc=2*i;108. while(c=currentsize)109. 110. if(chea

11、pc+1)111. c+;112. if(y=heapc)113. break;114. heapc/2=heapc;115. c*=2;116. 117. heapc/2=y;118. 119. 120. 121. template122. voidMinHeap:Deactivate()123. 124. heap=0;125. 2、6d9.cppcppview plaincopy1. /批作业调度问题优先队列分支限界法求解2. #includestdafx.h3. #includeMinHeap2.h4. #include5. usingnamespacestd;6. 7. classF

12、lowshop;8. classMinHeapNode9. 10. friendFlowshop;11. public:12. operatorint()const13. 14. returnbb;15. 16. private:17. voidInit(int);18. voidNewNode(MinHeapNode,int,int,int,int);19. ints,/已安排作业数20. f1,/机器1上最后完成时间21. f2,/机器2上最后完成时间22. sf2,/当前机器2上完成时间和23. bb,/当前完成时间和下界24. *x;/当前作业调度25. ;26. 27. classF

13、lowshop28. 29. friendintmain(void);30. public:31. intBBFlow(void);32. private:33. intBound(MinHeapNodeE,int&f1,int&f2,bool*y);34. voidSort(void);35. intn,/作业数36. *M,/各作业所需的处理时间数组37. *b,/各作业所需的处理时间排序数组38. *a,/数组M和b的对应关系数组39. *bestx,/最优解40. bestc;/最小完成时间和41. bool*y;/工作数组42. ;43. 44. template45. inline

14、voidS&a,Type&b);46. 47. intmain()48. 49. intn=3,bf;50. intM132=2,1,3,1,2,3;51. 52. int*M=newint*n;53. int*b=newint*n;54. int*a=newint*n;55. bool*y=newbool*n;56. int*bestx=newintn;57. 58. for(inti=0;i=n;i+)59. 60. Mi=newint2;61. bi=newint2;62. ai=newint2;63. yi=newbool2;64. 65. cout各作业所需要的时间处理数组M(i,j

15、)值如下：endl;66. 67. for(inti=0;in;i+)68. 69. for(intj=0;j2;j+)70. 71. Mij=M1ij;72. 73. 74. 75. for(inti=0;in;i+)76. 77. cout(;78. for(intj=0;j2;j+)79. coutMij;80. cout);81. 82. coutendl;83. 84. Flowshopflow;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.

16、bestc=1000;/给初值92. 93. flow.BBFlow();94. 95. cout最优值是：flow.bestcendl;96. cout最优调度是：;97. 98. for(inti=0;in;i+)99. 100. cout(flow.bestxi+1);101. 102. coutendl;103. 104. for(inti=0;in;i+)105. 106. deleteMi;107. deletebi;108. deleteai;109. deleteyi;110. 111. return0;112. 113. 114. /最小堆节点初始化115. voidMinH

17、eapNode:Init(intn)116. 117. x=newintn;118. for(inti=0;in;i+)119. 120. xi=i;121. 122. s=0;123. f1=0;124. f2=0;125. sf2=0;126. bb=0;127. 128. 129. /最小堆新节点130. voidMinHeapNode:NewNode(MinHeapNodeE,intEf1,intEf2,intEbb,intn)131. 132. x=newintn;133. for(inti=0;in;i+)134. 135. xi=E.xi;136. 137. f1=Ef1;138

18、. f2=Ef2;139. sf2=E.sf2+f2;140. bb=Ebb;141. s=E.s+1;142. 143. 144. /对各作业在机器1和2上所需时间排序145. voidFlowshop:Sort(void)146. 147. int*c=newintn;148. for(intj=0;j2;j+)149. 150. for(inti=0;in;i+)151. 152. bij=Mij;153. ci=i;154. 155. 156. for(inti=0;ii;k-)159. 160. if(bkjbk-1j)161. 162. Swap(bkj,bk-1j);163. S

19、wap(ck,ck-1);164. 165. 166. 167. 168. for(inti=0;in;i+)169. 170. acij=i;171. 172. 173. 174. deletec;175. 176. 177. /计算完成时间和下界178. intFlowshop:Bound(MinHeapNodeE,int&f1,int&f2,bool*y)179. 180. for(intk=0;kn;k+)181. 182. for(intj=0;j2;j+)183. 184. ykj=false;185. 186. 187. 188. for(intk=0;k=E.s;k+)189.

20、 190. for(intj=0;jE.f2)?f1:E.f2)+ME.xE.s1;198. intsf2=E.sf2+f2;199. ints1=0,s2=0,k1=n-E.s,k2=n-E.s,f3=f2;200. 201. /计算s1的值202. for(intj=0;jf1+bj0)?f2:f1+bj0;210. 211. s1+=f1+k1*bj0;212. 213. 214. 215. /计算s2的值216. for(intj=0;js2)?s1:s2);228. 229. 230. /解批处理作业调度问题的优先队列式分支限界法231. intFlowshop:BBFlow(void)232. 233. Sort();/对各作业在机器1和2上所需时间排序234. MinHeapH(1000);235. 236. MinHeapNodeE;237.