带有活动重叠的项目调度问题新算法:分支定界法

在复杂产品研发项目中,通常采用活动重叠的方式来缩短工期,带有活动重叠的资源受限项目调度问题的求解多以启发式算法为主,该方法虽然具有收敛速度快、计算规模大等优点,但无法得到最优解,而精确算法是求解上述问题最优解的有效方法。基于此,本文在深入分析活动重叠对项目调度影响的基础上,设计了分支定界法以获得最优解。首先,从理论上证明了算法的最优性,一是对仅考虑最小延迟替代集即可得到最优解进行了证明;二是对割集支配规则与左移支配规则在剪枝操作中的应用进行了证明。其次,在算法设计上采用数据结构——栈对搜索树上的节点信息进行存储,并针对活动重叠约束,定义了新的决策时刻点和新的搜索树节点的表示方法。最后,通过大量的算例实验分析验证了算法的可行性和有效性。综上,本文提出的算法具备成熟的理论意义与精准的计算结果,具有较高的研究价值。

基于扰动KKT条件的原始-对偶内点法和分支定界法的最优潮流研究

针对严格最优潮流模型的精确求解提出了一种新算法。新算法将基于扰动KKT(Karush鄄Kuhn鄄Tucker)条件的原始-对偶内点法和分支定界法巧妙结合,运用分支定界法的分支处理对离散变量进行整数逼近,同时采用基于扰动KKT条件的原始-对偶内点法求解系列松驰问题,然后通过剪支处理和逐层定界达到收敛,实现了精确求解严格最优潮流的目的。此外,新算法将原问题的可行域进行逐步细分实现了全局寻优性。通过对IEEE14-118节点测试系统的数值仿真和不同算法的比较分析,证明了该算法是行之有效的。

基于分支定界法的关键链项目计划重排

通过举例说明在关键链项目计划中插入输入缓冲后,可能出现资源冲突和紧前关系冲突。从局部和全局两个方面采用分支定界法对项目计划进行重排来解决冲突问题。通过举例说明基于分支定界法的计划重排算法是有效和可行的。通过模拟仿真,从三个不同层次分析项目活动任务的不确定性对项目完工率和项目惩罚成本的影响。结果显示,保留原始关键链的基于分支定界法的全局性关键链计划重排方法较之其他方法要好,不确定性更低,项目的完工率更高,项目的惩罚成本更低。

求解组合优化问题的一种方法—分枝定界法

较为详细地分析了分枝定界法的算法特征和过程,讨论了以该算法求解具体优化问题时所要采取的算法策略。笔者结合简单、具体的例子说明了上述过程,并且也说明了在实际应用该算法时,根据问题的局部信息和其它启发算法求解问题的必要性。

基于分支定界法的多资源约束下项目进度规划

基于分支定界法的思想提出了一种新的精确求解多资源约束下项目进度规划问题的最优化算法。首先依据网络图中活动的逻辑关系和资源约束进行分支构建搜索树,然后通过基于广探法思想提出的优选原则对搜索树中的分支节点进行分析比较,淘汰劣解进一步缩小搜索空间并提高求解效率,最终可获得最优解。最后通过实例进行分析表明算法在求解多资源约束条件下项目进度规划问题的有效性,同时对于资源平衡优化问题以及合理权衡项目竣工时间与资源配置两者之间关系都有一定的现实指导意义。

同时加工排序问题的分支定界法和启发式算法(英文)

同时加工机器或者称为批加工机器是可以同时加工多个工件的机器.本文研究使带权总完工时间为最小的同时加工排序问题1|B|∑wjCj.这个问题的计算复杂性还没有解决.我们给出这个问题的精确解法-分支定界法和几个启发式算法,并且用较多实例对启发式算法的性能进行了比较.

两层次非线性规划的整体解的分枝定界法

本文中我们研究了两层次数学规划问题.它是多层次决策系统的数学模型.在多层次决策系统中有多个决策者,他们的地位和目标都可能不一样.为了求解两层次数学规划问题,我们提出了一个分枝定界算法.这个算法的最大特点是对问题中的函数要求很低,只要求是Lipschitz函数而且得到的是整体解.文中还给出一个算例.

基于分枝定界法的车辆配载问题

建立了能实现配送中心车辆均衡与效率的车辆配载模型,提出了分枝定界法解决车辆配载问题的方法,从而达到帕累托效率配置的要求.算例验证了该方法的可行性和有效性.

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

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

Flow Shop排序问题Fm|prmu|∑w_jC_j的分枝定界法

本文讨论FlowShop排序问题Fm|prmu|∑ωjCj给出了求解该问题的一个分枝定界法．

基于分支定界法的客运站到发线运用优化研究

为高效使用铁路客运站到发线,提高车站工作效率,以满足车站到发线固定使用、均衡使用和旅客走行距离最短为优化目标,建立多目标0-1规划模型;通过功效系数法对多目标优化函数统一量纲,转化为单目标函数,利用分支定界法求解目标函数。依据成都站的实际数据,应用优化模型进行到发线运用分析计算,得到到发线运用优化方案。

一种基于分枝定界法的串行测试任务调度算法

目前的自动测试系统中,对于串行任务的测试一般是以整个任务为粒度,这就导致两个任务可能需要重复设置相同的状态或重复测试相同的内容,延长了测试时间,降低了测试效率。针对这个问题,建立了基于图论的串行测试任务时序模型,用"图"来描述串行任务的测试时间与测试顺序的关系,将实际工程问题转化为图论中的数学问题。在任务时序模型的基础上,提出了一个串行测试任务调度算法。对于多个需要串行测试的任务,利用该算法可以得到测试时间最短的串行任务序列。该算法是借助整数规划问题中分枝定界法的思想实现的,通过相关理论和具体实例对算法的正确性和复杂性进行了分析。在实际系统中对该算法进行了实验验证,结果表明给定任务的测试效率提高了40%以上。

内点-分支定界法在最优机组投入中的应用

机组投入是现代电力系统编制发电计划的重要优化任务,具有显著的经济效益。从数学上讲,机组投入问题是一个多约束的NP难组合优化问题,很难得到理论上的最优解。提出运用内点-分支定界法求解最优机组投入问题。该方法将机组投入的离散变量松弛为[0,1]区间上的连续变量,结合有功出力,进行优化。原始-对偶内点法收敛迅速、对初值不敏感,用来求解松弛问题,分支定界法用来处理离散变量。通过对2个算例的计算及与其它算法结果的比较,验证了该算法能得到更好的全局最优解。

基于分枝定界法的环肋圆柱壳优化研究

基于分枝定界方法,研究了环肋圆柱壳静水压力作用下,考虑强度和稳定性约束时重量最轻的混合变量优化设计问题,讨论了强度约束和稳定性约束以及材料、几何参数对优化结果的影响。该方法能够有效求解环肋圆柱壳的混合优化问题,计算量小,精度高;环肋圆柱壳经优化后,壳板的重量比例大约是70%,肋骨重量占30%,并且随壳体的长径比(L/R)变化不大。环肋圆柱壳的优化中,肋骨的应力约束是主要约束,肋骨应力已经非常接近许用应力标准,其他应力、局部和总体失稳压力还有一定的储备。

基于Q0-1规划模型用分枝定界法求解最大团问题

搜索图的最大团是经典的NP-难题。通过运用二次0-1规划模型(简称Q0-1规划模型)寻得最大团问题的解法,所用的分枝定界法建立在此模型之上。通过一个命题推导出图的最大团求解问题与一类特殊Q0-1规划的等价性,借助于求解一般Q0-1规划的分枝定界法推演出求最大团问题的分枝定界规则,从而将图论中的经典问题转化成代数问题加以解决,并给出实例说明该算法的有效性。

遗传算法与分枝定界法求解TSP研究

在解决旅行商问题时,有两种常用的方法,即遗传算法与分枝定界法。本文使用K均值聚类改进分枝定界法,求解给定的旅行商问题。通过运用这两种算法求解TSP进行比较,相比之下K均值聚类优化的分枝定界法在解决旅行商问题中表现得更好。

奔德斯分解法与分支定界法在物流网络设计中的对比研究

考虑一种需求确定、有容量、给定周期的物流网络设计问题,提出了一种新的物流网络设计模型。分别采用了分支定界法和奔德斯分解法求解该模型,并引入了LP松弛来改进两种算法。最后,选取了一组数据进行了计算实验。

基于深度优先搜索分支定界法的Graph-SLAM后端优化算法改进

针对未知环境中机器人定位的问题,提出了一种深度优先搜索分支定界法的优化改进算法。graph-slam是一种离线slam方法 ,通过采用该优化改进算法可以使graph-slam的后端优化所需耗时减少,使整个系统的效率提高,使其能基本达到一个实时的效果。实验结果表明,该优化改进算法能够使系统运行效率提高近50%,同时能保证系统的稳定性和精确度的要求。

整数规划的分支定界法及其MATLAB实现

讨论了整数规划问题中分支定界法的基本原理和求解过程以及算法思想,通过MATLAB中提供的优化函数,实现了快速解决整数规划的问题,同时改进了对于此类问题的计算量巨大和编制程序困难的问题,使用了堆栈而不是递归,节约了计算中的资源。编制的MATLAB线性整数规划的程序,可以编译成C/C++实现和COM组件。

分支定界法在最优化问题中的应用

分支定界法是一种应用范围很广的搜索算法，本文在最优化问题中充分体现了分支定界法的应用，投资问题上充分体现了分支定界法的优越性。