具有维修时间的两台平行机在线排序

在排序问题中,机器可能出现故障或其他原因而需要维修,因此,在加工工件时把维修时间考虑进去是很必要的.对机器维修时间完全重合、可中断的两台平行机排序问题,本文考虑它的在线情形.通过分析不同情形,给出其任意在线算法竞争比的下界为2,并给出一个最好可能的在线算法.     

路上最大最小图均衡问题的在线算法

研究路上最大最小图均衡问题的在线情形。对于边权不可分的情形,在路的长度为2,且总权重W已知或最大权重wmax已知的情况下,该问题没有有限的竞争比。对于边权可分的情形,当n≥3时,无论总权重W是否已知,该问题具有相同的竞争比下界,当n=2时,总权重W是否已知将令问题具有不同的竞争比下界。当n=2且W已知时,设计了一个最优算法;当n=2且W未知时,设计了一个竞争比为4/3的最优算法;当n=3时,设计了一个竞争比为3/2的最优算法;当n=4时,设计了一个竞争比为3/2的最优算法;当n≥5时,设计了一个竞争比为2的最优算法。     

预先知道最大请求的两条线路带宽分派问题

研究两条线路带宽问题,利用“预先知道所有请求中最大的那一个请求的大小”这一部分信息来设计算法,该算法比可能有的最好的在线算法在性能上要好得多,同时在某些情况下,该算法是可能有的最好的半在线算法.     

两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题

研究了两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题,要求在整数时刻到达工件,整数时刻开始加工工件,当然也会在整数时刻完工工件.利用对手法证明任一实例在任意算法下竞争比不小于5/4,而任意的稠密算法的竞争比都渐近地趋于2;其次找到一种稠密算法—层次算法,其竞争比为2,从而说明此层次算法为本问题的一个最好可能在线稠密算法.     

预先知道工件最大加工时间的带机器费用的排序

对大多数排序问题来说，机器集往往是事先给定的，而且在算法进行过程中，机器集是不变的。Imreh和Noga第一次提出了在排序中考虑机器费用的模型。他们研究了所谓的List Model problem，并给出了竞争比为（1＋5的平方根）／2≈1．618的在线算法，同时证明了该模型的任意在线算法的竞争比至少是4／3。本文研究List Model problem的一个半在线情形，我们假设工件的最大加工时间预先知道，我们将给出一个竞争比为19／12≈1．583的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是4／3。这表明部分信息有利于设计更好的算法。     

预先知道总加工时间的一类特殊的三台平行同类机在线排序

研究三台平行同类机在线排序问题的一种特殊情形,即三台同类机的加工速度分别为s1=s2=1,s3=s≥1．利用“总加工时间”这一部分信息来设计算法,证明了该算法的竞争比为(s 2)/s~(1/2)．结合文献中曾有的关于此问题在线算法的下界,可以知道当S≥2时,该算法比可能有的最好的在线算法在性能上要好．     

三台平行同型机的一个半在线排序算法

本文研究三台平行同型机的一个半在线排序算法，我们假设工作的最大加工时间预先知道，我们将给出一个竞争比为（1＋√73)/6≈1.5907的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是√2.     

具有前瞻区间和不相容工件族的流水车间在线排序问题

研究对多台单位流水车间上具有前瞻区间的不相容工件族无界批处理的在线排序问题。通过组合优化的方法分类讨论得到问题的下界，对算法Am（β）进行了竞争比分析说明这是该问题最好可能的在线算法。给出了该问题的下界为1+η，其中η是方程(2f－1)η2+(f+β)η+β－f=0的一个正根，这里0≤β<1。同时提供了一个最好可能的在线算法Am（β）。通过竞争比分析说明了算法的可行性。     

两台带准备时间的同类机的半在线排序

研究了带机器准备时间的两台同类机的半在线排序问题,这里目标函数为极小化最大机器完工时间.对于所有工件总的加工时间已知的半在线情形,我们给出了一个竞争比为max{52 1,1 bb}的半在线算法,其中b为机器速度.并且算法对于对于机器加工速度b<2时的同型机情形是最好的.     

MC-CDMA系统中信号的峰均功率比

MC-CDMA系统信号的峰均功率比远大于单载波系统.B.M.Popovic对MC-CDMA系统中的扩频码进行了分析,通过数值模拟表明,Zadoff-Chu序列具有最低的峰均功率比,是用于MCCDMA中的最佳候选.本文通过理论推导得出选用任意长度的Zadoff-Chu序列作为MC-CDMA系统的扩频码,其峰均功率比均不超过3 dB.对长度为32的Zadoff-Chu序列扩频和Golay互补序列扩频的MC-CDMA信号进行了比较,其峰均功率比分别为3 dB和6 dB.     

具有预约到达时间的平行机在线排序问题研究

以现代服务业预定系统中的实际问题为背景,研究了一类具有预约到达时间和最迟完工时间的在线排序问题;论证了两台机器时该问题的在线算法竞争比下界为2;在传统在线排序算法的基础上提出了针对该问题的在线贪婪算法,并分析了该算法的竞争比.     

工件带拒绝费用的三台单机排序问题研究

本文对带拒绝费用的排序问题进行了研究,目标是极小化接受工件的最大完工时间与拒绝工件的总拒绝费用之和。对于一种三台机器的特殊情况,提出了一个新的在线算法,并对新算法的竞赛比进行了分析。     

工件具有区间限制的批在线调度

研究同构并行机上的批在线调度问题,目标函数是使最大完成时间(最后一个工件的完成时间makespan)最小.工件以批方式到达且每个批中有m个工件,每个工件的加工时间随其批的到达而给定且限定在某个时间区间上.当一批工件到达时,在对其后批的信息不了解的情况下,要立即对该批中的工件进行调度,调度过程中不允许中断.针对这一问题,给出了一个批在线启发式列表调度算法,在同一批中的工件按LPT规则调度,当一批中的全部工件被调度完后,调度下一批中的工件.对算法的最坏情况进行了分析并给出了算法的竞争率.     

TSP邻近算法在Euclid平面上的性能比分析

旅行推销员问题(TSP)邻近算法的性能比已经被证明有一个关于点数的对数函数上界,本文就该方法在欧几里得平面上给出了性能比的一个对数下界。     

基于快速下界估算的瓶颈旅行商问题竞争决策算法

利用数学推导和证明得出了一个瓶颈旅行商问题下界快速估算法,在此基础上利用竞争决策算法(新型优化思想)的通用模型,给出了一种瓶颈旅行商问题的竞争决策算法,经过大量数据测试和验证,并将求解结果与下界相比较,部分结果与下界相同．     

OFDM系统中的峰值平均包络功率比上下界的分析

本文主要对OFDM系统中的峰值平均包络功率比(PMEPR)的上下界进行了推导.推导结果表明,PMEPR的上界仅和数据序列的非周期自相关函数有关,这对于迅速去除PMEPR超过给定门限的数据序列是非常有用的.从推导的PMEPR下界看,只有当子载波数N很少时,它才会随N变化较大.针对一个16子载波的BPSK OFDM系统,本文借助于PMEPR的上界还对一种降低PMEPR的选择性映射技术进行了分析,并给出了所有可能信息序列的PMEPR分布.分析结果表明,最大PMEPR约为6.5dB,比最坏情况下的PMEPR减少了5.5dB.     

一种新的正弦波频率估计算法

研究了高斯白噪声条件下大样本点单一正弦波信号的频率估计方法.首先利用离散傅里叶变换确定频率粗估计,然后以该值为参考频率构造本地信号,将原信号下变频至基带,对基带信号分段求和,能得到一个新的正弦波信号,该信号的频率为真实频率与参考频率之差,最后利用最小二乘法估计新信号的载频,修正粗估计值就能得到原信号频率的最优估计.推导了算法的渐近方差与克拉美-罗限之间的关系.仿真结果表明,本算法能适用于整个频段范围,频率估计的精度接近正弦波频率估计的克拉美-罗限.     

带机器准备时间的两台机器半在线排序

研究了两台机器的两个半在线排序问题.当机器为有准备时间的同类机时,总加工时间已知;当机器为有准备时间同型机时,最大加工时间已知.对这两个问题,给出了各自的半在线算法,证明了他们的竞争比分别至少为b 1/2b 1和2/3,其中b,为机器速度,b1=1,1＜b2=b.     

有限期作业调度问题的最优化算法

本文讨论了有限期作业调度问题,用计数排序、分离森林中的有效路径压缩、按秩合并方法,得到了有限期作业调度最优化算法,其时间复杂性为O(na(m,n)),m=O(n),在实际应用中是一个线性时间复杂性算法,是渐近性能最佳的算法.