Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

Dominating sets for rectilinear center location problems with polyhedral barriers

In planar location problems with barriers one considers regions which are forbidden for the siting of new facilities as well as for trespassing. These problems are important since they model various actual applications. The resulting mathematical models have a nonconvex objective function and are therefore difficult to tackle using standard methods of location theory even in the case of simple barrier shapes and distance functions. For the case of center objectives with barrier distances obtained from the rectilinear or Manhattan metric, it is shown that the problem can be solved in polynomial time by identifying a dominating set. The resulting genuinely polynomial algorithm can be combined with bound computations which are derived from solving closely connected restricted location and network location problems. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 647–665, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10038     

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     

Dynamic learning,pricing, and ordering by a censored newsvendor

We address the problem of determining optimal ordering and pricing policies in a finite‐horizon newsvendor model with unobservable lost sales. The demand distribution is price‐dependent and involves unknown parameters. We consider both the cases of perishable and nonperishable inventory. A very general class of demand functions is studied in this paper. We derive the optimal ordering and pricing policies as unique functions of the stocking factor (which is a linear transformation of the safety factor). An important expression is obtained for the marginal expected value of information. As a consequence, we show when lost sales are unobservable, with perishable inventory the optimal stocking factor is always at least as large as the one given by the single‐period model; however, if inventory is nonperishable, this result holds only under a strong condition. This expression also helps to explain why the optimal stocking factor of a period may not increase with the length of the problem. We compare this behavior with that of a full information model. We further examine the implications of the results to the special cases when demand uncertainty is described by additive and multiplicative models. For the additive case, we show that if demand is censored, the optimal policy is to order more as well as charge higher retail prices when compared to the policies in the single‐period model and the full information model. We also compare the optimal and myopic policies for the additive and multiplicative models. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A note on “resource flexibility with responsive pricing”

We revisit the capacity investment decision problem studied in the article “Resource Flexibility with Responsive Pricing” by Chod and Rudi [Operations Research 53, (2005) 532–548]. A monopolist firm producing two dependent (substitutable or complementary) products needs to determine the capacity of one flexible resource under demand risk so as to maximize its expected profit. Product demands are linear functions of the prices of both products, and the market potentials are random and correlated. We perform a comparative statics analysis on how demand variability and correlation impact the optimal capacity and the resulting expected profit. In particular, C&R study this problem under the following assumptions/approximations: (i) demand intercepts follow a bivariate Normal distribution; (ii) demand uncertainty is of an additive form; (iii) and under approximate expressions for the optimal capacity and optimal expected profit. We revisit Propositions 2, 3, 4, 5, and 10 of C&R without these assumptions and approximations, and show that these results continue to hold (i) for the exact expressions for the optimal expected profit and optimal capacity, and (ii) under any arbitrary continuous distribution of demand intercepts. However, we also show that the additive demand uncertainty is a critical assumption for the C&R results to hold. In particular, we provide a case of multiplicative uncertainty under which the C&R results (Propositions 2 and 3) fail. © 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     

Incorporation dynamic aspects and uncertainty in 1‐median location problems

In this paper we present several 1‐median formulations on a tree network which incorporate dynamic evolution and/or uncertainty of node demands and transportation costs over a planning horizon. Dynamic evolution is modeled using linear demand functions for the nodes and linear length functions for the edges. Uncertainty is modeled with the use of multiple scenarios, where a scenario is a complete specification of the uncertain node demands and/or edge lengths. We formulate our objective using minimax regret like criteria. We use two different criteria, namely, robust deviation and relative robustness. We discuss what motivated the introduction of these objectives, as well as their relation to existing literature and decision making practices. For all of the models presented, we provide low‐order polynomial time algorithms. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 147–168, 1999     

基于区间数的第4代战斗机空战效能评估

根据第4代战斗机所具有的典型特征,建立了第4代战斗机的空战效能评估指标体系。采用区间数特征向量法确定了效能评估指标体系中的各指标的权重,给出了定量指标和定性指标的规范化方法,提出了采用区间数形式的加权和关系进行效能指标聚合的方法。最后,通过实例验证了所建立的空战效能评估指标体系的合理,评估方法的有效、可行。     

The collection depots location problem on networks

In this paper we investigate the collection depots location problem on a network. A facility needs to be located to serve a set of customers. Each service consists of a trip to the customer, collecting materials, dropping the materials at one of the available collection depots and returning to the facility to wait for the next call. Two objectives are considered: minimizing the weighted sum of distances and minimizing the maximum distance. The properties of the solutions to these problems are described. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 15–24, 2002; DOI 10.1002/nav.10000     

Detection of a Markovian target with optimization of the search efforts under generalized linear constraints

This paper deals with search for a target following a Markovian movement or a conditionally deterministic motion. The problem is to allocate the search efforts, when search resources renew with generalized linear constraints. The model obtained is extended to resource mixing management. New optimality equations of de Guenin's style are obtained. Practically, the problem is solved by using an algorithm derived from the FAB method. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 117–142, 2002; DOI 10.1002/nav.10009     

Markovian models of three‐on‐one combat involving a hidden defender

In this paper, Markovian models of three‐on‐one stochastic firefights between ground‐based weapon systems are developed. These models address a common scenario of interest to the military, but one which has been much neglected in analytic combat models, that of combat between a hidden defender and an exposed attacking force. Each combatant must detect an opponent before commencing their firing cycle, a task which is considerably more difficult for the attacker. In the models developed here, the defender detects the exposed attacking group after an exponentially distributed time interval, while each attacker has a fixed probability of detecting the defender via the flash signature produced after each shot fired by him. The utility of the approach is demonstrated by investigating what impact the introduction of a coordinated gun‐laying system for the attacking force might have, a system made possible by battlefield digitization. The method used here allows models to be developed incrementally. This and other advantages of the Markovian approach are discussed. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 627–646, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10041     

Designing a screening experiment for highly reliable products

Within a reasonable life‐testing time, how to improve the reliability of highly reliable products is one of the great challenges to today's manufacturers. By using a resolution III experiment together with degradation test, Tseng, Hamada, and Chiao (1995) presented an interesting case study of improving the reliability of fluorescent lamps. However, in conducting such an experiment, they did not address the problem of how to choose the optimal settings of variables, such as sample size, inspection frequency, and termination time for each run, which are influential to the correct identification of significant factors and the experimental cost. Assuming that the product's degradation paths satisfy Wiener processes, this paper proposes a systematic approach to the aforementioned problem. First, an intuitively appealing identification rule is proposed. Next, under the constraints of a minimum probability of correct decision and a maximum probability of incorrect decision of the proposed identification rule, the optimum test plan (including the determinations of inspection frequency, sample size, and termination time for each run) can be obtained by minimizing the total experimental cost. An example is provided to illustrate the proposed method. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 514–526, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10024     

Modeling and analysis of multiobjective lot splitting for N‐product M‐machine flowshop lines

Lot splitting is a new approach for improving productivity by dividing production lots into sublots. This approach enables accelerating production flow, reducing lead‐time and increasing the utilization of organization resources. Most of the lot splitting models in the literature have addressed a single objective problem, usually the makespan or flowtime objectives. Simultaneous minimization of these two objectives has rarely been addressed in the literature despite of its high relevancy to most industrial environments. This work aims at solving a multiobjective lot splitting problem for multiple products in a flowshop environment. Tight mixed‐integer linear programming (MILP) formulations for minimizing the makespan and flowtime are presented. Then, the MinMax solution, which takes both objectives into consideration, is defined and suggested as an alternative objective. By solving the MILP model, it was found that minimizing one objective results in an average loss of about 15% in the other objective. The MinMax solution, on the other hand, results in an average loss of 4.6% from the furthest objective and 2.5% from the closest objective. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Multiple-attribute decision making with partial information: The comparative hypervolume criterion

A new approach is presented for analyzing multiple-attribute decision problems in which the set of actions is finite and the utility function is additive. The problem can be resolved if the decision makers (or group of decision makers) specifies a set of nonnegative weights for the various attributes or criteria, but we here assume that the decision maker(s) cannot provide a numerical value for each such weight. Ordinal information about these weights is therefore obtained from the decision maker(s), and this information is translated into a set of linear constraints which restrict the values of the weights. These constraints are then used to construct a polytope W of feasible weight vectors, and the subsets H_i (polytopes) of W over which each action a_i has the greatest utility are determined. With the Comparative Hypervolume Criterion we calculate for each action the ratio of the hypervolume of H_i to the hypervolume of W and suggest the choice of an action with the largest such ratio. Justification of this choice criterion is given, and a computational method for accurately approximating the hypervolume ratios is described. A simple example is provided to evaluate the efficiency of a computer code developed to implement the method.     

Optimal service rates of a service facility with perishable inventory items

In this paper we optimally control service rates for an inventory system of service facilities with perishable products. We consider a finite capacity system where arrivals are Poisson‐distributed, lifetime of items have exponential distribution, and replenishment is instantaneous. We determine the service rates to be employed at each instant of time so that the long‐run expected cost rate is minimized for fixed maximum inventory level and capacity. The problem is modelled as a semi‐Markov decision problem. We establish the existence of a stationary optimal policy and we solve it by employing linear programming. Several numerical examples which provide insight to the behavior of the system are presented. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 464–482, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10021     

Determination of suppliers' optimal quantity discount schedules with heterogeneous buyers

Although the quantity discount problem has been extensively studied in the realm of a single supplier and a single buyer, it is not well understood when a supplier has many different buyers. This paper presents an analysis of a supplier's quantity discount decision when there are many buyers with different demand and cost structures. A common discrete all‐unit quantity discount schedule with many break points is used. After formulating the model, we first analyze buyers' responses to a general discrete quantity discount schedule. This analysis establishes a framework for a supplier to formulate his quantity discount decision. Under this framework, the supplier's optimal quantity discount schedule can be formulated and solved by a simple non‐linear programming model. The applicability of the model is discussed with an application for a large U.S. distribution network. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 46–59, 2002; DOI 10.1002/nav.1052     

Multiple-attribute decision making with partial information: The expected-value criterion

We consider the multiple-attribute decision problem with finite action set and additive utility function. We suppose that the decision maker cannot specify nonnegative weights for the various attributes which would resolve the problem, but that he/she supplies ordinal information about these weights which can be translated into a set of linear constraints restricting their values. A bounded polytope W of feasible weight vectors is thus determined. Supposing that each element of W has the same chance of being the “appropriate one,” we compute the expected utility value of each action. The computation method uses a combination of numerical integration and Monte Carlo simulation and is equivalent to finding the center of mass of the bounded polytope W . Comparisons are made with another criterion already presented, the comparative hyper-volume criterion, and two small examples are presented.     

适用于认知无线传感器网络的高效频谱分配方法

广泛工作在ISM(Industrial,Scientific and Medical)频段的无线传感器网络面临严重的频谱稀缺问题。在无线通信中,动态频谱分配被认为是提高频谱效能的重要途径。针对典型集中式管理的认知无线传感器网络设计了基于图着色结合负载强度的高效频谱分配算法。首先在协议干扰模型下确保频谱资源在空间上充分利用,随后综合考虑节点负载强度与公平性建立优化模型并按照乘子法加拟牛顿法框架求解最优值。仿真实验表明算法与固定频谱分配方式和传统自适应频谱分配算法相比,在系统吞吐量和节点缓冲区队列长度两个关键性能指标上具有显著优势。     

An interactive procedure for selecting acceptable alternatives in the presence of multiple criteria

In this paper, we consider the multiple criteria decision‐making problem of partitioning alternatives into acceptable and unacceptable sets. We develop interactive procedures for the cases when the underlying utility function of the decision maker is linear, quasiconcave, and general monotone. We present an application of the procedures to the problem of admitting students to the master's degree program at the Industrial Engineering Department, Middle East Technical University. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 592–606, 2001.     

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