| 
  中国学术期刊网络出版总库
  关闭
三台机并行工件排序问题的改进的下界  
   推荐 CAJ下载 PDF下载
【英文篇名】 Improved lower bound for online scheduling of parallel jobs on three machines
【下载频次】 ★
【作者】 余国松; 徐刚;
【英文作者】 YU Guosong; XU Gang; Department of Mathematics; Nanchang University;
【作者单位】 南昌大学数学系;
【文献出处】 计算机工程与应用 , Computer Engineering and Applications, 编辑部邮箱 2015年 10期  
期刊荣誉：中文核心期刊要目总览  ASPT来源刊  中国期刊方阵  CJFD收录刊
【中文关键词】 排序; 并行工件; 在线算法; 竞争比;
【英文关键词】 scheduling; parallel job; online algorithm; competitive ratio;
【摘要】 与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。
【英文摘要】 The online scheduling of parallel jobs on parallel machines is considered in this paper. Contrary to classical parallel machine scheduling problems, jobs may require processing on several machines in parallel. The standard metric for worst-case performance is the competitive ratio. By constructing certain adversary sequence, all the nine kinds of cases are analyzed. It is shown that 2.07 is a new lower bound on the competitive ratio of any online algorithm, which is better than the previous lower bound of 1...
【基金】 国家自然科学基金(No.61175127); 江西省自然科学基金(No.20142BAB211021)
【更新日期】 2015-06-18
【分类号】 O223
【正文快照】 1引言与经典的排序问题不同的是,并行工件排序可能要求在平行机上并行工作,这种类型的排序问题的最近发展可以参考文献[1]。在这里,研究的是P3|online-listmj|Cmax(参考文献[1]和文献[2]),即在工件到达(事先并不知道会有什么类型的工件到达)的要求下,如何在三台机上加工这些?

xxx
【读者推荐文章】中国期刊全文数据库
【相似文献】
中国期刊全文数据库
中国优秀硕士学位论文全文数据库
中国博士学位论文全文数据库
中国重要会议论文全文数据库
中国重要报纸全文数据库
中国学术期刊网络出版总库
点击下列相关研究机构和相关文献作者，可以直接查到这些机构和作者被《中国知识资源总库》收录的其它文献，使您全面了解该机构和该作者的研究动态和历史。
【文献分类导航】从导航的最底层可以看到与本文研究领域相同的文献，从上层导航可以浏览更多相关领域的文献。

数理科学和化学
　 数学
　　 运筹学
　　　 统筹方法
  
 
  CNKI系列数据库编辑出版及版权所有：中国学术期刊(光盘版)电子杂志社
中国知网技术服务及网站系统软件版权所有：清华同方知网(北京)技术有限公司
其它数据库版权所有：各数据库编辑出版单位（见各库版权信息）
京ICP证040431号    互联网出版许可证 新出网证（京）字008号