【摘 要】
:
排序(scheduling),是组合优化领域中最经典的问题之一。一般而言,排序指的是:给定机器和待加工的工件,对工件制定一个在机器上加工的计划,使得所有工件尽可能快的完工。随着人们对排序问题研究的深入,与排序相关的更为复杂的问题也被清晰的刻画了出来,成为了更贴合实际的研究热点。它们不但具有很高的理论价值,更具有非常广泛的应用背景。本文主要研究与排序相关的优化问题:排序博弈(scheduling g
论文部分内容阅读
排序(scheduling),是组合优化领域中最经典的问题之一。一般而言,排序指的是:给定机器和待加工的工件,对工件制定一个在机器上加工的计划,使得所有工件尽可能快的完工。随着人们对排序问题研究的深入,与排序相关的更为复杂的问题也被清晰的刻画了出来,成为了更贴合实际的研究热点。它们不但具有很高的理论价值,更具有非常广泛的应用背景。本文主要研究与排序相关的优化问题:排序博弈(scheduling game)、旅行商问题(TSP)和覆盖约束排序(scheduling with covering constraints)。本文第一章内容主要是介绍一些与本文所研究的三个问题相关基础知识以及相关问题的概念和定义。同时,介绍了上述问题相关的研究工作,并展示了本文所得到的结果。第二章研究了两代理单机排序博弈问题。在该博弈问题中,两位代理人竞争同一台机器来加工他们各自的工件且他们的目标均为最小化各自工件完工时间和。当其中一位代理仅有两个工件且所有工件加工时间都大于零时;本章证明了该问题中所有的KS-公平排序可以在多项式时间内找到,且其公平的代价为PoFKS=1/2。第三章研究了单起点在线m-Steiner旅行商问题。在服务客户的途中,旅行商们可能会遭遇到现实中短时间不可恢复的障碍。最小化最大在线m-Steiner旅行商问题(MinMax-mSTSPonline)的目标是找到m个封闭的回路去访问每个客户至少一次,使得m个旅行商中的最大费用尽可能小。本章给出了一个在线算法并且证明了在m≥2时,它的竞争比至多为k-1/m+10,其中k为障碍的数量;当m=1时,竞争比至多为k+2。注意到,该问题的下界为(?)+1,因此,本章竞争比的结果为渐近紧。对于目标为最小化总旅行费用的在线m-Steiner旅行商问题(MinSum-mSTSPonline),上述算法仍然适用,其竞争比至多为5m+k-1。第四章研究了集合覆盖约束下的排序问题。在该排序问题中,给定的工件集对应着集合覆盖问题中的集合族,其目标是选择一些工件进行加工,使得所选工件集满足集合覆盖条件。本章分别从机器环境和数量出发,研究了不同条件下的集合覆盖约束排序问题;当机器为变速机且数量任意时,本章给出了近似比为fmax+1的算法,其中fmax为集合覆盖中任一元素在预选集合中所出现的最大频率;当机器为同速机时,则给出了近似比为fmax·(1+2ε)的算法,ε为任意大于零的正数。当机器数量为固定常数时,本章给出的算法近似比为α,其中α为最小权集合覆盖问题近似比;当机器为变速机时,给出了近似比为fmax的近似算法。第五章通过总结全文,提出了一些相关的具体问题,为将来的研究提供了方向。
其他文献
虾青素在饲料、食品及保健品等领域应用广泛,雨生红球藻是天然虾青素的最佳生物来源。目前雨生红球藻光自养培养生产虾青素的两步法存在产量低、易污染、易受天气影响等缺点,导致雨生红球藻来源的虾青素成本高昂。笔者所在团队开发的“异养-稀释-光诱导”串联培养(SHDP)工艺,通过异养代替光自养,可稳定、高效地获得绿色细胞。该工艺解决了绿色阶段产量低、易污染的问题,尽管笔者所在团队前期在雨生红球藻异养细胞光诱导
镀件冲洗、铬浴排水和废铬酸盐钝化等过程产生的Cr(Ⅵ)通常与甲基橙(MO)染料共存,处理难度大,生物毒性强。由于两者具有显著不同的物理化学性质,现有大部分技术仅仅用于单独去除Cr(Ⅵ)或MO,很少有报道或研究关注同时去除Cr(Ⅵ)和MO。透过式电极,是一种融合过滤和电化学技术的新型电极。透过式电极允许水流垂直穿过电极的结构设计,使得污染物与电极的碰撞机率变大,传质速率高。透过式电极已经被用于电还原
病原细菌依靠复杂的蛋白调控网络来适应充满“敌意”的营养限制的宿主环境。磷酸烯醇式丙酮酸磷酸转移酶系统(Phosphoenolpyruvate:carbohydrate phosphotransferase system,PTS)是细菌的一种保守途径,负责将特定的PTS-糖(PTS-sugar)跨膜转运与磷酸化信号转导结合起来,以监测和利用环境中的碳水化合物,维持菌体的能量水平,全局调控菌体的能量代
雨生红球藻是目前发现的最强抗氧化剂—左旋虾青素(最佳的天然虾青素)的唯一生物来源,因此雨生红球藻的大规模培养是目前生产天然虾青素的唯一方式。迄今,雨生红球藻的大规模培养技术主要是基于光自养的两阶段法,但雨生红球藻培养效率低且光生物反应器占地面积大,严重制约了天然虾青素产业的发展。为此,笔者所在团队在国内外首创“异养-稀释-光诱导串联”培养技术(SHDP),解决了户外光自养培养效率低及光生物反应器占
动物的先天免疫系统作为广泛存在的天然防御机制,是宿主抵抗病原微生物入侵的第一道防线。程序性细胞死亡是多细胞生物生命过程中重要的生理或病理现象,更是宿主先天免疫防御病原入侵的重要环节。在与病原菌博弈的过程中,宿主会启动程序性细胞死亡,清除被感染的细胞和胞内的病原菌,并暴露病原,实现病原菌抗原信息呈递,激活适应性免疫,以促进病原清除和免疫防御。为了躲避宿主免疫识别,细菌也进化出多种机制,操控宿主细胞的
木质纤维素生物质是地球上用于生产生物燃料和生物基化学品的储量最为丰富的原料。预处理是克服后续酶水解和发酵过程中存在的物理和化学顽固性的前提。而另一方面,预处理过程会产生一系列抑制物,影响细胞生长、糖化和发酵。应采取解毒步骤从预处理木质纤维素原料中去除有毒抑制剂。因此必须通过脱毒来去除预处理过程中从木质纤维素中产生的抑制物。生物脱毒是一种通过微生物去除木质纤维素原料中抑制物的方法。目前已分离出多种能
生物炼制菌株在木质纤维素生物炼制过程中不可避免地会遭遇到各种胁迫,这些胁迫会抑制生物炼制菌株的生长以及发酵,进而导致发酵过程难以进行以及生物炼制过程无法持续。因此,解除或者缓解这些胁迫对于生物炼制菌株的抑制作用,一直以来是木质纤维素生物炼制领域研究的关键问题。本研究主要为了解决生物炼制菌株遭遇到的三种胁迫,包括酚类抑制物、高温以及低pH值。酚类抑制物来源于木质素的降解,包括酚醛抑制物以及醌类抑制物
病原微生物采取多种机制入侵宿主并在宿主体内存活,造成宿主的发病。炎症小体是细胞内模式识别受体(Pattern recognition receptor,PRR)响应多种生理和病原性刺激,通过招募下游的接头蛋白与效应蛋白,形成的多聚体复合物。它是固有免疫系统的重要组成部分,对于病原体或受损细胞的清除发挥重要功能。其中NLRP1(NLR family pyrin domain containing 1
醛类物质大多具有浓郁的香气而作为香精香料应用于食品、日化等领域,并且因为其化学活泼性而作为有机合成中重要的砌块,广泛地应用于医药合成中。然而,醛类物质的选择性化学合成却存在诸多限制。羧酸还原酶通过辅因子ATP和NADPH的作用,可选择性地将自然界中储量丰富的有机酸选择性转化为相应的醛,就为其合成提供了有潜力的生物催化方案。然而,天然的羧酸还原酶很难满足工业应用状况下的需求,主要表现为催化活力较低。
海洋天然产物是天然药物化学的重要研究方向之一,由于海洋生物的次生代谢产物合成途径与陆生生物差异巨大,因此海洋次生代谢产物有着更为丰富的化学和功能多样性,在新药先导化合物的发现以及新药的研发中起着重要作用。本研究中我们对采集自中国南海的无脊椎动物多穗软珊瑚(Litophyton nigrum)的化学成分与生物活性进行了系统研究。综合运用多种柱层析方法对采自我国海南省三亚西沙岛的一种多穗软珊瑚(L.n