孙云[1]2003年在《立方形递归网络若干性质的研究》文中提出互连网络的研究是数学和计算机科学的一个热点，在图论、算法设计与分析、计算机体系结构、并行与分布计算、计算机网络与通信以及大规模集成电路的设计等诸多方面起着非常重要的作用。超立方体及其变体是一类具有良好的拓扑性质和网络参数的互连网络模型，所以关于它们的研究与应用在互连网络的研究中备受青睐。 本文正是围绕超立方体及其变体展开研究工作的，主要成果如下： (1)通过超立方体及其部分变体(如交叉立方体、M(?)bius立方体、广义扭立方休、扭n—立方体、扭立方体连接网络)的网络结构分析，引入立方形递归互连函数的概念，提出一类包含交叉立方体、M(?)bius立方体、广义扭立方体、扭n—立方体、扭立方体连接网络等在内，反映超立方体及其部分变体结构递归性的互连网络模型——立方形递归网络。 (2)分析研究了低维立方形递归网络的拓扑类型，给出了立方形递归网络互连函数代数表达式，为研究立方形递归网络给出了新方法。 (3)证明了n维立方形递归网络是一类连通度为n的n正则网络；讨论了立方形递归网络直径界的问题；研究了立方形递归网络的容错指标(或容错性能)： ①证明了立方形递归网络顶点容错度，边容错度皆为n； ②给出了立方形递归网络核度的上下界； ③证明了立方形递归网络是1—坚韧的网络； ④给出了立方形递归网络离散度的取值范围； (4)对立方形递归网络的子网和超网进行了讨论，揭示了该类网络的结构递归性。 (5)证明了立方形递归网络是一类Hamilton图。该证明是基于立方形递归网络的结构递归性给出的一个构造性证明，证明方法巧妙，证明过程直观。
孙云[2]2007年在《二进制立方形递归网络拓扑性质研究》文中认为互连网络技术在并行计算机、计算机体系结构领域被广泛研究。在众多互连网络拓扑中,超立方体及其变体是一类具有良好拓扑性质和网络参数的互连网络模型,关于它们的研究与应用在互连网络的研究中备受青睐。本文在定义了一类特殊的超立方体变体的基础上,对该类互连网络的网络参数及环网可嵌入问题进行了系统而深入的研究。我们通过对二进制递归网络拓扑结构的对比分析发现,研究者最感兴趣的一类二进制递归网络都有一个共同特征:它们均以3维立方体和扭3立方体作为基本模式进行网络互连。根据这一特征,本文对该类特殊的二进制递归网络进行了代数定义,并称其为“二进制立方形递归网络”。二进制立方形递归网络虽然只是二进制递归网络的一个子集,但却是当前二进制递归网络中的重点研究对象。由于网络的很多参数和性质都是与网络的拓扑结构直接相关的,所以真正了解并正确刻画网络的拓扑结构,对得出与网络拓扑相关的正确结论,以及更好地对网络进行优化起着至关重要的作用。本文借助超网的概念,对二进制立方形递归网络的拓扑结构进行了详细分析,对其拓扑特征给出了精确描述。网络直径是用来衡量网络性能的一个重要参数,直径的大小直接决定着网络的通信时延,任何一种新型网络的产生都离不开对网络直径的讨论。本文给出了n维二进制立方形递归网络直径的上确界和下确界,并根据二进制立方形递归网络的特征描述证明了结论的正确性。这不仅能为试图寻找具有更小网络直径的新型二进制立方形递归网络提供可行性参考,还能指导人们在实际算法中设定消息接收的最大与最小等待时间。路由算法是网络算法中最基本和最重要的算法之一,它的目的是在网络拓扑图上寻求由源点到目的点的路径,它是所有其它网络算法的基础。给出了一个适用于所有二进制立方形递归网络的路由算法,该算法能使几种非常重要的二进制立方形递归网络取得最短路径。网络的连通度是衡量一种互连网络可靠性的重要参数。证明了相同维数的所有二进制递归网络的连通度相同,这说明那些直径小于超立方体直径的变体在降低了超立方体直径的情况下并没有降低网络的可靠性。网络的故障直径是与网络连通度密切相关的一种网络参数,它指出了系统中某些给定数目的处理机发生故障时的最大传输延迟。本文确定了n维二进制立方形递归网络故障直径的上确界和下确界,说明了任何二进制立方形递归网络的最大故障时延不会高于超立方体的最大故障时延。环(圈)可嵌入问题是互连网络研究中的又一个重要议题。网络中可以嵌入Hamilton圈,说明该网络中可以嵌入与它具有相同顶点数量的环网。利用二进制立方形递归网络的拓扑特征,给出了在二进制立方形递归网络中嵌入Hamilton圈的构造算法,打破了使用归纳假设方法证明超立方体及其变体中Hamilton圈存在性的传统,为实际应用提供了保证。依据该Hamilton圈的构造算法,给出了二进制立方形递归网络具有几乎泛圈性的一个充分条件,同时给出了在二进制立方形递归网络中构造任意长圈的构造算法,使得环网中的并行计算算法直接用于超立方体及其变体成为可能。
张思佳[3]2016年在《几类重要互连网络拓扑结构图的反馈数研究》文中提出图的反馈数问题是在实际应用中提出来的。计算机操作系统中解决“死锁”问题、网络攻击中最小攻击点集问题等都可以转化为在图中求一个最小反馈点集的问题。求图的反馈数问题已被证明是NP困难问题,其每一个进展都十分艰辛。到目前为止,只有少数的图类得到了其反馈数,已经得到反馈数界的图类也不多。本文对与互连网络拓扑结构设计方法(笛卡儿乘积方法、线图方法、Cayley方法)密切相关的几个重要的图类的反馈数进行了研究,分别给出了Flower Snark相关图Jn、Knodel图W△,n。和循环图Gn(1,k)的反馈数、增广立方体AQn反馈数的上下界、局部扭立方体LTQn反馈数的上界以及Kautz有向图K(d,n)反馈数的上界。(1)对Flower Snark相关图Jn、Knodel图W3,n和W4,n、循环图Cn(1,K)的反馈数进行了研究。利用Jn、W3,n、W4,n和Gn(1,k)的循环结构,分别找到了相应的带循环节的无圈子图顶点集的构造方法,基于这些顶点集分别得到了如下结论。①给出了Flower Snark相关图Jn反馈数为：f(Jn)=n+1；②给出了W3,n反馈数：f(W3,n)=(?)；③给出了W4,n反馈数：f(W4,n)=(?)；④ 给出了偶数n≥5+1+2(?)+mod3)且3≤奇数k<n/2时的Cn(1,k)反馈数：f(Cn(1,k))=(?)(2) 对增广立方体AQn、局部扭立方体LTQn两种变型超立方体网络的反馈数进行了研究。利用AQn和LTQn顶点递推结构和边集性质,分别构造出了相应的可递推的无圈子图顶点集函数,基于这些函数,分别给出如下结论。①给出了AQn反馈数紧的上下界为：2n-3×2n-3≤f(AQ)≤2n-(2n-2+2(?))；②给出了LTQn反馈数的上界为：f(LTQn)≤2n-1。(3)对有向Kautz图K(d,n)的反馈数进行了研究。给出了Kautz有向图K(d,n)的一种新的反馈点集顶点短表达式模式,基于该模式得到了更小的反馈点集,给出K(d,n)渐进估计从O(dn-4)下降到O(d2)。
郑晓军[4]2010年在《生产车间设施布局优化方法研究》文中认为生产制造企业的设施布局是设施规划领域的一个重要问题。它研究如何按照一定的原则,在预先给定的生产车间内,将生产系统所使用的机器、仓库等的位置以及与之相关的物料流和人员流进行合理地组织与布置,以达到最优的设计目标(如物流成本最低、设备利用率最高等)。一个设计良好的设施布局能加快物料处理效率,减少在制品的停留时间,显着提高企业的生产效率。在理论上,本问题属组合优化问题,NP-hard问题,本文讨论的车间设施布局问题与一般的布局优化问题(如Packing问题和Cutting问题)相比,在问题描述、数学建模、数值求解等方面更困难,在工程应用上,本文研究的生产制造系统的设施布局问题是实际生产中存在的尚未很好解决的难题,具有重要的工程实用价值。本文在国家自然科学基金项目的资助下,以生产车间设施布局为研究对象,研究该类布局问题的有效求解方法。车间设施布局可分为块状布局和详细布局,前者不考虑设备的尺寸形状,只确定其在车间内的相对位置,而后者考虑设备的尺寸形状等信息,并确定其在车间内的坐标和方位。与块状布局相比,详细布局的优化目标与约束条件更多,求解也更加复杂。本文重点讨论后者。论文的主要工作如下：(1)针对一类块状布局问题——环形布局问、题的求解,提出一种称之为设施相对位置编码的方法,并基于差异演化(DE)算法,构成相对位置编码的DE算法,用于环形布局问题的求解。编码方式是决定用进化算法求解问题效率和质量的关键,该编码方式利用环形布局序列问题的解具有设施的位置排序的特点,省去实数编码算法求解该类问题时需要进行实数到整数序列的映射过程,解决了用实数编码算法求解时编码空间远大于环形布置解空间的缺点,并且减少无效编码。(2)提出一种基于图论的求解设施之间避障曼氏最短路经的连接图生成方法,用于求解详细布局问题的设施间的最短曼氏距离。设施间的物流量是设施布局优化的一个最主要的目标,而物流量的大小又与选择的设施之间的路径长度直接相关,因而设施间的路径会直接影响布局优化算法求解的质量,对于详细布局问题尤其重要。本文连接图生成方法利用了曼氏距离不同于欧氏距离的特点,可较快计算设施间的最短路径及其距禺。(3)建立了更加贴近于实际的设施详细布局数学模型并且给出一种基于满意度的差异演化算法求解该详细布局问题。建模方面,与以往详细布局文献中仅考虑设施的外形尺寸不同,该数学模型还额外考虑了设施的装卸点、设施间的连通性、设施间的最短路径、设施布置的整齐美观性等要求。求解方面,针对设施详细布局问题的多约束、多目标且具有NP难度的特点,以及求解最优解难以实现的问题,本文提出用满意解代替最优解,将满意优化原理与差异演化算法相结合,用综合满意度函数作为差异演化算法的目标函数,并且在运行过程中综合考虑满意求解,从而完成详细布局问题的求解。(4)给出开发设施详细布局优化与仿真的系统原型及其关键技术,包括：①从设施的CAD几何图形数据库中检索给定设施的检索方法,本文给出一种基于叁维几何模型局部缩放的叁维CAD模型检索方法；②基于Pro/E的实体简化技术,用于设备几何外形数据提取；③干涉量计算模块,用于详细布局算法求解过程中设备间干涉量的计算；④基于Pro/E二次开发的布局仿真,用于将求解获得的设施布局结果在Pro/E环境中进行叁维仿真,便于设施规划人员进行综合评判。本文给出车间设施的环形布局和详细布局的数学模型和相应的求解方法,并且给出开发一类设施详细布局优化与仿真的关键技术及其系统原型实现,可为设施规划人员提供设计参考。本文方法可望推广应用于其他类型的设施规划应用领域,如机场、医院、办公室等的设施布局问题。
参考文献：
[1]. 立方形递归网络若干性质的研究[D]. 孙云. 大连海事大学. 2003
[2]. 二进制立方形递归网络拓扑性质研究[D]. 孙云. 国防科学技术大学. 2007
[3]. 几类重要互连网络拓扑结构图的反馈数研究[D]. 张思佳. 大连理工大学. 2016
[4]. 生产车间设施布局优化方法研究[D]. 郑晓军. 大连理工大学. 2010