下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《草坪建植与养护学》试卷-1(答案及评分标准)
- (2025年)中小学教师副高水平能力测试题附答案
- (完整版)电工试题库-含答案
- (完整版)5G试题及答案
- (完整版)急性中毒试题及答案
- 2025财税专业知识摸拟测试题(三)(有答案)
- 2025 年百科知识题库及答案
- (2025年)(完整)三基三严考试试题及参考答案
- (2026)消防法考试题库及参考答案
- 《医疗器械经营质量管理规范》培训试卷及答案
- 江苏无锡市2026-2027学年高三上学期期中考试语文试题
- 高压配电柜安全操作规程
- 老年人抗菌药物的使用与注意事项
- 2026年护士条例学习解读课件(含案例分析)
- 2026年湖南普通高中学业水平选择性考试化学真题及答案
- 露天矿山开采施工方案
- 钠离子电池用硬炭负极材料技术要求
- 驾驶服务外包投标方案
- DLT 5035-2016 发电厂供暖通风与空气调节设计规范
- 评茶员培训教案
- 工程造价咨询服务投标方案(专家团队版-)
评论
0/150
提交评论