一类分布最优问题的指数时间收敛算法

具有全局等式约束分布优化问题在资源分配、投资组合、智能电网等领域有广泛应用.针对这类协作式的分布优化问题,设计了一个指数时间收敛的分布式算法,利用凸分析、代数图论和Lyapunov稳定性理论,证明了该算法的指数时间收敛性.最后,通过一个电力调度问题,验证了提出的算法在求解具有全局等式约束分布优化问题时的有效性.     

求解TSP问题的动态邻域粒子群优化算法

旅行商(TSP)问题是一个典型的NP问题.为了克服基本粒子群优化(PSO)算法在求解离散问题所具有的计算时间长和容易陷入停滞状态等问题,本文基于“簇”思想,对粒子间距离进行重新定义并给出了相应的动态邻域PSO算法.实验结果表明了新型算法在求解TSP问题中的有效性,同时提高了算法的性能,并具有更快的收敛速度.     

具有学习效应的两台机器流水作业排序问题

讨论了具有学习效应的2台机器流水作业排序问题,目标函数为极小化总完工时间.首先证明了2个相关引理,基于2个引理和对问题的分析,证明了用SPT算法解决问题的界为一个与工件的最小加工时间和最大加工时间相关的且小于2的一个值.     

结合优先指派规则的车间作业问题的枚举算法

车间作业调度问题是一个典型的NP完全问题,这种问题的精确求解算法的计算时间会随着问题实例规模的增大而呈指数增加.针对车间作业调度问题的难解性,给出了一个求解该问题的快速枚举算法.该算法是按照枚举算法的一般步骤来进行设计的,在设计过程中对于算法所涉及到的初始解问题、分枝问题以及剪枝策略等问题给出了旨在减少算法计算时间的解决方案.该算法找到了所测试的9个标准算例中4个算例的精确最优解.     

最小化时间表长的平行机调度近似算法研究

讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.     

带准备时间和强制工期的单机排序问题

讨论了带准备时间和强制工期的单机排序问题. 在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小. 由于工件不允许延迟,首先考虑了问题的可行性. 通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法. 对于可行问题,给出了一个算法在多项式时间内获得最优排序.     

非退化中心问题的构造性方法

在中心焦点判定问题中,时间可逆性是一个非常有用的概念.给出了时间可逆系统的一个性质,利用此性质 可以优化时间可逆条件推导的算法.对一类解析微分系统,给出了系统具有非退化中心的充要条件,利用此结论构 造了三次微分系统的一些非平凡中心条件.     

带有时间窗的电商物流终端配送研究

物流配送是支撑电子商务发展的关键环节和重要基础,而电商物流终端配送更是制约配送效率、影响服务质量的关键.以电商物流终端配送为对象,研究时间约束下的带有时间窗的多快递员任务分配和线路优化.将其抽象为一个具有时间窗的团体定向问题,并设计一个四步骤启发式算法进行求解.为验证算法性能,通过构建算例对比该算法和标准遗传算法、粒子群算法的效果差异.方差分析结果表明,该四步骤启发式算法能够获得更好效果.     

一类时滞非线性抛物型方程时间周期解的有限差分方法

建立了一个用于求解一类时滞非线性抛物型方程时间周期解的有限差分方法,在空间和时间方向上该方法分别具有四阶和二阶精度.为了证明解的存在唯一性,建立了一个单调迭代算法,该算法也给出了一个求解算法.同时讨论了数值解的收敛性.     

加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

单台机器有使用限制的排序问题

研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.     

一种实用的启发式资源平衡优化算法的改进

资源平衡优化问题即资源有限项目调度问题,是一个NP难问题,现在商用项目管理软件系统中的资源平衡优化问题多采用基于优先规则的启发式算法.通过定义一个新的作业集合和一个巧妙的修改动态参数的方法,使算法在实现上极大地减少了调度时间,进一步增强了启发式算法的实用性.     

基于终端滑模控制的有限时间拥塞控制

针对TCP网络的有限时间拥塞控制问题,考虑到输入受限、网络参数不确定和非响应流干扰的情况,提出了一种基于自适应终端滑模控制的主动队列管理算法.为了使网络系统不确定的界不需要事先获得,给出一个自适应律对总不确定的界进行了估计.考虑到系统输入受限的情况,给出另一个自适应律以补偿输入受限对系统稳定性造成的影响.为了改善网络系统的收敛性能,基于终端滑模控制设计了一个有限时间拥塞控制器.仿真结果表明,所提出的算法不仅具有有限时间收敛的品质,而且具有良好的稳定性和鲁棒性.     

蚁群算法与免疫算法的混合算法

蚁群算法是近些年来启发式算法研究的一个热点,在求解复杂组合优化问题上具有强大的优势.作为一种全局搜索的方法,它具有正反馈性、并行性、分布性、自组织性等特点.但是,蚁群算法也存在一些不足之处:例如,算法需要较长的搜索时间、容易出现早熟、停滞现象.针对上述不足,在深入研究蚁群算法的同时,又对免疫算法进行了一定的研究和分析后,针对蚁群算法中的个体蚂蚁缺乏识别问题特征信息的能力,将免疫算法中疫苗的思想引入到蚁群算法中,提出了蚁群算法与免疫算法的混合算法.将问题的特征信息作为疫苗注射给蚂蚁,使蚂蚁具有"免疫"的能力,旨在借鉴其他仿生算法的长处,利用其优点弥补蚁群算法的不足,从而提高蚁群算法的求解性能.     

非线性抛物型方程时间周期解的有限差分方法(英)

建立了一个用于求解非线性抛物型方程时间周期解的有限差分方法，在空间和时间方向上该方法分别具有四阶和两阶精度. 为了证明解的存在唯一性，建立了一个单调迭代算法，该算法也给出了一个求解算法. 同时讨论了数值解的收敛性. 数值结果显示了该方法的优越性.     

线性圆锥互补问题的光滑化牛顿法

给出求解线性圆锥互补问题一种新的光滑化牛顿法. 首先, 基于一个圆锥互补函数的光滑化函数, 将线性圆锥互补问题转化成一个方程组,  然后用光滑化牛顿法求解该方程组; 其次, 在适当假设下, 证明该算法具有全局收敛性和局部二阶收敛性. 数值结果表明, 该算法求解线性圆锥互补问题所需的CPU时间和迭代次数均较少, 且相对稳定, 从而证明了算法的有效性.     

经济网格中基于剪枝策略的时间-费用优化任务调度

由于在经济网格环境下,存在着资源异构和分布的特征,网格任务调度变成了一个复杂的问题.为此,针对独立任务,在考虑用户的服务质量经济需求偏好的基础上,提出了一个优化用户时间和费用的任务调度方案选择算法.该算法首先将网格中兼顾时间和费用的任务调度方案形式化为一个n层m叉树,然后将调度方案的选择问题转化为树的遍历问题,最后利用剪枝方法避免无效路径的搜索,降低了时间复杂度,实现了任务的优化调度.结果表明该算法能按照用户的时限和费用需求偏好选择优化的调度方案,且在性能上优于传统的未剪枝算法.所以该算法是一种可行的任务调度算法.     

具有小周期震荡参数时间分数阶扩散方程的二阶双尺度有限元算法

针对具有小周期参数时间分数阶扩散方程,给出了一个二阶双尺度展开式.基于该二阶双尺度展开式构造出了求解具有小周期参数时间分数阶扩散方程的二阶双尺度有限元算法,通过数值例子表明了该算法是有效的.     

基于频率的Read Mapping种子选择算法

选择具有最低频率的最优种子是一个复杂的计算问题,往往需要很长时间.提出了一种read的基于频率的合并种子选择算法(FMSS),该算法能够高效地选择接近最优的种子集合,可用于改善现有映射工具的性能.实验对比了平均种子选择方法和当前最优的种子选择策略(OSS,optimal seed solver),结果显示FMSS算法能够用很少的时间代价给出接近OSS的最优种子集合,这表明FMSS算法可集成到现有映射工具中用于处理更大规模的read mapping问题.     

轧辊热处理过程中具有组批的并行机调度问题

研究了在轧辊热处理过程中加热炉体积相同的情况下,具有组批的并行机调度问题.以使最长完成时间最小化为目标建立了该问题的数学模型.提出了辊坯组批启发式算法和批次调度启发式算法,并将二者结合形成了一个两阶段启发式算法,对模型进行求解.通过对实验结果的比较与分析,验证了方法的有效性.针对不同规模的问题给出了相应的最优求解方法,提高了轧辊的生产效率,为决策者合理安排生产提供了有效的策略.