A Branch-and-Bound Based Heuristic Algorithm for Minimizing Makespan in Machining-Assembly Flowshop Scheduling

This paper proposes a heuristic algorithm, called list-based squeezing branch and bound algorithm, for solving a machine-fixed, machining-assembly flowshop scheduling problem to minimize makespan. The machine-fixed, machining-assembly flowshop consists of some parallel two-machine flow lines at a machining stage and one robot at an assembly stage. Since an optimal schedule for this problem is not always a permutation schedule, the proposed algorithm first finds a promising permutation schedule, and then searches better non-permutation schedules near the promising permutation schedule in an enumerative manner by elaborating a branching procedure in a branch and bound algorithm. The results of numerical experiments show that the proposed algorithm can efficiently provide an optimal or a near-optimal schedule with high accuracy such as mean relative error being less than 0.2% and the maximum relative error being at most 3%.

Lower Bounds and a Nearly Fastest General Parallel Branch-and-Bound Algorithm

In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.

Relaxation-strategy-based Modification Branch-and-Bound Algorithm for Solving a Class of Transportation-production Problems

In this paper,a new algorithm relaxation-strategy-based modification branchand-bound algorithm is developed for a type of solving the minimum cost transportationproduction problem with concave production costs.The major improvement of the proposed new method is that modification algorithm reinforces the bounding operation using a Lagrangian relaxation,which is a concave minimization but obtains a tighter bound than the usual linear programming relaxation.Some computational results are included.Computation results indicate that the algorithm can solve fairly large scale problems.

Bounded space algorithms for variant of variable-sized bin packing

Given a list of items and a sequence of variable-sized bins arriving one by one, it is NP-hard to pack the items into the bin list with a goal to minimize the total size of bins from the earliest one to the last used. In this paper a set of approximation algorithms is presented for cases in which the ability to preview at most k（〉=2） arriving bins is given. With the essential assumption that all bin sizes are not less than the largest item size, analytical results show the asymptotic worst case ratios of all k-bounded space and offiine algorithms are 2. Based on experiments by applying algorithms to instances in which item sizes and bin sizes are drawn independently from the continuous uniform distribution respectively in the interval [0,u] and [u,l ], averagecase experimental results show that, with fixed k, algorithms with the Best Fit packing（closing） rule are statistically better than those with the First Fit packing（closing） rule.

On the “Onion Husk” Algorithm for Approximate Solution of the Traveling Salesman Problem

The paper describes some implementation aspects of an algorithm for approximate solution of the traveling salesman problem based on the construction of convex closed contours on the initial set of points (“cities”) and their subsequent combination into a closed path (the so-called contour algorithm or “onion husk” algorithm). A number of heuristics related to the different stages of the algorithm are considered, and various variants of the algorithm based on these heuristics are analyzed. Sets of randomly generated points of different sizes (from 4 to 90 and from 500 to 10,000) were used to test the algorithms. The numerical results obtained are compared with the results of two well-known combinatorial optimization algorithms, namely the algorithm based on the branch and bound method and the simulated annealing algorithm. .

Algorithms for Multicriteria Scheduling Problems to Minimize Maximum Late Work, Tardy, and Early

This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (Vmax), maximum tardy job, denoted by (Tmax), and maximum earliness (Emax). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (Vmax, Tmax, Emax) and 1//(Vmax + Tmax + Emax). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.

基于Branch & Bound方法MIQP问题的求解及应用

研究基于 Branch & Bound (B&B) 方法的混合整数二次规划(Mixed Integer Quadratic Programming, MIQP)问题的求解,以及在一类混杂系统优化控制中的应用。B & B算法求解MIQP问题的过程,可视为对于一个二叉树的搜索。影响B & B算法寻优效率的两个主要方面是:分支变量的选择规则,以及树搜索策略。通过设定控制变量QPmax, 用以限制寻优过程求解QP问题的最大数目,可以在较短的时间内获得MIQP问题的满足整数约束条件次优解。利用MATLAB编制MIQP问题的求解程序,并在混杂系统优化控制中的应用,做了仿真计算。

State Bounding在目标跟踪中的应用

本文把Ｂｏｕｎｄｉｎｇ估计引入目标跟踪领域，提出一种用状态估计集几何中心作为目标滤波值的递推算法。该算法使用椭圆集来描述状态的不确定性并给和系统和观测噪声的界，以最小值椭圆作为更新准则。仿真结果给出了本算法与Ｋａｌｍａｎ滤波算法的性能比较以及界内噪声分布不同时跟踪性能的差别。

基于信号飞行时间与误差分析的改进无线传感网络Bounding-box定位算法

为提高无线传感网络定位算法的实效性,针对Bounding-box定位算法定位精度不足的问题,提出了基于信号飞行时间与误差分析的改进Bounding-box定位算法。该算法根据累计距离误差,在正方形重叠区域重新划分离散小方格,然后按照累计距离误差最小化准则,选择对应离散小方格的中心点坐标作为待定位节点的定位位置。通过仿真实验表明,提出的改进Bounding-box定位算法,在距离测量精确和小误差情况下,能够明显提高定位精度。此外,真实环境实验表明,在采用信号飞行时间作为距离测量技术的条件下,提出算法的定位误差最小。

State Bounding跟踪机动目标研究

提出一种用 State Bounding估计跟踪机动目标的算法。用预测集、观测集中心距检测目标机动 ,修正系统噪声集尺寸适应目标机动 ,很好地解决了用 state Bounding估计跟踪机动目标问题。模拟结果表明本算法与相应的 kalman滤波器的性能相比 。

基于无线传感器离散网络模型的Bounding Box定位算法研究

Bounding Box算法是一种典型的基于离散网络模型的无线传感器网络节点定位算法。针对Bounding Box算法定位误差大、覆盖率低的缺点,提出一种采用虚拟锚节点策略的改进定位算法。首先未知节点利用其通信范围内的锚节点进行定位;其次,已定位的节点根据升级策略有选择性的升级为虚拟锚节点;最后,无法定位的节点利用虚拟锚节点实现定位。另外,在离散网络模型的基础上,通过建立双半径网络节点模型从而进一步约束了未知节点的位置。理论分析及仿真结果均表明,该算法在显著提高定位覆盖率的同时,有效地提高了定位精度。

一种基于虚拟锚节点策略改进的Bounding Box定位算法

针对Bounding Box算法定位误差大、覆盖率低的缺点,提出了一种采用虚拟锚节点策略的改进定位算法。首先未知节点利用其通信范围内的锚节点进行定位;其次,已定位的节点根据升级策略有选择性的升级为虚拟锚节点;最后,无法定位的节点利用虚拟锚节点实现定位。另外,在离散网络模型的基础上,通过建立双半径网络节点模型从而进一步约束了未知节点的位置。理论分析及仿真结果均表明,该算法在显著提高定位覆盖率的同时,有效地提高了定位精度。

Job－shop问题的Branch－bound方法

本文给出了Ｊｏｂ－ｓｈｏｐ问题的一种Ｂｒａｎｃｈ－ｂｏｕｎｄ方法。

极限分割估计矩形的Bounding-Box定位算法

针对无线传感器网络中Bounding-Box算法定位精度低的问题,在Bounding-Box算法的基础上提出一种极限分割估计矩形的方法来改进定位算法,分割后的估计矩形产生一个待选质心,当满足分割条件时,对估计矩形继续分割,并不断产生待选质心,当满足终止分割条件时,将上一次分割得到的待选质心坐标作为未知节点的最终位置,通过极限分割的方法可以修正未知节点的定位误差。仿真结果表明,在无需增加额外通信开销的情况下,改进的算法在一定程度上降低了算法的平均相对定位误差。

A novel algorithm of adaptive IIR lattice notch filter and performance analysis

A novel adaptive algorithm of IIR lattice notch filter realized by all-pass filter is presented. The time-averaged estimation of cross correlation of the present instantaneous input signal and the past output signal is used to update the step-size, leading to a considerably improved convergence rate in a low SNR situation and reduced steady-state bias and MSE. The theoretical expression for steady-state bounds on the step-size is derived, and the influence factors on the stable performance of the algorithm theoretically are analyzed. A normalized power factor is then introduced to control variation of step-size in its steady-state bounds. This technique prevents divergence due to the influence of large power input signal and improves robustness. Numerical experiments are performed to demonstrate superiority of the proposed method.

Upper-bound limit analysis based on the natural element method

The natural element method （NEM） is a newly- developed numerical method based on Voronoi diagram and Delaunay triangulation of scattered points, which adopts natural neighbour interpolation to construct trial functions in the framework of Galerkin method. Owing to its distinctive advantages, the NEM is used widely in many problems of computational mechanics. Utilizing the NEM, this paper deals with numerical limit analysis of structures made up of perfectly rigid-plastic material. According to kinematic the- orem of plastic limit analysis, a mathematical programming natural element formulation is established for determining the upper bound multiplier of plane problems, and a direct iteration algorithm is proposed accordingly to solve it. In this algorithm, the plastic incompressibility condition is handled by two different treatments, and the nonlinearity and nons- moothness of the goal function are overcome by distinguishing the rigid zones from the plastic zones at each iteration. The procedure implementation of iterative process is quite simple and effective because each iteration is equivalent to solving an associated elastic problem. The obtained limit load multiplier is proved to monotonically converge to the upper bound of true solution. Several benchmark examples are investigated to validate the significant performance of the NEM in the application field of limit analysis.

基于bounding-box与卡尔曼滤波的优化压缩感知算法的目标定位

针对无线传感器网络目标定位过程中存在的测量矩阵维数高、运算量大以及测量向量不准确的问题,文章提出一种优化压缩感知(compressive sensing,CS)定位算法。首先对传感器采集的接收信号强度值进行卡尔曼滤波保证压缩感知测量向量的准确性;然后引入bounding-box方法估计位置区域,缩小节点定位范围从而降低后一阶段压缩感知测量矩阵的维数;最后在节点估计区域进行压缩感知定位,并提出基于原子相关度阈值的回溯匹配追踪算法,通过原子相关度阈值控制对候选集原子进行二次筛选剔除低相关度原子,在支撑集中保留系数较大的原子,提升重建精度。实验结果表明,在信噪比为5 dB,目标数为8时,相较于传统的OMP算法、GMP算法、CoSaMP算法,所提优化定位算法的定位精度分别提升61.21%、51.53%和45.12%。

Analysis of Five Typical Localization Algorithms for Wireless Sensor Networks

In this paper, the self-localization problem is studied. It is one of the key technologies in wireless sensor networks (WSNs). And five localization algorithms: Centroid algorithm, Amorphous algorithm, DV-hop algorithm, APIT algorithm and Bounding Box algorithm are discussed. Simulation of those five localization algorithms is done by MATLAB. The simulation results show that the positioning error of Amorphous algorithm is the minimum. Considering economy and localization accuracy, the Amorphous algorithm can achieve the best localization performance under certain conditions.

Upper bound solution for active thrust of nonhomogeneous cohesive soil considering effects of intermediate principal stress

Considering the variation of cohesion along the depth,the upper bound solution of active earth pressure for a rough inclined wall with sloped backfill is formulated based on a log-spiral failure mechanism.For a more accurate prediction,the influence of intermediate principal stress is taken into consideration using the unified strength theory.Converting the search for the active pressure to an optimization problem,the most critical failure surface can be located by a natural selection-based gravitational search algorithm(GSA).The proposed method is validated compared with existing methods for noncohesive and cohesive cases and proved to be more accordance with the limit equilibrium solution.The influences of the variation of soil cohesion and intermediate principal stress on active earth pressure coefficient are then fully studied.It can be concluded that both the variations of soil cohesion and intermediate principal stress have a significant influence on the active earth pressure coefficient.

Algorithmic Optimization of BDDs and Performance Evaluation for Multi-level Logic Circuits with Area and Power Trade-offs

Binary Decision Diagrams (BDDs) can be graphically manipulated to reduce the number of nodes and hence the area. In this context, ordering of BDDs play a major role. Most of the algorithms for input variable ordering of OBDD focus primarily on area minimization. However, suitable input variable ordering helps in minimizing the power consumption also. In this particular work, we have proposed two algorithms namely, a genetic algorithm based technique and a branch and bound algorithm to find an optimal input variable order. Of course, the node reordering is taken care of by the standard BDD package buddy-2.4. Moreover, we have evaluated the performances of the proposed algorithms by running an exhaustive search program. Experi-mental results show a substantial saving in area and power. We have also compared our techniques with other state-of-art techniques of variable ordering for OBDDs and found to give superior results.