现在的位置: 首页 > 综合 > 正文

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

2017年11月05日 ⁄ 综合 ⁄ 共 5071字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

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

分类： 算法2013-03-30
17:51 382人阅读 评论(0) 收藏 举报
多机调度问题算法笔记贪心算法最小堆

     1、问题描述

     设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内由m台机器加工处理完成。 

     多机调度问题是一个NP完全问题，到目前为止还没有完全有效的解法。对于这类问题，用贪心选择策略有时可以设计出一个比较好的近似算法。

     2、贪心算法求解思路

     采用最长处理时间作业优先的贪心策略:
     当n≤m时, 只要将机器i的[0, ti]时间区间分配给作业i即可。
     当n>m时, 将n个作业依其所需的处理时间从大到小排序,然后依次将作业分配给空闲的处理机。

      具体代码如下：

     (1)MinHeap.h

[cpp] view
plaincopy

  1. #include <iostream>  
  2. using namespace std;  
  3. template<class T>  
  4. class MinHeap  
  5. {  
  6.     private:  
  7.         T *heap; //元素数组，0号位置也储存元素  
  8.         int CurrentSize; //目前元素个数  
  9.         int MaxSize; //可容纳的最多元素个数  
  10.   
  11.         void FilterDown(const int start,const int end); //自上往下调整，使关键字小的节点在上  
  12.         void FilterUp(int start); //自下往上调整  
  13.   
  14.     public:  
  15.         MinHeap(int n=1000);  
  16.         ~MinHeap();  
  17.         bool Insert(const T &x); //插入元素  
  18.   
  19.         T RemoveMin(); //删除最小元素  
  20.         T GetMin(); //取最小元素  
  21.   
  22.         bool IsEmpty() const;  
  23.         bool IsFull() const;  
  24.         void Clear();  
  25. };  
  26.   
  27. template<class T>  
  28. MinHeap<T>::MinHeap(int n)  
  29. {  
  30.     MaxSize=n;  
  31.     heap=new T[MaxSize];  
  32.     CurrentSize=0;  
  33. }  
  34.   
  35. template<class T>  
  36. MinHeap<T>::~MinHeap()  
  37. {  
  38.     delete []heap;  
  39. }  
  40.   
  41. template<class T>  
  42. void MinHeap<T>::FilterUp(int start) //自下往上调整  
  43. {  
  44.     int j=start,i=(j-1)/2; //i指向j的双亲节点  
  45.     T temp=heap[j];  
  46.   
  47.     while(j>0)  
  48.     {  
  49.         if(heap[i]<=temp)  
  50.             break;  
  51.         else  
  52.         {  
  53.             heap[j]=heap[i];  
  54.             j=i;  
  55.             i=(i-1)/2;  
  56.         }  
  57.     }  
  58.     heap[j]=temp;  
  59. }  
  60.   
  61. template<class T>  
  62. void MinHeap<T>::FilterDown(const int start,const int end) //自上往下调整，使关键字小的节点在上  
  63. {  
  64.     int i=start,j=2*i+1;  
  65.     T temp=heap[i];  
  66.     while(j<=end)  
  67.     {  
  68.         if( (j<end) && (heap[j]>heap[j+1]) )  
  69.             j++;  
  70.         if(temp<=heap[j])  
  71.             break;  
  72.         else  
  73.         {  
  74.             heap[i]=heap[j];  
  75.             i=j;  
  76.             j=2*j+1;  
  77.         }  
  78.     }  
  79.     heap[i]=temp;  
  80. }  
  81.   
  82. template<class T>  
  83. bool MinHeap<T>::Insert(const T &x)  
  84. {  
  85.     if(CurrentSize==MaxSize)  
  86.         return false;  
  87.   
  88.     heap[CurrentSize]=x;  
  89.     FilterUp(CurrentSize);  
  90.   
  91.     CurrentSize++;  
  92.     return true;  
  93. }  
  94.   
  95. template<class T>  
  96. T MinHeap<T>::RemoveMin( )  
  97. {  
  98.     T x=heap[0];  
  99.     heap[0]=heap[CurrentSize-1];  
  100.   
  101.     CurrentSize--;  
  102.     FilterDown(0,CurrentSize-1); //调整新的根节点  
  103.   
  104.     return x;  
  105. }  
  106.   
  107. template<class T>  
  108. T MinHeap<T>::GetMin()  
  109. {  
  110.     return heap[0];  
  111. }  
  112.   
  113. template<class T>  
  114. bool MinHeap<T>::IsEmpty() const  
  115. {  
  116.     return CurrentSize==0;  
  117. }  
  118.   
  119. template<class T>  
  120. bool MinHeap<T>::IsFull() const  
  121. {  
  122.     return CurrentSize==MaxSize;  
  123. }  
  124.   
  125. template<class T>  
  126. void MinHeap<T>::Clear()  
  127. {  
  128.     CurrentSize=0;  
  129. }  

     (2)4d7.cpp

[cpp] view
plaincopy

  1. //4d7 贪心算法 多机调度问题  
  2. #include "stdafx.h"  
  3. #include "MinHeap.h"  
  4. #include <iostream>   
  5. #include <fstream>    
  6. using namespace std;   
  7.   
  8. const int N = 7;//作业个数  
  9. const int M = 3;//机器台数  
  10. ifstream fin("4d7.txt");  
  11.   
  12. class JobNode  
  13. {  
  14.     //friend void Greedy(JobNode [],int,int);  
  15.     //friend int main(void);  
  16.     public:  
  17.         operator int() const  
  18.         {  
  19.             return time;  
  20.         }  
  21.     //private:  
  22.         int ID,time;  
  23. };  
  24.   
  25. class MachineNode  
  26. {  
  27.     //friend void Greedy(JobNode [],int,int);  
  28.     public:  
  29.         operator int() const  
  30.         {  
  31.             return avail;  
  32.         }  
  33.     //private:  
  34.         int ID,avail;  
  35. };  
  36.   
  37. template<class Type>    
  38. void Greedy(Type a[],int n,int m);  
  39.   
  40. template<class Type>    
  41. void SelectSort(Type a[],int n);  
  42.   
  43. int main()  
  44. {  
  45.     JobNode a[N+1] ;//各作业所需要的处理时间  
  46.   
  47.     cout<<"各作业所需要的处理时间为："<<endl;  
  48.     for(int i=1; i<=N; i++)  
  49.     {  
  50.         fin>>a[i].ID>>a[i].time;  
  51.         cout<<"ID:"<<a[i].ID<<",time:"<<a[i].time<<endl;  
  52.     }  
  53.     Greedy(a,N,M);  
  54.     return 0;  
  55. }  
  56.   
  57. template<class Type>    
  58. void Greedy(Type a[],int n,int m)  
  59. {  
  60.     if(n<=m)//机器数量比作业数量多，直接分配  
  61.     {  
  62.         cout<<"直接为每个作业分配一台机器."<<endl;  
  63.         return;  
  64.     }  
  65.       
  66.     SelectSort(a,n);//排序，从大到小  
  67.     MinHeap<MachineNode> H(m);  
  68.     MachineNode x;  
  69.   
  70.     for(int i=1; i<=m; i++)  
  71.     {  
  72.         x.avail = 0;  
  73.         x.ID = i;  
  74.         H.Insert(x);  
  75.     }  
  76.   
  77.     for(int i=1; i<=n; i++)  
  78.     {  
  79.         x = H.RemoveMin();  
  80.         cout<<"将机器"<<x.ID<<"从"<<x.avail<<"到"  
  81.             <<(x.avail+a[i].time)<<"的时间段分配给作业"  
  82.             <<a[i].ID<<endl;  
  83.         x.avail += a[i].time;  
  84.         H.Insert(x);//根据新的avail值将x插入Heap中适当位置  
  85.     }  
  86. }  
  87.   
  88. template<class Type>    
  89. void SelectSort(Type a[],int n)  
  90. {  
  91.     Type temp;    
  92.     int max;  
  93.     
  94.     for(int i=1;i<n;i++)    
  95.     {    
  96.         max=i;    
  97.         for(int j=i+1;j<=n;j++)    
  98.         {    
  99.             if(a[max]<a[j])    
  100.             {    
  101.                 max=j;    
  102.             }    
  103.         }    
  104.           
  105.         if(max != i)  
  106.         {  
  107.             temp = a[i];      
  108.             a[i] = a[max];      
  109.             a[max] = temp;    
  110.         }  
  111.     }    
  112. }  

     3、执行分析

     7个独立作业{1, 2, 3, 4, 5, 6, 7}由M1,M2和M3来加工处理各作业所需时间间分别为{2, 14, 4, 16, 6, 5, 3}。调度结果如下：


     4、复杂度

     n>m时, 排序耗时O(nlogn). 初始化堆耗时O(m). 堆的DeleteMin和insert 共需O(nlogm).因此算法Greedy 所需时间:O(nlogn)。

     程序执行结果如图：


返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞