自由作业下的一类物流排序

研究了一个两阶段物流排序问题,即第一阶段工件在自由作业机器上加工,第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.目标是极小化工件带权送到时间与运输费用总和.将动态规划与组合优化方法结合,在假设工件加工时间与权满足"一致性"条件下,利用动态规划算法,构造了性能比不超过2 m的多项式时间近似算法;对于一般情形,用传统排序问题的算法构造了多项式时间近似算法,并分析算法性能比.     

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

本文讨论如何将一堆底部为正方形 ,长、宽、高均不超过 1的盒子装入一底为 1× 1,高为正无穷的柱形箱子 ,使装箱高度 Z为最小的问题 .该问题已知为 N P难的问题 . Li和 Cheng在 1990年提出了多项式近似算法 C1,其渐近性能比 r( C1) = 2. 687 5(见参考文献 [1 ]) . 本文根据算法 C1的思想 ,进一步利用盒 子底部为正方形的特点 ,尽可能不浪费高度空间 ,提出了所谓“单元装箱法” D,使新算法的渐近性能比得到改进: r (D ) ≤ 2*251/78 4= 2. 3 201 5.     

工序问题的动态规划算法

提出了一个求解工序问题的动态规划算法,该算法排序含n个工件集合的期望时间为O(n)。     

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

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

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

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

可中断半在线排序问题

讨论两台同型机上的可中断半在线排序问题,目标函数为极大化最小的机器完工时间Cmin.首先考虑已知所有工件的加工时间在p和rp(p＞0,r≥1)之间的情形,对任意的参数r,设计了最优半在线算法.接着,对已知最大工件加工时间的情形作了研究,得到了一个竞争比为5/4的最优半在线算法.     

约束最小生成树问题研究

本文对约束最小生成树问题提出一个算法,它的计算复杂性是O(n3)．然后把约束最小生成树作为约束Steiner最小树的一个近似解,则近似解的性能比为3?/2．     

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

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

可能产生中断且考虑运输的两台平行机排序问题

讨论两台平行机排序问题,有一台机器在某一个特定时刻可能产生中断,中断持续时间长短满足相应的概率,且工件转移到另一台机器上加工需要考虑运输时间．证明该问题是NP-困难的,设计一个复杂性为O（n^3（TP）^1）的动态规划算法,调整机器原有的工件排序,使得目标函数为带权重的总完工时间期望值最小．其中,n是工件的个数,TP是所有工件的加工时间之和,     

两台同型平行机的复合半在线排序问题

研究了两台同型平行机的一个复合半在线排序问题.即对已知工件加工时间递减和实例最优值,目标为极大化机器最早完工时间的复合半在线排序模型,分析了它的下界,并给出了竞争比为9/8的最优算法.     

分支定界法及其自组织异步并行实现

在讨论分支定界法的并行计算的基础上，就分支定界法求解分段线性规划问题提出了一种具有自组织功能的并行计算过程，并给出了能提高并行效率的异步并行计算的实施方案．     

求解二维对流扩散方程的交替分带并行算法

根据saul’yev型非对称差分格式和Crank-Nicolson差分格式对二维的对流一扩散方程构造了一类新的并行算法，即交替分带的Crank-Nicolson方法．该方法具有并行性质，可以在高性能的并行计算机上直接计算，稳定性好．数值实验表明，该方法有很好的精度．     

线性二次型最优控制的并行算法和软件

构造了线性二次型最优控制的并行算法，介绍了这个并行算法在武汉大学“ＷＵＤＰ９１”并行分布式处理系统上试算的数值应用软件的框图．本软件适用于既定动态系统的平衡问题．对于经济系统，可通过政策控制变量来调节和改善其状态和响应．对于自治系统可找出最优控制使得消耗函数达到最小值．通过对一系列例子进行试算，结果证实，所构造的并行算法和相应的数值软件是有效的，其加速比约为７．     

在GPU上求解大规模优化问题的反向策略的PSO算法

本文通过对传统粒子群算法(PSO)的分析,在GPU(Graphic Process Unit)上设计了基于一般反向学习策略的粒子群算法,并用于求解大规模优化问题.主要思想是通过一般反向学习策略转化当前解空间,提高算法找到最优解的几率,同时使用GPU大量线程并行来加速收敛速度.对比数值实验表明,对于求解大规模高维的优化问题,本文算法比其他智能算法具有更好的精度和更快的收敛速度.     

求解函数优化问题的两种异步并行算法

对子空间搜索法（一类多父体重组搜索策略）与群体爬山法相结合的一种随机搜索新算法即郭涛算法的特点进行了分析与实例验证，并在此基础上提出两种异步并行算法，以适应各种类型的并行与分布计算环境。以Bump函数的优化问题为例在超级并行计算机上作了并行数值试验，得到了迄今最好的结果。     

可重构处理器阵列的容错上界

基于一定约束条件下的多处理器阵列重构问题是一个热点问题,并已被证明具有NP难度.对于可重构处理器阵列容错上界（最大可用处理器阵列的大小）问题的求解,由于其理论上的难解性,多年来未取得突破性的进展.对此本文提出了一种新的求解算法并给予了理论上的论证.该算法通过分析阵列中的删除行与收获的逻辑列之间的关系,阐明了影响逻辑列总数的瓶颈条件.通过使用未损坏处理器（在逻辑上）替换损坏的处理器,突破限制逻辑列增长的瓶颈,逐步增加逻辑列数,最终计算出问题的新上界.仿真实验表明,与同类最新算法相比,在规模为128×128的处理器阵列上、处理器错误率在10%的情况下,原上界被降低了8.68%.最佳情况下的改进高达20%.     

分布式异构数据库中相关规则并行开采研究

首先简单介绍了相关规则及其并行开采算法的一些基本情况,然后指出了现有算法在分布式异构数据库中不能有效利用计算资源和造成信息丢失的问题．在证明了一个基本的定理之后,提出了基于ＨＤＤＭｉｎｅｒ模型的异步并行算法,并就其中的一些问题作了说明．最后,介绍了分布式异构数据库中数据开采的并行算法中一些仍需继续研究的问题．     

时空转换思想与算法并行化

通过对求解最优化问题计算的４种并行化方法的剖析，分析了数学思维过程中如何应用时空转换，把一个复杂问题的求解分解为在多个时空上的并行计算．加深了对设计并行算法的思维过程和多时空变换的理解，     

约束最小支撑树 ( C-MST)问题: 复杂性和上下界估计

本文首先建立了约束最小支撑树问题的模型 ,利用背包问题的复杂性 ,证明了该问题是 N P-完 全的 . 然后利用一个广义线性规划的对偶算法 ,对目标函数的上下界作出了估计 ,最后分析了解的平面 性质 .     

基于支持向量机泛化误差界的多核学习方法

基于支持向量机（SVM）泛化误差界,提出了一种精确且有效的多核学习方法.首先,应用SVM泛化误差界推导多核学习优化形式,并给出求解其目标函数微分的计算公式.然后,设计高效的迭代算法来求解该优化问题.最后,分析了算法的时间复杂度,并基于Rademacher复杂度给出了算法的泛化误差界,该泛化界在基核个数很大时依然有效.在标准数据集上的实验表明,相对于一致组合方法以及当前流行的单核和多核学习方法,所提出的方法具有较高的准确率.