C++贪心算法处理多机调度问题详解_第1页
C++贪心算法处理多机调度问题详解_第2页
C++贪心算法处理多机调度问题详解_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第C++贪心算法处理多机调度问题详解1、把作业按加工所用的时间从大到小排序

2、如果作业数目比机器的数目少或相等，则直接把作业分配下去

3、如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业

可以考虑以下的贪心策略:

(1)最长处理时间作业优先的贪心选择策略。

(2)最短处理时间作业优先的贪心选择策略。

(3)作业到达时间优先的贪心选择策略。

*贪⼼策略：优先处理花费时间长的任务，这样可以减少短任务的等待时间.

问题描述

形式：有n个任务，m台机器，nm，每个作业i可以选择⼀台设备进⾏加⼯，加⼯时间为ti，每台机器同时只能加⼯⼀个作业，且不可中断。实现作业调度，使得n个作业的等待时间最短。

假定有7个独立作业，所需处理时间分别为｛2，14，4，16，6，5，3｝，由三台机器M1,M2,M3加工。按照贪心算法产生的作业调度如下图所示，所需总加工时间为17.

代码实现【C++】

#includeiostream

usingnamespacestd;

#defineN7

#defineM3

ints[M]={0,0,0};

//求出目前处理作业的时间和最小的机器号

intmin(intm){

intmin=0;

inti;

for(i=1;ii++){

if(s[min]s[i]){

min=i;

returnmin;

//求最终结果（最长处理时间）

intmax(ints[],intnum){

intmax=s[0];

for(inti=1;ii++){

if(maxs[i])

max=s[i];

returnmax;

//机器数大于待分配作业数

intsetwork1(intt[],intn){

inti=0;

for(;ii++){

s[i]=t[i];

intma=max(s,N);

returnma;

//机器数小于待分配作业数

intsetwork2(intt[],intn){

inti;

intmi=0;

for(i=0;ii++){

mi=min(M);

cout"接下来由"mi+1"号机器处理任务"i+1endl;

s[mi]=s[mi]+t[i];

intma=max(s,M);

returnma;

voidmain()//DEV中是int,vc++6.0中是void

inttime[N]={16,14,6,5,4,3,2};//处理时间按从大到小排序

intmaxtime;

if(M=N)

maxtime=setwork1(time,N);

else

m

人人文库> 全部分类> 办公材料 > 办公文档

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论