On parallel machine replacement problems with general replacement cost functions and stochastic deterioration

The parallel machine replacement problem consists of finding a minimum cost replacement policy for a finite population of economically interdependent machines. In this paper, we formulate a stochastic version of the problem and analyze the structure of optimal policies under general classes of replacement cost functions. We prove that for problems with arbitrary cost functions, there can be optimal policies where a machine is replaced only if all machines in worse states are replaced (Worse Cluster Replacement Rule). We then show that, for problems with replacement cost functions exhibiting nonincreasing marginal costs, there are optimal policies such that, in any stage, machines in the same state are either all kept or all replaced (No‐Splitting Rule). We also present an example that shows that economies of scale in replacement costs do not guarantee optimal policies that satisfy the No‐Splitting Rule. These results lead to the fundamental insight that replacement decisions are driven by marginal costs, and not by economies of scale as suggested in the literature. Finally, we describe how the optimal policy structure, i.e., the No‐Splitting and Worse Cluster Replacement Rules, can be used to reduce the computational effort required to obtain optimal replacement policies. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

A generalization of the weighted set covering problem

We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect b‐matching problem. In general, we may use a polynomial‐time greedy heuristic similar to the one for the classical weighted set covering problem studied by D.S. Johnson [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256–278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383–390], and V. Chvatal [A greedy heuristic for the set‐covering problem, Math Oper Res 4(3) (1979), 233–235] to get an approximate solution for the problem. We find a worst‐case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

英语阅读中如何猜词解义

在阅读英语时,首先遇到的问题是生词。如果时时停下来查词典,就会影响思维的连续性、阅读速度甚至丧失阅读兴趣。外语教学中常常提到根据上下文了解词义,即在碰到难以理解的词语时,可以引导学生根据词汇语境线索和已知信息及构词法来进行推测。掌握猜词解义的方法,有助于提高阅读能力。     

一种可用于指挥自动化网的USB安全钥设计

介绍了一种用于指挥自动化网络中进行身份认证的USB安全钥安全管理系统,给出了使用USB安全钥进入网络终端时的认证机制,调用与浏览服务器信息时的认证流程,以及USB安全钥软、硬件的设计要点.在该安全钥管理系统中可运行重要软件的关键程序和查询关键信息,有效增强保密强度,安全钥采用USB接口,具有支持热插拔、携带方便等优点.     

Minimizing makespan on a single batch processing machine with nonidentical job sizes

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst‐case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst‐case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 226–240, 2001     

Analysis of a new vehicle scheduling and location problem

We consider a container terminal discharging containers from a ship and locating them in the terminal yard. Each container has a number of potential locations in the yard where it can be stored. Containers are moved from the ship to the yard using a fleet of vehicles, each of which can carry one container at a time. The problem is to assign each container to a yard location and dispatch vehicles to the containers so as to minimize the time it takes to download all the containers from the ship. We show that the problem is NP‐hard and develop a heuristic algorithm based on formulating the problem as an assignment problem. The effectiveness of the heuristic is analyzed from both worst‐case and computational points of view. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 363–385, 2001     

弹炮一体化防空系统的服务概率模型

弹炮一体化防空系统是未来高技术局部战争中应急机动部队的主要防空武器。首先给出了弹炮一体化防空系统服务概率的定义 ,然后通过研究这种防空武器对目标服务过程的特点 ,建立了服务概率计算模型 ,为评价这种防空武器的射击能力和系统效能 ,提供了必要的分析手段     

HLA在战术C3I系统仿真平台中的应用

基于仿真技术规范 HL A,提出一种战术 C3 I系统仿真平台构建方法 ,给出了基于 HL A/ RTI仿真平台的设计方案 ,并对仿真的执行过程进行了深入分析。     

Primal dual algorithms for the vehicle refueling problem

Mehrez, Stern, and Ronen have defined a vehicle refueling problem in which a fleet of vehicles travels on a round-trip, self-contained mission from a common origin, with the objective of maximizing the operational range of the fleet. They have defined a “pure refueling chain” strategy for transferring fuel between vehicles in the fleet, and have solved the problem in the special cases when all vehicles have the same fuel capacity or consumption rate. In this article we present algorithms for the general case, where vehicles have different capacities and consumption rates. Our approach is based on a new primal dual formulation of the problem. The exact algorithm was effective to find the optimal solution for a fleet size n ⩽13. For larger fleets, we present an approximation version of it, which very quickly found a solution within 1% of the maximum possible range for arbitrarily large (up to n = 200) fleets. We also show that a small number of the best vehicles can always reach almost the same range as a large fleet. © 1992 John Wiley & Sons, Inc.     

AHP-SWOT分析法在控制下交付行动方案决策中的应用

控制下交付作为打击毒品犯罪尤其是跨国有组织毒品犯罪的重要措施和手段,已发挥越来越重要的作用,是其他缉毒措施和手段无法取代的。但是,由于毒品犯罪的集团化、国际化、种类多元化程度加剧,使得控制下交付的复杂性与不确定性越来越明显。鉴于此,将AHP植入SWOT分析法中,以定性和定量相结合的科学方法解决控制下交付行动方案的优选问题,对提高控制下交付的成功率具有重要意义。