A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry

The molten iron allocation problem (MIAP) is to allocate molten iron from blast furnaces to steel-making furnaces. The allocation needs to observe the release times of the molten iron defined by the draining plan of the blast furnaces and the transport time between the iron-making and steel-making stages. Time window constraints for processing the molten iron must be satisfied to avoid freezing. The objective is to find a schedule with minimum total weighted completion time. This objective reflects the practical consideration of improving steel-making efficiency and reducing operation cost caused by the need for reheating. Such a problem can be viewed as a parallel machine scheduling problem with time windows which is known to be NP-hard. In this paper, we first formulate the molten iron allocation problem as an integer programming model and then reformulate it as a set partitioning model by applying the Dantzig–Wolfe decomposition. We solve the problem using a column generation-based branch-and-price algorithm. Since the subproblem of column generation is still NP-hard, we propose a state-space relaxation-based dynamic programming algorithm for the subproblem. Computational experiments demonstrate that the proposed algorithm is capable of solving problems with up to 100 jobs to optimality within a reasonable computation time.     

基于画圆算法的简单弧形贴图算法

本文提出了一种基于画圆算法的简单弧形贴图算法，并分析了该算法的可行性。     

Tuning fuzzy power-system stabilizers in multi-machine systems by global optimization algorithms based on efficient domain partitions

In this paper, the problem of global tuning of fuzzy power-system stabilizers (FPSSs) present in a multi-machine power system in order to damp the power system oscillations is considered. In particular, it is formulated as a problem of global minimization of a multiextremal black-box function over a multidimensional hyperinterval. A global optimization technique, recently proposed, is used for solving the stated problem: the search hyperinterval is partitioned into smaller hyperintervals and the objective function is evaluated only at two vertices corresponding to the main diagonal of the generated hyperintervals, thus avoiding unnecessary ponderous simulations. Then, the performances of this technique are numerically compared with ones of a genetic algorithm (GA).     

采集数据曲线快速流动显示算法研究

该文分析了采集数据以图形方式在PC机标准适配器下快速流动显示问题，提出了逐点地址跟踪快速算法。     

军械调运方案优化算法的设计与仿真

军械调运问题的数学模型和手工算法过去已有研究,但是当问题较为复杂时,手工算法就要花费大量时间而且准确性也难以保证。针对这一缺陷,本文在已有的数学模型和手工算法的基础上,设计了一种可以用计算机实现的基于递归的算法来寻求军械紧急调运问题的最优方案,并使用面向对象的java语言将算法实现。     

用C语言链表解决大整数运算的精度问题

介绍用C语言链表解决大整数运算的精度问题的方法。     

EFFECTIVE PARALLELIZATION TECHNIQUES FOR LOOP NESTS WITH NON-UNIFORM DEPENDENCES

The parallelism of loop nests with non-uniform dependences is difficult to extract and ineffectively explored by the existing parallelization schemes. In this paper, we propose new efficient techniques in extracting parallelism of loop nests with non-uniform dependences using their irregularity. By this way, current highly parallel multiprocessor systems such as multithreaded and clustering multiprocessor systems can be fully utilized. These four mechanisms are (a) parallelization part splitting, (b) partial parallelization decomposition, (c) irregular loop interchange and (d) growing pattern detection. They explore parallelisms of special parallel patterns for nested loops with non-uniform dependences. The loop transformations used in uniform loops are also applied in non-uniform dependence loops after legality tests. We apply the results of classical convex theory and detect special parallel patterns of dependence vectors. We also proposed an algorithm that combines above mechanisms to enhance parallelism. We demonstrate that our technique gives much better speedup and extracts more parallelism than the existing techniques. Thus, we are encouraged by these apparent enhancements to pursue further development.     

A note on circle packing

The problem of packing circles into a domain of prescribed topology is considered. The circles need not have equal radii. The Collins-Stephenson algorithm computes such a circle packing. This algorithm is parallelized in two different ways and its performance is reported for a triangular, planar domain test case. The implementation uses the highly parallel graphics processing unit (GPU) on commodity hardware. The speedups so achieved are discussed based on a number of experiments.     

基于减聚类优化算法的无线传感网络分簇路由协议研究

无线传感网络是当前无线网络研究的热点领域,分簇路由协议作为降低网络能耗、提高网络生存时间的核心技术而备受关注。在深入分析已有算法存在诸多不足的基础上,本文提出了一种基于减聚类优化的分簇路由算法。本文首先建立一阶能耗模型,确定网络最优簇首数量;然后建立减聚类优化数学模型,确定可供选择的分簇方案;最后以最小化最大簇内距离方差作为评价指标,确定最优的分簇结果。仿真结果表明:相比经典的LEACH分簇路由协议,该算法划分的网络能够有效地降低网络能耗、提高网络生存时间,弥补已有算法的不足之处。     

基于模拟退火算法的旅行商问题的实现

旅行商问题TSP是一类典型的NP完全问题．围绕着这个问题有各种不同的求解方法,已有的算法例如动态规划法、分支限界法、回溯法等,这些精确式方法都是指数级的,根本无法解决目前的实际问题．贪心法是近似方法．无法达到比较满意的近似比。常用的遗传算法也是求解这类问题的常用方法之一。由于该问题的解是一种特殊的序列．所以遗传算法在求解该问题时的性能也并不理想。模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点．是解决旅行商问题的一种很好的算法。