【摘 要】
：
最近几十年,排序已经被广泛地应用于运筹学、管理科学、计算机理论科学等各个领域.在线排序作为排序的一个重要领域,近年来得到越来越多的关注.与离线排序不同,在在线排序中,关于未来工件的任何信息在该工件到达之前都是不知道的.而且,通过利用过去的信息,决策者必须做出一系列决策.可是,在很多实际情况中,所有工件的部分信息会被提前知道,这就是所谓的半在线排序.一般情况下,我们把半在线排序归入在线排序中.在传统
【基金项目】
：
国家自然科学基金（11501171）；
论文部分内容阅读
最近几十年,排序已经被广泛地应用于运筹学、管理科学、计算机理论科学等各个领域.在线排序作为排序的一个重要领域,近年来得到越来越多的关注.与离线排序不同,在在线排序中,关于未来工件的任何信息在该工件到达之前都是不知道的.而且,通过利用过去的信息,决策者必须做出一系列决策.可是,在很多实际情况中,所有工件的部分信息会被提前知道,这就是所谓的半在线排序.一般情况下,我们把半在线排序归入在线排序中.在传统的排序问题中,我们总是假设所有的工件必须被全部接受,并被安排在一个特殊的机器环境中进行加工,从而达到优化某些目标函数的目的.然而,在很多实际情况中,由于生产能力的限制或者更高的质量要求,生产商只可以加工一部分工件而把剩余的工件以支付一定费用的方式外包给第三方生产.这里的外包就是本学位论文中所提到的拒绝.由此可见,带拒绝的排序问题无论从理论角度还是实践角度来说都是十分有意义的.本学位论文主要研究工件可拒绝的单机在线排序问题.在我们所研究的问题模型中,所有的工件都是时间在线到达的,这意味着,每个工件Jj的释放时间rj,加工时间pj和惩罚费用ej等信息只有在该工件到达后才会被知道.而且,任意一个工件Jj,要么被接受并安排在机器上加工,要么以支付一定惩罚费用的方式被拒绝.值得注意的是,一个工件被释放之后可以在任意一个时刻被拒绝.而且,一台机器在同一时间只能加工一个接受工件.此外,中断是不被允许的.我们所研究的目标函数主要是最小化接受工件的总完工时间加上拒绝工件的总惩罚费用.本学位论文分为以下四个部分:第一部分,我们简要介绍了排序问题的分类,排序问题的三参数表示法,并且回顾了与我们研究内容相关的文献.第二部分,我们提供了一些常用的符号、基本定义和基本引理,它们的引入为本学位论文的描述提供了方便.第三部分,我们研究了问题1|online,rj,（?）,rej|∑Cj+R,并为该问题设计了一个多项式时间的半在线算法ADSPTR.在本部分,我们想采用“改善的实例归结”的技巧去分析竞争比.为了可以使用“改善的实例归结”的技巧,我们为ADSPTR注入了一些柔性,并引入了一个命名为FADSPTR的新的辅助的柔性半在线算法.值得注意的是,算法ADSPTR是FADSPTR的一种特殊情况.得益于FADSPTR的柔性,我们可以更好地使用“改善的实例归结”的技巧去分析竞争比.通过采用“改善的实例归结”的技巧,我们证明出算法FADSPTR是一个竞争比为1（?）的半在线算法.最后一部分,我们主要对本学位论文进行了总结,并阐述了本学位论文的贡献.此外,我们还指出了未来的研究方向.
其他文献
与传统窑具相比,框架式窑具具有节能、安装方便等特点,在烧制陶瓷行业得到广泛的应用。在实际使用过程中,框架式窑车立柱可能发生断裂,给生产带来一定的影响,本文通过理论和有限元软件模拟相结合,得到立柱横截面最大应力所在位置,进而得到立柱开始破坏的位置。首先,本文基于等效原理,得到开孔立柱的抗弯刚度;基于卡氏第二定理,得到立柱受力情况,进而得到立柱横截面的最大应力所在的部位。然后,通过有限元软件模拟,得到
煤的润湿性对于湿式除尘至关重要。影响水对煤润湿效果的因素有煤自身的亲疏水性（组成成分、含水率等）、煤表面微结构（粗糙度等）、表面活性剂等。其中煤自身的亲疏水性在润湿煤体过程中无法改变,只有通过改变煤表面微结构和在水中添加表面活性剂来影响润湿性能。因此,本文从煤表面粗糙度入手,以哈密褐煤、安阳焦煤和赵固二矿无烟煤为研究对象,研究不同粗糙度下纯水和含表面活性剂溶液下接触角大小差异,分析煤润湿性能变化特
底栖生物作为生态系统工程建造者,通过生物扰动作用改变海底沉积物的形态,诱发沉积物与海水之间的物质交换,不仅深刻影响着底栖生物群落向沉积物内部的殖居,同时显著影响着大气-海洋-沉积物地球化学循环。遗迹化石作为底栖生物活动的直接证据,为研究寒武纪底栖生态系统工程建造者的演化规律,评价底栖建造者的生态工程影响提供了依据。本文依据河南寒武纪遗迹化石数据,应用生态空间及生态系统工程模型,对底栖生态系统工程建
本文通过对河南禹州、登封和焦作地区下二叠统太原组岩性、沉积构造、沉积序列、实体和遗迹化石等沉积特征的研究,分析了沉积环境和沉积体系、建立了沉积相组合及沉积旋回序列,进而阐明了本区太原组沉积期旋回沉积与海平面升降变化的基本特征,并绘制了早二叠世海平面变化曲线。在上述工作的基础上,确定了区域地层对比标志,并探讨了海侵与海退的演化规律。取得了如下主要进展:（1）通过对区内沉积特征的系统总结和精细分析,识
“一带一路”作为中国三大战略之一,对我国经济发展具有重大意义,有效了解“一带一路”中国沿线地区经济发展情况,有助于经济战略部署,对于“一带一路”投资和建设具有重要意义。GDP是展现一个地区经济发展情况的重要指标,但传统GDP研究存在诸多局限性,同时无法表示区域内部差异。随地理信息技术的发展,GDP空间化提供了一种快速、准确的研究新思路和方法。本文基于夜间灯光影像数据,构建了改进型GDP空间化模型,
本文主要研究不可压磁流体方程的一阶格式和二阶格式的压力投影有限元方法.我们考虑如下形式的二维或三维不可压磁流体方程:#12且满足下面的初边值条件:#12其中,u,p,E,B分别是速度,压力,电场,磁场.另外,f是源项.磁流体力学方程组中含有两个参数:v是流体的黏性系数,且满足v=Re-1,Re为雷诺数,Rm为磁雷诺数,S为耦合系数.n是单位外法向量.为了简单起见,我们假设所有参数都是非负的.本文在
目前,叠层梁已经广泛应用于工程和实际生活中。众多学者采用多种研究和计算方法,不断加强和完善了叠层梁的相关研究。叠层梁计算的重点在于确定层间接触力的大小及分布情况。为克服以往解析解所得到的的结论与实际存在偏差的问题,本文利用位移变分法对叠层梁的层间接触力进行求解。本文以简支叠层梁和悬臂叠层梁两种计算模型为主来进行计算讨论。取上下部梁单独研究,将层间接触力视为施加在下部梁上的的外力。将接触力离散化并依
在本文,我们一方面致力于研究三维不可压磁流体方程组及相关模型在一些临界空间小初值解的整体适定性、解析性和衰减估计,另一方面考虑Lp（（?）3）空间三维不可压定常磁流体方程组及相关模型光滑解的Liouville定理.首先研究在χ1-2α（（?）3）临界空间三维广义不可压磁流体方程组小初值整体解的时间衰减估计?该方程组描述了导电流体在磁场作用下的运动规律.这里u=（u1,u2,u3）,b=（b1,b2
磁微极流体方程组描述了导电微极流体在磁场中的运动现象.当二维不可压缩磁微极流体方程组中速度场,微旋转场和磁场都具有完全耗散时,容易得到经典解的整体存在性和唯一性.而对于无粘性情况,该方程组解的整体正则性仍然是公开问题.所以,我们研究中间情形,即部分耗散情形.本文对两类具有部分耗散的二维磁微极流体方程的整体适定性和解的长时间行为进行了研究.在第三章中,我们研究了仅具有速度耗散和部分磁扩散的二维不可压
本硕士论文的研究内容属于Brunn-Minkowski理论和对偶Brunn-Minkowski理论领域,致力于凸体几何中的极值问题的研究.本硕士论文利用凸几何分析中的凸体理论来研究极值问题和等周不等式,涉及Ball-Barthe不等式,迷向测度,正弦椭球等问题.本文主要对三个问题进行研究,第一个问题是关于混合LYZ椭球的Mahler猜想.第二个问题是正弦椭球的迭代问题.第三个问题是新椭球的体积不等