A hybrid algorithm based on tabu search and large neighbourhood search for car sequencing problem

The car sequencing problem(CSP)concerns a production sequence of different types of cars in the mixed-model assembly line.A hybrid algorithm is proposed to find an assembly sequence of CSP with minimum violations.Firstly,the hybrid algorithm is based on the tabu search and large neighborhood search(TLNS),servicing as the framework.Moreover,two components are incorporated into the hybrid algorithm.One is the parallel constructive heuristic(PCH)that is used to construct a set of initial solutions and find some high quality solutions,and the other is the small neighborhood search(SNS)which is designed to improve the new constructed solutions.The computational results show that the proposed hybrid algorithm(PCH+TLNS+SNS)obtains100best known values out of109public instances,among these89instances get their best known values with100%success rate.By comparing with the well-known related algorithms,computational results demonstrate the effectiveness,efficiency and robustness of the proposed algorithm.

SEQUENTIAL QUADRATIC PROGRAMMING METHODS FOR OPTIMAL CONTROL PROBLEMS WITH STATE CONSTRAINTS

A kind of direct methods is presented for the solution of optimal control problems with state constraints. These methods are sequential quadratic programming methods. At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and linear approximations to constraints is solved to get a search direction for a merit function. The merit function is formulated by augmenting the Lagrangian function with a penalty term. A line search is carried out along the search direction to determine a step length such that the merit function is decreased. The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadratic programming methods.

Gravity-based heuristic for set covering problems and its application in fault diagnosis

A novel algorithm named randomized binary gravita- tional search （RBGS） algorithm is proposed for the set covering problem （SCP）. It differs from previous SCP approaches because it does not work directly on the SCP matrix. In the proposed algo- rithm, the solution of SCP is viewed as multi-dimension position of objects in the binary search space. All objects in the space attract each other by the gravity force, and this force causes a global movement of all objects towards the objects with heavier masses which correspond to good solutions. Computation results show that the proposed algorithm is very competitive. In addition, the proposed aigodthm is extended for SCP to solve the fault diagno- sis problem in graph-based systems.

一种带时间窗和容量约束的车辆路线问题及其TabuSearch算法

本文提出一种带时间窗和容量约束的车辆路线问题 (CVRPTW ) ,并利用TabuSearch快速启式算法 ,针对Solomon提出的几个标准问题 ,快捷地得到了优良的数值结果。

Emergency Local Searching Approach for Job Shop Scheduling

Existing methods of local search mostly focus on how to reach optimal solution.However,in some emergency situations,search time is the hard constraint for job shop scheduling problem while optimal solution is not necessary.In this situation,the existing method of local search is not fast enough.This paper presents an emergency local search(ELS) approach which can reach feasible and nearly optimal solution in limited search time.The ELS approach is desirable for the aforementioned emergency situations where search time is limited and a nearly optimal solution is sufficient,which consists of three phases.Firstly,in order to reach a feasible and nearly optimal solution,infeasible solutions are repaired and a repair technique named group repair is proposed.Secondly,in order to save time,the amount of local search moves need to be reduced and this is achieved by a quickly search method named critical path search(CPS).Finally,CPS sometimes stops at a solution far from the optimal one.In order to jump out the search dilemma of CPS,a jump technique based on critical part is used to improve CPS.Furthermore,the schedule system based on ELS has been developed and experiments based on this system completed on the computer of Intel Pentium(R) 2.93 GHz.The experimental result shows that the optimal solutions of small scale instances are reached in 2 s,and the nearly optimal solutions of large scale instances are reached in 4 s.The proposed ELS approach can stably reach nearly optimal solutions with manageable search time,and can be applied on some emergency situations.

Representation of measures of noncompactness and its applications related to an initial value problem in Banach spaces

This paper is devoted to studying the representation of measures of non-generalized compactness,in particular,measures of noncompactness,of non-weak compactness and of non-super weak compactness,defined on Banach spaces and its applications.With the aid of a three-time order-preserving embedding theorem,we show that for every Banach space X,there exist a Banach function space C(K)for some compact Hausdorff space K and an order-preserving affine mapping T from the super space B of all the nonempty bounded subsets of X endowed with the Hausdorff metric to the positive cone C(K)^(+) of C(K),such that for every convex measure,in particular,the regular measure,the homogeneous measure and the sublinear measure of non-generalized compactnessμon X,there is a convex function F on the cone V=T(B)which is Lipschitzian on each bounded set of V such that F(T(B))=μ(B),■B∈B.As its applications,we show a class of basic integral inequalities related to an initial value problem in Banach spaces,and prove a solvability result of the initial value problem,which is an extension of some classical results due to Bana′s and Goebel(1980),Goebel and Rzymowski(1970)and Rzymowski(1971).

NEW SYSTEMS OF GENERALIZED QUASI-VARIATIONAL INCLUSIONS IN FC-SPACES AND APPLICATIONS

In this paper, we study some new systems of generalized quasi-variational inclusion problems in FC-spaces without convexity structure.By applying an existence theorem of maximal elements of set-valued mappings due to the author, some new existence theorems of solutions for the systems of generalized quasi-variational inclusion problems are proved in noncompact FC-spaces. As applications, some existence results of solutions for the system of quasi-optimization problems and mathematical programs with the systems of generalized quasi-variational inclusion constraints are obtained in FC-spaces.

Heuristic tabu search scheduling algorithm for wet-etching systems in semiconductor wafer fabrications

To improve overall equipment efficiency(OEE) of a semiconductor wafer wet-etching system,a heuristic tabu search scheduling algorithm is proposed for the wet-etching process in the paper,with material handling robot capacity and wafer processing time constraints of the process modules considered.Firstly,scheduling problem domains of the wet-etching system(WES) are assumed and defined,and a non-linear programming model is built to maximize the throughput with no defective wafers.On the basis of the model,a scheduling algorithm based on tabu search is presented in this paper.An improved Nawaz,Enscore,and Ham(NEH) heuristic algorithm is used as the initial feasible solution of the proposed heuristic algorithm.Finally,performances of the proposed algorithm are analyzed and evaluated by simulation experiments.The results indicate that the proposed algorithm is valid and practical to generate satisfied scheduling solutions.

Systematic vs. Non-Systematic Search for 3D Aircraft Conflict Resolution

A conflict is an event in which two or more aircraft experience a loss of minimum separation. In this paper, we formulate the problem of solving conflicts arising among several aircraft moving in a shared airspace as a Constraint Satisfaction Problem (CSP). The constraint satisfaction problem being NP-complete, the algorithms developed to solve it have been of two types: non-systematic and systematic search methods. In this paper, we have considered a breakout algorithm as an example of non-systematic search methods and a backtracking procedure that maintains Arc Consistency (MAC) as an example of systematic search methods. The performance of these algorithms was compared experimentally and the Breakout algorithm is shown to be clearly superior.

基于电子商务竞标结构的分布式作战资源调度

针对现代战争作战任务规划问题,提出一种基于电子商务多轮竞标结构的作战资源调度方法,以异步、分散的方式让多个供应商协调来自多个消费者的任务资源请求。每个任务关联一个时间窗口,有些任务需要不同类的多个资源同步服务。招标由消费者发起,供应商对各资源请求发起投标,消费者根据投标结果中任务的3种状态,采取不同策略,并向供应商发送中标信息以执行任务或启动下一轮竞标。建立供应商和消费者调度问题数学模型,针对供应商资源调度非确定性多项式(nondeterministic polynomial,NP)完全问题特点,提出基于改进节约算法和自适应大邻域搜索算法的两阶段启发式求解方法;消费者模型使用混合整数线性规划来选择成本最低的投标组合,以满足任务需求。算例分析验证了所提方法的有效性。

两种高效局部搜索算法求解RB模型实例

RB(revised B)模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。

聚类蚁群混合算法求解CVRP

针对带容量约束的车辆路径问题,提出了一种聚类蚁群混合算法,将车辆路径问题拆分成数个旅行商问题进行求解。首先,改进了蚁群算法中信息素和路径的生成方式,使其能够对车辆路径问题进行有效的拆分求解;然后通过对种群进行分级,加快了蚁群算法的收敛速度,并设置3种邻域搜索算子来避免蚁群算法陷入局部最优;最后,设计了仿真实验对算法的部分参数进行合理设计,选取50个Solomon基准算例对算法进行实验验证。实验结果表明,算法收敛速度快,稳定性较高,求解结果较好。

顿悟与问题表征的转变

阐述了解决残缺棋盘问题的顿悟过程。该实验的结果证明，顿悟过程中需要发现一种正确的问题表征，即对等性问题空间，为了发现这一表征，被试必须使问题表征从“铺试问题空间”转变为“元水平的问题空间”．被试在这两个空间中进行搜索时，必须有很强的限制，使搜索成为有高度选择性的搜索，才能最终在元水平问题空间中发现正确的表征。本研究还发现，被试的搜索并不总是知觉驱动的，有时是概念驱动的，而且后者的迁移性更高。

一种具有混合编码的二进制差分演化算法

差分演化(DE)是Storn和Price于1997年提出的一种基于个体差异重组思想的演化算法,非常适用于求解连续域上的最优化问题.首先引入"差异算子"等概念,给出DE的一种简洁算法描述,并分析了它所具有的特性.然后,为了使DE能够求解离散域上的最优化问题,基于数学变换思想引入"辅助搜索空间"和"个体混合编码"等概念,通过定义一个特殊的满射变换,在辅助搜索空间的作用下将连续域上的高效差分演化搜索变换为离散域上的同步演化搜索,由此提出了第1个二进制差分演化算法:具有混合编码的二进制差分演化算法(HBDE).接着,给出了HBDE的依概率收敛和完全收敛的定义,并利用离散Markov随机理论证明了HBDE是完全收敛的.HBDE不仅完全具有DE的各种特性和所有优点,而且非常适用于求解离散域上的最优化问题,对随机生成的大规模3-SAT问题实例和典型0/1背包问题实例的数值计算表明:该算法具有很好的全局收敛性和稳定性,其性能远远超过二进制粒子群优化算法和遗传算法.

改进混沌优化及其在非线性约束优化问题中的应用

:研究一种比较新颖的优化方法——混沌优化 ,并在此基础上提出改进的混沌优化 .它利用混沌变量的特定内在随机性和遍历性跳出局部最优点 ,并在局部搜索空间经过线性搜索提高解的搜索速度和精度 ,通过结合精确不可微罚函数以用于求解非线性约束优化问题 .仿真结果表明 ,与已有的直接搜索方法相比 ,该算法简单 ,容易实现 ,求解精度、收敛速度和可靠性较高 ,满足约束的效果较好 。

基于分布式约束满足的产品配置研究

针对分布式网络化产品配置的特点,将产品配置问题抽象为约束满足问题进行研究.为解决配置知识共享及配置知识的语义表达问题,采用本体驱动的面向对象的思想构建产品配置约束网络结构模型,将该模型转化为分布式约束满足问题(Distributed Constraint Satisfaction Problem,DCSP)求解模型,从而可以准确、完全地描述产品零部件的结构及设计知识,并采用异步弱授权回溯算法进行约束求解,大大提高了求解的搜索效率和准确性.最后给出模型在水泵产品配置设计过程中的实际应用.

卫星任务调度问题的约束规划模型

卫星任务规划与调度是空间资源管理的重要内容之一,其目的在于为卫星系统的任务计划编制提供科学合理的决策手段与依据。卫星任务调度问题的重要特点在于,调度任务存在可见时间窗口约束。只有在可见时间窗口内,调度任务才可能执行并完成。在进行合理假设的基础上,建立卫星任务调度问题的约束规划模型。对基本禁忌搜索算法进行改进,提出了模型求解的变邻域禁忌搜索算法。应用结果表明,约束规划模型的建立与求解是合理的。

带连通性约束的蚁群优化算法主动解列断面求解策略

传统解列算法在实际系统断面搜索过程中面临两个难题:一是求解复杂度很高,属于NP难题;二是求解过程未考虑连通性,可能出现孤立发电机节点。因此,该文提出了一种带连通性约束的蚁群优化算法主动解列断面求解策略。该策略首先构建了主动解列的数学模型,然后将上述模型映射到具有单目标函数多约束条件的蚁群算法中,最后在充分保证连通性约束的基础上对该模型进行优化求解,获取具有最佳目标函数的解列断面。IEEE-118节点系统和某实际电网的仿真结果验证了文中所提方法的有效性与快速性。

求解TSP的空间锐化模拟退火算法

１引言模拟退火算法已被成功地用于求旅行商问题（ＴＳＰ）的最优路径［１］．但当ＴＳＰ实例搜索空间的“地形曲面”较粗糙时，有限时操作模拟退火过程可能因最终落入一个较差的局部“陷井”无法跳出，而难以得到高质量解．不同于通常改进算法自身的思路，本文提出了一种...

求解带动不平衡约束的卫星舱布局问题的启发式算法

以卫星舱中承载板上物件的三维布局为背景,研究一类带动不平衡约束的圆柱体形和长方体形待布物的混合布局问题.采用两阶段法进行求解,首先引入基面分配策略,将待布物分配到承载板上、下基面上;然后采用禁忌搜索算法对每一基面上的待布物进行布局优化:对传统禁忌搜索算法中的邻域格局提出启发式的产生策略,并对禁忌对象和格局接受原则进行有效改进,将改进的禁忌搜索算法与局部搜索的梯度下降法相结合,提出一种启发式的布局方法——基于梯度下降的禁忌搜索算法.最后通过算例验证了文中算法的高效性.