两台同型机多阶段维护调度问题的若干结果

研究了2种类型的机器维护:一种为周期性维护,另一种为决策维护.对于周期维护最小化时间表长问题,证明了经典的FFD算法是一个很好的启发式算法,并且得到了该算法的一个上界.对于决策维护最小化总完工时间问题,分析了SPT算法的界.特别地,对于单机并且机器仅需要2次维护的情况,给出SPT算法的界不超过11/9.     

具有负载依赖型维护时长和弹性维护开始时刻的单机调度问题

考虑维护时长为负载依赖型且维护开始时刻具有一定弹性的单机调度问题,其中机器在加工过程中需要进行一次维护,维护的开始时刻是决策量且需位于一个事先给定的时间段内,维护时长依赖于机器维护前已加工工件的加工时长之和,目标是确定维护的开始时刻并安排所有工件的加工使得制造期最小化。对维护时长函数的导函数大于或等于1的情形,给出了一个最优调度方案。对维护时长函数的导函数小于1的情形,证明了任何非延迟调度算法的最坏情况界都不超过2,并证明了经典的LS算法、LPT算法和SPT算法及它们的一些变形算法的最坏情况界均为2。     

集合覆盖问题降阶算法

集合覆盖问题是运筹学与计算机科学中的一个NP难题.首先将该问题转化为一个等价的二分图,给出该问题的上下界算法;接着给出该问题的数学性质,这些数学性质能降低问题的规模,加快算法的求解速度;然后将数学性质和上下界方法结合起来形成一个降阶算法,并给出了算法的时间复杂度分析.该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.最后通过多个示例进一步说明算法的原理及应用情况.     

工件带准备时间的平行机调度问题的一个近似算法

提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.     

二阶锥规划基于核函数凸组合的内点算法

首先给出了一个新的核函数,该函数为两个核函数的凸组合,进而将该核函数应用于求解二阶锥规划原始对偶内点算法中.分析了算法的复杂性并得到了一个关于大步校正方法的迭代界.最后给出了数值试验结果,讨论了参数对算法的影响.     

Flow shop排序问题F2|prmu|∑ωjCj的一个启发式算法

给出Flowshop排序问题F2|prmu|∑ωjCj的一个启发式算法,其最坏情况的界为2,且是紧界.此外,还讨论了它的三种多项式可解的条件.     

大规模带状线性方程组的追赶法

利用五对角线性方程组的追赶法思想矩阵LU分解的方法,推导出任意带宽的大规模带状线性方程组的追赶法.理论推导表明:对于带宽为2t+1的n阶带状线性方程组,该算法的运算量级为O([2t2+5t+3]n),存储量级为O[2(t+1)n].数值实验表明:该算法比其他一些算法有明显的速度和内存优势.这极大地提高了解线性方程的速度.     

时滞线性系统一致渐近稳定的时滞界

主要目的是确定线性时滞系统x(t)=Ax(t)+Bx(t-τ)稳定的时滞界,以改进现有有关该系统研究结果的保守性和降低稳定验算的计算复杂度.详细介绍了确定时滞界的数值算法,给出了释例并与现有有关结果进行了比较.     

面向多租户的业务模型版本管理

针对可重用业务模型库的SaaS应用对业务模型版本管理的问题,提出了一个面向多租户的模型版本维护方案.首先提出了面向多租户的业务模型管理架构;接着在模型版本维护方面,给出了一个模型版本维护算法;然后基于该算法,提出了模型文件存储的方式、模型版本控制逻辑以及模型数据存储的方案;最后以一个交通物流行业的信息平台为例验证了该版本维护机制的可行性和正确性.实验证明该方案可以满足多租户模型版本管理的要求.     

0-1多项式背包问题的一种精确算法

提出了0-1多项式背包问题的一种新的精确算法. 该算法是一个基于拉格朗日松弛和对偶搜索的分枝定界方法. 用外逼近法求拉格朗日对偶问题得到上界,其中拉格朗日松弛问题通过转化为一个网络最大流问题来求解. 为了提高算法的效率,利用两种启发式方法求初始可行解,并用填充和交换的方法改进后得到初始下界; 并且在分枝定界前, 利用所得到的拉格朗日界, 先固定最优解中某些变量的值. 数值结果表明该算法是有效的.     

同速度的具有m台通用机的n组工件的排序问题

 改进了经典的LPT(Longest Processing Time)算法，利用“首先空闲”准则安排机器，而对于工件的安排则按照“长时间任务优先”的原则，讨论了将n组工件安排在n台速度相同的专用机，m台同速度的通用机上的优化排序问题，得到了利用该近似算法所得的解T与最优解T*的一个估计：T/T*≤(2m+1)/(m+1)。     

序列相关Setup单机调度的最小化最大拖期分枝定界算法

研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性.     

基于阈值深度优先策略求解非对称旅行商问题的混合分枝定界算法

针对非对称旅行商问题(ATSP)模型计算难问题,提出了一种基于深度和广度方向混合搜索的启发式策略的分枝定界算法.该算法采取有阈值的深度优先加广度加权随机搜索的策略确定分枝节点,通过求解附加弧段约束的分配问题确定下界,通过消除子环的修补算法确定上界,从而有效综合了确定性方法的准确性和启发式方法的快速性.将此算法应用于求解经典TSPLIB库中的全部ATSP问题和热轧调度的仿真研究,表现出了较高的效率和可行性.     

具有通用机的三组工件的排序问题

该文讨论了具有三台速度相同的专用机,一台同速度的通用机的三组工件的Cmax问题,提出了改进的LPT算法,得到了近似算法的一个估计．     

A Branch and Bound-Based Algorithm for the Weak Linear Bilevel Programming Problems

Most real-world optimization problems are hierarchical involving non-cooperative objectives. Many of these problems can be formulated in terms of the first (upper level) objective function being minimized over the solution set mapping of the second (lower level) optimization problem. Often the upper level decision maker is risk-averse. The resulting class of problem is named weak bilevel programming problem. This paper presents a new algorithm which embeds a penalty function method into a branch and bound algorithm to deal with a weak linear bilevel programming problem. An example illustrates the feasibility of the proposed algorithm.     

带有延迟时间下界的k-(n1,1,…,1)-排序问题的拟多项式时间算法

研究Wikum提到的关于带有延迟时间下界的k-(n1,1,…,1)-链形结构排序问题的拟多项式时间算法,其中n1=2的情况己得到解决,这里主要以n1=3的情形为例作更加细致的分析,然后给出此原来的算法更加有效的拟多项式时间算法．     

下限极限分析的子迭代路径跟踪内点算法

采用路径跟踪内点法求解有限元下限极限分析所对应的非线性规划问题。在非线性方程组的Newton算法中引入子迭代过程,能够直接采用位移型有限元的数据存储格式和求解工具,并且大量计算可以在单元一级完成。改进的算法可直接利用现有的位移型有限元程序,实现过程简单。算例表明,该算法的效率和精度均可以得到保证。     

一类非凸规划的分支定界算法

针对一类非凸规划问题(NP)提出有效的分支定界算法.首先,利用目标函数的特性将其转化为等价的极小化问题(P),通过对其可行域的细分和求解一系列凸规划问题,不断更新(NP)全局最优值的上下界.为提高计算效率,一个问题的最优解作为下一个问题的初始解,并提出了新的删除技术.理论上证明该算法是收敛的,数值试验结果表明算法是有效可行的.     

管网改造布局和参数的交互式整体优化方法

本文建立了供水管网改造布局和参数优化设计问题的数学模型.利用交互式的思想和分枝-定界法的基本原理,提出了一种求解该问题的交互式整体优化方法.仿真结果表明该方法对解决我国管网改造的设计问题是有效的.     

针对带约束匹配搜索的扩展Kuhn-Munkres算法

提出了扩展的Kuhn-Munkres算法,可解决带下界约束的局部匹配存在性问题,即在匹配全集的给定子集中,搜索得到一个二分图匹配满足其边权和大于给定阈值．扩展Kuhn-Munkres算法构造了一棵以Kuhn-Munkres算法中间过程为节点的搜索树,利用搜索优先级和剪枝,将算法时间复杂度降低至二分图匹配全集与给定子集差集规模的多项式函数．