【摘 要】
：
排序问题是在一定的约束条件下对工件和机器按时间进行分配和安排次序,使得某一个或某一些目标达到最优.顶点覆盖是满足覆盖图上所有边的顶点的集合.组合优化问题的组合这个概念最初由王振波和崔振华提出.Epstein等人对点集覆盖和平行机排序的组合问题给出了 2+ε近似算法,这一近似因子应该是到目前为止较好的近似可能了.经典排序问题是给定m台平行机,n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器
论文部分内容阅读
排序问题是在一定的约束条件下对工件和机器按时间进行分配和安排次序,使得某一个或某一些目标达到最优.顶点覆盖是满足覆盖图上所有边的顶点的集合.组合优化问题的组合这个概念最初由王振波和崔振华提出.Epstein等人对点集覆盖和平行机排序的组合问题给出了 2+ε近似算法,这一近似因子应该是到目前为止较好的近似可能了.经典排序问题是给定m台平行机,n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能地小.如果每个工件的加工时间满足一定的条件,经典排序有望能在多项式时间内有效地得到最优的分配方案.顶点覆盖问题大多用Local Ratio这一算法框架进行求解.将两个组合优化问题进行组合,是一个比较新颖的研究方向.同时,为研究一类具有多层结构的组合问题提供了新思路.本文对经典排序问题提出了一种新算法.事实上,该算法是解决工件加工时间满足整除关系的经典平行机排序问题的多项式时间算法.我们发现,这一算法存在两个版本,文中考虑了这个新算法的两个版本,分别得到了3/2和2-（1/2q）（q∈Z+）的近似比.紧例子表明,我们对算法两个版本的分析都是紧的.此外,文中介绍了一些特殊图上的弱顶点覆盖问题以及特殊图上组合问题的一些结果.同时,给出了具有覆盖约束的平行机排序问题的一些算法和实例,本文还对这些问题给出了一些实际生活中的应用背景.
其他文献
全取代的1,2,3-三氮唑是一类非常重要的含氮杂环化合物,在对原有药物的改良或新型药物的研究开发、与生物分子之间的缀合以及先导化合物库的建立等诸多领域发挥着越来越重要的作用。鉴于铜催化末端炔烃和有机叠氮化合物的1,3-偶极环加成反应（Cu AAC）具有产率高、区域选择性好、反应速率快且具有普适性和可靠性等优点,因此在Cu AAC反应的基础上发展出的多组分串联环加成反应已经成为了构建全取代1,2,3
顶点覆盖问题是经典的组合最优化问题.顶点带非负权重的顶点覆盖问题在一般图上是NP-难的,而在二部图上却能在多项式时间之内被解决.解决二部图上的顶点覆盖问题,可利用二部图的特殊结构,通过考虑一个叫所谓边装填的问题得到解决.边装填问题可认为是匹配问题的推广,并在二部图上,恰好成了顶点覆盖问题的对偶问题.本文形式化描述边装填问题并主要研究和分析解决边装填问题的算法时间复杂度.给定一个顶点有非负整数权重的
在自然界中,时滞是无法避免的,时滞现象广泛存在于化学、力学、医学、生物学、经济学和控制科学等领域.对于具有时滞的动力系统,常常用时滞微分方程来描述.在时滞微分方程理论中,Hopf分支是一种重要的分支现象,而Hopf分支的出现往往可能伴随着混沌现象.本文根据时滞微分方程的Hopf分支理论和秩一混沌理论,研究了两类时滞微分方程的Hopf分支的存在性,分支方向及稳定性,并对扰动系统的秩一混沌进行了讨论.
受地形和道路条件的影响,山区公路上的交叉口大多为无信号控制,机动车、非机动车及行人混行现象明显,交叉口处的交通运行杂乱无章,使得驾驶人在此混合交通情境下的驾驶避让决策难度加大,进而影响交通安全。为研究驾驶人在这类交叉口处的驾驶避让决策行为,本文基于驾驶模拟实验,选取典型山区公路交叉口搭建虚拟实验场,采集多维度数据,分析驾驶人避让行为,构建驾驶避让决策模型,从而更精细地探究山区交叉口处混合交通情境下
产油微藻是制备生物柴油较好的原料,提高其油脂产率、解除其成本瓶颈为近年来的研究热点。采用两阶段培养、胁迫条件、植物激素诱导等工艺,是促进微藻积累油脂的有效手段。褪黑素（Melatonin,MT）,一种吲哚类衍生物,广泛存在于动植物和微藻中,对植物具有多种生理功能,但其对微藻的影响还研究甚少。本研究以MT作为植物生长调节剂,单针藻（Monoraphidium sp.QLY-1）为研究对象,分别考察了
马铃薯是全球第四大商品粮作物,我国马铃薯种植面积和产量长期以来都稳居世界首位。云、贵、川、渝西南四省市马铃薯种植面积和鲜薯产量均约占全国总量的一半。但西南地区马铃薯机械化程度远落后于全国平均水平,其中总机收率仅为1.84%,与全国平均水平29.77%相差巨大,西南地区综合机械化率约为20.92%,仅为全国平均水平的一半。西南马铃薯种植区多分布于干旱少雨、土质黏重板结的丘陵和山地,是天然的马铃薯优势
分数阶微分方程作为一个数学模型,在描述某些复杂系统和自然界中的现象与过程等方面发挥的作用越来越大,尤其是关于系统的稳定性、可控性、解的性质等问题的研究.Ulam-Hyers稳定性定理因其确保了系统近似解的存在性而有效解决了部分复杂的非线性系统难以求出精确解的问题,因此,对Ulam-Hyers稳定性的研究具有一定的理论意义和应用价值.本文主要运用压缩映像原理以及不动点定理研究了两类非瞬时脉冲分数阶微
木瓣树（Xylopia vielana Pierre）属番荔枝科（Annonaceae）木瓣树属（Xylopia Linn）乔木,我国仅一种,分布于广西南部,多生于山地林中,为热带和亚热带地区特色植物种群。番荔枝科植物中化学成分种类丰富,活性多样,包括萜类及其聚合物、黄酮类及其聚合物、生物碱类及其聚合物,以及一些黄酮生物碱或者倍半萜杂合聚合物等,部分具有较好的抗炎、抗疟、抗菌、抗肿瘤等生物活性。为
目前,环境污染问题已经成为影响我国综合发展的主要问题之一,而随着科学技术的进步,传统冶金行业逐渐引进先进的科学技术和生产设备,这不仅提高了生产效率,而且在一定程度上降低了对环境的污染。近年来,废弃物资源化被认为是更有效的环保手段,不仅可以变废为宝,还可以减少污染物的排放量。其中,有企业就冶炼低浓度二氧化硫烟气为原料来生产硫酸铵,并将所得硫酸铵用在土壤、作物、纺织、皮革和医药等方面,这既有利于建设环