On a class of multiple failure mode systems

The primary objective of this work is to introduce and perform a detailed study of a class of multistate reliability structures in which no ordering in the levels of components' performances is necessary. In particular, the present paper develops the basic theory (exact reliability formulae, reliability bounds, asymptotic results) that will make it feasible to investigate systems whose components are allowed to experience m ≥ 2 kinds of failure (failure modes), and their breakdown is described by different families of cut sets in each mode. For illustration purposes, two classical (binary) systems are extended to analogous multiple failure mode structures, and their reliability performance (bounds and asymptotic behavior) is investigated by numerical experimentation. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 167–185, 2002; DOI 10.1002/nav.10007     

Managing waiting times of backordered demands in single‐stage (Q,r) inventory systems

We present a service constrained (Q, r) model that minimizes expected holding and ordering costs subject to an upper bound on the expected waiting time of demands that are actually backordered. We show that, after optimizing over r, the average cost is quasiconvex in Q for logconcave continuous lead time demand distributions. For logconcave discrete lead time demand distributions we find a single‐pass efficient algorithm based on a novel search stopping criterion. The algorithm also allows for bounds on the variability of the service measure. A brief numerical study indicates how the bounds on service impact the optimal average cost and the optimal (Q, r) choice. The discrete case algorithm can be readily adapted to provide a single pass algorithm for the traditional model that bounds the expected waiting time of all demands (backordered or not). © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 557–573, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10028     

Two‐stage component test plans for testing the reliability of a series system

A system reliability is often evaluated by individual tests of components that constitute the system. These component test plans have advantages over complete system based tests in terms of time and cost. In this paper, we consider the series system with n components, where the lifetime of the i‐th component follows exponential distribution with parameter λ_i. Assuming test costs for the components are different, we develop an efficient algorithm to design a two‐stage component test plan that satisfies the usual probability requirements on the system reliability and in addition minimizes the maximum expected cost. For the case of prior information in the form of upper bounds on λ_i's, we use the genetic algorithm to solve the associated optimization problems which are otherwise difficult to solve using mathematical programming techniques. The two‐stage component test plans are cost effective compared to single‐stage plans developed by Rajgopal and Mazumdar. We demonstrate through several numerical examples that our approach has the potential to reduce the overall testing costs significantly. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 95–116, 2002; DOI 10.1002/nav.1051     

Evaluating methods for the reliability of a large 2‐dimensional rectangular k‐within‐consecutive‐(r,s)‐out‐of‐(m,n):F system

A 2‐dimensional rectangular k‐within‐consecutive‐(r, s)‐out‐of‐(m, n):F system consists of m × n components, and fails if and only if k or more components fail in an r × s submatrix. This system can be treated as a reliability model for TFT liquid crystal displays, wireless communication networks, etc. Although an effective method has been developed for evaluating the exact system reliability of small or medium‐sized systems, that method needs extremely high computing time and memory capacity when applied to larger systems. Therefore, developing upper and lower bounds and accurate approximations for system reliability is useful for large systems. In this paper, first, we propose new upper and lower bounds for the reliability of a 2‐dimensional rectangular k‐within‐consecutive‐(r, s)‐out‐of‐(m, n):F system. Secondly, we propose two limit theorems for that system. With these theorems we can obtain accurate approximations for system reliabilities when the system is large and component reliabilities are close to one. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

A new reformulation approach for the generalized partial covering problem

In this paper, we consider a situation in which a group of facilities must be constructed in order to serve a given set of customers, where the facilities might not be able to guarantee an absolute coverage to the different customers. We examine the problem of maximizing the total service reliability of the system subject to a budgetary constraint. We propose a new reformulation of this problem that facilitates the generation of tight lower and upper bounds. These bounding mechanisms are embedded within the framework of a branch‐and‐bound procedure. Computational results on problem instances ranging in size up to 100 facilities and 200 customers reveal the efficacy of the proposed exact and heuristic approaches. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

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     

Sharp bounds for the reliability of systems and mixtures with ordered components

In this article, we study how to derive bounds for the reliability and the expected lifetime of a coherent system with heterogeneous ordered components. These bounds can be used to compare the performance of the systems obtained by permuting the components at a given system structure, that is, to study where we should place the different components at a system structure to get the most reliable system. Moreover, a similar procedure is applied to get bounds for mixtures and for the generalized proportional hazard rate model when the baseline populations are ordered. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 108–116, 2017     

Bicriteria multiresource generalized assignment problem

In this study, we consider a bicriteria multiresource generalized assignment problem. Our criteria are the total assignment load and maximum assignment load over all agents. We aim to generate all nondominated objective vectors and the corresponding efficient solutions. We propose several lower and upper bounds and use them in our optimization and heuristic algorithms. The computational results have shown the satisfactory behaviors of our approaches. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 621–636, 2014     

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     

Computing bounds on project duration distributions for stochastic PERT networks

We consider the PERT model with activities whose durations are random variables with known discrete independent distributions. We develop an algorithm to compute lower and upper bounds for the distribution function of the project duration of the stochastic PERT network. The algorithm is based on conditioning on the longest distances to nodes in the network. In addition, we develop an extension of the Kleindorfer's upper bound. We evaluate the method developed in this paper with some numerical examples. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 559–580, 2000     

Combination setwise-Bonferroni-type bounds

We consider three classes of lower bounds to P(c) = P (X₁ ≤ c₁,…, X_n ≤ c); Bonferroni-type bounds, product-type bounds and setwise bounds. Setwise probability inequalities are shown to be a compromise between product-type and Bonferroni-type probability inequalities. Bonferroni-type inequalities always hold. Product-type inequalities require positive dependence conditions, but are superior to the Bonferroni-type and setwise bounds when these conditions are satisfied. Setwise inequalities require less stringent positive dependence bound conditions than the product-type bounds. Neither setwise nor Bonferroni-type bounds dominate the other. Optimized setwise bounds are developed. Results pertaining to the nesting of setwise bounds are obtained. Combination setwise-Bonferroni-type bounds are developed in which high dimensional setwise bounds are applied and second and third order Bonferroni-type bounds are applied within each subvector of the setwise bounds. These new combination bounds, which are applicable for associated random variables, are shown to be superior to Bonferroni-type and setwise bounds for moving averages and runs probabilities. Recently proposed upper bounds to P(c) are reviewed. The lower and upper bounds are tabulated for various classes of multivariate normal distributions with banded covariance matrices. The bounds are shown to be surprisingly accurate and are much easier to compute than the inclusion-exclusion bounds. A strategy for employing the bounds is developed. © 1996 John Wiley & Sons, Inc.     

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     

Probabilistic solution and bounds for serial inventory systems with discounted and average costs

We consider the infinite horizon serial inventory system with both average cost and discounted cost criteria. The optimal echelon base‐stock levels are obtained in terms of only probability distributions of leadtime demands. This analysis yields a novel approach for developing bounds and heuristics for optimal inventory control polices. In addition to deriving the known bounds in literature, we develop several new upper bounds for both average cost and discounted cost models. Numerical studies show that the bounds and heuristic are very close to optimal.© 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Lagrangian solution of maximum dispersion problems

We address the so‐called maximum dispersion problems where the objective is to maximize the sum or the minimum of interelement distances amongst a subset chosen from a given set. The problems arise in a variety of contexts including the location of obnoxious facilities, the selection of diverse groups, and the identification of dense subgraphs. They are known to be computationally difficult. In this paper, we propose a Lagrangian approach toward their solution and report the results of an extensive computational experimentation. Our results show that our Lagrangian approach is reasonably fast, that it yields heuristic solutions which provide good lower bounds on the optimum solution values for both the sum and the minimum problems, and further that it produces decent upper bounds in the case of the sum problem. For the sum problem, the results also show that the Lagrangian heuristic compares favorably against several existing heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 97–114, 2000     

Two‐machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs

This article studies two due window scheduling problems to minimize the weighted number of early and tardy jobs in a two‐machine flow shop, where the window size is externally determined. These new scheduling models have many practical applications in real life. However, results on these problems have rarely appeared in the literature because of a lack of structural and optimality properties for solving them. In this article, we derive several dominance properties and theorems, including elimination rules and sequencing rules based on Johnsos order, lower bounds on the penalty, and upper bounds on the window location, which help to significantly trim the search space for the problems. We further show that the problems are NP‐hard in the ordinary sense only. We finally develop efficient pseudopolynomial dynamic programming algorithms for solving the problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Failure profiles of coherent systems

In this paper we first introduce and study the notion of failure profiles which is based on the concepts of paths and cuts in system reliability. The relationship of failure profiles to two notions of component importance is highlighted, and an expression for the density function of the lifetime of a coherent system, with independent and not necessarily identical component lifetimes, is derived. We then demonstrate the way that failure profiles can be used to establish likelihood ratio orderings of lifetimes of two systems. Finally we use failure profiles to obtain bounds, in the likelihood ratio sense, on the lifetimes of coherent systems with independent and not necessarily identical component lifetimes. The bounds are relatively easy to compute and use. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Newsvendor bounds and heuristics for serial supply chains with regular and expedited shipping

We study an infinite‐horizon, N‐stage, serial production/inventory system with two transportation modes between stages: regular shipping and expedited shipping. The optimal inventory policy for this system is a top–down echelon base‐stock policy, which can be computed through minimizing 2N nested convex functions recursively (Lawson and Porteus, Oper Res 48 (2000), 878–893). In this article, we first present some structural properties and comparative statics for the parameters of the optimal inventory policies, we then derive simple, newsvendor‐type lower and upper bounds for the optimal control parameters. These results are used to develop near optimal heuristic solutions for the echelon base‐stock policies. Numerical studies show that the heuristic performs well. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Distribution free bounds for service constrained (Q,r) inventory systems

A classical and important problem in stochastic inventory theory is to determine the order quantity (Q) and the reorder level (r) to minimize inventory holding and backorder costs subject to a service constraint that the fill rate, i.e., the fraction of demand satisfied by inventory in stock, is at least equal to a desired value. This problem is often hard to solve because the fill rate constraint is not convex in (Q, r) unless additional assumptions are made about the distribution of demand during the lead‐time. As a consequence, there are no known algorithms, other than exhaustive search, that are available for solving this problem in its full generality. Our paper derives the first known bounds to the fill‐rate constrained (Q, r) inventory problem. We derive upper and lower bounds for the optimal values of the order quantity and the reorder level for this problem that are independent of the distribution of demand during the lead time and its variance. We show that the classical economic order quantity is a lower bound on the optimal ordering quantity. We present an efficient solution procedure that exploits these bounds and has a guaranteed bound on the error. When the Lagrangian of the fill rate constraint is convex or when the fill rate constraint does not exist, our bounds can be used to enhance the efficiency of existing algorithms. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 635–656, 2000     

Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times

We study a stochastic outpatient appointment scheduling problem (SOASP) in which we need to design a schedule and an adaptive rescheduling (i.e., resequencing or declining) policy for a set of patients. Each patient has a known type and associated probability distributions of random service duration and random arrival time. Finding a provably optimal solution to this problem requires solving a multistage stochastic mixed‐integer program (MSMIP) with a schedule optimization problem solved at each stage, determining the optimal rescheduling policy over the various random service durations and arrival times. In recognition that this MSMIP is intractable, we first consider a two‐stage model (TSM) that relaxes the nonanticipativity constraints of MSMIP and so yields a lower bound. Second, we derive a set of valid inequalities to strengthen and improve the solvability of the TSM formulation. Third, we obtain an upper bound for the MSMIP by solving the TSM under the feasible (and easily implementable) appointment order (AO) policy, which requires that patients are served in the order of their scheduled appointments, independent of their actual arrival times. Fourth, we propose a Monte Carlo approach to evaluate the relative gap between the MSMIP upper and lower bounds. Finally, in a series of numerical experiments, we show that these two bounds are very close in a wide range of SOASP instances, demonstrating the near‐optimality of the AO policy. We also identify parameter settings that result in a large gap in between these two bounds. Accordingly, we propose an alternative policy based on neighbor‐swapping. We demonstrate that this alternative policy leads to a much tighter upper bound and significantly shrinks the gap.