【摘 要】
：
排序问题是组合优化的一个重要分支,它在理论上大都是NP-H问题.排序问题不仅具有组合数学的典型特点,同时与相关领域的一些热点问题密切相关,其问题的解决涉及许多学科的交叉领域,具有重要的理论价值.伴随着计算机科学的发展,在该领域出现了许多新的模型和研究方法.作为现代排序中的在线排序和博弈排序,也取得了相当丰富的成果.本文研究了在平行机环境下的这两类排序问题.全文分为三章.第一章简要介绍了组合优化以及
论文部分内容阅读
排序问题是组合优化的一个重要分支,它在理论上大都是NP-H问题.排序问题不仅具有组合数学的典型特点,同时与相关领域的一些热点问题密切相关,其问题的解决涉及许多学科的交叉领域,具有重要的理论价值.伴随着计算机科学的发展,在该领域出现了许多新的模型和研究方法.作为现代排序中的在线排序和博弈排序,也取得了相当丰富的成果.本文研究了在平行机环境下的这两类排序问题.全文分为三章.第一章简要介绍了组合优化以及排序问题,特别是在线排序和博弈排序的相关内容作了较为系统简洁地阐述,同时综述了在线排序和博弈排序的有关研究成果.另外,对我们取得的主要研究成果进行了梳理.第二章讨论了同类平行机环境下工件有到达时间,目标函数为极小化最大完工时间的在线排序问题Qm|online,rj|Cmax（m≥2）,分析了LS算法的竞争比.得到了机器环境为2台和不少于3台同类平行机时竞争比的紧界,分别是（?）.另外给出了比LS算法的竞争比要好的算法MLS算法,并分析了其竞争比.第三章主要研究的是相同平行机环境下机器和工件均具有自私性的二元平衡博弈排序问题Pm‖Cmax（m≥2）.此模型中,工件和机器因自私性,均为各自的目标函数而相互进行博弈.当博弈形成一种稳定的平衡状态时,均不会使工件和机器各自的决策发生改变,这种平衡状态被称为二元平衡状态,简写成DE.本章采用权函数的方法,通过对比DE状态下和最优状态下的工件排序情况确定最大完工时间来分析PoA.首先讨论了2台机器的情况,得到了8/7这个PoA的紧界,并给出了以工件长度相似系数r为参数的PoA结果,是一个关于r的分段函数.接着,讨论了机器数3 ≤ m ≤ 9时,4/3为DE状态PoA的一个上界,且是紧界.当m ≥ 10时,得到7/5-9/5（5m-3）为PoA的一个上界.这比此前该模型仅有的结果7/5要好.
其他文献
"米粉、面条、包子、糕点、轻食、米粥……饭菜味道也很好吃,每天都有新花样,菜品一周都没有重样的!"午餐时间到了,中国兵器江麓机电集团有限公司的职工食堂便热闹起来,就餐的员工们纷纷为食堂的新变化点赞。江麓集团将打造食材好、营养好、厨艺好、环境好、节约好的"五好"食堂作为"我为群众办实事"实践活动的重要内容,以员工诉求为中心,突出创新服务,着力为群众办实事、办好事,不断提升职工的幸福感、满意感、
草鱼（Ctenopharyngodon idellus）是我国产量最高的重要养殖经济鱼类,2018年其年产量达550万吨（2019年中国渔业统计年鉴）。然而,连续人工自交容易导致草鱼种质资源退化,造成其染病及死亡。为了获得遗传改良草鱼,本研究通过雌核发育技术,首次使用灭活的锦鲤精子作为刺激源激活草鱼成熟卵子,经过染色体加倍处理后获得改良雌核发育草鱼,建立了改良雌核发育草鱼群体,并对其遗传等生物学特
本文在相对论框架下,讨论了量子探测的理论研究及超导量子电路的应用。相对论量子信息学是近年来兴起的一个前沿且热门的交叉学科,其理论框架根植于相对论、量子力学、量子场论、信息学等等。该学科研究的主要内容包括:相对论运动和效应对量子体系的影响,弯曲时空的结构和性质对量子资源的影响,以及探讨如何利用量子信息中前沿的技术方法探测时空。相对论量子信息学的发展具有深远的意义,从理论上而言,这一学科是量子信息理论
引力透镜效应是指光经过致密星体等强引力天体附近偏离原来传播方向的现象。黑洞则是广义相对论所预言的一种超大质量的致密天体,其强大的引力使得其表面的光也无法逃逸。人们可以通过黑洞的引力透镜效应来鉴别黑洞和检验各种引力理论,因而引力透镜效应在宇宙学、天文学以及黑洞物理学中得以广泛的研究和应用。经典混沌通常与轨迹的指数分离有关。在量子力学中,量子态的位置和动量等共轭观测量因不确定性原理而不能同时具有确定的
本文研究非凸问题鞍点计算的新算法及其应用,主要内容分为四个部分.第一部分,我们研究计算无约束鞍点的基于新的优化策略的局部极小极大方法（LMM）.首先,我们给出一类推广的局部极小极大原理,并从连续动力学的角度理解LMM能以稳定方式计算不稳定鞍点的数学本质.然后,我们在使用一般下降方向的LMM算法框架下,系统地讨论各种步长搜索准则的可行性,并建立完整的全局收敛性结果.这使得各种高效的优化策略可以应用到
基于非相对论的组分夸克模型,我们研究了基态全重味四夸克态和壳层数N≤2的ΩQQQ（Q=s,c,b）重子态的质量谱。同时利用夸克势模型得到的质量和波函数,我们进一步研究了壳层数N ≤ 2的ΩQQQ（Q=s,c,b）重子态的衰变性质。主要的研究结果如下:一、通过研究全重味四夸克态我们发现:（1）所有的全重味四夸克系统cccc、bbbb、bbcc/ccbb、bccc/ccbc、bcbb/bbbc、和 b
声波的多体散射问题在工程与医学上有广泛的应用。本文提出了当散射体在均匀或者局部非均匀介质中时求解多体散射问题的一种高效迭代算法。该算法的核心思想是利用人工边界分别将每个散射体包围,对于局部非均匀介质我们要求人工边界要将非均匀介质一同包围,然后利用波的叠加原理,将散射波分解为单纯向外传播的场的叠加。原始多体散射问题将被分解为一系列有限多个单体散射问题,其中每个单体散射问题与其他散射问题的相互作用仅发
从量子意义上说,真空不再是一无所有的虚空,而是存在着时刻涨落的量子场。因此,量子世界中任何真实的系统都不能再被当作孤立系统,因为它们与真空这类外部环境之间的相互作用总是不可避免的,而正是涨落量子场的诸多类型造就了开放量子系统多样的动力学行为。最近,人们直接探测到来自双黑洞合并系统的引力波信号,这一突破既证实了爱因斯坦在广义相对论中对引力波存在的预测,又推动了人们对引力波量子化所导致效应的研究。如果