Adjacency‐based local top‐down search method for finding maximal efficient faces in multiple objective linear programming

It is well‐known that the efficient set of a multiobjective linear programming (MOLP) problem can be represented as a union of the maximal efficient faces of the feasible region. In this paper, we propose a method for finding all maximal efficient faces for an MOLP. The new method is based on a condition that all efficient vertices (short for the efficient extreme points and rays) for the MOLP have been found and it relies on the adjacency, affine independence and convexity results of efficient sets. The method uses a local top‐down search strategy to determine maximal efficient faces incident to every efficient vertex for finding maximal efficient faces of an MOLP problem. To our knowledge, the proposed method is the first top‐down search method that uses the adjacency property of the efficient set to find all maximal efficient faces. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several MOLP problems with the code.     

The effects of model parameter deviations on the variance of a linearly filtered time series

We consider a general linear filtering operation on an autoregressive moving average (ARMA) time series. The variance of the filter output, which is an important quantity in many applications, is not known with certainty because it depends on the true ARMA parameters. We derive an expression for the sensitivity (i.e., the partial derivative) of the output variance with respect to deviations in the model parameters. The results provide insight into the robustness of many common statistical methods that are based on linear filtering and also yield approximate confidence intervals for the output variance. We discuss applications to time series forecasting, statistical process control, and automatic feedback control of industrial processes. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Robustness of efficient server assignment policies to service time distributions in finite‐buffered lines

We study the assignment of flexible servers to stations in tandem lines with service times that are not necessarily exponentially distributed. Our goal is to achieve optimal or near‐optimal throughput. For systems with infinite buffers, it is already known that the effective assignment of flexible servers is robust to the service time distributions. We provide analytical results for small systems and numerical results for larger systems that support the same conclusion for tandem lines with finite buffers. In the process, we propose server assignment heuristics that perform well for systems with different service time distributions. Our research suggests that policies known to be optimal or near‐optimal for Markovian systems are also likely to be effective when used to assign servers to tasks in non‐Markovian systems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Analytic solution for the nucleolus of a three‐player cooperative game

The nucleolus solution for cooperative games in characteristic function form is usually computed numerically by solving a sequence of linear programing (LP) problems, or by solving a single, but very large‐scale, LP problem. This article proposes an algebraic method to compute the nucleolus solution analytically (i.e., in closed‐form) for a three‐player cooperative game in characteristic function form. We first consider cooperative games with empty core and derive a formula to compute the nucleolus solution. Next, we examine cooperative games with nonempty core and calculate the nucleolus solution analytically for five possible cases arising from the relationship among the value functions of different coalitions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Supply chain coordination with shelf‐space and retail price dependent demand and heterogeneous retailers

We consider supply chain coordination in which a manufacturer supplies some product to multiple heterogeneous retailers and wishes to coordinate the supply chain via wholesale price and holding cost subsidy. The retail price is either exogenous or endogenous. The market demand is described by the market share attraction model based on all retailers'shelf‐spaces and retail prices. We obtain optimal solutions for the centralized supply chain, where the optimal retail pricing is a modified version of the well‐known cost plus pricing strategy. We further get feasible contracts for the manufacturer to coordinate the hybrid and decentralized supply chains. The manufacturer can allocate the total profit free to himself and the retail market via the wholesale price when the retail price is exogenous, but otherwise he cannot. Finally, we point out that different characteristics of the retail market are due to different powers of the manufacturer, and the more power the manufacturer has, the simpler the contract to coordinate the chain will be. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Information security: Designing a stochastic‐network for throughput and reliability

Todas information and communication network requires a design that is secure to tampering. Traditional performance measures of reliability and throughput must be supplemented with measures of security. Recognition of an adversary who can inflict damage leads toward a game‐theoretic model. Through such a formulation, guidelines for network designs and improvements are derived. We opt for a design that is most robust to withstand both natural degradation and adversarial attacks. Extensive computational experience with such a model suggests that a Nash‐equilibrium design exists that can withstand the worst possible damage. Most important, the equilibrium is value‐free in that it is stable irrespective of the unit costs associated with reliability vs. capacity improvement and how one wishes to trade between throughput and reliability. This finding helps to pinpoint the most critical components in network design. From a policy standpoint, the model also allows the monetary value of information‐security to be imputed. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Approximating the nondominated frontiers of multi‐objective combinatorial optimization problems

Finding all nondominated vectors for multi‐objective combinatorial optimization (MOCO) problems is computationally very hard in general. We approximate the nondominated frontiers of MOCO problems by fitting smooth hypersurfaces. For a given problem, we fit the hypersurface using a single nondominated reference vector. We experiment with different types of MOCO problems and demonstrate that in all cases the fitted hypersurfaces approximate all nondominated vectors well. We discuss that such an approximation is useful to find the neighborhood of preferred regions of the nondominated vectors with very little computational effort. Further computational effort can then be spent in the identified region to find the actual nondominated vectors the decision maker will prefer. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Energy‐efficient scheduling for sustainable manufacturing systems with renewable energy resources

Environmentally friendly energy resources open a new opportunity to tackle the problem of energy security and climate change arising from wide use of fossil fuels. This paper focuses on optimizing the allocation of the energy generated by the renewable energy system to minimize the total electricity cost for sustainable manufacturing systems under time‐of‐use tariff by clipping the peak demand. A rolling horizon approach is adopted to handle the uncertainty caused by the weather change. A nonlinear mathematical programming model is established for each decision epoch based on the predicted energy generation and the probability distribution of power demand in the manufacturing plant. The objective function of the model is shown to be convex, Lipchitz‐continuous, and subdifferentiable. A generalized benders decomposition method based on the primal‐dual subgradient descent algorithm is proposed to solve the model. A series of numerical experiments is conducted to show the effectiveness of the solution approach and the significant benefits of using the renewable energy resources.     

Optimal allocation of minimal repairs in parallel and series systems

In reliability engineering, the concept of minimal repair describes that the repair brings the failed unit (eg, system or component) to the situation which is same as it was just before the failure. With the help of the well‐known Gamma‐Poisson relationship, this paper investigates optimal allocation strategies of minimal repairs for parallel and series systems through implementing stochastic comparisons of various allocation policies in terms of the hazard rate, the reversed hazard rate, and the likelihood ratio orderings. Numerical examples are presented to illustrate these findings as well. These results not only strengthen and generalize some known ones in the seminal work of Shaked and Shanthikumar, but also solve the open problems proposed by Chahkandi et al.'s study and Arriaza et al.'s study.