流域变换的串行与并行策略研究

流域变换是数字形态学中用于图像分割的一种经典方法,其并行化问题成为近年来研究的重点。首先给出了流域变换的数学模型,并归纳列举了几种离散情况下的形式化定义;其次分类总结了近年来流域变换串行算法研究的新进展,从而在此基础上重点讨论了相应的并行化策略。详细分析了设计并行流域算法需要考虑的几个问题;并比较评价了现有并行算法的性能特点,得出了一些结论;最后提出了有待进一步研究的问题。     

Short‐term capacity allocation problem with tool and setup constraints

We consider a short‐term capacity allocation problem with tool and setup constraints that arises in the context of operational planning in a semiconductor wafer fabrication facility. The problem is that of allocating the available capacity of parallel nonidentical machines to available work‐in‐process (WIP) inventory of operations. Each machine can process a subset of the operations and a tool setup is required on a machine to change processing from one operation to another. Both the number of tools available for an operation and the number of setups that can be performed on a machine during a specified time horizon are limited. We formulate this problem as a degree‐constrained network flow problem on a bipartite graph, show that the problem is NP‐hard, and propose constant factor approximation algorithms. We also develop constructive heuristics and a greedy randomized adaptive search procedure for the problem. Our computational experiments demonstrate that our solution procedures solve the problem efficiently, rendering the use of our algorithms in real environment feasible. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Approximation of multiclass queueing networks with highly variable arrivals under deterministic routing

In this paper, we present the heavy‐traffic bottleneck phenomenon under multiclass deterministic routing and discuss how it can be addressed by decomposition approximation. Examples show that Bitran and Tirupati's method and Whitt's enhancements for deterministic routing may not properly account for this phenomenon. We propose refinements to these methods based on Whitt's variability functions. Results of numerical experiments on simple networks and semiconductor manufacturing process show significant improvement in the approximation of expected waiting time at bottleneck stations. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

基于遗传算法的信息系统安全技术方案

组织如何制定优化的信息安全技术方案以降低脆弱性对其信息系统的威胁,是信息安全管理领域的关键问题。在描述信息系统安全技术方案决策模型的基础上,提出了一种求解信息系统安全技术方案优化问题的自适应遗传算法,使得组织能以最少的方案实施费用最大限度地处置脆弱性,并以实例说明了该算法的有效性。     

基于RS近似算法的医疗诊断知识挖掘

针对医学领域诊断规则挖掘算法中时间和空间复杂性问题,提出一种基于邻域系统的决策表近似算法,用于医疗诊断数据挖掘预处理阶段的数据压缩.该方法以代表元素代替若干相近元素,有效地压缩了原始决策表的对象个数,同时保证决策表本身的判断能力基本不变.实例仿真表明,该算法具有比传统聚类算法更优的性能.     

改进的接触算法及其在光滑粒子流体动力学中的应用

采用以黎曼解描述粒子间相互作用的接触算法,模拟一维情况下包含间断的流场。在弱间断的条件下,采用弱波近似的黎曼解来描述粒子间的相互作用;在强间断的条件下,则引入非迭代黎曼解来描述粒子间的相互作用。并引入Taylor展开思想,提高了接触算法在自由边界的计算精度。该算法无需引入人为粘性,程序结构简洁。数值计算表明,改进后的接触算法能很好地描述强间断,并有效改善了原始接触算法在自由面的计算缺陷。     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Maximizing project cash availability

Consider a project during the life cycle of which there are cash payouts and in‐flows. To better meet his financial commitments, the project owner would like to meet all deadlines without running out of cash. We show that the cash availability objective is similar to the total weighted flowtime used to measure work‐in‐progress performance in the scheduling and inventory control literatures. In this article we provide several specialized solution methods for the problem of minimizing total weighted flowtime in an arbitrary acyclic project network, subject to activity release times and due dates, where the activity weights may be positive or negative and represent cash in‐ and out‐flows. We describe the structure of an optimal solution and provide several efficient algorithms and their complexity based on mincost and maxflow formulations. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000