解复杂二次整数规划问题的新型分枝定界算法

针对二次整数规划问题的特征，本文对传统分枝定界算法做了一系列的改进，其包括用HNF算法寻求初始整数可行解、对变量进行某种先验排序以确定分枝变量的选取次序、及针对变量的特性来选取分枝方向等，给出了可用于求解中大规模复杂二次整数规划问题的改进型分枝定界算法。数值试验结果表明所给算法大大改进了传统的分枝定界算法，并有广泛的适用性。     

具有任务资源需求分布与资源时变约束的RCPSP分枝定界算法

研究资源受限项目调度问题，考虑了项目中每个任务对可更新（再生）资源需求的任意分布、可更新（再生）资源的最大供给量随时间而变化的情形。作为对前人研究结果的进一步推广，利用了分枝定界技术，以及事件驱动的时间增量方式，成功地解决了这种一般项目的调度问题     

带有二次约束二次规划问题的分枝定界方法

提出了一种解带有二次约束二次规划问题的新的分枝定界算法对该算法进行了收敛性分析。这种方法是用新的线性规划松弛定界技术确定最优值的下界，并且把分枝定界技术和外逼近方法有机地结合起来。     

适用于编码MIMO系统的软输出估计算法

提出了适用于检测与译码相级联的编码MIMO系统次最优接收机的软输出估计算法。它利用基于均值软输出估计算法的似然比输出，为译码器组提供软输入信息，使接收机运算量与发射天线的数目呈线性关系。瑞利平衰落环境的仿真结果表明，本文提出的算法与VVA相比，性能虽有一定的损失，但运算量大幅度减少；与采用最大似然检测(MIMO)的次最优接收机相比，其在运算量减少的同时还获得了一定的软输入增益。     

基于广义高斯噪声模型的低频线谱检测

研究浅海环境噪声中低频线谱的检测问题.首先对实测海洋环境噪声的统计特性进行分析,提出了应用广义高斯分布对海洋环境噪声建模方法.在此基础上,针对低频线谱检测问题,推导了广义高斯噪声场中的最大似然检测器和渐近检测器,给出了弱线谱条件下线谱频率的最大似然估计.最后,利用实测数据对三种检测器的线谱检测性能进行了验证,结果表明:...     

非理想信道估计条件下OFDM系统的最大似然检测算法

基于最大似然的准则,研究了理想信道估计条件下和非理想信道估条件下OFDM系统的最优检测算法。研究结果表明,当发送信号为PSK调制方式时,无论是理想信道估计还是非理想信道估计,最大似然检测算法与传统的迫零检测算法等价。但当信道估计非理想且发送信号的调制方式为16QAM或高阶QAM时,采用最大似然检测算法才能够获得更好的性能。     

基于AMLE的高光谱本征维数估计方法研究

最大似然估计法（MLE）能快速计算高光谱影像数据的本征维数,原理简单,但它不是一种很好的本征维数估计法。因为它存在忽略单个数据点贡献的缺点,导致冗余信息放大、重要信息被湮没,不利于特征提取和分类。对此．本文引入自适应性最大似然估计法（AMLE）。该方法通过引入权函数,突出每个数据点的贡献,能提取出被最大似然估计法湮没的重要特征。在对高光谱影像进行特征提取及分类的试验中验证了该方法的有效性。     

一种似然曲线的图像拼接的改进算法

本文在大量调研国内外的相关算法的基础上,介绍了图像拼接的算法分类,并提出了一种基于灰度似然曲线的寻找匹配点的改进算法.其算法原理为首先进行匹配点的粗匹配,再进行改进后的似然曲线快速拼接,其不但保持了原始算法的精度,而且大大的加快了速度.通过仿真实验,在精度不变的情况下,对应于不同图像,速度较原始方法提高了约60%.     

一种基于线性预测和极大似然估计的基音检测算法

用线性预测的方法求出语音信号的LPC(Linear Predictive Coding)谱,然后根据候选的声门激励与LPC谱卷积重构语音信号的短时频谱,当重构频谱与原始语音频谱之间的畸变最小时,声门激励之间的间隔为基音周期.为了提高计算效率,采用频域动态搜索的方法搜索基音周期的候选值.数值实验表明,采用线性预测和极大似燃估计 (Maximum Likelihood, ML)的基音检测算法可保留更多的基音信息,并能有效地减少基音检测的错误,并且该算法比传统的ML法有更强的鲁棒性.     

用于MIMO空分复用系统上行链路接收机的球形检测算法

本文涉及的MIMO空分复用系统上行链路的子信号流在空间维和时间维上未进行编码,直接将高速数据流分解为若干低速数据流,进行分层调制后用多个天线发送,实现MIMO空分复用发射,可使移动台的发射机设计简化。但是这要求MIMO空分复用系统上行链路接收机有较高的信号检测能力。本文提出改进初始半径的球形检测算法进行信号复原,该算法能在较低的计算复杂度逼近最大似然的误码性能。仿真试验的结果验证所提出的球形检测算法在误码性能上优于现有其它检测算法。     

A fast branch,bound and remember algorithm for disassembly line balancing problem

In recent years, the interests of disassembly line have increased owing to economic reasons and the increase of environmental awareness. Effective line can provide many advantages in terms of economic aspect and it facilitates competition the companies with others. This study contributes to the relevant literature by a branch, bound and remember algorithm for disassembly line balancing problem with AND/OR precedence. The proposed exact solution method employs the memory-based dominance rule to eliminate the reduplicated sub-problems by storing all the searched sub-problems and to utilise cyclic best-first search strategy to obtain high-quality complete solutions fast. In this paper, minimising the number of stations is taken as the performance measure. The proposed methodology is tested on a set of 260 instances and compared with the mathematical model using CPLEX solver and five well-known metaheuristics. Computational results show that the proposed method is capable of obtaining the optimal solutions for all the tested instances with less than 0.1?seconds on average. Additionally, comparative study demonstrates that the proposed method is the state-of-the-art algorithm and outperforms the CPLEX solver and metaheuristics in terms of both solution quality and search speed aspects.     

A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows

A branch and bound algorithm is described for optimal cyclic scheduling in a robotic cell with processing time windows. The objective is to minimise the cycle time by determining the exact processing time on each machine which is limited within a time window. The problem is formulated as a set of prohibited intervals of the cycle time, which is usually applied in the robotic cyclic scheduling problem with fixed processing times. Since both bounds of these prohibited intervals are linear expressions of the processing times, we divide these prohibited intervals into a series of the subsets and transform the problem into enumerating the non-prohibited intervals of cycle time in each subset. This enumeration procedure is completed by an efficient branch and bound algorithm, which could find an optimal solution by enumerating partial non-prohibited intervals. Computational results on the benchmark instances and randomly generated test instances indicate that the algorithm is effective.     

A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan

In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution.     

A branch and bound algorithm for the strip packing problem

We propose a new branch and bound algorithm for the two dimensional strip packing problem, in which a given set of rectangular pieces have to be packed into a strip of given width and infinite length so as to minimize the required height of the packing. We develop lower bounds based on integer formulations of relaxations of the problem as well as new bounds based on geometric considerations, and reduce the tree search with some dominance criteria. An extensive computational study shows the relative efficiency of the bounds and the good performance of the exact algorithm.     

Hybrid branch and bound algorithms for the two-stage assembly scheduling problem with separated setup times

This article proposes hybrid branch and bound algorithms to minimise the makespan for the two-stage assembly scheduling problem with separated setup times. In the studied problem, there are multiple machines at the first stage, each of which produces a component of a job. When all components are available, a single assembly machine at the second stage completes the job. Existing algorithms are based on the state space search and hence suffer from the state space explosion problem. In order to reduce the search space, lower and upper bounds for a partial schedule are proposed. Also, a heuristic function and a dominance rule are developed to guide the search process. Moreover, accelerated factors are introduced to increase the speed of the search. Experimental results indicate that our algorithms outperform an existing method, and can find the optimal or near-optimal schedules in a short time for all tested problems with up to ten thousand jobs and nine first-stage machines.     

Capacity allocation problem in flexible manufacturing systems: branch and bound based approaches

This study considers an operation assignment and capacity allocation problem that arises in flexible manufacturing systems. The machines have limited time and tool magazine capacities and the available tools are limited. Our objective is to maximise total weight of assigned operations. We develop a branch and bound algorithm that finds the optimal solutions and a beam search algorithm that finds high quality solutions in polynomial time.     

An improved best-first branch-and-bound algorithm for constrained two-dimensional guillotine cutting problems

The constrained two-dimensional cutting problem involves maximising the sum of the profits obtained from small rectangular pieces cut from a large rectangular plate where the number of each type of cut piece cannot exceed a prescribed quantity. This paper proposes a best-first branch-and-bound algorithm to find the optimal solution to the problem. The proposed algorithm uses an efficient method to remove the duplicate patterns, and it improves the existing upper bounds. It also prevents the construction of dominated patterns and introduces a new bounding strategy that can prune more than one node at a time. Computational results are compared with a well-known exact algorithm to demonstrate the efficiency of the proposed algorithm. The proposed algorithm is as fast as or faster than the existing algorithm and reduces the average computing time by up to 99% for benchmark problems. For some problems, it can also find optimal solutions that existing algorithms are not able to find.     

移动机器人在大尺度未知环境下的自主导航方法——改进的FastSLAM算法

在移动机器人同时定位和地图创建过程中,标准FastSLAM算法（对SLAM因式分解的一种快速算法）通常假设机器人观测值和环境陆标之间的数据关联是已知的（即采用预置陆标）来回避数据关联问题。针对标准FastSLAM算法的这一缺陷,提出了一种适合大尺度未知环境（即数据关联未知）下的基于单个粒子最大似然数据关联和环境否定信息相结合的FastSLAM改进算法。该算法用基于单个粒子最大似然数据关联法保证当前运动噪声对下一步关联数据精度的影响和“失踪”问题的出现,而用环境否定信息法避免错误陆标添加到环境地图中。仿真结果表明,改进的FastSLAM算法解决了大尺度未知环境下的数据关联问题,提高了机器人自身定位和地图创建的精度,可真正实现机器入在大尺度未知环境的自主导航。     

An exact algorithm for a workforce allocation problem with application to an analysis of cross-training policies

The evaluation of workforce staffing and scheduling policies is of paramount importance for meeting the challenge of simultaneously providing good customer service and low operational costs. Policy studies are particularly critical in workforce environments plagued by staffing shortages. The cross-utilization of employees among different departments or work centers is a well-recognized staffing policy for coping with shortages. We revisit a non-linear assignment problem for allocating cross-trained workers so as to maximize overall utility, which is measured using a quadratic function of labor shortages. We develop a branch-and-bound algorithm that efficiently provides optimal solutions for problems of practical size. This algorithm is then used to conduct a computational investigation of cross-training policies. Among the most critical factors affecting utility improvement are the coefficient of variation for demand, worker absenteeism, the percentage of cross-trained workers and cross-training breadth. Several important interactions among these and other factors are also identified.     

一种改进的球形解码算法

提出了算法根据累积分布函数得到一个阈值,在搜索到叶子节点后,将累积度量值和阈值进行比较来判断是否找到最大似然解,从而降低了球形解码算法在高信噪比范围内的复杂度.阈值的选取对球形解码算法的性能有一定的影响,在取值时,可以根据不同的信噪比范围对性能和复杂度做一个权衡.仿真结果表明,所提出算法的展开节点数在高信噪比范围内收敛于m.