【摘 要】
：
排序问题是组合优化领域中的一个基本问题,同时也是组合优化研究最为广泛的问题之一。排序问题广泛应用于生产制造、资源调度和物流运输等行业。带服务器的并行专用机排序问题是指工件在加工过程中需要一台服务器进行加载（或安装）,即工件必须先经服务器加载到机器上,然后才能进行加工,服务器一次只能对一个工件进行加载操作,专用机的定义是每台机器上需要加工的工件已知。本文主要研究的是两个目标函数为极小化最大完工时间的
论文部分内容阅读
排序问题是组合优化领域中的一个基本问题,同时也是组合优化研究最为广泛的问题之一。排序问题广泛应用于生产制造、资源调度和物流运输等行业。带服务器的并行专用机排序问题是指工件在加工过程中需要一台服务器进行加载（或安装）,即工件必须先经服务器加载到机器上,然后才能进行加工,服务器一次只能对一个工件进行加载操作,专用机的定义是每台机器上需要加工的工件已知。本文主要研究的是两个目标函数为极小化最大完工时间的带服务器的并行专用机排序问题,三参数法表示为PDm,S1 fixed-seq,sj=1|Cmax和PDm,S1| fixed-seq,pj=p|Cmax,这两个问题已经被证明了是强NP-难的,本论文主要工作是设计求解上述两个问题的多项式时间近似算法并给出算法最坏情况界的理论证明,并且通过计算机编程计算验证算法的实际效率。特别地,在算法设计时一方面要考虑每机器上工件加工时间总和,另一方面也要兼顾服务器不能有非必要的空闲,从而保证服务器尽可能连续工作。论文结构安排如下。第一章,介绍了组合优化问题概述、近似算法的基本定义和问题的数学模型描述,并对该类问题的研究背景和现状进行分析,得出研究该类问题的目的以及意义。第二章,介绍了一些解决该类问题的预备知识,包括问题描述,符号与最优解下界和本文主要结果。第三章,介绍了PDm,S1|fixed-seq,sj=1|Cmax问题,首先分析了数学规划模型;其次分析了最大剩余优先时间规则的近似算法和最坏情况界;再次分析了基于总加工时间递减规则的近似算法,并对3台机器以及m台机器的情形给出了算法最坏情况界理论证明,之后通过计算机编程进行数值实验以验证算法的实际性能;最后对本章的结论进行简单总结。第四章,介绍了PDm,S1| fixed-seq,pj=p|Cmax问题,首先分析了数学规划模型;其次分析了基于最大工件个数的近似算法对于该问题的可行性;再次对于m台机器不仅给出了 3种特殊情况下算法的最坏情况界,同时给出了一般情况下的最坏情况界和相关数值实验;最后对本章的结论进行简单总结。第五章,对本文所研究的内容进行总结和展望。
其他文献
计算机心脏瓣膜流固耦合仿真在临床医学和理论医学上拥有重要的研究意义,但目前为止学术社区中的心脏瓣膜仿真方法都需要耗费大量仿真时间,提出一种快速的心脏瓣膜仿真方法是亟待解决的问题。本研究针对上述问题提出了一种快速的计算机心脏瓣膜仿真算法。在求解瓣膜小叶在心脏周期内形变的问题中,利用分片非均匀有理B样条（Non-Uniform Rational B-Spline,NURBS）曲面表示瓣膜小叶几何,并在
随着信息技术的迅猛发展和普及,社会信息化程度持续提高,应用数据呈爆炸式增长。由于代价昂贵或设备故障,采集到的数据集往往是不完整的,这大大降低了数据的可用性。为进一步挖掘数据背后的价值,恢复缺失数据至关重要。然而,当前的数据通常具有多维结构,传统的矩阵填充方法难以处理。近年来,低秩张量填充（LRTC）模型因其能很好保留高阶数据的复杂结构,在视觉数据恢复、流量数据恢复等领域广受青睐。本文以张量列（TT
Censor和Elfving于1994年首次提出分裂可行性问题,用来表示相位复原和医学图像抽象出来的数学模型问题.实际上,分裂可行性问题还可以应用到信号和图像恢复、基因调控以及医学调强放射治疗等方面.许多学者对此类问题进行了深入的研究,且提出了相关的迭代算法,如CQ算法、松弛CQ算法等.近年来,有不少学者提出了在Hilbert空间中的广义分裂可行性问题,如分裂公共不动点问题、分裂等式问题等,都是分
图像分解是指将图像分解为卡通（cartoon）和纹理（texture）两部分,是图像处理中最基本的问题之一。图像恢复是将不清晰或信息不完全的图像还原为清晰或可识别的图像,它同样是图像处理中的一个核心问题。本文从图像分解问题出发,针对经典交替方向乘子法（ADMM）处理三块以上的凸优化问题不一定收敛的缺陷,提出具有全局收敛性的交替极小化方法实现分块低秩图像分解优化模型的求解。此外,我们基于分块低秩图像
计算投影算子的次微分是数值最优化中的重要研究课题之一。本文主要以刻画一类特殊集合上的投影算子的次微分为主题展开。在此基础之上,本文的结果为一类优化问题的算法设计和理论分析提供可能。具体的,本文的主要内容可以分为以下两个部分。本文第三章主要聚焦在刻画到广义单纯形集合上的投影算子的B-次微分集合。该节主要利用了一种特殊的雅可比矩阵——Han-Sun雅可比矩阵。在引入了该矩阵之后,本章节完全刻画了到该集
非负矩阵分解（Nonnegative Matrix Factorization,NMF）算法实现简便,且具有较好的可解释性和明确的物理意义,应用广泛.随着信息技术的迅速发展,需要处理更高阶的数据,即张量,而这些数据往往具有非负性,如彩色图像、视频数据等.因此,非负张量分解的理论及算法研究受到广泛关注.目前,关于非负张量分解的研究主要是基于CP分解,其利用原有数据结构信息进行图像识别,但在可解释性和
Halpern迭代算法是在Hilbert空间和Banach空间中寻找非扩张映射不动点的一类迭代算法,由Halpern在1967年提出.由于许多优化问题都可以转化为非扩张映射的不动点问题,因此Halpern迭代算法在优化问题中扮演着至关重要的角色.本文在Hilbert空间框架下,首先,介绍Halpern迭代算法并讨论在步长序列选择不同的情况下其收敛性,特别地,证明惯性Halpern迭代算法的强收敛性
多智能体系统是一个网络化的系统,智能体之间相互联系、相互作用。多智能体系统的一致性问题不仅要考虑每个智能体自身的动力学行为,更要关注智能体的连接拓扑对最终一致性行为的影响。在领导-追随者多智能体系统中,研究领导者的数目和位置对一致性的影响一直是一致性问题中的一个研究热点。本论文研究噪声网络的领导-追随者一致性,在一定问题背景下,其一致性是由拉普拉斯矩阵的顺序主子阵的特征值来刻画。由于特征值跟网络的
分裂可行性问题（SFP）来源于相位恢复和调强放射治疗,是刻画真实世界逆问题的强有力的模型,在信号处理、图像重建等领域中有着广泛的应用。该问题自提出以来,引起了众多研究者的兴趣,一系列求解算法也陆续被提出来,其中,最经典的当属CQ算法。然而,该算法最开始提出缺乏较容易理解的算法推导;且其作为梯度投影方法的一个特例,在求解过程中不可避免地涉及到步长的选择。在现有的研究工作中,对步长的选择依赖于矩阵谱范
近几十年来,随着振动梁研究理论的不断完善,Timoshenko梁和Rayleigh梁控制系统的稳定性研究已成为热点之一.事件触发控制是一种分段常值反馈控制,它能很好地保持控制系统的性能,在计算和通讯上效率更高,且能有效地降低能耗.因此,对弹性梁系统的事件触发控制的研究,无论是在控制系统理论上还是在工程技术应用上都是十分有意义的.本文主要研究Timoshenko梁和Rayleigh梁系统的事件触发控