0026算法笔记——【贪心算法】多机调度问题.docx

1、问题描述 设有n个独立的作业1, 2, , n, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内由m台机器加工处理完成。 多机调度问题是一个NP完全问题，到目前为止还没有完全有效的解法。对于这类问题，用贪心选择策略有时可以设计出一个比较好的近似算法。 2、贪心算法求解思路 采用最长处理时间作业优先的贪心策略: 当nm时, 只要将机器i的0, ti时间区间分配给作业i即可。 当nm时, 将n个作业依其所需的处理时间从大到小排序,然后依次将作业分配给空闲的处理机。 具体代码如下： (1)MinHeap.hcppview plaincopy1. #include2. usingnamespacestd;3. template4. classMinHeap5. 6. private:7. T*heap;/元素数组，0号位置也储存元素8. intCurrentSize;/目前元素个数9. intMaxSize;/可容纳的最多元素个数10. 11. voidFilterDown(constintstart,constintend);/自上往下调整，使关键字小的节点在上12. voidFilterUp(intstart);/自下往上调整13. 14. public:15. MinHeap(intn=1000);16. MinHeap();17. boolInsert(constT&x);/插入元素18. 19. TRemoveMin();/删除最小元素20. TGetMin();/取最小元素21. 22. boolIsEmpty()const;23. boolIsFull()const;24. voidClear();25. ;26. 27. template28. MinHeap:MinHeap(intn)29. 30. MaxSize=n;31. heap=newTMaxSize;32. CurrentSize=0;33. 34. 35. template36. MinHeap:MinHeap()37. 38. deleteheap;39. 40. 41. template42. voidMinHeap:FilterUp(intstart)/自下往上调整43. 44. intj=start,i=(j-1)/2;/i指向j的双亲节点45. Ttemp=heapj;46. 47. while(j0)48. 49. if(heapi=temp)50. break;51. else52. 53. heapj=heapi;54. j=i;55. i=(i-1)/2;56. 57. 58. heapj=temp;59. 60. 61. template62. voidMinHeap:FilterDown(constintstart,constintend)/自上往下调整，使关键字小的节点在上63. 64. inti=start,j=2*i+1;65. Ttemp=heapi;66. while(j=end)67. 68. if(jheapj+1)69. j+;70. if(temp=heapj)71. break;72. else73. 74. heapi=heapj;75. i=j;76. j=2*j+1;77. 78. 79. heapi=temp;80. 81. 82. template83. boolMinHeap:Insert(constT&x)84. 85. if(CurrentSize=MaxSize)86. returnfalse;87. 88. heapCurrentSize=x;89. FilterUp(CurrentSize);90. 91. CurrentSize+;92. returntrue;93. 94. 95. template96. TMinHeap:RemoveMin()97. 98. Tx=heap0;99. heap0=heapCurrentSize-1;100. 101. CurrentSize-;102. FilterDown(0,CurrentSize-1);/调整新的根节点103. 104. returnx;105. 106. 107. template108. TMinHeap:GetMin()109. 110. returnheap0;111. 112. 113. template114. boolMinHeap:IsEmpty()const115. 116. returnCurrentSize=0;117. 118. 119. template120. boolMinHeap:IsFull()const121. 122. returnCurrentSize=MaxSize;123. 124. 125. template126. voidMinHeap:Clear()127. 128. CurrentSize=0;129. (2)4d7.cppcppview plaincopy1. /4d7贪心算法多机调度问题2. #includestdafx.h3. #includeMinHeap.h4. #include5. #include6. usingnamespacestd;7. 8. constintN=7;/作业个数9. constintM=3;/机器台数10. ifstreamfin(4d7.txt);11. 12. classJobNode13. 14. /friendvoidGreedy(JobNode,int,int);15. /friendintmain(void);16. public:17. operatorint()const18. 19. returntime;20. 21. /private:22. intID,time;23. ;24. 25. classMachineNode26. 27. /friendvoidGreedy(JobNode,int,int);28. public:29. operatorint()const30. 31. returnavail;32. 33. /private:34. intID,avail;35. ;36. 37. template38. voidGreedy(Typea,intn,intm);39. 40. template41. voidSelectSort(Typea,intn);42. 43. intmain()44. 45. JobNodeaN+1;/各作业所需要的处理时间46. 47. cout各作业所需要的处理时间为：endl;48. for(inti=1;iai.IDai.time;51. coutID:ai.ID,time:ai.timeendl;52. 53. Greedy(a,N,M);54. return0;55. 56. 57. template58. voidGreedy(Typea,intn,intm)59. 60. if(n=m)/机器数量比作业数量多，直接分配61. 62. cout直接为每个作业分配一台机器.endl;63. return;64. 65. 66. SelectSort(a,n);/排序，从大到小67. MinHeapH(m);68. MachineNodex;69. 70. for(inti=1;i=m;i+)71. 72. x.avail=0;73. x.ID=i;74. H.Insert(x);75. 76. 77. for(inti=1;i=n;i+)78. 79. x=H.RemoveMin();80. cout将机器x.ID从x.avail到81. (x.avail+ai.time)的时间段分配给作业82. ai.IDendl;83. x.avail+=ai.time;84. H.Insert(x);/根据新的avail值将x插入Heap中适当位置85. 86. 87. 88. template89. voidSelectSort(Typea,intn)90. 91. Typetemp;92