【摘 要】
：
列表在线排序是一类重要的现代排序模型.本文主要研究的是单机批容量有界的列表在线排序问题,目标函数为极小化工件的最大完工时间.所谓单机上的列表在线排序:工件是一个接一
论文部分内容阅读
列表在线排序是一类重要的现代排序模型.本文主要研究的是单机批容量有界的列表在线排序问题,目标函数为极小化工件的最大完工时间.所谓单机上的列表在线排序:工件是一个接一个的到来,在下一个工件到来之前,我们要对刚到来的这个工件做出安排,要么将其安排在已存在的一个非满批中,要么将其安排为一个新的非满批.每个批至多只能有6个工件.论文的主要内容如下:
第一章简要介绍了排序问题的一些相关定义、记号及相关知识.
在第二章中,我们考虑的是批容量为2的情形,用Graham等人(1979)引入的三参数法,该问题可表示为:
1｜online-list,p-batch,b=2｜Cmax.
我们先给出了该问题的一个下界1+α,这里α是方程
α(1+α)2=1
在(√2-1,1／2)内的一个正根.接着给出了一个竞争比为√5+1／2的在线算法.最后,我们给出了一个猜想竞争比更好的在线算法.
在第三章中,我们考虑的是批容量为3的情形,用Graham等人(1979)引入的三参数法,该问题可表示为:
1｜online-list,p-batch,b=3｜ Cmax.
我们给出了一个下界1+α,其中α是方程
(1+α)(1+(α)2)=2
在(1／2,√5-1／2)内的一个正根.接着给出了一个竞争比为2的在线算法.
最后,我们总结全文并指出了下一步要研究的问题.
其他文献
在本论文中，我们介绍了紧的广义K(a)hler流形上的一些性质，主要通过这些性质研究了紧的广义K(a)hler流形上的Formality性质。在紧流形上的广义K(a)hler结构(J1,J2)中如果J1有全
近三十年来,数学与计算机科学的交叉,尤其是拓扑方法、格序结构、范畴结构等在计算机科学中的应用引起了人们的广泛关注.二十世纪70年代初,Scott、Plotkin、Lawson等人创建了
众所周知,通用开折是奇点理论中非常重要的课题.它是突变理论的核心.如果F是映射芽f的通用开折,那么对f作扰动产生的每一个开折都可由通用开折F“诱导”出来为了研究映射芽的
本文考虑不同光滑程度变系数部分线性模型Y=g(Z)+f+ε，f=p∑j=1βj(U)Xj其中Y∈R是响应变量,Z∈R,U∈E,X=(X1,X2,…,Xp)T∈Rp是协变量,U可以是X1,…,Xp中的一个,s为随机误差,E
本文在完全分配格的格值环境下,主要关注L—fuzzifying(不分明)拓扑学中如下的问题:(1)L—fuzzifying拓扑结构与可延L—fuzzy(格值)拓扑结构相互确定的问题；(2)L—fuzzifying
本文共分四章,主要研究二阶非线性Sturm-Liouville边值问题、二阶非线性Dirichlet脉冲边值问题和六阶非线性脉冲微分方程边值问题解的存在性.
第一章简述了非线性常微分
态射是两个数学结构之间保持结构过程的一种抽象，在范畴理论与基础代数学中有着重要的意义。本文在群的态射及拟态射的研究基础上，首先，定义了一种具有某些性质的群同态，我们称之
研究非线性系统时，反向（reciprocal）变换可以把目前性质还不清楚的Camassa-Holm（CH）型可积系统对应到已知的经典系统，从而导出CH型的可积性质如守恒量、Hamilton结构并构造CH型方程