骨有前瞻区间和运输时间在线排序

来源 :郑州大学 | 被引量 : 0次 | 上传用户:cqhy2009
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
排序就是在一定的限制条件下,分配时间资源去完成一些任务,使得一个或者多个目标达到最优.近年来,平行分批排序和在线排序是两个发展比较迅速的排序模型.平行分批排序模型中,机器可以同时加工多个工件,并且每批的加工时间是该批所有工件中加工时间的最大者.一旦批开始加工就不能被中断,直到该批被加工完毕.在线排序模型中,工件的信息在其到达之前是一无所知的,并且一旦工件被安排之后就不允许再改变.在LKβ模型下,在时刻t,在线算法能预见到将在时间区间(t,t+βp(t)]内到达的所有工件的信息,而p(t)是在时刻t可用工件中加工时间最大者.   本文研究了两种排序模型:(1)带有前瞻区间的平行分批处理机的在线排序问题;(2)带有运输时间的单机在线排序问题.采用Graham等人[1]提供的三参数表示法,这些问题分别表示为   1|on-line,rj,p-batch,b=∞,LKβ|Cmax;   1|on-line,rj,p-batch,agreeable(pj,qj),b=∞,LKβ|Lmax;   1|on-line,rj,qj≥pj|Lmax.   下面我们具体地给出本文的主要结果.@2在第二章中,对于前两个在线分批排序问题,我们分别证明了这些问题的竞争比的下界至少是1+α,其中α是方程α2+(β+1)α+β-1=0的一个正根,然后分别提供了一个竞争比为1+α的在线算法H1(α,β)和H2(α,β),最后我们证明了当0<β≤1/6时,算法H1(α,β)和H2(α,β)是最好可能的.   在第三章中,对于在线排序问题1|on-line,rj,qj≥pj|Lmax,我们首先证明了该问题的所有在线算法的竞争比的下界是√3+1/2,进一步,我们提供了一个竞争比为√2的在线算法H.
其他文献
本论文主要是研究如下一类广义Boussinesq方程(简记为IBMq方程):的解在Besov空间中的色散估计.其中u(x,t)为未知函数,f(s)是已知的非线性函数,u0(x)和u1(x)是已知的初始函数,下标t
在本文中,我们讨论了一类二重量可约循环码,得到这类二重量可约循环码可以由两个一重量simplex码的直和构成.对这一类型的二重量可约循环码,利用特征标和高斯和的一些结论和性质
在统计推断中,从分布未知的总体中获取样本通常采用都是简单随机抽样。但是,在某些实际问题中,当采用简单随机抽样比较耗时耗费时,这时可采用排序集抽样。排序集抽样发展至今在参
P2P(Peer-to-Peer)即对等网络,目前已经成为Internet应用系统中最重要的成员之一。由于P2P网络具有的开放性、匿名性以及松耦合性等,使得网络系统中的实体之间由于缺乏信任而带
本文利用收缩(contraction)的方法由两个变量的量子环面构造出一个新的无穷维李代数,并对它进行了研究.本文第一部分研究了这个李代数的结构,并证明它可看成Virasoro-like代数
设()是复数域上的一个n× n阶的可逆矩阵群.我们称()是一个伪置换矩阵群,如果()中的每一个矩阵都相似于一个置换矩阵.一个中心问题是:在什么条件下一个伪置换矩阵群将等价于一
本文主要运用变分方法研究如下带Hardy奇异项和Sobolev临界指数的拟线性椭圆方程-N∑(l)=1(e)/(e)x(l)|▽u|p-2(e)u/(e)x(l))-μ|u|p-2u/|x|p=|u|p*-2u+g(x),u∈D1,p(RN).其中N