Scheduling to minimize the total compression and late costs

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 67–82, 1998     

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展开思想,提高了接触算法在自由边界的计算精度。该算法无需引入人为粘性,程序结构简洁。数值计算表明,改进后的接触算法能很好地描述强间断,并有效改善了原始接触算法在自由面的计算缺陷。     

现代机载探测系统多源信息融合算法

针对机载探测系统的特性,应用Dempster-Shafer(D-S)证据理论和主观Bayes的组合算法,对来自机载SAR雷达、机载前视红外搜索跟踪系统(IRS)、电子支援系统(ESM)等探测系统多次观测所获得的数据,以及来自地面的电子情报(ELINT)的不同信息进行实时融合、识别,进而确定攻击对象.通过实例进行仿真证明,这种组合算法适用于不同类传感器和不同格式信息间的融合,适合于复杂信号环境.     

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     

模糊逻辑系统在船舶风险评估中的应用

为了合理进行船舶风险评估,提出了一种基于模糊逻辑系统的船舶风险评估方法.根据模糊逻辑系统的基本原理,建立了船舶风险评估的模糊逻辑模型;按照国家标准、规范,并结合经验建立了风险指标的模糊集合、风险矩阵及模糊规则,然后进行了模糊推理,得到了系统的风险等级,并制定了预防风险的措施.以某艇消防系统的风险评估为例,证明了其能够合理地评估出系统的风险,可为决策提供参考.     

A bidirectional heuristic for maximizing the net present value of large‐scale projects subject to limited resources

We consider the scheduling of large‐scale projects to maximize the project net present value given temporal and resource constraints. The net present value objective emphasizes the financial aspects of project management. Temporal constraints between the start times of activities make it possible to handle practical problem assumptions. Scarce resources are an expression of rising cost. Since optimization techniques are not expedient to solve such problems and most heuristic methods known from literature cannot deal with general temporal constraints, we propose a new bidirectional priority‐rule based method. Scheduling activities with positive cash flows as early and activities with negative cash flows as late as possible results in a method which is completed by unscheduling techniques to cope with scarce resources. In a computational experiment, we compare the well‐known serial generation scheme where all activities are scheduled as early as possible with the proposed bidirectional approach. On the basis of a comprehensive data set known from literature containing instances with up to 1002 activities, the efficiency of the new approach is demonstrated. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003