两类特殊的在线分批排序问题

来源 :郑州大学 | 被引量 : 0次 | 上传用户:ten_wang
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要考虑了两类特殊的在线分批排序问题。所谓在线,本文指的是按时在线。工件信息在其到达之前是一无所知的,并且一旦工件被安排后就不允许再改变。所谓平行分批排序是指机器可以同时成批加工多个工件。每批包含的工件同时开工同时完工,批的加工时间是这批中加工时间的最大者。  首先研究了批容量为3的单机平行分批排序。主要结果如下:  (1)对排序问题1p- batch,b=3;pj=1; on- line;ri;limited restartsCmax,我们给出了竞争比为的最好可能的在线算法。  (2)对排序问题1p- batch, b=3; on- line, ri; limited restartsCmax,我们证明了竞争比下界为,并给出了竞争比为的在线算法。其次,对带有特殊工件的平行分批排序问题进行了研究。这里所有工件都是在线的,但是,其中有一些工件,它们要求单独成批,其它工件不能与其共批,并且一旦到达就要对其立即加工。我们称其为特殊工件,其它工件称为普通工件。假设特殊工件间不冲突。  主要结果如下:  (1)对排序问题1special job(restart);pj=1; on- line, ri, DΣfj,我们给出了竞争比为(?)的最好可能的在线算法。  (2)对排序问题P2special job(pmtn);p- batch, b=∞; on- line, riCmax,我们证明了竞争比下界为(?),并给出了竞争比为(?)的在线算法。  (3)对排序问题P2special job(restart);p- batch, b=∞; on-line, riCmax,我们给出了竞争比为2的最好可能的在线算法。
其他文献
本文由一个4×4的矩阵谱问题,导出两类与之相联系的新的非线性演化方程,并利用迹公式证明了这两类非线性演化方程具有广义Hamilton形式。找到了第一类方程中第一个非平凡的非
本文分别探讨了两种情况下的经济增长模型—环境治理的内生经济增长模型和能源消费的经济增长模型。  首先,在环境治理的内生经济增长模型中,用环境质量代替以往模型中的环
本文主要由下面两部分组成:第一部分主要介绍一些记号,定义及定理;第二部分详细说明有限维分解定理的内容并给予证明。针对预解式的分解问题,侯振挺教授在《马尔可夫过程的Q-
利用五阶和七阶模等式,我们得到一类分拆函数的同余性质,其中∑∞n=D a(n)qn=(q;q)k∞(mod m),这里k是满足1≤ k
学位
近年来,随着非线性动力学研究的发展,利用非线性方法分析电价成为研究的热点。目前广泛使用的非线性分析方法有:时间序列的分维数、最大Lyapunov指数及复杂度等技术,这些技术
多年来中小型企业的档案工作的发展滞后,本文针对中型建筑设计企业浅谈一下企业档案中建设项目文件归档存在的问题和解决思路。
期刊
非单调信赖域方法把非单调技术应用到信赖域法中,不要求函数值在每一步都下降,这样有利于算法的收敛。非单调信赖域方法有很强的收敛性以及较好的数值表现,是求解无约束最优
复动力系统由Fatou和Julia等数学家创立于上个世纪二十年代,是复分析的主要分支.由于该学科与其它领域有着紧密的联系,已受到数学界的广泛关注,越来越多的数学家从事这方面的研
摘要:本文就华阴河务局采砂管理的现状和存在问题进行了阐述,并进行了原因剖析,提出了下一步采砂管理的对策与措施。  关键词:河道采砂;管理;浅析  中图分类号:P619.22+8文献标识码:A文章编号:    引言  砂石是重要的建材资源,随着经济的发展,建筑业的兴旺,对砂石的需求量也日益增加。长期以来,渭河下游各河段砂石资源的开发利用对流域内各县、市(区)经济发展做出了一定的贡献,尤其为区域重点工
期刊