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.     

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.     

Alternative branching rules for some nonconvex problems

Following Linderoth (A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program. 103 (2005), pp. 251–282), in this paper we show how a preliminary theoretical analysis about the quality of convex and concave envelopes over different regions may suggest branching rules alternative to the traditional ones based on boxes. For two nonconvex problems (minimization of the sum of products of affine functions and maximization of the sum of ratios of affine functions, in both cases over polytopes), we show how the indications of the theoretical analysis lead to computational results which confirm the superiority of the alternative branching rules with respect to those based on boxes.     

Minimizing the total completion time in a two-machine flowshop problem with time delays

This article proposes to solve the problem of minimizing the total completion time in a two-machine permutation flowshop environment in which time delays between the machines are considered. For this purpose, an enumeration algorithm based on the branch-and-bound framework is developed, which includes new lower and upper bounds as well as dominance rules. The computational study shows that problems with up to 40 jobs can be solved in a reasonable amount of time.     

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.     

用分支定界算法求解旅行商问题

在0—1整数规划的基础上建立了数学模型,利用MATLAB6．5优化工具箱中的linprog函数进行求解,再经过分支定界算法计算,求出了只含有0和1的解．实验结果表明,该算法可以求解小规模旅行商问题．     

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

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

使用R树进行k-NN搜索

在地理信息系统中经常要做k-NN搜索，进行这些查询用到的算法与位置和范围查询的算法不同，需要专门进行研究，介绍了一种分支界限遍历R树算法，并将该算法概括为k-NN算法。文中讨论了两种方法。对R树进行结点内MBR的排序以及剪枝过程，以减少搜索空间中需访问结点的数量，有效地进行k-NN搜索。     

快速非参数分类器BDPATCH-GBB

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