基本题一：多机调度问题
一、实验目的与要求
1、熟悉多机调度问题的算法；
2、初步掌握贪心算法；
二、实验题
要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
三、实验提示
1、把作业按加工所用的时间从大到小排序
2、如果作业数目比机器的数目少或相等，则直接把作业分配下去
3、 如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。
typedef struct Job
{
int ID;//作业号
int time;//作业所花费的时间
}Job;
typedef struct JobNode //作业链表的节点
{
int ID;
int time;
JobNode *next;
}JobNode,*pJobNode;
typedef struct Header //链表的表头
{
int s;
pJobNode next;
}Header,pHeader;
int SelectMin(Header* M,int m)
{
int k=0;
for(int i=1;i<m;i++)
{
if(M[i].s<m[k].s)k=i;
}
return k;
}
四、源代码
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 7
#define M 3
typedef struct job
{
int ID;
int time;
} Job;
typedef struct machine
{
int ID;
int avail;
} Machine;
Job a[N]={{1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3}}; //原始作业数据，from:教材
vector<Job> m_vec_job;
vector<Machine> m_vec_machine;
bool UDgreater(Job elem1,Job elem2)
{
return elem1.time>elem2.time;
}
bool UDless(Machine elem1,Machine elem2)
{
return elem1.avail<elem2.avail;
}
int main()
{
if(M>N)
cout<<"给每个任务分配一台机器即可"<<endl;
for (int i=0;i<N;i++)
{
m_vec_job.push_back(a[i]);
}
sort(m_vec_job.begin(),m_vec_job.end(),UDgreater); //作业按时间长度排序完毕
// cout<<m_vec_job[0].ID<<endl; //作业是按照时间从大到小排列的
for (i=0;i<M;i++)
{
Machine tmp={i+1,0}; //机器的编号是从1开始的
m_vec_machine.push_back(tmp);
}
for(i=0;i<N;i++)
{
vector<Machine>::iterator it;
it = min_element(m_vec_machine.begin(),m_vec_machine.end(),UDless);
cout<<"将机器"<<(*it).ID<<"从"<<(*it).avail<<"到"<<(*it).avail+ m_vec_job[i].time<<"的时间段分配给作业"<<m_vec_job[i].ID<<endl;
(*it).avail+=m_vec_job[i].time;
}
return 0;
}
结果：
本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/824847
