多机调度问题报告.doc

湖南涉外经济学院计算机科学与技术专业

《算法设计与分析》课程

多机调度问题

实验报告

班级：计科1002

学号：

姓名：

教师：

成绩：

2023年5月

【实验目的】

1掌握贪心算法

2利用贪心算法解决多机调度问题

3分析实验结果，是否能将机器处理时间最短化

【系统环境】

Windows7平台

【实验工具】

VC++6.0英文企业版

【问题描述】

描述：设有n个独立的作业{1,2，…，n}，由m台相同的机器进行加工处理。作业i所需的处理时间为t。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。

多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

例：设7个独立作业{1,2,3,4,5,6,7}有3台机器m1，m2，m3来加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。现要求用贪心算法给出最优解。

【实验原理】

贪心算法的应用，该算法总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

贪心法根本策略：

分析问题性质，确定适当的贪心选择标准；

按贪心选择标准对n个输入进行排序，初始化局部解；

按序每次输入一个量，如果这个输入和当前已构成在这种选择标准下的局部解加在一起不能产生一个可行解，那么此输入不能参加到局部解中，否那么形成新的局部解；

继续处理下一输入，直至n个输入处理完毕，最终的局部解即 为此问题的最优解。

【源程序代码】

#include<stdio.h>

#defineN10

typedefstructnode

{

intID,time;//作业所需时间

}jobnode;

typedefstructNode

{

intID,avail;//ID机器编号avail每次作业的初始时间

}manode;

manodemachine[N];

jobnodejob[N];

/*

找出下个作业执行机器

*/

manode*Find_min(manodea[],intm)

{

manode*temp=&a[0];

for(inti=1;i<m;i++)

{

if(a[i].avail<temp->avail)

temp=&a[i];

}

returntemp;

}

/*

对作业时间由大到小进行排序

*/

voidSort(jobnodet[],intn)

{

jobnodetemp;

for(inti=0;i<n-1;i++)

for(intj=n-1;j>i;j--)

{

if(job[j].time>job[j-1].time)

{

temp=job[j];

job[j]=job[j-1];

job[j-1]=temp;

}

}

}

voidmain()

{

intn,m,temp,i;

manode*ma;

printf("输入作业数目(作业编号按输入顺序处理)\n");

scanf("%d",&n);

printf("输入相应作业所需处理时间:\n");

for(i=0;i<n;i++)

{

scanf("%d",&job[i].time);

job[i].ID=i+1;

}

printf("输入机器数目(机器编号按输入顺序处理)\n");

scanf("%d",&m);

for(i=0;i<m;i++)//给机器进行编号并初始化

{

machine[i].ID=i+1;

machine[i].avail=0;

}

putchar('\n');

if(n<=m)

{

printf("为每个作业分配一台机器,可完成任务!\n");

return;

}

Sort(job,n);

for(i=0;i<n;i++)

{

ma=Find_min(machine,m);

printf("将机器:M%d从%d----->%d的时间段分配给作业:%d\n",ma->ID,ma->avail,ma->avail+job[i].time,job[i].ID);

ma->avail+=job[i].time;

}

temp=machine[0].avail;

for(i=1;i<m;i++)

{

if(machine[i].avail>temp)

temp=machine