- 1、本文档共7页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
一种改进有限期作业排序算法研究
一种改进的有限期作业排序算法研究
摘要:提出了作业最晚运行次序的概念,改进算法的时间复杂度完全取决于排序算法的时间复杂度,并且改进算法可以直接得到最大效益作业子集的一种可行运行次序。
关键词:有限期作业;贪心方法;作业最晚运行次序;排序
中图分类号:TP301.6 文献标识码:A 文章编号:1672-3198(2010)02-0252-02
1 改进算法
1.1 算法思想
改进的有限期作业排序的贪心方法:取得最大效益的作业子集一定是运行作业数目最多的子集,在不考虑获得最大效益的前提下,首先将n个作业按有限期从小到大排序,然后求出在一批作业中CPU最多能运行的作业数目m(m* pData,int count)
{ int i,j;
int k;
Job* t;
for(i=0;ideadline(*pData)[j]-deadline)k=j;
if(k!=i){t=(*pData)[i];(*pData)[i]=(*pData)[k];(*pData)[k]=t;}
}
}
long runMostJobNumber(vector* pVecPJob)
{ int t=0;
int i;
for(i=0;ideadline )t++;
return t;
}
1.3 设置作业的最晚运行次序
作业最晚运行次序依赖于具体一个作业集合,同一个作业在不同作业集合中时其最晚运行次序值可能是不同的。如果一个作业在一个作业集中运行的次序大于它的最晚运行次序,那么无法获得该作业的效益值,因为CPU运行到改该作业时作业已过期。根据m给每个作业设置CPU运行该作业的最晚次序(lateRunOrder)。作业集仍按deadline从小到大有序,将排列中最后一个作业的最晚运行次序设为m。然后从排列倒数第二个作业开始依次给剩下的作业设置最晚运行次序,作业的最晚运行次序按以下原则设置:对于任一对相邻的两个作业,如果前一个作业的期限值小于它后面作业的期限值,那么前一个作业的最晚运行次序等于它后面一个作业最晚运行次序减1,否则两个作业的最晚运行次序相同。具体算法如下:
void setJobLateRunOrder(vector* pVecPJob,int mostJobNumber)
{ int i;
int lateRunOrder=mostJobNumber;
int s=(*pVecPJob).size();
((*pVecPJob)[s-1])-lateRunOrder=lateRunOrder;
for(i=s-2;i=0;i--){
if(((*pVecPJob)[i])-deadlinedeadline ){
lateRunOrder--;
((*pVecPJob)[i])-lateRunOrder=lateRunOrder;
}
else ((*pVecPJob)[i])-lateRunOrder=lateRunOrder;
}
}
1.4 求解作业集的最大效益
定义一个能存储m个Job对象的数组,数组初始化为空,即未保存任何作业对象。首先将作业集按效益值从大到小排序,然后按下述规则用m个Job对象把数组填满:取有序排列中的第一个作业,试着将作业放入数组中,首先尝试作业在数组中存放位置和该作业的lateRunOrder相同。如果第lateRunOrder数组元素没有放入作业,则将作业放放在此第lateRunOrder数组元素中;如果第lateRunOrder数组元素中早有作业放入,则从数组的第lateRunOder-1个数组元素直到第1个数组元素反向查找作业在数组中的放入位置,如果能找到,就将作业放在首次发现的未放入作业的数组元素中,如果找不到就将该作业舍弃,然后开始查找下一个作业在数组中的存放位置,也就是首先试着将作业放入第lateRunOder-1个数组元素,如果该数组元素中没有作业,那么作业就放入这个数组元素中,否则将作业放入它左边的第1个空着的数组元素中。按着上述规则试着依次将作业放入数组中,只要数组中填满m个Job对象,就停止比较其它作业能否放在数组中,剩余的作业全部被忽略,此时数组中存放的作业子集j就是CPU运行作业集能获得最大效益的作业子集,并且数组中作业的存放次序就是CPU运行该子集的一种可行顺序。之所以按上述规则将作业放入数组中,是因为作业运行地最晚次序是lateRunOrder,但作业可以在最晚运行次序之前运行。具体算法如下:
void so
您可能关注的文档
- 一名模特“菜农”生活.doc
- 一名警察劳务费之争.doc
- 一场“会展城”冷暖暗战.doc
- 一场为了城市明天战役.doc
- 一场乡镇促销“游击队”销售活动纪实.doc
- 一场智慧与谋略共生激荡.doc
- 一场没有输赢“战争”.doc
- 一场罕见蟋蟀豪赌案.doc
- 一场营销绍兴头脑风暴.doc
- 一块绝世巨玉引起风波.doc
- 建筑电气工程施工质量验收规范GB50303-2015知识培训.pdf
- 新型肠道清洁剂的前世今生.pdf
- 2024年《学考精练》数学九年级全册北师大版教学 第二章 一元二次方程 6 应用一元二次方程(第二课时).pdf
- 2024年《学考精练》数学七年级上册北师大版 第三章 整式及其加减 3.2 整式的加减 第一课时 合并同类项.pdf
- 生产建设项目水土保持技术标准(GB50433-2018)知识培训.pdf
- 《GB 17625.1-2022电磁兼容 限值 第1部分:谐波电流发射限值(设备每相输入电流≤16A.pdf
- 火灾自动报警系统组件兼容性要求 GB22134-2008专题培训.pdf
- 2024年《学考精练》数学七年级上册北师大版 第二章 有理数及其运算 2.5 有理数的混合运算 第二课时 用计算器进行运算.pdf
- 2024年《学考精练》数学七年级上册北师大版 第四章 基本平面图形 第一课时 角.pdf
- 《建筑防烟排烟系统技术标准》GB51251-2017知识培训.pdf
文档评论(0)