【摘 要】
：
平行分批排序和在线排序是两个发展迅速的排序模型。平行分批排序是指机器可以同时成批加工多个工件(有限或无限)。每批包含的工件同时开工同时完工。每批的加工时间是这批工
论文部分内容阅读
平行分批排序和在线排序是两个发展迅速的排序模型。平行分批排序是指机器可以同时成批加工多个工件(有限或无限)。每批包含的工件同时开工同时完工。每批的加工时间是这批工件的最大加工时间。在线排序是指工件信息在其到达之前是一无所知的,并且一旦工件被安排后就不允许再改变。 本文主要考虑了目标函数是和式的分批排序问题。首先研究了目标是最小化加权完工时间平方和的分批在线排序问题。在这个问题中,我们有一台批处理机,有n个按时在线到达的工件1,2,…,n.每个工件的加工时间为p_j,权重为w_j,到达时间为r_j.根据批容量b是无界还是有界,我们所考虑的模型可分别记为1on-line,r_j,p-batch∑w_jC_J~2与1on-line,r_j,p-batch,b0)的在线算法。 (2)给出了问题1on-line,r_j,p-batch∑w_jC_j~2的一个竞争比为11.3429的在线算法。其次,本文对目标是加权完工时间常数次幂和的单机平行分批排序问题进行了研究。这里我们只考虑了批容量无界的情形。所研究问题可表示为1|p-batch,r_j∑w_jC_j~h(h≥1为固定常数)。 文中通过利用划分时间轴和几何舍入的方法,把原始实例转化为较为简单的实例,并利用已有的拟多项式时间算法,最终给出了1p-batch,r_j∑w_jC_j~h(h≥1为固定常数)的一个全多项式时间近似方案。
其他文献
随着我国房地产业的不断发展,房地产投资者进行地域上和房地产投资品种上的投资组合是我国目前许多地产企业以及投资主体进行积极实践的客观现实.而如何最大限度的获得最高的
本文研究了一类具有时滞的HIV感染的微分方程模型.在文[7]的基础上，以模型中的时滞为参数进行了Hopf分支的分析，得出了在正平衡点存在的条件下，系统的正平衡点附近可能会产生Hop
排序问题是一类重要的组合优化问题.在经典排序模型中通常假设工件的加工时间为常数.但在许多实际问题中,工件的加工时间可能与其开工时间、所用资源或所处的位置有着某种联
本文将各向异性非协调元应用于三维空间中描述细菌传染的反应扩散方程组的初边值问题。借助单元的一些特性和误差估计技巧,分别在半离散和全离散有限元格式下,研究了其数值解
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
本文通过分析2005-2014国内外发表的191篇商务英语语言学期刊论文,研究了语言学视角下商务英语语言学的总体特点、研究主题及发展趋势。从多维度的角度研究可以看出,商务英语
批判性思维即是人质疑现有的物理观点且提出新的观点,且通过实践来说明自己的观点的一种思维方法。它是通过实践探索人们进一步了解物理真相的过程,也是一种重要的科学态度。
在小学教学体系中,数学概念作为形成数学知识体系的基石,对小学生各种数学能力的形成和数学思维的发展都扮演着极为重要的角色.数学概念是对客观事物的数量关系、空间形式以
初中语文教学中,要注重提高学生捕捉文眼的能力,对文章进行深入的理解和学习,促进学生对文章的整体把握,让学生在文章学习过程中积累更多的知识,激发学生对语文学习的兴趣.本
作为劝谏艺术的经典之作,《邹忌讽齐王纳谏》的劝谏过程可谓入情入理,劝谏语言可谓文质兼美.表现出如下特点:劝谏方式上,由己推人,由小到大,层层深入;劝谏语言上,措词委婉,比