Variable sampling plans for normal distribution indexed by Taguchi's loss function

Taguchi has presented an approach to quality improvement in which reduction of deviation from the target value is the guiding principle. In this approach any measured value x of a product characteristic X brings a loss to consumer in general, where the loss is expressed as a quadratic form with respect to the difference between the measured value x and the target value T of a product characteristic. Then, it is natural to reject the lot which may bring a large loss to consumer. This concept induces us to construct new variable sampling plans based on the Taguchi's loss criterion. In this article, a design procedure of the sampling plans for assuring the loss in the Taguchi's method is proposed. Some numerical results based on the proposed design procedures are illustrated. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 591–603 (1997)     

低轨预警自由段弹道估计的多项式逼近算法

低轨单星对自由段弹道的估计是天基预警系统需解决的关键技术之一.建立了低轨预警卫星对自由段弹道的观测模型,针对极大似然估计批处理算法的大运算量问题,给出了一种多项式逼近算法,由观测数据的逼近多项式在一些特定采样点的值形成伪观测数据,以伪观测数据代替原观测数据进行弹道估计.仿真表明,精度与极大似然估计相当,运算量显著降低.     

Two-agent scheduling with linear resource-dependent processing times

This paper considers a two-agent scheduling problem with linear resource-dependent processing times, in which each agent has a set of jobs that compete with that of the other agent for the use of a common processing machine, and each agent aims to minimize the weighted number of its tardy jobs. To meet the due date requirements of the jobs of the two agents, additional amounts of a common resource, which may be in discrete or continuous quantities, can be allocated to the processing of the jobs to compress their processing durations. The actual processing time of a job is a linear function of the amount of the resource allocated to it. The objective is to determine the optimal job sequence and resource allocation strategy so as to minimize the weighted number of tardy jobs of one agent, while keeping the weighted number of tardy jobs of the other agent, and the total resource consumption cost within their respective predetermined limits. It is shown that the problem is -hard in the ordinary sense, and there does not exist a polynomial-time approximation algorithm with performance ratio unless ; however it admits a relaxed fully polynomial time approximation scheme. A proximal bundle algorithm based on Lagrangian relaxation is also presented to solve the problem approximately. To speed up convergence and produce sharp bounds, enhancement strategies including the design of a Tabu search algorithm and integration of a Lagrangian recovery heuristic into the algorithm are devised. Extensive numerical studies are conducted to assess the effectiveness and efficiency of the proposed algorithms.     

矩阵代数中可乘保范映照的显形式

在矩阵的可乘映照理论与应用中,判定一个可乘映照是否保持某类特定的数值特征以及获取可乘映照在保持某类数值特征条件下的解析式备受关注.对此,着重研究了一般可乘映照在具有某种保秩性或保范性下的表示问题.借助于构造的方法,给出了判定一个可乘映照是否为保秩映照的新的便捷方法.针对F=R或C,分别得到了Mn(F)上保1-范数、保∞-范数以及保F范数的可乘映照的显形式,进而证明了Mn(F)上保持1-范数可乘映照必为保F范数映照,而可乘保F范数映照又一定保谱半径、保数值半径、保正规性、保酉性等.     

Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016     

Approximation algorithms for sequential batch‐testing of series systems

We introduce and study a generalization of the classic sequential testing problem, asking to identify the correct state of a given series system that consists of independent stochastic components. In this setting, costly tests are required to examine the state of individual components, which are sequentially tested until the correct system state can be uniquely identified. The goal is to propose a policy that minimizes the expected testing cost, given a‐priori probabilistic information on the stochastic nature of each individual component. Unlike the classic setting, where variables are tested one after the other, we allow multiple tests to be conducted simultaneously, at the expense of incurring an additional set‐up cost. The main contribution of this article consists in showing that the batch testing problem can be approximated in polynomial time within factor , for any fixed . In addition, we explain how, in spite of its highly nonlinear objective function, the batch testing problem can be formulated as an approximate integer program of polynomial size, while blowing up its expected cost by a factor of at most . Finally, we conduct extensive computational experiments, to demonstrate the practical effectiveness of these algorithms as well as to evaluate their limitations. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 275–286, 2016     

Pricing bridges to cross a river

We consider a pricing problem in directed, uncapacitated networks. Tariffs must be defined by an operator, the leader, for a subset of m arcs, the tariff arcs. Costs of all other arcs in the network are assumed to be given. There are n clients, the followers, and after the tariffs have been determined, the clients route their demands independent of each other on paths with minimal total cost. The problem is to find tariffs that maximize the operator's revenue. Motivated by applications in telecommunication networks, we consider a restricted version of this problem, assuming that each client utilizes at most one of the operator's tariff arcs. The problem is equivalent to pricing bridges that clients can use in order to cross a river. We prove that this problem is APX‐hard. Moreover, we analyze the effect of uniform pricing, proving that it yields both an m approximation and a (1 + lnD)‐approximation. Here, D is upper bounded by the total demand of all clients. In addition, we consider the problem under the additional restriction that the operator must not reject any of the clients. We prove that this problem does not admit approximation algorithms with any reasonable performance guarantee, unless P = NP, and we prove the existence of an n‐approximation algorithm. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Maintenance scheduling for modular systems: Modeling and algorithms

We study new models of scheduled maintenance management for modular systems, consisting of multiple components with respective cycle limits. The cycle limit of each component specifies the time interval in which this component must be repaired or replaced. The goal is to compute a feasible maintenance schedule that minimizes the cost associated with component maintenance. Applications of these models arise in Air Force aircraft maintenance as well as in other arenas with required preventive maintenance. The typical cost structures that arise in practical settings are submodular, which make the resulting models computationally challenging. We develop two efficient and operationally tenable approximation algorithms. We prove constant factor worst‐case guarantees for both algorithms, and present computational experiments showing that these algorithms perform within a few percent of optimality on operationally relevant instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 472–488, 2014     

Scheduling twin robots on a line

This article introduces the twin robots scheduling problem (TRSP), in which two robots positioned at the opposite ends of a rail are required to deliver items to positions along the rail, and the objective is to minimize the makespan. A proof of ‐hardness of the TRSP is presented, along with exact and heuristic algorithms. Computational results on challenging instances are provided.Copyright © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 119–130, 2014