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
#include <iostream>
using namespace std;
template<class T>
class MinHeap
{
private:
T *heap; //元素数组，0号位置也储存元素
int CurrentSize; //目前元素个数
int MaxSize; //可容纳的最多元素个数
void FilterDown(const int start,const int end); //自上往下调整，使关键字小的节点在上
void FilterUp(int start); //自下往上调整
public:
MinHeap(int n=1000);
~MinHeap();
bool Insert(const T &x); //插入元素
T RemoveMin(); //删除最小元素
T GetMin(); //取最小元素
bool IsEmpty() const;
bool IsFull() const;
void Clear();
};
template<class T>
MinHeap<T>::MinHeap(int n)
{
MaxSize=n;
heap=new T[MaxSize];
CurrentSize=0;
}
template<class T>
MinHeap<T>::~MinHeap()
{
delete []heap;
}
template<class T>
void MinHeap<T>::FilterUp(int start) //自下往上调整
{
int j=start,i=(j-1)/2; //i指向j的双亲节点
T temp=heap[j];
while(j>0)
{
if(heap[i]<=temp)
break;
else
{
heap[j]=heap[i];
j=i;
i=(i-1)/2;
}
}
heap[j]=temp;
}
template<class T>
void MinHeap<T>::FilterDown(const int start,const int end) //自上往下调整，使关键字小的节点在上
{
int i=start,j=2*i+1;
T temp=heap[i];
while(j<=end)
{
if( (j<end) && (heap[j]>heap[j+1]) )
j++;
if(temp<=heap[j])
break;
else
{
heap[i]=heap[j];
i=j;
j=2*j+1;
}
}
heap[i]=temp;
}
template<class T>
bool MinHeap<T>::Insert(const T &x)
{
if(CurrentSize==MaxSize)
return false;
heap[CurrentSize]=x;
FilterUp(CurrentSize);
CurrentSize++;
return true;
}
template<class T>
T MinHeap<T>::RemoveMin( )
{
T x=heap[0];
heap[0]=heap[CurrentSize-1];
CurrentSize--;
FilterDown(0,CurrentSize-1); //调整新的根节点
return x;
}
template<class T>
T MinHeap<T>::GetMin()
{
return heap[0];
}
template<class T>
bool MinHeap<T>::IsEmpty() const
{
return CurrentSize==0;
}
template<class T>
bool MinHeap<T>::IsFull() const
{
return CurrentSize==MaxSize;
}
template<class T>
void MinHeap<T>::Clear()
{
CurrentSize=0;
}
(2)4d7.cpp
//4d7 贪心算法 多机调度问题
#include "stdafx.h"
#include "MinHeap.h"
#include <iostream>
#include <fstream>
using namespace std;
const int N = 7;//作业个数
const int M = 3;//机器台数
ifstream fin("4d7.txt");
class JobNode
{
//friend void Greedy(JobNode [],int,int);
//friend int main(void);
public:
operator int() const
{
return time;
}
//private:
int ID,time;
};
class MachineNode
{
//friend void Greedy(JobNode [],int,int);
public:
operator int() const
{
return avail;
}
//private:
int ID,avail;
};
template<class Type>
void Greedy(Type a[],int n,int m);
template<class Type>
void SelectSort(Type a[],int n);
int main()
{
JobNode a[N+1] ;//各作业所需要的处理时间
cout<<"各作业所需要的处理时间为："<<endl;
for(int i=1; i<=N; i++)
{
fin>>a[i].ID>>a[i].time;
cout<<"ID:"<<a[i].ID<<",time:"<<a[i].time<<endl;
}
Greedy(a,N,M);
return 0;
}
template<class Type>
void Greedy(Type a[],int n,int m)
{
if(n<=m)//机器数量比作业数量多，直接分配
{
cout<<"直接为每个作业分配一台机器."<<endl;
return;
}
SelectSort(a,n);//排序，从大到小
MinHeap<MachineNode> H(m);
MachineNode x;
for(int i=1; i<=m; i++)
{
x.avail = 0;
x.ID = i;
H.Insert(x);
}
for(int i=1; i<=n; i++)
{
x = H.RemoveMin();
cout<<"将机器"<<x.ID<<"从"<<x.avail<<"到"
<<(x.avail+a[i].time)<<"的时间段分配给作业"
<<a[i].ID<<endl;
x.avail += a[i].time;
H.Insert(x);//根据新的avail值将x插入Heap中适当位置
}
}
template<class Type>
void SelectSort(Type a[],int n)
{
Type temp;
int max;
for(int i=1;i<n;i++)
{
max=i;
for(int j=i+1;j<=n;j++)
{
if(a[max]<a[j])
{
max=j;
}
}
if(max != i)
{
temp = a[i];
a[i] = a[max];
a[max] = temp;
}
}
}
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)。
程序执行结果如图：
