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

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

工件可预处理的单台机排序问题

考虑一个工件可预处理的单机排序问题．要求在所有工件能够按时完工的前提下,使得预处理工件的费用最小,证明了对于一般情况,该问题是NP-难的,并给出了动态规划算法．进一步,得到当每个工件的预处理费用都相同时该问题是多项式可解的,并给出了强多项式时间算法．     

带有多次速率改变行为的单机排序问题

研究机器带有多次速率改变行为的单机排序问题.机器可以通过不超过t个时段的中断来调整加工速度, 即每个工件在每次中断时段前后加工的加工时间可能不同.因此问题就需要决定是否中断,以及何时中断,使得最大完工时间、完工时间总和、加权完工时间总和等尽可能小.对任意固定的t,关于最大完工时间和完工时间总和目标分别给出了多项式时间最优算法,对满足正则假设的加权完工时间总和目标也给出了一个多项式时间最优算法.     

带准备时间的两台同类机已知工件总加工时间的半在线排序问题的近似算法

主要研究带准备时间的两台同类机已知工件最大加工时间的半在线排序问题，目标函数极小化最大机器完工时间和极小化最大工件完工时间．对此问题给出了竞争比为√2的近似算法，并证明了不存在竞争比小于1＋√3/2的近似算法．     

一个带退化工件的单机准时生产制问题

研究带退化工件的单机排序问题,即工件的加工时间是其开始加工时间的线性递增函数,且不同的工件具有不同的退化率.要求为所有工件寻找一共同的最优交货期和最优序,以极小化这些工件的共同交货期、超前罚和迟后罚之和.给出了一O(nlogn)时间的最优算法.     

线性约束凸规划问题的仿尺度算法

对一般线性约束凸规划问题，给出了相应的仿尺度算法，并证明由该算法所产生的迭代点要么直接到达问题的最优解，要么其极限点满足问题的最优性条件。     

社会网络中影响集选择的一个近似算法

在研究社会网络影响集的选择问题中,目标是选取网络G中的一个最小点集S,使得V（G）-S中的每个点都至少有一半邻点在S中.本文给出一个α（△＋1）/δ＋1-近似算法,其中δ和△分别表示图G的最小度和最大度,α是局部独立数,它指示着图G的局部区域中最多含有的独立点的个数.     

次模函数近似算法求最小颜色生成树

给定图G并对其进行边着色,G的最小颜色生成树（MCST）问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有近似比为常数的近似算法.本文中,我们利用次模函数理论（贪婪算法的思想）给出最小颜色生成树问题的一个近似算法,且此算法的近似比为最好结果.     

多项式零点同时逼近算法的加速

对多项式重零点同时逼近算法提出了一种加速技巧,求得了加速算法的收敛阶,并给出了数值计算实例。     

有界区域上多峰函数全局优化问题的改进演化算法

针对演化算法求解有界区域上的多峰函数全局优化问题中，保持种群多样性和搜索效率的矛盾，提出了一种结合了多样性维持机制和加速算子的改进演化算法并对算法作了收敛性分析．实验结果表明，在低维情况下，算法容易收敛于全局最优解，优于基本遗传算法；在高维情况下，虽不满足收敛条件，但算法仍能收敛到本文意义下的ε-满意解，优于基本粒子群算法．     

一个新的交通网络平衡设计模型及其算法

针对城市道路网络改造问题中，待改造道路和拟添加道路均具有等级选择的特点，提出了一种更加符合实际的新的网络平衡设计二层规划模型，设计了粒子群求解算法，并给出了一个简单的算例，实际算例表明该算法具有计算简单，收敛速度快的特点．     

基于变长编码求解一维下料问题的演化算法

针对一维下料问题的特点,将线性规划方法与演化算法相结合,提出了一种基于变长编码求解一维下料问题的演化算法,该算法设计了一种新颖的遗传算子,实现简单,求解快速,实验表明,运用该法求解下料问题,材料利用率高,平均达到97．5％以上,具有很好的实用价值。     

平面图团覆盖问题的核心化和参数化算法

团覆盖问题是经典的理论计算问题,本文从参数理论角度考虑平面图团覆盖问题,提出了核心化简化规则,通过这些简化规则可以得到平面图团覆盖问题的核心,其规模为4k-4.根据该问题核心设计了参数化算法,可以用O（20k＋n2）复杂度求得平面图团覆盖问题的精确解.通过实验与现有的求解团覆盖的算法进行了比较.     

一种交互式的Ad Hoc网络QoS路由算法

针对分簇结构的Ad Hoc网络以及一些特定业务对于多个目标同时性能的要求，本文选取带宽作为约束条件，把时延和丢失率作为QoS优化目标，建立了QoS路由选择的多目标整数优化模型，并给出了求解模型的交互式算法。该算法能够根据决策者的偏好以及网络的实际情况压缩目标空间，快速地找到满意路由。实例计算结果表明了算法的可行性。     

关系模式关键字的一个求解算法

本文给出了关系数据库模式中求解关键字的一个算法。算法很简洁并且对于[1]定义的一大类问题,执行时间是多项式级的。     

Goertzel算法的一种改进计算结构

针对Goertzel算法的计算结构硬件实现效率低等问题,提出了利用两个FIR滤波器实现Goerztel算法,并且将改进后的计算结构由原来的AR（2）过程推广到一般的AR（p）过程.改进后的计算结构避免了递推运算,能够预确定数据的动态范围进行定标,充分利用了DSP等信号处理器的硬件结构,适合定点处理器的编程.通过在定点DSP处理器TMS320C5510上进行软件仿真,测试结果表明改进计算结构后算法的效率是改进前算法效率的3.7倍.