改进的循环谱估计快速算法与性能分析

该文提出了一种改进的循环谱估计快速算法,在估计性能不降低的条件下,减小了原有数字化频域平滑谱估计算法对数据量的要求。算法将时域平滑算法中数据加窗、重叠等处理方法引入频域算法,有效降低了估计方差,改善循环谱的估计效果。论文对改进算法渐进性均值、方差、谱分辨率的表达式进行推导。理论与实验结果分析表明:在相同数据量和谱估计分辨率的条件下,改进方法估计性能优于原算法,可用于实际低信噪比、小数据量、高分辨率要求下循环谱估计。

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

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

两台机器及时完工工件数最大化问题的近似算法

平行机排序问题 Pm∥ ∑uj当 m≥ 2时是一个 NP-难的问题 .本文利用求解 1∥ ∑ uj的 Moore算法构造了与 P2∥ ∑ uj等价的 P2∥ n -∑ uj问题的一个多项式时间近似算法 ,并证明了该算法的绝对性能比为 3/4 .此外还研究了机器带有准备时间的问题 P2 ,ri∥ n-∑uj,并证明了在这种情况下算法的渐近性能比为 2

Polar码并行级联结构设计及性能分析

提出一种基于Polar系统码的并行级联结构,通过引入迭代译码过程,以提升有限码长Polar码性能。首先利用分组码的联合界技术,在均匀交织的条件下分析了所提级联码的码重分布特性,并给出了在中高信噪比下的渐近性能界。然后,利用分量译码器外信息转移图分析了不同码长Polar码并行级联的迭代收敛性能。仿真结果表明,在AWGN信道条件下,所提并行级联码性能优于相同码长、码率的系统Polar码,并且与理论分析结果匹配,证明了理论分析的有效性。

参数摄动对FMS性能影响的研究

本文首先研究了加工时间参数摄动对FMS渐近性能的影响,得出了一个有较高精度的关于FMS渐近性能改变的估计式.然后根据此估计式详细分析了参数摄动对2×n型串行FMS渐近性能的影响.

基于强化学习的切换系统综合性能优化设计

研究连续时间切换自治线性系统综合性能优化,基于分阶段设计思路计算其最小(状态模)超调、在超调约束下的最小调节时间、在过渡过程约束下的最快指数收敛速度.借鉴强化学习方法,通过以模压缩路径的策略空间进行扩展获得有限步结束的迭代优化算法.数值仿真验证了所提算法的有效性.

周期性任务调度的装箱算法

针对基于时间触发的CAN控制系统,给出了确定周期性任务表中的基本周期的两种策略,提出了构造周期性任务调度表的下次适应、降序下次适应、最佳适应和降序最佳适应四种算法,分析了这四种不同算法的时间复杂度和最坏渐近性能比,最后对不同规模下的四种算法进行了仿真比较,结果表明文中给出的四种算法效果均优于经典的一维装箱算法。

TTCAN周期性任务的优化调度算法

TTCAN周期性任务调度是最优装载问题的推广,它在通信时间关键的实时分布式系统中有着很强的应用背景.本文提出了4种确定基本周期的策略,给出了首次适应和最佳适应两种不同的可以在多项式时间内构造出TTCAN周期性任务调度表的算法,最后对不同规模下的两种算法的实验结果进行了比较,指出了两种算法在不同的周期策略下的渐近性能比.

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

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

柔性Flow Shop加权完成时间调度问题的启发式分析

针对柔性 flow shop 加权完成时间调度问题,通过对机器环境进行分组,证明了一个基于有效作业最短加权平均处理时间的启发式算法是渐近最优的.

多天线频谱共享认知网络保密中断概率分析

针对单输入多输出认知无线电网络,研究了瑞利衰落信道下采用最大比合并时保密中断性能。在所研究的系统中,次用户发射机发送机密信息给另一个次用户接收机,次用户接收机配备多个天线并且采用最大比例合并多个接收信号。同时,拥有多个天线窃听者也采用最大比合并方案偷听次用户发射机和次用户接收机之间传送的信息。频谱共享下次用户发射机工作时必须保证主用户的服务质量。推导了保密中断概率的精确表达式,分析了系统保密中断概率渐近性能。仿真结果验证了分析的正确性。

局内装箱算法综述

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

基于时间触发的CAN协议任务调度优化算法

在基于时间触发的CAN协议的实时分布系统中,时间触发的CAN协议的任务调度是一个重要的问题。一种多项式时间复杂度的优化算法被提出来构造调度表,其基本周期有4种假定情况,其中在实验中给出了每种算法的渐近性能比,并证明折衷周期算法的性能要优于其它三种算法。

恒速处理机的多机Flow shop最小和调度问题的启发式算法分析

本文研究有n个作业需在s个处理机中心进行加工,处理机中心i由li个恒速机组成的非抢占式多机flowshop调度最小和问题.每个作业有s个工序,每个工序需在对应的处理机中心的任一台机器上加工处理,作业到达前不能加工,所有作业通过处理机中心的路径相同.目标是确定一个作业在每个处理机中心机器上的可行调度序列,使所有作业在最后处理机中心的加权完成时间总和最小化.在作业处理时间需求、作业权重分别为独立同分布的有界随机变量时,通过特殊flowshop调度松弛方法,我们证明该问题在作业数趋于无穷时,一个基于有效作业最短加权平均处理时间需求的启发式算法是渐近最优的.

最小费用箱子覆盖问题及其算法

提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,并证明了不存在绝对性能比大于1的算法.

带核元的带拒绝装箱问题

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

底为正方形的三维装箱问题

本文讨论如何将一堆底部为正方形，长、宽、高均不超过１的盒子装入一底为１×１，高为正无穷的柱形箱子，使装箱高度Ｚ为最小的问题．该问题已知为ＮＰ难的问题．Ｌｉ和Ｃｈｅｎｇ在１９９０年提出了多项式近似算法Ｃ１，其渐近性能比ｒ（Ｃ１）＝２．６８７５（见参考文献［１］）．本文根据算法Ｃ１的思想，进一步利用盒子底部为正方形的特点，尽可能不浪费高度空间，提出了所谓“单元装箱法”Ｄ，使新算法的渐近性能比得到改进：ｒ（Ｄ）≤２２５１７８４＝２．３２０１５．

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

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

工件和工具混合搬运的多吊机调度问题

从钢铁企业罩式退火过程提炼出一类工件和工具混合搬运的多吊机调度问题以最小化最大完工时间.由于该问题是强NP-难的,提出一个基于工具分配的启发式算法并证明了算法的绝对性能比为2,渐近性能比为3.算法的性能通过数值计算实验给出了估测,结果表明,所提出的启发式算法对大规模问题也可以产生高质量的解.

局内最优问题的决策

一前言经济及其它领域中的最优决策问题经常是从实际问题中提炼出数学模型,并找出影响该数学模型的因素,然后求出问题的解并实施决策,然而现实生活中有些因素是在决策过程中发生的,在建立数学模型时,并不能确切地知道这些因素怎么发生(什么时候发生,发生的概率多大,……),而这些因素对决策的效果有很大的影响,如何找出问题的解并实施决策呢? 例如装箱问题:N件物品存放到容积为L的箱子中去。