带机器准备时间的同类机在线与半在线排序问题

研究带机器准备时间的m台同类机 (uniformmachines)在线和半在线排序问题 ,目标函数为极小化最大机器 (工件 )完工时间 .对于在线情形 ,证明了LS算法的最坏情况为 ρ =( 1+ 5 ) 2 ,m =2 ,1+ 2m - 2 2 ,m≥ 3 ,并且当m =2时 ,LS算法是最好的近似算法 ;当m =2 ,3 ,… ,6时界是紧的 ,特别地 ,当s1 =s2 =… =sm - 1 ,sm ≥ 1时 ,证明了LS算法的最坏情况界为 ρ =( 1+ 5 ) 2 ,m =2 ,3 - 4 (m + 1) ,m≥ 3 ,而且界是紧的 ;对于已知加工时间递减的半在线排序问题 ,证明了LS算法的最坏情况界为 2 - 2 (m + 1) .

调和装箱算法的平均性能分析

经典一维装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用 .该文系统地分析了在待处理的物品大小相互独立的情况下 ,L ee & L ee提出的调和近似装箱算法的平均性能 ;具体给出了在均匀分布下 ,调和算法平均性能比的值 ,并用实验验证了这些结果 .

椭圆型蜗壳设计与CFD分析

椭圆型蜗壳最大优点是蜗壳断面向纵向延伸 ,与传统的带蝶形边假椭圆不同 ,它是箱式结构的断面可以用椭圆函数表达的真椭圆 ,在流速系数相同的条件下 ,能够减小蜗壳控制尺寸 ,或者在控制尺寸相同情况下 ,适当增加转轮直径。通过优化设计 ,椭圆型蜗壳可获得优异的水力性能。但是 ,椭圆的长宽比不可无限增大 ,本文通过CFD分析 ,给出椭圆型蜗壳长宽比的限制值。

最坏情况下的鲁棒自适应波束形成算法性能分析

研究了最坏情况下的鲁棒自适应波束形成算法,它通过对角加载提高波束对方向矢量误差的鲁棒性.给出了其最优对角加载因子的近似解析达式,揭示了各种因素如何影响最优加载因子.在此基础上,对该算法进行了性能分析,推导出了关于目标功率估计和信号干扰噪声比的近似表达式.计算机仿真验证了本文的分析.

考虑加工与运输协同调度的单机排序问题

在考虑加工与运输协同调度的单机排序问题中,每个工件尺寸不同,工件在一台机器加工后,由m辆有容量限制的运输工具运送到同一个顾客处,目标是极小化最后一个送到其顾客的工件的到达时间,本文给出了该问题的一个最优算法,并且证明了该算法的最坏情况界为3/2。

带并行工件的平行机排序问题的一个新近似算法

讨论并行工件平行机排序问题,目标为极小化所有工件的总完工时间.这是一个强NP-难的问题.通过对(0,1]区间划分的深入研究,提出了一个多项式时间的近似算法,其渐近性能比的上界为1.6,下界为1.5.该算法比LI(1999)中提出的算法的渐近性能比明显地小.

受启动空间约束的装箱问题

提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.

工件带链约束和尺寸的并行批排序

主要对带链优先约束和尺寸的工件并行批排序问题进行了研究,当工件的加工时间一致时对目标函数是极小化所有工件加工时间之和的情形,借助于拆分的技巧,给出了一个最差性能比为2的近似算法.

机器具有不可用时间间隔的两机流水车间调度问题求解性质

在实际制造环境中,机器由于随机故障或进行预防性维护等,在某些时间段内处于不可用状态,为此,该文研究了任意一台机器具有不可用时间间隔的两机流水车间调度问题,给出了使用Johnson算法得到问题最优解的条件,分析了将Johnson算法作为问题启发式算法的最坏性能比范围。该文研究结果为探索机器具有不可用时间间隔的两机流水车间调度问题的最优算法提供了理论依据。

受位置约束的有色装箱问题

作为对有色装箱问题的推广,提出了一种受位置约束的有色装箱问题(longest item at the bottom coloring bin packingproblem,LIBCBPP),即在有色物品的装箱过程中,要求重(长)的物品置于轻(短)的物品下方。该问题在任务调度和日常生活中的运输等问题中有着广泛的应用背景。给出了一个求解该问题的近似KC-LIBFF算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果。

高强方钢管高强混凝土柱-钢梁套管环板节点有限元分析

目的研究一种新型方钢管混凝土柱与钢梁套管环板节点,以解决T型连接件与柱壁分离的现象以及外环板在外荷载作用下对节点承载力贡献不足的问题。方法采用ABAQUS对节点在低周往复荷载作用下的力学性能进行有限元分析。研究轴压比、梁柱抗弯承载力比值、套板高度、套管厚度等参数对该新型套管环板节点受力性能的影响。结果套管环板节点为半刚性节点,且具备良好的抗震性能和耗能能力,通过材料强度改变梁柱抗弯承载力比值会影响节点的破坏模态和抗震性能。结论建议轴压比控制在0.4~0.6;套管高度取100~200 mm;套管厚度取6~10 mm。

局内装箱算法综述

系统地介绍了局内装箱算法,归纳了其发展过程中的各种改进如数据分配模型、箱的划分等。阐述了该算法在工作分配、任务调度以及日常生活中的计划、包装、调度等计算机工程领域的应用。最后,对局内装箱算法提出了进一步的研究方向。

加工时间成比例的两阶段自由作业排序问题

对一类工件加工时间成比例的两阶段自由作业排序问题进行了研究.工件需要分别在包含m1和m2台平行机的两阶段中进行加工,工件在阶段间的加工满足自由作业环境要求,且相同工件在两阶段的加工时间相同,目标是极小化时间表长,即最后完工工件的完工时间.证明了当min{m1,m2}≥2时该问题是NP-难的,给出了该问题的一个近似算法,并证明了该算法的最坏情况界不大于3/2-3/2(2min{m1,m2}+1).得到了当min{m1,m2}=1时,该算法为问题的最优算法.

工件有优先约束和尺寸的单机分批排序问题

研究了工件有优先约束和尺寸大小关系的分批排序问题,这里目标函数为工件的极大完工时间,这类问题是NP—完备的.对工件加工时间相同和有特殊到达时间的情况给出了它的近似算法,并证明其最差性能比不超过2.

带启动重量的脆度装箱问题

讨论如下定义的带启动重量的脆度装箱问题:设有许多等长的一维箱子,给定一个物品集,每个物品有2个参数(脆度和重量),若箱子是首次装入物品,则需要添加额外的启动重量,在装箱的过程中要保证每个箱子的启动重量和所装物品重量之和不能超过该箱子内物品的最小脆度,问怎样安排物品使所用箱子数最小.该问题是一个新的组合优化问题,来源于CDMA蜂窝通信系统中的信道分配.本研究给出了一个求解该问题的线性脱线算法C-NFI,分析了其最坏情况渐进性能比为2,并给出了相应的试验结果.

带核元的带拒绝装箱问题

讨论了如下定义的带核元带拒绝装箱问题:设有许多等长的箱子,给定一个带核元的物品集,每个非核元有2个参数:大小和罚值.非核元物品可以放入箱子也可被拒绝放入箱子.如果某物品被拒绝放入箱中,则产生惩罚值,同时要求核元不允许被拒绝且每只箱子中所装核元个数不超过1,问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,在多处理器任务调度及内部互联网信息管理等问题中有着广泛的应用背景.提出了一个求解该问题的局外近似算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果.

基于最差情况性能优化的稳健盲波束形成算法

针对在实际通信应用中存在导向向量偏差的情况下,阵列输出的信干噪比SINR性能急剧下降的问题,提出了稳健受限LSCMA算法,并对其输出性能进行了理论分析.该算法利用后验概率密度函数估计信号导向向量,并增加权向量的二次型约束,降低了信号波达方向的不确定性,提高了对信号导向向量偏差的稳健性,使阵列输出的信干噪比SINR接近最优值.仿真实验表明,所提稳健受限LSCMA算法比传统线性受限LSCMA算法的输出性能要好,更适合实际的通信环境.

基于LIB的有色箱覆盖问题

提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方。该问题是一个新的组合优化问题,来源于多处理器任务调度。给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏情况渐进性能比为0,并给出了相应的实验结果;进一步对求解该问题的局内算法性能比的下界进行了讨论。

互联网信息管理中的带拒绝装箱覆盖问题

作为对装箱覆盖问题的推广,提出了带拒绝的装箱覆盖问题:设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子。每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱。如果物品被放入箱中,则产生费用。该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景。给出了一个求解该问题的局外近似算法C-FF,分析其最坏情况渐进性能比为1/2,并给出了相应的实验结果。

带拒绝箱覆盖问题的局内算法

作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题。设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱。如果物品被放入箱中,则产生费用。该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景。给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果。