A nested benders decomposition approach for telecommunication network planning

Despite its ability to result in more effective network plans, the telecommunication network planning problem with signal‐to‐interference ratio constraints gained less attention than the power‐based one because of its complexity. In this article, we provide an exact solution method for this class of problems that combines combinatorial Benders decomposition, classical Benders decomposition, and valid cuts in a nested way. Combinatorial Benders decomposition is first applied, leading to a binary master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition. The algorithm is enhanced using valid cuts that are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem. The valid cuts proved efficient in reducing the number of times the combinatorial Benders master problem is solved and in reducing the overall computational time. More than 120 instances of the W‐CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

大型舰船平台购置费投资分布及控制

针对大型舰船平台购置费的特点,分析了其投资分布问题,利用龚伯兹曲线研究了在没有样本条件下的大型舰船平台购置费的投资分布,提出了基于生命周期曲线的大型舰船平台购置费投资分布模型,并用具体实例验证了模型的可行性。在大型舰船平台购置费投资分布研究以及总结对比武器装备费用控制方法的基础上,根据大型舰船平台购置费控制的特点,进行了大型舰船平台购置费控制问题的分析。针对原材料费用的控制,提出了基于材料纳期的费用控制方法;针对工时费用的控制,提出了基于国有单位平均工资指数的费用控制方法,并提出了大型舰船平台购置费控制的整体的观点。     

Inventory control under substitutable demand: A stochastic game application

Substitutable product inventory problem is analyzed using the concepts of stochastic game theory. It is assumed that there are two substitutable products that are sold by different retailers and the demand for each product is random. Game theoretic nature of this problem is the result of substitution between products. Since retailers compete for the substitutable demand, ordering decision of each retailer depends on the ordering decision of the other retailer. Under the discounted payoff criterion, this problem is formulated as a two‐person nonzero‐sum stochastic game. In the case of linear ordering cost, it is shown that there exists a Nash equilibrium characterized by a pair of stationary base stock strategies for the infinite horizon problem. This is the unique Nash equilibrium within the class of stationary base stock strategies. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 359–375, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10018     

Detection of a Markovian target with optimization of the search efforts under generalized linear constraints

This paper deals with search for a target following a Markovian movement or a conditionally deterministic motion. The problem is to allocate the search efforts, when search resources renew with generalized linear constraints. The model obtained is extended to resource mixing management. New optimality equations of de Guenin's style are obtained. Practically, the problem is solved by using an algorithm derived from the FAB method. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 117–142, 2002; DOI 10.1002/nav.10009     

光纤陀螺惯性导航算法及其仿真

针对角速率和比力输入时的惯性导航算法进行了深入的研究。对高动态环境下的不同的姿态更新算法进行了对比研究,提出了一种新的速度和位置更新中的转动补偿算法,它将低动态和高动态(划船效应和涡卷效应)转动效应合二为一进行修正。并对系统算法进行了计算机仿真研究,最后给出了仿真结果。     

超音速等离子喷涂连续梯度热障涂层工艺优化研究

采用"双通道、双温区"超音速等离子喷涂工艺制备了Ce-YSZ/NiCoCrAlY连续梯度热障涂层(CG-TBCs)。借助热喷涂粒子状态在线监测系统Spraywatch-2i,分别研究了电弧功率、喷涂距离对Ce-YSZ/NiCoCrAlY粒子速度和温度的影响。实验结果表明,当电弧功率为70 kW和68 kW时,Ce-YSZ与NiCoCrAlY粒子速度达到最高,分别为620 m/s和430 m/s。Ce-YSZ和NiCoCrAlY粉末粒子的平均温度均随电弧功率的增加而上升,但当功率分别达到60 kW和65 kW时,粒子温度的上升趋势不再明显。电弧功率选择在68 kW,喷涂距离定为90 mm左右时,制备的CG-TBCs在经历100次热循环后,其表面和内部均未出现明显的裂纹,具有优异的热震性能。     

Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine

This paper tackles the general single machine scheduling problem, where jobs have different release and due dates and the objective is to minimize the weighted number of late jobs. The notion of master sequence is first introduced, i.e., a sequence that contains at least an optimal sequence of jobs on time. This master sequence is used to derive an original mixed‐integer linear programming formulation. By relaxing some constraints, a Lagrangean relaxation algorithm is designed which gives both lower and upper bounds. The special case where jobs have equal weights is analyzed. Computational results are presented and, although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 50: 2003     

Discrete‐time analysis of MAP/PH/1 multiclass general preemptive priority queue

We use the matrix‐geometric method to study the MAP/PH/1 general preemptive priority queue with a multiple class of jobs. A procedure for obtaining the block matrices representing the transition matrix P is presented. We show that the special upper triangular structure of the matrix R obtained by Miller [Computation of steady‐state probabilities for M/M/1 priority queues, Oper Res 29(5) (1981), 945–958] can be extended to an upper triangular block structure. Moreover, the subblock matrices of matrix R also have such a structure. With this special structure, we develop a procedure to compute the matrix R. After obtaining the stationary distribution of the system, we study two primary performance indices, namely, the distributions of the number of jobs of each type in the system and their waiting times. Although most of our analysis is carried out for the case of K = 3, the developed approach is general enough to study the other cases (K ≥ 4). © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 662–682, 2003.     

Scheduling patients in an ambulatory surgical center

This paper presents a deterministic approach to schedule patients in an ambulatory surgical center (ASC) such that the number of postanesthesia care unit nurses at the center is minimized. We formulate the patient scheduling problem as new variants of the no‐wait, two‐stage process shop scheduling problem and present computational complexity results for the new scheduling models. Also, we develop a tabu search‐based heuristic algorithm to solve the patient scheduling problem. Our algorithm is shown to be very effective in finding near optimal schedules on a set of real data from a university hospital's ASC. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

A branch‐and‐cut algorithm for the quay crane scheduling problem in a container terminal

The quay crane scheduling problem consists of determining a sequence of unloading and loading movements for cranes assigned to a vessel in order to minimize the vessel completion time as well as the crane idle times. Idle times originate from interferences between cranes since these roll on the same rails and a minimum safety distance must be maintained between them. The productivity of container terminals is often measured in terms of the time necessary to load and unload vessels by quay cranes, which are the most important and expensive equipment used in ports. We formulate the quay crane scheduling problem as a vehicle routing problem with side constraints, including precedence relationships between vertices. For small size instances our formulation can be solved by CPLEX. For larger ones we have developed a branch‐and‐cut algorithm incorporating several families of valid inequalities, which exploit the precedence constraints between vertices. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006