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     

Single‐warehouse multi‐retailer inventory systems with full truckload shipments

We consider a multi‐stage inventory system composed of a single warehouse that receives a single product from a single supplier and replenishes the inventory of n retailers through direct shipments. Fixed costs are incurred for each truck dispatched and all trucks have the same capacity limit. Costs are stationary, or more generally monotone as in Lippman (Management Sci 16, 1969, 118–138). Demands for the n retailers over a planning horizon of T periods are given. The objective is to find the shipment quantities over the planning horizon to satisfy all demands at minimum system‐wide inventory and transportation costs without backlogging. Using the structural properties of optimal solutions, we develop (1) an O(T²) algorithm for the single‐stage dynamic lot sizing problem; (2) an O(T³) algorithm for the case of a single‐warehouse single‐retailer system; and (3) a nested shortest‐path algorithm for the single‐warehouse multi‐retailer problem that runs in polynomial time for a given number of retailers. To overcome the computational burden when the number of retailers is large, we propose aggregated and disaggregated Lagrangian decomposition methods that make use of the structural properties and the efficient single‐stage algorithm. Computational experiments show the effectiveness of these algorithms and the gains associated with coordinated versus decentralized systems. Finally, we show that the decentralized solution is asymptotically optimal. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

A multi‐objective model for bank ATM networks

In this paper we present an application of the core solution concepts for multi‐objective games to a bank ATM network model. In these games, the worth of a coalition is given by a subset of vectors of the k‐dimensional space rather than by a scalar. The paper investigates how an ATM network model based on multi‐objective cooperative game theory could be used as an alternative way of setting interchange fees paid by the customer's bank to the one that owns the ATM. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Duality in constrained multi‐facility location models

We consider the ??_p‐norm multi‐facility minisum location problem with linear and distance constraints, and develop the Lagrangian dual formulation for this problem. The model that we consider represents the most general location model in which the dual formulation is not found in the literature. We find that, because of its linear objective function and less number of variables, the Lagrangian dual is more useful. Additionally, the dual formulation eliminates the differentiability problem in the primal formulation. We also provide the Lagrangian dual formulation of the multi‐facility minisum location problem with the ??_pb‐norm. Finally, we provide a numerical example for solving the Lagrangian dual formulation and obtaining the optimum facility locations from the solution of the dual formulation. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 410–421, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10010     

Consecutive k‐within‐m‐out‐of‐n:F system with exchangeable components

As a generalization of k‐out‐of‐n:F and consecutive k‐out‐of‐n:F systems, the consecutive k‐within‐m‐out‐of‐n:F system consists of n linearly ordered components such that the system fails iff there are m consecutive components which include among them at least k failed components. In this article, the reliability properties of consecutive k‐within‐m‐out‐of‐n:F systems with exchangeable components are studied. The bounds and approximations for the survival function are provided. A Monte Carlo estimator of system signature is obtained and used to approximate survival function. The results are illustrated and numerics are provided for an exchangeable multivariate Pareto distribution. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Reliability of a 2‐dimensional k‐within‐consecutive‐r × s‐out‐of‐m × n:F system

A 2‐dimensional rectangular (cylindrical) k‐within‐consecutive‐r × s‐out‐of‐m × n:F system is the rectangular (cylindrical) m × n‐system if the system fails whenever k components in a r × s‐submatrix fail. This paper proposes a recursive algorithm for the reliability of the 2‐dimensional k‐within‐consecutive‐r × s‐out‐m × n:F system, in the rectangular case and the cylindrical case. This algorithm requires min ( O (mk^r(n?s)), O (nk^s(m?r))), and O (mk^rn) computing time in the rectangular case and the cylindrical case, respectively. The proposed algorithm will be demonstrated and some numerical examples will be shown. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 625–637, 2001.     

Signature based analysis of m‐Consecutive‐k‐out‐of‐n: F systems with exchangeable components

In this article, we study reliability properties of m‐consecutive‐k‐out‐of‐n: F systems with exchangeable components. We deduce exact formulae and recurrence relations for the signature of the system. Closed form expressions for the survival function and the lifetime distribution as a mixture of the distribution of order statistics are established as well. These representations facilitate the computation of several reliability characteristics of the system for a given exchangeable joint distribution or survival function. Finally, we provide signature‐based stochastic ordering results for the system's lifetime and investigate the IFR preservation property under the formulation of m‐consecutive‐k‐out‐of‐n: F systems. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Component importance for linear consecutive‐ k ‐Out‐of‐ n and m ‐Consecutive‐ k ‐Out‐of‐ n systems with exchangeable components

Measuring the relative importance of components in a mechanical system is useful for various purposes. In this article, we study Birnbaum and Barlow‐Proschan importance measures for two frequently studied system designs: linear consecutive k ‐out‐of‐ n and m ‐consecutive‐ k ‐out‐of‐ n systems. We obtain explicit expressions for the component importance measures for systems consisting of exchangeable components. We illustrate the results for a system whose components have a Lomax type lifetime distribution. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

New heuristic methods for the capacitated multi‐facility Weber problem

In this paper we consider the capacitated multi‐facility Weber problem with the Euclidean, squared Euclidean, and ?_p‐distances. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the distance between them. We first present a mixed integer linear programming approximation of the problem. We then propose new heuristic solution methods based on this approximation. Computational results on benchmark instances indicate that the new methods are both accurate and efficient. © 2006 Wiley Periodicals, Inc. Naval Research Logistics 2006     

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     

Optimal maintenance policies for serial,multi‐machine systems with non‐instantaneous repairs

We study optimal age‐replacement policies for machines in series with non‐instantaneous repair times by formulating two nonlinear programs: one that minimizes total cost‐rate subject to a steady‐state throughput requirement and another that maximizes steady‐state throughput subject to a cost‐rate budget constraint. Under reasonable assumptions, the single‐machine cost‐optimal and throughput‐optimal solutions are unique and orderable, and the multi‐machine optimal solutions have appealing structure. Furthermore, we establish equivalence between the two formulations and provide an illustrative numerical example. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A branch and bound algorithm for computing optimal replacement policies in consecutive k‐out‐of‐n‐systems

This paper presents a branch and bound algorithm for computing optimal replacement policies in a discrete‐time, infinite‐horizon, dynamic programming model of a binary coherent system with n statistically independent components, and then specializes the algorithm to consecutive k‐out‐of‐n systems. The objective is to minimize the long‐run expected average undiscounted cost per period. (Costs arise when the system fails and when failed components are replaced.) An earlier paper established the optimality of following a critical component policy (CCP), i.e., a policy specified by a critical component set and the rule: Replace a component if and only if it is failed and in the critical component set. Computing an optimal CCP is a optimization problem with n binary variables and a nonlinear objective function. Our branch and bound algorithm for solving this problem has memory storage requirement O(n) for consecutive k‐out‐of‐n systems. Extensive computational experiments on such systems involving over 350,000 test problems with n ranging from 10 to 150 find this algorithm to be effective when n ≤ 40 or k is near n. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 288–302, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10017     

Repairable consecutive‐k‐out‐of‐n: F system with Markov dependence

In this article, a model for a repairable consecutive‐k‐out‐of‐n: F system with Markov dependence is studied. A binary vector is used to represent the system state. The failure rate of a component in the system depends on the state of the preceding component. The failure risk of a system state is then introduced. On the basis of the failure risk, a priority repair rule is adopted. Then the transition density matrix can be determined, and the analysis of the system reliability can be conducted accordingly. One example each of a linear and a circular system is then studied in detail to explain the model and methodology developed in this paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 18–39, 2000     

Using a birth‐and‐death process to estimate the steady‐state distribution of a periodic queue

If the number of customers in a queueing system as a function of time has a proper limiting steady‐state distribution, then that steady‐state distribution can be estimated from system data by fitting a general stationary birth‐and‐death (BD) process model to the data and solving for its steady‐state distribution using the familiar local‐balance steady‐state equation for BD processes, even if the actual process is not a BD process. We show that this indirect way to estimate the steady‐state distribution can be effective for periodic queues, because the fitted birth and death rates often have special structure allowing them to be estimated efficiently by fitting parametric functions with only a few parameters, for example, 2. We focus on the multiserver M_t/GI/s queue with a nonhomogeneous Poisson arrival process having a periodic time‐varying rate function. We establish properties of its steady‐state distribution and fitted BD rates. We also show that the fitted BD rates can be a useful diagnostic tool to see if an M_t/GI/s model is appropriate for a complex queueing system. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 664–685, 2015     

Optimal FCFS allocation rules for periodic‐review assemble‐to‐order systems

In Assemble‐To‐Order (ATO) systems, situations may arise in which customer demand must be backlogged due to a shortage of some components, leaving available stock of other components unused. Such unused component stock is called remnant stock. Remnant stock is a consequence of both component ordering decisions and decisions regarding allocation of components to end‐product demand. In this article, we examine periodic‐review ATO systems under linear holding and backlogging costs with a component installation stock policy and a First‐Come‐First‐Served (FCFS) allocation policy. We show that the FCFS allocation policy decouples the problem of optimal component allocation over time into deterministic period‐by‐period optimal component allocation problems. We denote the optimal allocation of components to end‐product demand as multimatching. We solve the multi‐matching problem by an iterative algorithm. In addition, an approximation scheme for the joint replenishment and allocation optimization problem with both upper and lower bounds is proposed. Numerical experiments for base‐stock component replenishment policies show that under optimal base‐stock policies and optimal allocation, remnant stock holding costs must be taken into account. Finally, joint optimization incorporating optimal FCFS component allocation is valuable because it provides a benchmark against which heuristic methods can be compared. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 158–169, 2015     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

A new outranking‐based approach for assigning alternatives to ordered classes

We consider the problem of assigning alternatives evaluated on several criteria into ordered categories C₁,C₂,…,C_p. This problem is known as the multi‐criteria sorting problem and arises in many situations such as classifying countries into different risk levels based on economical and socio‐political criteria, evaluating credit applications of bank customers. We are interested in sorting methods that are grounded on the construction of outranking relations. Among these, the Electre Tri method requires defining multidimensional profiles that represent the “frontier” separating consecutive categories C_h and C_h+1, and assigns an alternative to categories according to how it compares to each of the profiles. The explicit specification of the profiles of consecutive categories can be difficult for decision makers. We develop a new outranking based sorting method that does not require the explicit definition of profiles. We instead require the decision maker to assign a subset of reference alternatives to the categories. To assign the remaining alternatives, each such alternative is compared to reference alternatives, and assigned to categories accordingly. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Path optimization for the resource‐constrained searcher

We formulate and solve a discrete‐time path‐optimization problem where a single searcher, operating in a discretized three‐dimensional airspace, looks for a moving target in a finite set of cells. The searcher is constrained by maximum limits on the consumption of one or more resources such as time, fuel, and risk along any path. We develop a specialized branch‐and‐bound algorithm for this problem that uses several network reduction procedures as well as a new bounding technique based on Lagrangian relaxation and network expansion. The resulting algorithm outperforms a state‐of‐the‐art algorithm for solving time‐constrained problems and also is the first algorithm to solve multi‐constrained problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

The one‐warehouse multiretailer problem with an order‐up‐to level inventory policy

We consider a two‐level system in which a warehouse manages the inventories of multiple retailers. Each retailer employs an order‐up‐to level inventory policy over T periods and faces an external demand which is dynamic and known. A retailer's inventory should be raised to its maximum limit when replenished. The problem is to jointly decide on replenishment times and quantities of warehouse and retailers so as to minimize the total costs in the system. Unlike the case in the single level lot‐sizing problem, we cannot assume that the initial inventory will be zero without loss of generality. We propose a strong mixed integer program formulation for the problem with zero and nonzero initial inventories at the warehouse. The strong formulation for the zero initial inventory case has only T binary variables and represents the convex hull of the feasible region of the problem when there is only one retailer. Computational results with a state‐of‐the art solver reveal that our formulations are very effective in solving large‐size instances to optimality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

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