【摘 要】
：
排序论是组合优化的重要分支之一,在计算机和管理科学等方面都有着广阔的应用.随着现代工业的蓬勃发展,在制造业等领域出现一批诸如加工时间可变、可拒绝、双代理等排序新模型.本文研究了加工时间依赖位置的双代理排序问题,其中工件的实际加工时间会随着位置而改变.全文共分为四章.第一章介绍了排序的背景,复杂性理论及算法.第二章介绍了工件加工时间依赖位置的双代理流水作业排序问题,考虑了两台处理机的情况.在代理B的
论文部分内容阅读
排序论是组合优化的重要分支之一,在计算机和管理科学等方面都有着广阔的应用.随着现代工业的蓬勃发展,在制造业等领域出现一批诸如加工时间可变、可拒绝、双代理等排序新模型.本文研究了加工时间依赖位置的双代理排序问题,其中工件的实际加工时间会随着位置而改变.全文共分为四章.第一章介绍了排序的背景,复杂性理论及算法.第二章介绍了工件加工时间依赖位置的双代理流水作业排序问题,考虑了两台处理机的情况.在代理B的时间表长不大于给定值的前提下,证明了极小化代理A的时间表长问题是NP-难的,并证明了工件在每一台机器上原始加工时间相等的特殊情形是多项式可解的.如果工件具有不同到达时间,证明了极小化代理A的时间表长问题在代理B的总完工时间不大于给定值的前提下是强NP-难的.对极小化两个代理时间表长加权和问题,利用Johnson规则设计了一个最坏性能比为(（1+α）/αf（1）/f（n）,（1+α）f（1）/f（n）的近似算法.第三章介绍了工件加工时间依赖位置的双代理可拒绝单机排序问题.在代理B接收工件的时间表长加拒绝工件总惩罚费用不大于给定值的前提下,首先证明了极小化代理A接收工件的时间表长、总完工时间加拒绝工件总惩罚费用的问题都是NP-难的,然后设计了对应的伪多项时间动态规划算法,最后分别给出了基于几何舍入技术和膨胀的拒绝惩罚的全多项式时间近似方案.第四章介绍了工件加工时间依赖位置的双代理可拒绝平行机排序问题.在代理B接收工件的时间表长加拒绝工件总惩罚费用不大于给定值的前提下,分别考虑了两台同型机和两台同类机问题.针对前者,证明了极小化代理A接收工件的时间表长、总完工时间加拒绝工件总惩罚费用问题是NP-难的,并分别设计了伪多项式时间动态规划算法.对于后者,用标准完工时间设计了极小化代理A接收工件的时间表长加拒绝工件总惩罚费用问题的伪多项式时间算法.
其他文献
数学史是数学文化的主要载体,数学史在数学教学中的应用是人们热议的话题。数学教师的专业发展关系着教育的根基、民族的命脉。而职前数学教师一直是教师的后备力量,担负着教书育人的使命和责任,是未来教师职业发展的一个关键时期。本人结合自身实践经验,深度挖掘数学史与职前数学教师教学设计能力之间的关系。主要从以下两个角度去展开:（1）职前教师在学习HPM理念之前,职前数学教师在教学设计方面的能力如何?数学设计能
在经典的排序问题中,人们一般假设在加工工件的整个过程中机器都是连续可用的.然而,在实际的生产过程中,存在机器损坏或者机件故障的情况,会导致机器在某个时间段不可用,因此适时地对机器进行维护可以有效地提高机器生产效率或产品质量.同时,由于资源配置有限,制造商通常会拒绝加工部分利润小的工件,以获得最大的利润,拒绝工件需要支付一定的惩罚费用.因此,研究带有维护活动的排序问题、工件可拒绝的排序问题,有着重大
近年来,随着控制理论的发展,人们对控制精度的要求越来越高.众所周知,由于机械和电气系统的摩擦和负载变化、测量噪声、环境干扰、传感器和执行器等引起的误差,在大多数实际控制过程中都存在着干扰.这些干扰会降低系统性能,甚至使动态系统变得不稳定.因此,受到干扰的动态系统的稳定性分析和控制器设计已成为近几十年来的研究热点.为了抑制和消除干扰,人们提出了多种抗干扰方法,如鲁棒控制、自适应控制、滑模控制、∞控制
本文主要研究了非线性两项分数阶微分方程边值问题解的存在唯一性,包含四章内容.第一章是绪论,主要介绍了两项分数阶微分方程边值问题的背景及研究意义.第二章研究了一类带有积分边界条件的分数阶微分方程（?）解的存在唯一性,其中n-1＜α≤n,a＞0,D0+α是标准的Riemann-Liouville导数,f:[0,1]× R3→R是连续函数,Φu（t）=∫0tΦ（t,s）u（s）ds,Ψu（t）=∫01
近年来,关于非线性分数阶微分方程边值问题的理论和研究众多,例如多点边值问题、带有Ricmann-Sticltjcs积分的边值问题、带p-Laplacian算子的奇异问题、带有Ricmann-Liouville和Caputo的混合分数阶边值问题等.分数阶微分方程大量应用于空气动力学、聚合物流变学、物理学、生物物理学、热力学、电路、生物学、血流现象等.本文主要研究了几类非线性分数阶微分方程解的存在性,
自然界中的许多现象可以由分段微分动力系统来表示.极限环的分支问题是当前分段微分动力系统的重要研究课题之一.本文以分段近哈密顿系统为核心,对系统添加不同的切换流形和扰动,讨论系统的极限环分支个数问题.本文的研究内容分为三部分.首先,我们研究了一类具有三条非线性切换曲线的平面分段近哈密顿系统的极限环分支问题.三条切换曲线从原点出发,将相平面分为三个子区域.在系统存在周期环域的假设下,建立了 Poinc
思维是语言的内核,口语交际训练中,思维训练必不可少。初中语文口语交际教学的任务之一,是通过口语交际活动训练学生的思维,培养他们良好的思维习惯。将语文口语交际教学和思维训练相联结,不仅可以提高学生的口语交际能力和水平,增强他们的思维能力,还能够改善和优化当前的口语交际教学实践,提高课堂效率和质量。不容忽视的是,在初中语文口语交际教学实践之中,思维训练还没有引起足够的重视。基于此,论文以初中语文口语交
在新时代教师教育政策对教师专业知识的持续关注以及基础教育改革对数学教师专业知识不断提出新要求和新挑战的背景下,职前数学教师作为教师队伍的未来生力军,针对其开展教师知识研究极具现实意义。本研究基于Carrillo等人提出的“数学教师的专门知识”（Mathematics Teacher’s Specialised Knowledge,简称MTSK）模型将研究内容确定为教育实习中职前数学教师的专门知识并
在算子代数的研究中,保持问题是比较热门的研究方向之一.多年以来,引起了一大批的数学家和科研人员的广泛关注.Kubo,Ando,Molnár,Petz,Palmer,Gaál和Semrl等学者对均值的保持问题展开了大量的研究,并得到了一系列有意义的成果.其中,Molnár对各类均值的保持问题进行了一系列的刻画和研究,从而极大促进了算子代数领域中均值的保持问题的发展.本文第一章主要介绍了算子代数中的相
随着青少年成长过程中相关问题凸显,生命教育越来越引起社会重视。初中阶段是人生发展的关键时期,身心、认知、思想等各方面处于急遽变化中,在此阶段对学生进行生命教育有助于其树立正确的生命观,找准人生方向,找到自我存在的价值和意义,平稳过渡到青年时期,提升生命质量。同时,语文学科蕴藏着丰富的生命教育资源,以其人文性、创生性等特点,可以在青少年生命教育方面发挥重要作用。论文以部编本初中语文教材为抓手,分析教