【摘 要】
：
顶点覆盖约束下的平行机排序问题和拒绝费用受限的平行机排序问题都是著名的NP-难问题,假设P≠NP,那么这两个问题不存在多项式时间精确算法.在顶点覆盖约束下的平行机排序问题中,工件和图的顶点一一对应,工件的加工时间代表顶点的权重,图的边限制了工件之间的关系,目标是找到一部分工件使得这部分工件既是图中的一个顶点覆盖同时在机器上的最大完工时间达到最小.在拒绝费用受限的平行机排序问题中,每个工件都有一个加
论文部分内容阅读
顶点覆盖约束下的平行机排序问题和拒绝费用受限的平行机排序问题都是著名的NP-难问题,假设P≠NP,那么这两个问题不存在多项式时间精确算法.在顶点覆盖约束下的平行机排序问题中,工件和图的顶点一一对应,工件的加工时间代表顶点的权重,图的边限制了工件之间的关系,目标是找到一部分工件使得这部分工件既是图中的一个顶点覆盖同时在机器上的最大完工时间达到最小.在拒绝费用受限的平行机排序问题中,每个工件都有一个加工时间和拒绝费用,目标是如何安排所有工件使得被拒绝的工件总费用不超过给定界限的同时,被接受的工件安排在机器上的最大完工时间达到最小.在总结前人研究工作的基础上,本文主要研究上述两类平行机排序问题.具体研究内容如下:（1）对于一般图上顶点覆盖约束下的平行机排序问题,设计了一个近似算法,算法的近似比为3-1/m;对于2度连通图上特殊的顶点覆盖约束下的平行机排序问题,给出了一个多项式时间算法;对于一类图上特殊的顶点覆盖约束下的平行机排序问题,给出了一个多项式时间算法.（2）对于拒绝费用受限的平行机排序问题,本文首先考虑将工件集划分为接受集和拒绝集;然后在机器上加工接受集的工件.由于寻找划分方式的困难性,因此考虑问题在某个或某些特殊条件下的多项式时间可解性.针对加工时间和拒绝费用为qN（q≥2,N≥ 0）,拒绝费用界限为2的拒绝费用受限的平行机排序问题,受0-1背包问题的启发,设计了一个多项式时间算法.
其他文献
预应力混凝土连续刚构桥综合了连续梁桥和T型刚构桥的优点,有着优越的跨越能力和良好的结构性能,在地形地貌复杂的地区有着绝对的优势。但是随着大跨度预应力混凝土连续刚构桥的大量建造,其在运营过程中病害不断出现,尤其是跨中长期下挠、开裂等病害。所以研究如何控制连续刚构桥主跨跨中长期下挠,确保桥梁结构在建设、运营、最终完成其使命的整个寿命期间,能够保证桥梁结构、车辆和人员的安全,以合理的经济成本维持桥梁本身
随着计算流体力学的发展,数值模拟已经成为了研究流体流动的一个不可或缺的重要手段。而低阶离散方法在获取高精度数值结果中的困难,使人们逐渐对高阶的离散方法产生了极大的兴趣。在保持计算效率的同时努力提高其数值模拟结果的精度是目前的一个重要发展方向,因此高阶空间离散方法在学术界和工业界都变得越来越流行。基于Spectral/hp单元法结合了谱方法的高精度特性和有限元法的几何灵活性,对于解光滑的问题能够实现
上同调代数是数学中经典的基础理论,有限元方法是求解偏微分方程的数值计算方法,二者通过有限元外微分结合起来.曲面上的调和微分形式空间同构于曲面的上同调群,且调和微分形式是微分形式定义泛函的极小解.本文将讨论曲面上调和微分形式计算的应用和误差估计.主要工作包括:（1）讨论具有复杂拓扑结构的封闭曲面的方形图表示算法.通过应用同伦群生成元的计算方法,简化封闭曲面的拓扑结构.由于曲面的一阶同伦群生成元集合也
本文依托于国家重点研发计划项目（2017YFC0707603）、云南省科技厅重点专项（202003AC100001）,针对传统摩擦阻尼器的阻尼力和刚度在起滑之后保持不变、在持续增大的地震作用下不能提供有效的阻尼力和刚度的问题,设计了一种新型四弧面挤压型摩擦阻尼器（Four Arc Extrusion Friction Damper,简称FAEF型阻尼器）,该FAEF型阻尼器的主要特点是:可以依靠四
潮流能的有效开发与利用在减少碳排放、促进能源可持续发展等方面具有非常重要的科学价值和现实意义。水平轴潮流能水轮机作为潮流能转换装置的关键设备,其能量利用率、压力脉动特性、噪声特性的研究受到了众多学者的特别关注。目前,通常都是在水轮机外部安装导管来实现,该方法也受到了国内外学者的广泛青睐。尽管如此,目前潮流能水轮机的发展仍存在一些关键技术问题亟待解决,例如:1、导管与转轮间的间隙对潮流能水轮机水动力
我国西部地区大量运营公路隧道地处高烈度地震区,与此同时,运营隧道质量缺陷及病害问题较为突出,结构质量缺陷的存在会影响隧道抗震性能,使得含质量缺陷区域成为隧道抗震薄弱部位。带缺陷服役的隧道,将会成为未来公路隧道震害的高危区,严重危及国家交通生命线工程安全和人民生命财产安全。因此,开展缺陷影响下隧道结构地震损伤的研究,对揭示隧道地震响应的缺陷影响机理、实现全寿命周期抗震性能评价具有重要的理论意义。目前
目标检测是计算机视觉领域的经典任务,是后续进行图像分析、图像理解的关键。随着卷积神经网络的不断发展,基于深度学习的目标检测模型在检测精度和检测速度上都有重大的突破。小目标检测是现阶段目标检测的重点和难点问题,一方面,因为小目标像素分辨率低、特征信息少,易造成漏检、错检问题;另一方面,为了满足实时检测的需要,基于深度学习的小目标检测模型不能过于复杂。基于此,本文从提高模型检测精度和模型压缩两个角度出
自1972年以来,泰国政府为了照顾企业员工和雇主的利益实行了最低工资标准制度,通过一系列政策和法律,设定了最低工资标准及三方工资委员会,推行最低工资标准的有效实施。随着世界经济贸易的发展,泰国越来越多的外资投入为泰国各行各业的发展带来了新的活力,推动了泰国经济快速发展。经济发展带来了人们收入的增加,泰国最低工资标准受外商投资的影响发生若干次变化,外商投资因此的工资变化已经成为泰国经济领域、社会保障
排序问题是一种被广泛应用于生产计划、计算机控制等众多领域的一类重要的组合最优化问题,经常在理论界得到研究讨论.其就是要充分利用某些资源,达到以最佳方式完成一组任务的目标.排序问题在现实生活中的许多领域都扮演着不可替代的角色,人们对于各种排序问题的研究越来越多,等级约束下的排序问题就是其中之一.等级约束下的平行机排序问题是组合优化领域中的经典难题之一,近十年来得到了广泛的研究,在近似算法设计中发挥了
我国岩溶发育茂盛,众多房屋建筑以及基础设施包括市政道路、公路和铁路需在浅埋岩溶地下洞穴密布和发育的地区修建,而这些设施可能因为地下洞穴的影响发生地面变形、滑坡等灾害从而严重影响各类设施的安全与使用,所以在岩溶地方开展各类建设项目时,往往需要对有关场地进行稳定性评估。目前国内外的研究成果中,有关地下洞穴与岩土体稳定性关系的研究绝大部分专注于研究岩溶与地下洞穴的关系、地下洞穴本身的力学参数及其形成规律