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

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

Revenue management under randomly evolving economic conditions

We consider a dynamic pricing model in which the instantaneous rate of the demand arrival process is dependent on not only the current price charged by the concerned firm, but also the present state of the world. While reflecting the current economic condition, the state evolves in a Markovian fashion. This model represents the real‐life situation in which the sales season is relatively long compared to the fast pace at which the outside environment changes. We establish the value of being better informed on the state of the world. When reasonable monotonicity conditions are met, we show that better present economic conditions will lead to higher prices. Our computational study is partially calibrated with real data. It demonstrates that the benefit of heeding varying economic conditions is on par with the value of embracing randomness in the demand process. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 66:73–89,2019     

Optimal job splitting on a multi‐slot machine with applications in the printing industry

In this article, we define a scheduling/packing problem called the Job Splitting Problem, motivated by the practices in the printing industry. There are n types of items to be produced on an m‐slot machine. A particular assignment of the types to the slots is called a “run” configuration and requires a setup cost. Once a run begins, the production continues according to that configuration and the “length” of the run represents the quantity produced in each slot during that run. For each unit of production in excess of demand, there is a waste cost. Our goal is to construct a production plan, i.e., a set of runs, such that the total setup and waste cost is minimized. We show that the problem is strongly NP‐hard and propose two integer programming formulations, several preprocessing steps, and two heuristics. We also provide a worst‐case bound for one of the heuristics. Extensive tests on real‐world and randomly generated instances show that the heuristics are both fast and effective, finding near‐optimal solutions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

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.     

Reliability inference for field conditions from accelerated degradation testing

Accelerated degradation testing (ADT) is usually conducted under deterministic stresses such as constant‐stress, step‐stress, and cyclic‐stress. Based on ADT data, an ADT model is developed to predict reliability under normal (field) operating conditions. In engineering applications, the “standard” approach for reliability prediction assumes that the normal operating conditions are deterministic or simply uses the mean values of the stresses while ignoring their variability. Such an approach may lead to significant prediction errors. In this paper, we extend an ADT model obtained from constant‐stress ADT experiments to predict field reliability by considering the stress variations. A case study is provided to demonstrate the proposed statistical inference procedure. The accuracy of the procedure is verified by simulation using various distributions of field stresses. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

关于Reich的公开问题

设E是具有一致G -可微范数的实Banach空间 ,D是E的非空闭凸子集 ,T :D→D是非扩张映象 ,F(T)非空。设 {αn} ,{ βn}是 [0 ,1]中满足一定条件的两个序列 ,定义压缩映象St:D→D为 :St(z) =(1-t)x tTz , x ,z∈D , n≥ 1,t∈ (0 ,1) .设zt 是St 的唯一不动点 ,若当t→ 1-时 ,{zt}强收敛于某点z∈F(T) .那么 ,Reich序列 {xn}强收敛于某点z∈F(T) .     

Transporting jobs through a two‐machine open shop

We consider the two‐machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a ‐approximation algorithm. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

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