基于列表的迭代分枝定界MIMO检测算法

提出了基于列表的迭代分枝定界算法,利用搜索到的候选列表计算比特软信息,降低了MAP计算复杂度,同时进一步提出了改进的列表分枝定界算法,每次迭代利用更新的先验信息重新计算候选列表,提高了列表质量。仿真结果表明列表分枝定界算法通过在MIMO信道检测和信道解码之间传递外信息,取得了逼近信道容量的性能,而修正的考虑先验信息的列表分枝定界算法在性能损失可忽略的情况下,减小了候选列表的大小。     

An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance

In this paper, we investigate a single-machine scheduling problem with periodic maintenance, which is motivated by various industrial applications (e.g. tool changes). The pursued objective is to minimise the number of tardy jobs, because it is one of the important criteria for the manufacturers to avoid the loss of customers. The strong NP-hardness of the problem is shown. To improve the state-of-the-art exact algorithm, we devise a new branch-and-bound algorithm based on an efficient lower bounding procedure and several new dominance properties. Numerical experiments are conducted to demonstrate the efficiency of our exact algorithm.     

快速非参数分类器BDPATCH-GBB

本文提出了一种快速的浓缩近邻分类器BDPATCH-GBB,并从压缩样本集和减少计算 量两方面着手提高分类器的性能.实验表明,与其它近邻分类器相比,BDPATCH-GBB是高 效的.     

Parallel branch-and-bound search in Parlog

The concurrent logic languages, of which Parlog is one, have been promoted as a new generation of software languages specifically designed for parallel programming. This paper investigates their application to a search problem commonly used as an illustration of artificial intelligence techniques, the 8-puzzle. It notes that programs written in the concurrent logic languages which do not pay attention to the parallelism can fall into two possible traps: either there is little real parallelism in them due to data dependencies, or there is too much parallelism and any practical architecture will be overwhelmed. A solution which controls the parallelism using user-defined priorities is proposed. This solution has the advantage of being architecture-independent.     

Tight bounds for the identical parallel machine-scheduling problem: Part II

A companion paper introduces new lower bounds and heuristics for the problem of minimizing makespan on identical parallel machines. The objective of this paper is threefold. First, we describe further enhancements of previously described lower bounds. Second, we propose a new heuristic that requires solving a sequence of 0–1 knapsack problems. Finally, we show that embedding these newly derived bounds in a branch‐and‐bound procedure yields a very effective exact algorithm. Moreover, this algorithm features a new symmetry‐breaking branching strategy. We present the results of computational experiments that were carried out on a large set of instances and that attest to the efficacy of the proposed algorithm. In particular, we report proven optimal solutions for some benchmark problems that have been open for some time.     

Embedding Branch and Bound within Evolutionary Algorithms

A framework for hybridizing evolutionary algorithms with the branch-and-bound algorithm (B&B) is presented in this paper. This framework is based on using B&B as an operator embedded in the evolutionary algorithm. The resulting hybrid operator will intelligently explore the dynastic potential (possible children) of the solutions being recombined, providing the best combination of formae (generalized schemata) that can be constructed without introducing implicit mutation. As a basis for studying this operator, the general functioning of transmitting recombination is considered. Two important concepts are introduced, compatibility sets, and granularity of the representation. These concepts are studied in the context of different kinds of representation: orthogonal, non-orthogonal separable, and non-separable.The results of an extensive experimental evaluation are reported. It is shown that this model can be useful when problem knowledge is available in the form of an optimistic evaluation function. Scalability issues are also considered. A control mechanism is proposed to alleviate the increasing computational cost of the algorithm for highly multidimensional problems.     

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

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

物流网络设计建模与求解算法研究

研究了制造系统中物流网络设计问题,构建了一个带固定费用的容量受限的网络设计模型,提出了一种求解该问题的基于拉格朗日启发式算法的增强型分枝定界方法。通过大量的试验测试,结果表明该算法能有效地解决大型的具有NP-hard特性的网络设计问题。     

一种复杂项目调度问题的混合智能算法

针对有资源约束的项目调度问题模型的不足,调研了企业需求,提出了带有预约时间窗口约束的项目调度模型,并针对该类模型的特点分析了原有算法存在的问题,将分枝定界算法与启发式算法相结合,提出了一种解决该类问题的混合智能算法.仿真结果表明,该算法的优化效果明显优于其他算法.     

A sequencing problem for a mixed-model assembly line in a JIT production system

In an assembly line of a just-in-time (JIT) production system, workers have the power and the responsibility to stop the line when they fail to complete their operations within their work zones. This paper deals with a sequencing problem for the mixed-model assembly conveyor line in the JIT production system. In some environment, the most important criterion is the line stoppage rather than the variation of production rates. The problem is to find an optimal sequence of units that minimizes the total line stoppage time. Lower and upper bounds of the total line stoppage time are derived and the branch-and-bound method is applied to the problem. A numerical example is given.