Production to order and off‐line inspection when the production process is partially observable

This study combines inspection and lot‐sizing decisions. The issue is whether to INSPECT another unit or PRODUCE a new lot. A unit produced is either conforming or defective. Demand need to be satisfied in full, by conforming units only. The production process may switch from a “good” state to a “bad” state, at constant rate. The proportion of conforming units in the good state is higher than in the bad state. The true state is unobservable and can only be inferred from the quality of units inspected. We thus update, after each inspection, the probability that the unit, next candidate for inspection, was produced while the production process was in the good state. That “good‐state‐probability” is the basis for our decision to INSPECT or PRODUCE. We prove that the optimal policy has a simple form: INSPECT only if the good‐state‐probability exceeds a control limit. We provide a methodology to calculate the optimal lot size and the expected costs associated with INSPECT and PRODUCE. Surprisingly, we find that the control limit, as a function of the demand (and other problem parameters) is not necessarily monotone. Also, counter to intuition, it is possible that the optimal action is PRODUCE, after revealing a conforming unit. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Subspace dynamic‐simplex linear interpolation search for mixed‐integer black‐box optimization problems

Design and management of complex systems with both integer and continuous decision variables can be guided using mixed‐integer optimization models and analysis. We propose a new mixed‐integer black‐box optimization (MIBO) method, subspace dynamic‐simplex linear interpolation search (SD‐SLIS), for decision making problems in which system performance can only be evaluated with a computer black‐box model. Through a sequence of gradient‐type local searches in subspaces of solution space, SD‐SLIS is particularly efficient for such MIBO problems with scaling issues. We discuss the convergence conditions and properties of SD‐SLIS algorithms for a class of MIBO problems. Under mild conditions, SD‐SLIS is proved to converge to a stationary solution asymptotically. We apply SD‐SLIS to six example problems including two MIBO problems associated with petroleum field development projects. The algorithm performance of SD‐SLIS is compared with that of a state‐of‐the‐art direct‐search method, NOMAD, and that of a full space simplex interpolation search, Full‐SLIS. The numerical results suggest that SD‐SLIS solves the example problems efficiently and outperforms the compared methods for most of the example cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 305–322, 2017     

Sensor placement in active multistatic sonar networks

The idea of deploying noncollocated sources and receivers in multistatic sonar networks (MSNs) has emerged as a promising area of opportunity in sonar systems. This article is one of the first to address point coverage problems in MSNs, where a number of points of interest have to be monitored in order to protect them from hostile underwater assets. We consider discrete “definite range” sensors as well as various diffuse sensor models. We make several new contributions. By showing that the convex hull spanned by the targets is guaranteed to contain optimal sensor positions, we are able to limit the solution space. Under a definite range sensor model, we are able to exclude even more suboptimal solutions. We then formulate a nonlinear program and an integer nonlinear program to express the sensor placement problem. To address the nonconvex single‐source placement problem, we develop the Divide Best Sector (DiBS) algorithm, which quickly provides an optimal source position assuming fixed receivers. Starting with a basic implementation of DiBS, we show how incorporating advanced sector splitting methods and termination conditions further improve the algorithm. We also discuss two ways to use DiBS to find multiple source positions by placing sensors iteratively or simultaneously. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 287–304, 2017     

Non‐zero‐sum nonlinear network path interdiction with an application to inspection in terror networks

A simultaneous non‐zero‐sum game is modeled to extend the classical network interdiction problem. In this model, an interdictor (e.g., an enforcement agent) decides how much of an inspection resource to spend along each arc in the network to capture a smuggler. The smuggler (randomly) selects a commodity to smuggle—a source and destination pair of nodes, and also a corresponding path for traveling between the given pair of nodes. This model is motivated by a terrorist organization that can mobilize its human, financial, or weapon resources to carry out an attack at one of several potential target destinations. The probability of evading each of the network arcs nonlinearly decreases in the amount of resource that the interdictor spends on its inspection. We show that under reasonable assumptions with respect to the evasion probability functions, (approximate) Nash equilibria of this game can be determined in polynomial time; depending on whether the evasion functions are exponential or general logarithmically‐convex functions, exact Nash equilibria or approximate Nash equilibria, respectively, are computed. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 139–153, 2017     

Scheduling economic lot sizes in deteriorating production systems

The paper considers the economic lot scheduling problem (ELSP) where production facility is assumed to deteriorate, owing to aging, with an increasing failure rate. The time to shift from an “in‐control” state to an “out‐of‐control” state is assumed to be normally distributed. The system is scheduled to be inspected at the end of each production lot. If the process is found to be in an “out‐of‐control” state, then corrective maintenance is performed to restore it to an “in‐control” state before the start of the next production run. Otherwise, preventive maintenance is carried out to enhance system reliability. The ELSP is formulated under the capacity constraint taking into account the quality related cost due to possible production of non‐conforming items, process inspection, and maintenance costs. In order to find a feasible production schedule, both the common cycle and time‐varying lot sizes approaches are utilized. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 650–661, 2003     

Optimal replacement for fault-tolerant systems

We consider the optimal replacement problem for a fault tolerant system comprised of N components. The components are distingushable, and the state of the system is given by knowing exactly which components are operationl and which have failed. The individual component failure rates depend on the state of the entire system. We assume that the rate at which the system produces income decreases as the system deteriorates and the system replacement cost rises. Individual components cannot be replaced. We give a greedy-type algorithm that produces the replacement policy that maximizes the long-run net system income per unit time.     

Maintaining systems with heterogeneous spare parts

We consider the problem of optimally maintaining a stochastically degrading, single‐unit system using heterogeneous spares of varying quality. The system's failures are unannounced; therefore, it is inspected periodically to determine its status (functioning or failed). The system continues in operation until it is either preventively or correctively maintained. The available maintenance options include perfect repair, which restores the system to an as‐good‐as‐new condition, and replacement with a randomly selected unit from the supply of heterogeneous spares. The objective is to minimize the total expected discounted maintenance costs over an infinite time horizon. We formulate the problem using a mixed observability Markov decision process (MOMDP) model in which the system's age is observable but its quality must be inferred. We show, under suitable conditions, the monotonicity of the optimal value function in the belief about the system quality and establish conditions under which finite preventive maintenance thresholds exist. A detailed computational study reveals that the optimal policy encourages exploration when the system's quality is uncertain; the policy is more exploitive when the quality is highly certain. The study also demonstrates that substantial cost savings are achieved by utilizing our MOMDP‐based method as compared to more naïve methods of accounting for heterogeneous spares.     

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     

Optimal burn‐in procedure for periodically inspected systems

Burn‐in is a widely used method to improve the quality of products or systems after they have been produced. In this paper, we study burn‐in procedure for a system that is maintained under periodic inspection and perfect repair policy. Assuming that the underlying lifetime distribution of a system has an initially decreasing and/or eventually increasing failure rate function, we derive upper and lower bounds for the optimal burn‐in time, which maximizes the system availability. Furthermore, adopting an age replacement policy, we derive upper and lower bounds for the optimal age parameter of the replacement policy for each fixed burn‐in time and a uniform upper bound for the optimal burn‐in time given the age replacement policy. These results can be used to reduce the numerical work for determining both optimal burn‐in time and optimal replacement policy. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Optimizing usage and maintenance decisions for k‐out‐of‐n systems of moving assets

We consider an integrated usage and maintenance optimization problem for a k‐out‐of‐n system pertaining to a moving asset. The k‐out‐of‐n systems are commonly utilized in practice to increase availability, where n denotes the total number of parallel and identical units and k the number of units required to be active for a functional system. Moving assets such as aircraft, ships, and submarines are subject to different operating modes. Operating modes can dictate not only the number of system units that are needed to be active, but also where the moving asset physically is, and under which environmental conditions it operates. We use the intrinsic age concept to model the degradation process. The intrinsic age is analogous to an intrinsic clock which ticks on a different pace in different operating modes. In our problem setting, the number of active units, degradation rates of active and standby units, maintenance costs, and type of economic dependencies are functions of operating modes. In each operating mode, the decision maker should decide on the set of units to activate (usage decision) and the set of units to maintain (maintenance decision). Since the degradation rate differs for active and standby units, the units to be maintained depend on the units that have been activated, and vice versa. In order to minimize maintenance costs, usage and maintenance decisions should be jointly optimized. We formulate this problem as a Markov decision process and provide some structural properties of the optimal policy. Moreover, we assess the performance of usage policies that are commonly implemented for maritime systems. We show that the cost increase resulting from these policies is up to 27% for realistic settings. Our numerical experiments demonstrate the cases in which joint usage and maintenance optimization is more valuable. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 418–434, 2017     

Exact algorithms and bounds for the dynamic assignment interdiction problem

We study a multi‐stage dynamic assignment interdiction (DAI) game in which two agents, a user and an attacker, compete in the underlying bipartite assignment graph. The user wishes to assign a set of tasks at the minimum cost, and the attacker seeks to interdict a subset of arcs to maximize the user's objective. The user assigns exactly one task per stage, and the assignment costs and interdiction impacts vary across stages. Before any stage commences in the game, the attacker can interdict arcs subject to a cardinality constraint. An interdicted arc can still be used by the user, but at an increased assignment cost. The goal is to find an optimal sequence of assignments, coupled with the attacker's optimal interdiction strategy. We prove that this problem is strongly NP‐hard, even when the attacker can interdict only one arc. We propose an exact exponential‐state dynamic‐programming algorithm for this problem as well as lower and upper bounds on the optimal objective function value. Our bounds are based on classical interdiction and robust optimization models, and on variations of the DAI game. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 373–387, 2017     

Generalizing the survival signature to unrepairable homogeneous multi‐state systems

The notion of signature has been widely applied for the reliability evaluation of technical systems that consist of binary components. Multi‐state system modeling is also widely used for representing real life engineering systems whose components can have different performance levels. In this article, the concept of survival signature is generalized to a certain class of unrepairable homogeneous multi‐state systems with multi‐state components. With such a generalization, a representation for the survival function of the time spent by a system in a specific state or above is obtained. The findings of the article are illustrated for multi‐state consecutive‐k‐out‐of‐n system which perform its task at three different performance levels. The generalization of the concept of survival signature to a multi‐state system with multiple types of components is also presented. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 593–599, 2017     

Determining optimal sizes of bounded batches with rejection via quadratic min‐cost flow

In this article, we consider a single machine scheduling problem, in which identical jobs are split into batches of bounded sizes. For each batch, it is allowed to produce less jobs than a given upper bound, that is, some jobs in a batch can be rejected, in which case a penalty is paid for each rejected job. The objective function is the sum of several components, including the sum of the completion times, total delivery cost, and total rejection cost. We reduce this problem to a min‐cost flow problem with a convex quadratic function and adapt Tamir's algorithm for its solution. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 217–224, 2017     

Optimal control policies in service systems with limited information on the downstream stage

Existing models in multistage service systems assume full information on the state of downstream stages. In this paper, we investigate how much the lack of such information impacts jobs' waiting time in a two‐stage system with two types of jobs at the first stage. The goal is to find the optimal control policy for the server at the first stage to switch between type‐1 and type‐2 jobs, while minimizing the long‐run average number of jobs in the system. We identify control policies and corresponding conditions under which having no or partial information, the system can still capture the most benefit of having full information.     

Bounding the optimal burn‐in time for a system with two types of failure

Burn‐in is a widely used method to improve the quality of products or systems after they have been produced. In this paper, we consider the problem of determining bounds to the optimal burn‐in time and optimal replacement policy maximizing the steady state availability of a repairable system. It is assumed that two types of system failures may occur: One is Type I failure (minor failure), which can be removed by a minimal repair, and the other is Type II failure (catastrophic failure), which can be removed only by a complete repair. Assuming that the underlying lifetime distribution of the system has a bathtub‐shaped failure rate function, upper and lower bounds for the optimal burn‐in time are provided. Furthermore, some other applications of optimal burn‐in are also considered. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Preemptive parallel‐machine scheduling with a common server to minimize makespan

We consider parallel‐machine scheduling with a common server and job preemption to minimize the makespan. While the non‐preemptive version of the problem is strongly NP‐hard, the complexity status of the preemptive version has remained open. We show that the preemptive version is NP‐hard even if there is a fixed number of machines. We give a pseudo‐polynomial time algorithm to solve the case with two machines. We show that the case with an arbitrary number of machines is unary NP‐hard, analyze the performance ratios of some natural heuristic algorithms, and present several solvable special cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 388–398, 2017     

A robust sensor covering and communication problem

We consider the problem of placing sensors across some area of interest. The sensors must be placed so that they cover a fixed set of targets in the region, and should be deployed in a manner that allows sensors to communicate with one another. In particular, there exists a measure of communication effectiveness for each sensor pair, which is determined by a concave function of distance between the sensors. Complicating the sensor location problem are uncertainties related to sensor placement, for example, as caused by drifting due to air or water currents to which the sensors may be subjected. Our problem thus seeks to maximize a metric regarding intrasensor communication effectiveness, subject to the condition that all targets must be covered by some sensor, where sensor drift occurs according to a robust (worst‐case) mechanism. We formulate an approximation approach and develop a cutting‐plane algorithm to solve this problem, comparing the effectiveness of two different classes of inequalities. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 582–594, 2015     

基于状态的检查与修理综合决策模型

分析了单部件系统退化过程的特点,建立了基于状态的检查与修理决策模型。该模型根据系统的当前状态来决定检查与修理,通过分析计算系统在一个更新周期内平均检查次数、预防性维修及修复性故障的概率,建立维修费用与检查问隔及预防性维修阈值的关系,以平均维修费用最小为目标,优化检查间隔及预防性维修阈值。最后运用Matlab对模型进行数值计算,结果表明,模型能有效地降低维修费用。     

Optimal replacement of continuously degrading systems in partially observed environments

Motivated by wind energy applications, we consider the problem of optimally replacing a stochastically degrading component that resides and operates in a partially observable environment. The component's rate of degradation is modulated by the stochastic environment process, and the component fails when it is accumulated degradation first reaches a fixed threshold. Assuming periodic inspection of the component, the objective is to minimize the long‐run average cost per unit time of performing preventive and reactive replacements for two distinct cases. The first case examines instantaneous replacements and fixed costs, while the second considers time‐consuming replacements and revenue losses accrued during periods of unavailability. Formulated and solved are mixed state space, partially observable Markov decision process models, both of which reveal the optimality of environment‐dependent threshold policies with respect to the component's cumulative degradation level. Additionally, it is shown that for each degradation value, a threshold policy with respect to the environment belief state is optimal if the environment alternates between two states. The threshold policies are illustrated by way of numerical examples using both synthetic and real wind turbine data. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 395–415, 2015