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     

On efficient algorithms for finding efficient salvo policies

We consider the salvo policy problem, in which there are k moments, called salvos, at which we can fire multiple missiles simultaneously at an incoming object. Each salvo is characterized by a probability p_i: the hit probability of a single missile. After each salvo, we can assess whether the incoming object is still active. If it is, we fire the missiles assigned to the next salvo. In the salvo policy problem, the goal is to assign at most n missiles to salvos in order to minimize the expected number of missiles used. We consider three problem versions. In Gould's version, we have to assign all n missiles to salvos. In the Big Bomb version, a cost of B is incurred when all salvo's are unsuccessful. Finally, we consider the Quota version in which the kill probability should exceed some quota Q. We discuss the computational complexity and the approximability of these problem versions. In particular, we show that Gould's version and the Big Bomb version admit pseudopolynomial time exact algorithms and fully polynomial time approximation schemes. We also present an iterative approximation algorithm for the Quota version, and show that a related problem is NP-complete.     

目标宽频带RCS的快速算法研究

目标宽带RCS预估算法一直是计算电磁学的一个研究热点,本文分别研究了渐近波形估计技术（AWE）与最佳一致逼近技术在宽频带RCS预估领域内的应用。首先,介绍了传统矩量法计算RCS的原理,并分析了两种快速算法的计算过程。然后,采用这两种技术,分别计算了简易飞机模型的RCS值,并对这两种方法进行比较。计算结果表明相比传统的矩量法,这两种方法在不影响精度的前提下大大提高了计算效率。同时,相比渐近波形估计技术,最佳一致逼近技术在节省内存,节约时间方面更具优势。最后,采用最佳一致逼近理论,结合电磁计算软件,实现较大尺寸目标的宽频带RCS的计算。     

Single‐machine scheduling with deadlines to minimize the total weighted late work

We consider scheduling a set of jobs with deadlines to minimize the total weighted late work on a single machine, where the late work of a job is the amount of processing of the job that is scheduled after its due date and before its deadline. This is the first study on scheduling with the late work criterion under the deadline restriction. In this paper, we show that (i) the problem is unary NP‐hard even if all the jobs have a unit weight, (ii) the problem is binary NP‐hard and admits a pseudo‐polynomial‐time algorithm and a fully polynomial‐time approximation scheme if all the jobs have a common due date, and (iii) some special cases of the problem are polynomially solvable.     

Simple paths with exact and forbidden lengths

We study new decision and optimization problems of finding a simple path between two given vertices in an arc weighted directed multigraph such that the path length is equal to a given number or it does not fall into the given forbidden intervals (gaps). A fairly complete computational complexity classification is provided and exact and approximation algorithms are suggested.