独立任务最优调度 C++程序.docx
- 文档编号:9330158
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:27
- 大小:19.59KB
独立任务最优调度 C++程序.docx
《独立任务最优调度 C++程序.docx》由会员分享,可在线阅读,更多相关《独立任务最优调度 C++程序.docx(27页珍藏版)》请在冰点文库上搜索。
独立任务最优调度C++程序
独立任务最优调度问题
【问题描述:
】
用2台处理机A和B处理n个作业。
设第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。
由于各作业的特点和机器的性能关系,很可能对于某些i,有ai≥bi,而对于某些j,j≠i,有aj 既不能将一个作业分开由2台机器处理,也没有一台机器能同时处理2个作业。 设计一个动态规划算法,使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。 研究一个实例: (a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2);(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)。 【编程任务】: 对于给定的2台处理机A和B处理n个作业,找出一个最优调度方案,使2台机器处理完这n个作业的时间最短。 【数据输入】: 由文件input.txt提供输入数据。 文件的第1行是1个正整数n,表示要处理n个作业。 接下来的2行中,每行有n个正整数,分别表示处理机A和B处理第i个作业需要的处理时间。 【结果输出】: 程序运行结束时,将计算出的最短处理时间输出到文件output.txt中。 【算法思路】: 对于算法来说,没有最好,只有更好,算法的结果不一定是最佳答案,但至少是最接近最佳答案的。 在权衡算法时间复杂度和空间复杂度的情况下,找到一个在时间和空间都能接受的算法才是上上之策。 本例采样贪心算法的思想,但又不是严格意义上的贪心算法。 思路: 1)、把n个任务按一定规则分别存储到二维数组a[][]和b[][]中,规则,对任意i满足a[i][0] 时间复杂度为O(n)。 2)、对数组a[][]&b[][]排序: 数组a[][]按a[i][0]的大小进行降序排列,对于a[i][0]==a[i+1][0]时按a[i][1]进行降序排列。 同理数组b[][]。 时间复杂度为O(NlogN) 3)、优先使机器A&B分别处理数组A&B中的任务。 4)、当A或B先处理好自己的时,在B或A还有剩余的整数个任务时再按照如下规则处理,首先把剩余的整数个任务按(s[i][0]-s[i][1])的大小进行生序排列,时间复杂度为O(NlogN) a)、若是A先于B处理完任务,则,则A优先选做间隔时间大的任务,可以理解无,节省的时间多。 b)、若是B先于A处理完任务,则,则B优先选做间隔时间小的任务,可以理解无,浪费的时间少。 5)、计算机器A&B的处理时间,则最小处理时间ShortestTime=Max(TimeA,TimeB) 6)、把ShortestTime导入到output.txt文件中。 详细代码程序: //IndependentTask.h #ifndefINDEPENDENTTASK_H #defineINDEPENDENTTASK_H classIndependentTask { public: IndependentTask(); ~IndependentTask(); voidrun();//运行接口 private: intnumber;//任务数量 intcountA;//在机器A上用时间较少的任务个数 intcountB;//在机器B上用时间较少的任务个数 intShortestTime;//记录最短处理时间 int**s;//存储number个任务在机器A&B的用时 int**a;//存储在机器A上用时间较少的任务 int**b;//存储在机器A上用时间较少的任务 boolinput();//输入接口 voidsort(int**s,inti,intj,intX);//快速排序X=0120-a[][]1--b[][]2--a[][]或b[][] voidOptimizationSorting(int**s,intlength,intX);//优化排序目的是降低处理时间和显示已排好序的数据 //X=0--a[][]X=1---b[][] voidoutput();//输出显示 }; #endif //IndependentTask.cpp #include #include #include #include #include"IndependentTask.h" #defineN50//预定义50个任务数根据实际问题大小来确定不要太大 ifstreaminputFile("input.txt",ios: : in); ofstreamoutputFile("output.txt",ios: : out); IndependentTask: : IndependentTask() { number=0; countA=0; countB=0; ShortestTime=0; s=newint*[N]; a=newint*[N]; b=newint*[N]; for(inti=0;i { s[i]=newint[2]; a[i]=newint[2]; b[i]=newint[2]; } } IndependentTask: : ~IndependentTask() { for(inti=0;i { delete[]s[i]; delete[]a[i]; delete[]b[i]; } delete[]s; delete[]a; delete[]b; } voidIndependentTask: : run() { if(input()) { sort(a,0,countA-1,0); sort(b,0,countB-1,1); OptimizationSorting(a,countA,0); OptimizationSorting(b,countB,1); output(); } } boolIndependentTask: : input() { inputFile>>number; outputFile<<"总任务个数: "< for(intj=0;j<2;j++)//j==0时读取的是在机器A上作业用时 {//j==1时读取的是在机器B上作业用时 if(j==0) { outputFile<<"各个任务在机器A上处理用时为: "; } else { outputFile<<"各个任务在机器B上处理用时为: "; } for(inti=0;i { inputFile>>s[i][j]; outputFile< } outputFile< } outputFile< inputFile.close(); for(inti=0;i { if(s[i][0] { a[countA][0]=s[i][0]; a[countA][1]=s[i][1]; countA++; } else { b[countB][0]=s[i][0]; b[countB][1]=s[i][1]; countB++; } } //显示在机器A上处理用时少的任务 outputFile< "< for(j=0;j<2;j++) { if(j==0) { outputFile<<"在机器A上处理用时为: "; } else { outputFile<<"在机器B上处理用时为: "; } for(inti=0;i { outputFile< } outputFile< } outputFile< //显示在机器B上处理用时少的任务 outputFile< "< for(j=0;j<2;j++) { if(j==0) { outputFile<<"在机器A上处理用时为: "; } else { outputFile<<"在机器B上处理用时为: "; } for(inti=0;i { outputFile< } outputFile< } outputFile< if(s! =NULL) { if(a! =NULL||b! =NULL) { returntrue; } returnfalse; } returnfalse; } voidIndependentTask: : sort(int**s,inti,intj,intX)//对在机器A上用时较少的任务按机器A处理时间降序排列 { if(i { intleft=i; intright=j; intpivot; if(X==0||X==1) { pivot=s[left][X]; } else { pivot=s[left][0]-s[left][1]; } j++; while(i { while(i { if(X==0||X==1) { if(s[++i][X]>pivot)//从左边寻找第一个小于等于pivot的值 { continue; } break; } else { if((s[++i][0]-s[++i][1]) { continue; } break; } } while(j>left) { if(X==0||X==1) { if(s[--j][X] { continue; } break; } else { if((s[--j][0]-s[--j][1])>pivot)//升序排列 { continue; } break; } } if(i {//a[i][]和a[j][]交换 intt; t=s[i][0]; s[i][0]=s[j][0]; s[j][0]=t; t=s[i][1]; s[i][1]=s[j][1]; s[j][1]=t; } } {//a[left][]和a[j][]交换 intt; t=s[left][0]; s[left][0]=s[j][0]; s[j][0]=t; t=s[left][1]; s[left][1]=s[j][1]; s[j][1]=t; } sort(s,left,j-1,X); sort(s,i,right,X); }//已经对a[i][X]排好序 } voidIndependentTask: : OptimizationSorting(int**s,intlength,intX) { for(intk=0;k>0;k++) {//对已经排序好的s[i][0]在s[i][x]==a[i+1][x]情况下按s[i][~x]降序排列目的是降低机器处理时间 intflag=0; for(inti=0;i { if(s[i][X]==s[i+1][X]) { intY=(X+1)%2; if(s[i][Y] { intt;//降序 t=s[i][Y]; s[i][Y]=s[i+1][Y]; s[i+1][Y]=t; flag++; } } } if(flag==0) { break; } } //输出已经排序好的在机器A上用时较少的任务 outputFile< 'A': 'B')<<"上用时较少的任务: "< for(intj=0;j<2;j++) { if(j==0) { outputFile<<"在机器A上处理用时为: "; } else { outputFile<<"在机器B上处理用时为: "; } for(inti=0;i { outputFile< } outputFile< } outputFile< } voidIndependentTask: : output() { intsumA=0;//机器A用时 intsumB=0;//机器A用时 for(inti=0;i { sumA+=a[i][0]; } for(i=0;i { sumB+=b[i][1]; } outputFile<<"假如所有在机器A上处理时间较少的任务都在机器A上处理,需要时间为: "< outputFile<<"假如所有在机器B上处理时间较少的任务都在机器B上处理,需要时间为: "< if(sumA==sumB) { ShortestTime=sumA; outputFile< "< outputFile<<"在机器A上处理任务有: "< for(intj=0;j<2;j++) { if(j==0) { outputFile<<"在机器A上处理用时为: "; } else { outputFile<<"在机器B上处理用时为: "; } for(inti=0;i { outputFile< } outputFile< } outputFile< outputFile<<"在机器B上处理任务有: "< for(j=0;j<2;j++) { if(j==0) { outputFile<<"在机器A上处理用时为: "; } else { outputFile<<"在机器B上处理用时为: "; } for(inti=0;i { outputFile< } outputFile< } outputFile< return; } elseif(sumA>sumB)//相当于机器B先于A完成任务 { intcount=0;//记录机器A剩下任务个数 for(inti=countA-1;i>=1;i--) { intTimeA=sumA; if((TimeA-a[i][0])>=sumB)//等号成立说明在B结束时A刚好处理好某个任务 { TimeA-=a[i][0]; count++; continue; } break; } if((count==0)||(count==1&&(sumA<=(sumB+a[countA-1][1])))) { ShortestTime=sumA; outputFile< "< outputFile<<"机器A处理任务用的时间为: "< outputFile<<"在机器A上处理任务有: "< for(intj=0;j<2;j++) { if(j==0) { outputFile<<"在机器A上处理用时为: "; } else { outputFile<<"在机器B上处理用时为: "; } for(inti=0;i { outputFile< } outputFile< } outputFile< outputFile<<"机器B处理任务用的时间为: "< outputFile<<"在机器B上处理任务有: "< for(j=0;j<2;j++) { if(j==0) { outputFile<<"在机器A上处理用时为: "; } else { outputFile<<"在机器B上处理用时为: "; } for(inti=0;i { outputFile< } outputFile< } outputFile< return; } else { sort(a,countA-count,countA-1,3);//按间隔排序间隔恒小于等于0间隔最小反而最大 intm=0;//记录机器B可以帮助机器A处理任务的个数 for(inti=countA-1;i>=1;i--)//机器B优先处理间隔小的任务浪费时间少 { if((sumB+a[i][1]) { m++; sumB+=a[i][1]; sumA-=a[i][0]; continue; } break; } ShortestTime=sumA; outputFile< "< outputFile< "< outputFile<<"在机器B上处理的任务有"<<(countB+m)<<"个,处理时间为: "< outputFile<<"在机器B上处理的任务有: "< for(intj=0;j<2;j++) { if(j==0) { outputFile<<"在机器A上处理用时为: "; } else { outputFile<<"在机器B上处理用时为: "; } for(inti=0;i { outputFile< } outputFile<<""; for(i=countA-1;i>=countA-m;i--)//A帮B处理最后m个任务 { outputFile< } outputFile< } outputFile< outputFile<<"在机器A上处理的任务有"<<(countA-m)<<"个,处理时间为: "< outputFile<<"在机器A上处理任务有: "< for(j=0;j<2;j++) { if(j==0) { outputFile<<"在机器A上处理用时为: "; } else { outputFile<<"在机器B上处理用时为: "; } for(inti=0;i { outputFile< } outputFile<<""; for(i=countA-count;i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 独立任务最优调度 C+程序 独立 任务 最优 调度 C+ 程序