基于遗传分枝定界算法的Flow-shop调度问题

Flow shop调度问题属于NP难题,传统的方法很难求出精确最优解,提出了一种遗传分枝定界算法,即在遗传算法中引入分枝定界算法保持对优化解有贡献的工件部分顺序,求解3机Flow shop调度问题,该算法与常用的遗传局部算法和遗传动态规划算法类似,用随机方法测试例子,与目前著名的Taillard的禁忌搜索算法和Reeves的遗传算法两种改进算法进行比较,大量的数据实验证实了遗传分枝定界算法的有效性。     

单机序列相关Setup最小化最大拖期算法

研究了一个具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期。提出了一个求解该问题的分枝定界枚举算法,其中包括确定问题上界和下界的方法,以及两条优势规则。计算实验证明了本文提出算法的有效性。     

基于遗传分枝定界算法的F1ow—shop调度问题

F1ow—shop调度问题属于NP难题，传统的方法很难求出精确最优解，提出了一种遗传分枝定界算法，即在遗传算法中引入分枝定界算法保持对优化解有贡献的工件部分顺序，求解3机F1ow—shop调度问题，该算法与常用的遗传局部算法和遗传动态规划算法类似，用随机方法测试例子，与目前著名的Taillard的禁忌搜索算法和Reeves的遗传算法两种改进算法进行比较，大量的数据实验证实了遗传分枝定界算法的有效性。     

非凸二次规划全局极小问题的新型分枝定界算法

针对求解多面集上二次函数的全局近似最优解问题,利用逐步缩小对偶间隙的处理办法,提出了一个新型分枝定界算法。新算法的主要改进之处是利用了Lagrange 对偶性获取下界。最后,用构造和随机产生的问题实例,对提出的新算法和传统的分枝定界算法做了初步的数值比较实验。计算实验表明算法对求解中大规模非凸二次规划问题的有效性。     

业务流程管理中的大规模整数规划问题求解

对从企业业务流程管理中抽象出来的大规模整数规划问题的计算机求解方法进行讨论。提出一种内存优化管理方法,能更高效地存储海量数据。同时对求解整数规划问题的经典算法——分枝定界算法进行研究,利用人工智能的搜索思想,给出分枝定界法的改进算法,使其能快速求解大规模整数规划问题。     

分枝定界算法设计模式研究与应用

分枝定界算法是传统算法设计方法中重要算法之一,很多重要问题可以用它来解决。本文在对分枝定界算法进行深入研究的基础上,将其抽象成分枝定界算法设计模式,并使用C＋＋的模板机制加以实现。最后通过具体实例说明本文开发的分枝定界算法模板具有较高的可重用性、可编程性和可靠性。     

求解具0－1变量的两级决策问题的分枝－定界优化方法

在一类具０－１变量的两级决策问题基础上，研究了求解该问题的分枝－定界优化方法，分析了算法中定界的设计和分枝准则的选择。文中示例的仿真结果表明，该算法是有效的。     

求解具0—1变量的两级决策问题的分枝—定界优化方法

在一类具０－１变量的两级决策问题基础上，研究了求解该问题的分枝－定界优化方法，分析了算法中定界的设计和分枝准则的选择。文中示例的仿真结果表明，该算法是有效的。     

3机Flow-shop调度问题研究

提出了一种遗传分枝定界算法求解3机Flow-s hop调度问题，该算法类似于常用的遗传局部算法和遗传动态规划算法．用随机方法生成测 试例子，通过与著名的Taillard的禁忌搜索算法和Reeves的遗传算法进行比较，实验结果证 实了遗传分枝定界算法的有效性．     

P2P分层流媒体中源服务器参与的数据层分配算法

P2P流媒体是一种性价比良好的流媒体服务体系．由于Peer节点的服务能力有限,在大规模的系统应用中,源服务器的带宽等资源仍可能成为系统的瓶颈．基于P2P分层流媒体,研究如何在Peer节点之间对数据层进行优化分配,以减少对源服务器带宽的占用,该优化问题属NP难问题．提出了两种算法：一种是基于多目标优化的近似算法,分析了该算法的近似比;另一种是基于分枝定界的精确算法,它利用计算二分图中的最大流值来确定分枝上界及被裁剪的分枝．仿真实验表明两种算法都有较大的性能改进,且精确算法中的分枝定界策略有较高的效率．     

具有优先关系的累积调度问题的约束传播算法

约束传播是约束规划成功应用的关键技术之一. 针对累积调度问题提出一种结合工作间优先关系和工作最早开始/最晚完成时间约束的约束传播算法, 给出了算法的理论依据. 引用资源受限项目调度问题库PSPLIB中的典型问题对算法进行了测试, 结果表明: 针对测试问题新的约束传播算法在总体约减效果上优于现有约束传播算法, 新算法与基于能量推理的约束传播算法可以互补, 两者结合推理效果更好.     

Experimental investigations of combined algorithms of branch and bound method and dynamic programming method for knapsack problems

An algorithm combined of the branch and bound algorithm and the algorithm of dynamic programming for the knapsack problem with one constraint is proposed. An extensive computational experiment for the problems with dimension up to 3000 was conducted; on the basis of this experiment, the proposed algorithm is compared with the branch and bound algorithm and the algorithm of dynamic programming. The possible number of processors required by the combined algorithm is considered.     

Exact resolution of the one-machine sequencing problem with no machine idle time

This paper investigates the one-machine sequencing problem in a workshop where the machine has to satisfy the no-idle constraint, that is, the machine must process jobs without interruption. The objective is to minimize the makespan. Each job has a release date for which it is available for processing on the machine and a delivery time during which it must remain in the system after being processed by the machine. This problem has been studied without adding the no-idle constraint. It is solved in polynomial time, when the preemption of jobs is allowed, applying Jackson’s rule. But, when the preemption of jobs is not allowed, it becomes strongly NP-hard. Although, it can be solved in a very short time using Carlier’s branch and bound algorithm. Below, we propose to adapt Carlier’s branch and bound method in order to calculate an optimal nonpreemptive schedule for the problem when adding the no-idle constraint.     

加权约束满足问题的符号ADD求解算法

加权约束满足问题(WCSP)是一类软约束满足问题。给出WCSP的代数决策图(ADD)描述,以及基于ADD的两种符号求解算法。首先,通过对变量和变量域值的二进制编码,给出软约束图的ADD表示。其次,将分支定界搜索算法与桶消元算法及符号ADD技术相结合,在静态变量序下,利用结点一致性预处理技术,对WCSP问题进行符号ADD求解。通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界,对符号ADD求解算法作了改进。最后,对大量随机生成的测试用例进行实验分析。结果表明,文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法。     

The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time

This work studies the scheduling problem where a set of jobs are available for processing in a no-wait and separate setup two-machine flow shop system with a single server. The no-wait constraint requires that the operations of a job have to be processed continuously without waiting between two machines. The setup time is incurred and attended by a single sever which can perform one setup at a time. The performance measure considered is the total completion time. The problem is strongly NP-hard. Optimal solutions for several restricted cases and some properties for general case are proposed. Both the heuristic and the branch and bound algorithms are established to tackle the problem. Computational experiments indicate that the heuristic and the branch and bound algorithm are superior to the existing ones in term of solution quality and number of branching nodes, respectively.     

Bi-level programming modeling and hierarchical hybrid algorithm for antimissile dynamic firepower allocation problem with uncertain environment

Aiming at the shortcomings of antimissile dynamic firepower allocation (ADFA) researches under uncertain environment, the fuzzy chance-constrained bi-level programming model with complex constraints is proposed by introducing the uncertain programming theory. Firstly, maximization cost-effectiveness ratio and earliest interception time as the upper and the lower objective functions of the model, respectively, are used. In order to close to the battlefield environment, the model constraint includes interception time window, effective damage lower bound and intercept strategy, etc. Secondly, a particle coding scheme and repairing scheme are given with hierarchical structure for multi-constrained bi-level ADFA problem. Furthermore, the improved variable neighborhood PSO algorithm with convergence criterions and the PSO algorithm with doubt and repulsion factor (PSO-DR) are effectively combined. On these bases, the hierarchical hybrid fuzzy particle swarm optimization algorithm is presented with fuzzy simulation technique. Finally, the results of comparison show the proposed algorithm has stronger global searching ability and faster convergence speed, which can effectively solve large-scale ADFA problem and adapt to the requirements of real-time decision.     

基于改进遗传算法的可靠性网络优化设计

在可靠性条件约束下,使网络成本最低是网络规划NP-hard问题。从遗传算法的基本原理出发并对其进行改进,分析带有可靠性约束条件的通信网设计中的网络优化问题,这一方法的最大优点是可将其推广到求解一般带有约束的网络优化问题。而且结果表明无论是解的精度还是运算速度遗传算法都优于分枝定界法及其它启发式算法。     

飞机牵引车语音识别的动态时间规整优化算法

为研究飞机牵引车智能语音控制,实现机场环境下牵引车对飞行员语音命令的精确、高效识别,同时针对传统动态时间规整（DTW）算法计算量大、时间复杂度高、算法识别效率低的问题,提出了一种车辆语音识别的六边形弯曲窗口约束DTW优化算法。首先,从DTW算法原理、牵引车指令的语音特性和机场环境三方面,分析了弯曲窗口对DTW算法识别精度、效率的影响;然后,在Itakura Parallelogram菱形弯曲窗口约束DTW优化算法的基础上,进一步提出了六边形弯曲窗口约束的DTW全局优化算法;最后,通过改变优化系数,实现了最优六边形弯曲窗口约束的DTW算法方案。基于孤立词识别的实验结果表明,所提最优算法与传统DTW算法、菱形弯曲窗口约束的DTW算法相比,识别错误率分别降低77.14%和69.27%,识别效率分别提高48.92%和27.90%。该最优算法更具鲁棒性、时效性,可以作为飞机牵引车智能控制的理想指令输入端口。     

A hybrid algorithm for finding minimal unsatisfiable subsets in over‐constrained CSPs

Minimal Unsatisfiable Subsets (MUSes) are the subsets of constraints of an overconstrained constraint satisfaction problem (CSP) that cannot be satisfied simultaneously and therefore are responsible for the conflict in the CSP. In this paper, we present a hybrid algorithm for finding MUSes in overconstrained CSPs. The hybrid algorithm combines the direct and the indirect approaches to finding MUSes in overconstrained CSPs. Experimentation with random CSPs reveals that the hybrid approach is not only quite efficient but when operating under a time bound it finds a more representative set of MUSes. © 2011 Wiley Periodicals, Inc.     

约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。