Search

This paper generalizes, by the use of compound distributions, a result of HAIGHT (1966) on counts that are delayed but not lost. An application of Markov chains indicates a simple method of numerical evaluation of the distributions involved. Finally a continuous time analogue is studied. [ABSTRACT FROM AUTHOR]

This paper provides the solution to the problem of the distribution of busy periods of the single-channel queue characterized by a time-dependent Poisson-distributed arrival rate and a general class of holding times. The notation is chosen in such a fashion that the main body of computations and mathematical analysis is identical with what was required in the solution of the general queuing equations considered in a previous paper which should be read first [4]. The solution of the problem for winch the traffic intensity is constant and the holding time distribution is Pearson type III is derived in closed form in terms of the Ink functions introduced previously. [ABSTRACT FROM AUTHOR]

In Weighted Scoring Rules and Convex Risk Measures, Dr. Zachary J. Smith and Prof. J. Eric Bickel (both at the University of Texas at Austin) present a general connection between weighted proper scoring rules and investment decisions involving the minimization of a convex risk measure. Weighted scoring rules are quantitative tools for evaluating the accuracy of probabilistic forecasts relative to a baseline distribution. In their paper, the authors demonstrate that the relationship between convex risk measures and weighted scoring rules relates closely with previous economic characterizations of weighted scores based on expected utility maximization. As illustrative examples, the authors study two families of weighted scoring rules based on phi-divergences (generalizations of the Weighted Power and Weighted Pseudospherical Scoring rules) along with their corresponding risk measures. The paper will be of particular interest to the decision analysis and mathematical finance communities as well as those interested in the elicitation and evaluation of subjective probabilistic forecasts. This paper establishes a new relationship between proper scoring rules and convex risk measures. Specifically, we demonstrate that the entropy function associated with any weighted scoring rule is equal to the maximum value of an optimization problem where an investor maximizes a concave certainty equivalent (the negation of a convex risk measure). Using this connection, we construct two classes of proper weighted scoring rules with associated entropy functions based on ϕ-divergences. These rules are generalizations of the weighted power and weighted pseudospherical rules. [ABSTRACT FROM AUTHOR]

In a previous paper the ground work was laid for a new theoretical model of combat called the 'stochastic duel.' The principal elements of the model were fixed kill probabilities on each round fired, a random time between rounds fired, and unlimited ammunition supply. This paper extends the solution to those more realistic cases of limited ammunition supply. The general solution (as a quadrature) is obtained and it is applied to several specific examples. The special case of finite, fixed ammunition supply is treated separately. [ABSTRACT FROM AUTHOR]

Intensive care unit (ICU) beds are valuable resources that are typically in short supply and therefore their effective and efficient use is essential particularly during periods when patient demand is high. In "Allocation of Intensive Care Unit Beds in Periods of High Demand," H. Ouyang, N.T. Argon, and S. Ziya provide insights into what kind of patient prioritization decisions are likely to improve patient health outcomes by analyzing stylized mathematical formulations that capture the fundamental trade-off involved in ICU bed management. They also propose simple policies that are likely to perform well in practice and test them with a simulation study. Findings suggest that even simple policies are likely to bring significant benefits, although more work is needed to investigate whether there could be benefits to using methods that aim to capture patient health condition in a manner that is more precise than assumed in the paper. The objective of this paper is to use mathematical modeling and analysis to develop insights into and policies for making bed allocation decisions in an intensive care unit (ICU) of a hospital during periods when patient demand is high. We first develop a stylized mathematical model in which patients' health conditions change over time according to a Markov chain. In this model, each patient is in one of two possible health stages, one representing the critical and the other representing the highly critical health stage. The ICU has limited bed availability and therefore when a patient arrives and no beds are available, a decision needs to be made as to whether the patient should be admitted to the ICU and if so, which patient in the ICU should be transferred to the general ward. With the objective of minimizing the long-run average mortality rate, we provide analytical characterizations of the optimal policy under certain conditions. Then, based on these analytical results, we propose heuristic methods, which can be used under assumptions that are more general than what is assumed for the mathematical model. Finally, we demonstrate that the proposed heuristic methods work well by a simulation study, which relaxes some of the restrictive assumptions of the mathematical model by considering a more complex transition structure for patient health and allowing for patients to be possibly queued for admission to the ICU and readmitted from the general ward after they are discharged. [ABSTRACT FROM AUTHOR]

This paper discusses the application of the likelihood ratio gradient estimator to simulations of large Markovian models of highly dependable systems. Extensive empirical work, as well as some mathematical analysis of small dependability models, suggests that (in this model setting) the gradient estimators are not significantly more noisy than the estimates of the performance measures themselves. The paper also discusses implementation issues associated with likelihood ratio gradient estimation, as well as some theoretical complements associated with application of the technique to continuous-time Markov chains. [ABSTRACT FROM AUTHOR]

This paper presents an approach, similar to penalty functions, for solving arbitrary mathematical programs. The surrogate mathematical program is a lesser constrained problem that, in some cases, may be solved with dynamic programming. The paper deals with the theoretical development of this surrogate approach. [ABSTRACT FROM AUTHOR]

This paper introduces a generalization of the frequently discussed problem of finding the optimum redundancy that maximizes the reliability of a network of components. Past work has restricted consideration to arrangements of redundant components called series-parallel networks. This paper allows a much broader class of arrangements called series-parallelseries networks. It is important to consider such arrangements for realistic situations in which components have more than one failure mode, or the combination of parallel paths introduces a failure probability. A dynamic programming algorithm is used to solve the more general problem for the case in which there are no constraints on the optimum solution. The algorithm is extended to handle multiple constraints using dominance and a variety of elimination methods to reduce the storage required in a compurer implementation of the algorithm. Problems with as many as 15 serial components and three constraints have been solved with reasonable digital computer computation times. [ABSTRACT FROM AUTHOR]

This paper gives general conditions for the convergence of a class of cutting-plane algorithms without requiring that the constraint sets for the subproblems be sequentially nested. Conditions are given under which inactive constraints may be dropped after each subproblem. Procedures for generating cutting-planes include those of KELLEY, CHENEY AND GOLDSTEIN, and a generalization of the one used by both ZOUTENDIJK and VEXNoTT. For algorithms with nested constraint sets, these conditions reduce to a special case of those of ZANGWILL for such problems and include as special cases the algorithms of Kelley, Cheney and Goldstein, and Veinott. Finally, the paper gives an arithmetic convergence rate. [ABSTRACT FROM AUTHOR]

In 1964, Kleinrock proposed a queueing discipline for a single-server queue in which customers from different classes accumulate priority as linear functions of their waiting time. At the instant that a server becomes free, it selects the waiting customer with the highest accumulated priority, provided that the queue is nonempty. He developed a recursion for calculating the expected waiting time for each class. In 2014, Stanford, Taylor, and Ziedins reconsidered this queue, which they termed the accumulating priority queue (APQ), and derived the waiting time distribution for each class. Kleinrock and Finkelstein in 1967 also studied an accumulating priority system in which customers' priorities increase as a power-law function of their waiting time. They established that it is possible to associate a particular linear APQ with such a power-law APQ, so that the expected waiting times of customers from all classes are preserved. In this paper, we extend their analysis to characterise the class of nonlinear APQs for which an equivalent linear APQ can be found, in the sense that, for identical sample paths of the arrival and service processes, the ordering of all customers is identical at all times in both the linear and nonlinear systems. [ABSTRACT FROM AUTHOR]

This paper considers the two-dimensional strip-packing problem (2SP) in which a set of rectangular items have to be orthogonally packed, without overlapping, into a strip of a given width and infinite height by minimizing the overall height of the packing. The 2SP is NP-hard in the strong sense and finds many practical applications. We propose reduction procedures, lower and upper bounds, and an exact algorithm for the 2SP. The new lower bounds are both combinatorial bounds and bounds derived from different relaxations of mathematical formulations of the 2SP. The new upper bounds are obtained by constructive heuristics based on different strategies to place the items into the strip. The new exact method is based on a branch-and-bound approach. Computational results on different sets of test problems derived from the literature show the effectiveness of the new lower and upper bounds and of the new exact algorithm. [ABSTRACT FROM AUTHOR]

This paper describes a computer program that accepts as input a symbolic mathematical statement of an arbitrary mathematical programming problem, placing the problem into none or at least one of the categories: linear, quadratic, separable, posynomial, signomial, or convex. This categorization program is intended to reveal properties that can be exploited by special-purpose numerical computer programs--properties that might easily be overlooked because of the size of the problem, the complexity of the problem, or the limited knowledge of a novice who wishes to solve an optimization problem. The paper includes a brief demonstration of the program, a discussion of the underlying techniques, and a summary of the performance for some large problems. [ABSTRACT FROM AUTHOR]

This paper is concerned with the problem of locating n new facilities in the plane when there are m facilities already located. The objective is to minimize the weighted sum of rectilinear distances. Necessary and sufficient conditions for optimality are established. We show that the optimum locations of the new facilities are dependent on the relative orderings of old facilities along the two coordinate axes but not on the distances between them. Based on these results an algorithm is presented that requires the solution of at most m-1 minimum cut problems on networks with at most n+2 vertices. All of these results are easily extended to the same location problem on a tree graph. [ABSTRACT FROM AUTHOR]

This paper presents a unified method for obtaining duality results for concave-convex fractional programs. We obtain these results by transforming the original nonconvex programming problem into an equivalent convex program. Known results by several authors are related to each other. Moreover, we prove additional duality theorems, in particular, converse duality theorems for nondifferentiable as well as quadratic fractional programs. [ABSTRACT FROM AUTHOR]

This paper presents a simpler proof for a result of Magazine, Nemhauser, and Trotter, which states recursive necessary and sufficient conditions for the optimality of a heuristic solution for a class of knapsack problems. [ABSTRACT FROM AUTHOR]

This paper describes a finite procedure for locating a global minimum of a problem with linear objective constraints except for one nonlinear constraint, which is of the 'reverse convex' variety; that is, the direction of the inequality is the opposite of that required for a convex constraint. Budget constraints in which the cost functions are subject to economies of scale are typically of this form. An illustrative example of the procedure is provided. [ABSTRACT FROM AUTHOR]

The sequential decision problem considered in this paper consists of finding an optimal policy for increasing the capacity of a multiterminal network with requirements increasing over a planning period and arcs subject to failure. This problem is formulated as a shortest-route problem in a very large network and solved by Dijkstra's algorithm. Computational experience is also presented. [ABSTRACT FROM AUTHOR]

In this paper we study sensitive discount optimality criteria for finite state and action, discrete time parameter, stationary generalized Markov decision chains. We extend previous results obtained by Miller and Veinott and Veinott for substochastic transition matrices to arbitrary non-negative matrices with spectral radius not exceeding one. In particular, we generalize their policy improvement algorithm for finding a stationary policy maximizing the expected discounted reward for all sufficiently small positive interest rates. [ABSTRACT FROM AUTHOR]

In order to evaluate alternative policies for over-issuing permits for a limited number of parking spaces, this paper develops a probabilistic model that allows several classes of users to be considered simultaneously. The sensitivity of the model to its underlying assumptions is derived and illustrated with data from a case study. The paper shows how its model can be used to evaluate over-issuance policies such as a common over-issuance of several lots and mixing different classes of users in one lot. It also discusses the factors to be considered in implementing this approach in the context of a total-parking-system model incorporating other means of satisfying user demands on parking spaces. The model is of an inventory type and is applicable to other problems where there are various classes of customers with varying demand characteristics. [ABSTRACT FROM AUTHOR]

This paper presents a pseudo-boolean formulation of location problems based on a concept of a ‘dummy’ supply source activated outside a given distribution. First, it formulates a simple location problem as a pseudo-boolean function that can be optimized with existing boolean optimization algorithms. Later the formulation is extended to multidimensional location problems. Two such problems are analyzed: the first involves a distribution system with plants for production of different commodities; the second involves a distribution system with consumer demand and its pattern varying with time. [ABSTRACT FROM AUTHOR]

This paper develops an algorithm for pure integer programming problems. It first transforms the integer programming problem to an algebraically equivalent Hermite canonical problem, and then employs the Fourier-Motzkin elimination. These algebraic operations transform the problem into a form that leads to an efficient implicit enumeration scheme to calculate an optimal solution. The algorithm constructs, in a finite number of operations, an optimal solution to an integer program with n variables and n or n + 1 inequality constraints. If the original problem has more than n + 1 constraints, then the integer program with only the constraints that are binding at an optimal linear programming solution is solved in place of the original problem. Computational results are presented. [ABSTRACT FROM AUTHOR]

This paper considers a class of optimization problems characterized by constraints that themselves contain optimization problems. The problems in the constraints can be linear programs, nonlinear programs, or two-sided optimization problems, including certain types of games. The paper presents theory dealing primarily with properties of the relevant functions that result in convex programming problems, and discusses interpretations of this theory. It gives an application with linear programs in the constraints, and discusses computational methods for solving the problems. [ABSTRACT FROM AUTHOR]

Kleinrock has studied linearly time-dependent queue disciplines with a set of positive variable parameters. This paper continues his work by deriving a result for a delay-dependent priority system in which a unit's priority is decreased from zero linearly with time in proportion to a negative rate assigned to the unit's group. The two queuing structures provide the system designers the same number of degrees of freedom. [ABSTRACT FROM AUTHOR]

This paper considers optimal design models for queuing systems in which the decision variables are the number of servers and the mean rate at which each serves, the total cost per unit time of operating the system is the sum of a service cost per unit time and a waiting cost per unit time, and the optimality criterion is long-run expected average cost per unit time. It is shown that a single-server system is optimal for a wide class of arrival processes and service-time distributions, and for a wide variety of waiting cost functions. [ABSTRACT FROM AUTHOR]

This paper analyzes priority rules that are mixtures of preemption and postponable rules. Whether a preemption occurs is made to depend on some factor in addition to priority class; dependence on the completed portion of service (age) of the lower-priority customer in service and the number of prior preemptions of the lower-priority customer in service are each considered. The stochastic model (without priorities) is that of the M/G/1 queue. The paper obtains first-moment expressions (e.g., expected number of customers in the system) in the steady-state case for each priority class as a function of the particular factor being considered. It then introduces a linear cost model that is a function of expected waiting time and expected number of preemptions, and formulates the problem of finding an optimal rule from each class by considering a parametric class of rules determined by each factor. In each case, conditions are sought for the global optimality of a rule over a class of rules, but results are obtained only after restrictions (e.g., monotone failure rates) on service distributions are imposed. [ABSTRACT FROM AUTHOR]

A certain class of integer programming problems, called asymptotic or steady-state, has been shown by GOMORY to be cost equivalent to a group-optimization problem. This paper extends the algebraic characterization by demonstrating that there are cost-equivalent group problems for all integer programming problems. Finally, the result is interpreted from the viewpoint of dynamic programming, and this provides the turnpike theorem. [ABSTRACT FROM AUTHOR]

Many problems of the practicing operations analyst do not fit the standard forms of analytic OR procedures and do not lend themselves to precise optimization methods. The voracious appetite of the computer demands numerical algorithms in order to give answers. Very often an optimum is not absolutely essential to management, as long as the answer is efficient or superior to guesswork. So heuristic approaches are adapted to the problem. This paper presents a heuristic approach to a nonstandard, practical assignment problem. It concerns a problem that the analyst had to solve in the field' at Cape Canaveral (now Cape Kennedy) wherein 74 telemetry channels for 19 missiles had to be assigned to 28 available frequency bands. A conflict for a channel occurs if (a) time for use of the range by the missile channels is demanded and (b) another channel on another missile has the same frequency assignment and also wishes the same time. A conflict means one or more missiles must be denied time on the range, which causes costly delay. It is desirable to assign channels to frequencies (which is done at the time the missile is designed) so as to minimize the total expected amount of conflict (or cost of conflict). This paper shows a general, heuristic (not-necessarily optimum) procedure for handling typical, nonstandard assignment problems and gives details of the Cape Kennedy application. This is an example of what can happen 'in the field' when standard mathematical forms are not available. [ABSTRACT FROM AUTHOR]

Duality and symmetry of nonlinear programs are considered. The duality theorem of this paper assures that if the primal problem is solvable at a certain point of its domain of definition then the dual problem is also solvable at the same point and vice versa. [ABSTRACT FROM AUTHOR]

The parts requirements (or `explosion') problem is that of finding the total numbers of components, subassemblies, and assemblies needed to fulfill an order, given the individual requirements needed in each assembly. In this paper two methods are presented for solving the problem, together with the so-called `spare parts' and `netting' problems. The first method involves the use of the inverse of the matrix I-Q where Q is the quantity matrix. The second method is a generalization of the successive multiplication algorithm, first discussed in a special case by ELMALGHRABY. Mathematical proofs of the methods are presented, as is computational experience with small problems. [ABSTRACT FROM AUTHOR]

For a service facility serving more than one class of customers a problem arises as to the order in which customers should be served (i.e., the priority rule). A typical example is a manufacturing facility that produces two products to meet a random stream of incoming orders. In this paper the alternating priority nile (also known as the `zero switch rule') is introduced and investigated. Two classes of customers are served by a single service facility. Customers of class i(i= 1, 2) have priority over customers of class j(j=I, 2; ≠1) whenever a class i customer is in service. When the service facility is idle, the first arriving customer enters service and acquires the priority right for customers of his class. Within classes the `first-come, first-served' rule is observed. Customers' arrivals are assumed to be Poisson and service times are assumed to be arbitrarily distributed in- dependent random variables. The steady-state densities of queuing times are formulated by the use of a special mathematical procedure. The expectations of queuing times and sizes of queues as well as the first two moments of the busy periods are obtained in terms of the basic parameters of the arrival process and service time distributions. All the results are related to the case where switching from one type of customers to another is not penalized by setup time. The alternating priority rule is compared to the 'head-of-the-line' and the 'first-come, first-served' rules with respect to expected queuing times and queue sizes. The last part of the paper discusses the possibilities of extending the suggested rule to cases involving more than two classes of customers and nonzero setup times and setup costs. [ABSTRACT FROM AUTHOR]

This paper extends the work of White and Christie, reported in OPERATION RESEARCH, vol 6, pp 79-95 (January-February, 1958), on preemptive priority queuing. A random walk procedure yields recursive relations between the state probabilities in the steady state. Recursive relations for the moments of the length of the lower priority queue follow. Combined with the use of moment generating functions, this approach provides moments of the waiting time for elements of the lower priority class that arrive when the system is in a given state, i e, the two queues are of given lengths. The moments of waiting time and time in the system are also obtained recursively for the steady state Routines for computing and checking are provided. [ABSTRACT FROM AUTHOR]

The paper considers two-person zero-sum game. Let B be an arbitrary positive real number and let &b.Theta; be a real number between zero and one. First player chooses a number, t1, with t1 ranging between 0 to B+1. Second player chooses a number, t2, with t2 ranging between 0 to B. The pay-off function, &b.Theta, which specifies the amount the first player receives from second player, is given in the article. If &b.Theta; were continuous, it would be known that these two numbers are equal and hence the game would have a well-determined value. However, the pay-off function considered here is not continuous and this standard theorem cannot be applied. It should be clear that the optimal strategies for first player and second player are not unique.

Chance constraints are an important modeling tool in stochastic optimization, providing probabilistic guarantees that a solution "succeeds" in satisfying a given constraint. Although they control the probability of "success," they provide no control whatsoever in the event of a "failure." That is, they do not distinguish between a slight overshoot or undershoot of the bounds and more catastrophic violation. In short, they do not capture the magnitude of violation of the bounds. This paper addresses precisely this topic, focusing on linear constraints and ellipsoidal (Gaussian-like) uncertainties. We show that the problem of requiring different probabilistic guarantees at each level of constraint violation can be reformulated as a semi-infinite optimization problem. We provide conditions that guarantee polynomial-time solvability of the resulting semi-infinite formulation. We show further that this resulting problem is what has been called a comprehensive robust optimization problem in the literature. As a byproduct, we provide tight probabilistic bounds for comprehensive robust optimization. Thus, analogously to the connection between chance constraints and robust optimization, we provide a broader connection between probabilistic envelope constraints and comprehensive robust optimization. [ABSTRACT FROM AUTHOR]

The perspective relaxation (PR) is a general approach for constructing tight approximations to mixed-integer nonlinear programs (MINLP) with semicontinuous variables. The PR of a MINLP can be formulated either as a mixed-integer second-order cone program (MI-SOCP), provided that the original objective function is SOCP-representable, or as a semi-infinite MINLP. In this paper, we show that under some further assumptions (rather restrictive, but satisfied in several practical applications), the PR of a mixed-integer quadratic program (MIQP) can also be reformulated as a piecewise-quadratic program (QP), ultimately yielding a QP relaxation of roughly the same size of the standard continuous relaxation. Furthermore, if the original problem has some exploitable structure, then this structure is typically preserved in the reformulation, thus allowing the construction of specialized approaches for solving the PR. We report on implementing these ideas on two MIQPs with appropriate structure: a sensor placement problem and a quadratic-cost (single-commodity) network design problem. [ABSTRACT FROM AUTHOR]

In this paper, we propose a model of intertemporal choice that explicitly incorporates satiation due to previous consumption in the evaluation of the utility of current consumption. In the discounted utility (DU) model, the utility of consumption is evaluated afresh in each time period. In our model, the utility of current consumption represents an incremental utility from the past level. When the time interval between consumption periods is large, and there are, therefore, no carryover effects, our model coincides with the DU model. For short time intervals between consumption periods, the satiation due to previous consumption lowers the utility of current consumption. Several implications of our model are examined, and comparisons with the DU model and the habituation model are made. [ABSTRACT FROM AUTHOR]

We consider the scheduling problems arising when two agents, each with a set of nonpreemptive jobs, compete to perform their respective jobs on a common processing resource. Each agent wants to minimize a certain objective function, which depends on the completion times of its jobs only. The objective functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs, and total weighted completion times.We obtain different scenarios, depending on the objective function of each agent, and on the structure of the processing system (single machine or shop). For each scenario, we address the complexity of various problems, namely, finding the optimal solution for one agent with a constraint on the other agent's cost function, finding single nondominated schedules (i.e., such that a better schedule for one of the two agents necessarily results in a worse schedule for the other agent), and generating all nondominated schedules. [ABSTRACT FROM AUTHOR]

In an attempt to improve the procedures for statistical process control many researchers have developed and proposed a variety of adaptive control charts in the last decade. The common characteristic of those charts is that one or more of the chart parameters (sampling interval, sample size, control limits) is allowed to change during operation, taking into account current sample information. Due to their flexibility, adaptive charts are more effective than their static counterparts but they are also more complex in terms of implementation. The purpose of this paper is to evaluate the economic performance of various adaptive control schemes to derive conclusions about their relative effectiveness. The analysis concentrates on Bayesian control charts used for monitoring the process mean in finite production runs. We present dynamic programming formulations and properties of the optimal solutions, which we then use to solve a number of numerical examples. The results from our comparative numerical study indicate that the chart parameter having the most positive impact on the economic performance by being adaptive is the sampling interval. It is therefore sufficient in most cases to use control charts with adaptive sampling intervals rather than other types of partially adaptive charts or the more complicated fully adaptive control charts. [ABSTRACT FROM AUTHOR]

In Markov models of sequential decision processes, one is often interested in showing that the value function is monotonic, convex, and/or supermodular in the state variables. These kinds of results can be used to develop a qualitative understanding of the model and characterize how the results will change with changes in model parameters. In this paper we present several fundamental results for establishing these kinds of properties. The results are, in essence, 'metatheorems' showing that the value functions satisfy property P if the reward functions satisfy property P and the transition probabilities satisfy a stochastic version of this property. We focus our attention on closed convex cone properties, a large class of properties that includes monotonicity, convexity, and supermodularity, as well as combinations of these and many other properties of interest. [ABSTRACT FROM AUTHOR]

Stochastic multicriteria acceptability analysis (SMAA) is a multicriteria decision support method for multiple decision makers in discrete problems. In SMAA, the decision makers need not express their preferences explicitly or implicitly. Instead, the method is based on exploring the weight space in order to describe the valuations that would make each alternative the preferred one. Inaccurate or uncertain criteria values are represented by probability distributions from which the method computes confidence factors describing the reliability of the analysis. In this paper we introduce the SMAA-2 method, which extends the original SMAA by considering all ranks in the analysis, in situations where the ‘elitistic’ SMAA may assess large acceptability only for extreme alternatives without sufficient majority support, the more holistic SMAA-2 analysis can be used to identify good compromise candidates. The results are presented graphically. We consider also situations where partial preference information is available. We demonstrate the new method using a real-life decision problem. [ABSTRACT FROM AUTHOR]

This paper addresses a discrete time inventory model where the maximum amount of supply from which instantaneous replenishment orders can be made is a random variable. Optimal ordering policies are characterized as critical number policies with monotone increasing optimal critical values. A sufficient condition is then presented for myopic ordering policies to be optimal. [ABSTRACT FROM AUTHOR]

In this paper we describe four axioms that uniquely characterize the class of locations in tree networks that are obtained by minimizing an additively separable, nonnegative, nondecreasing, differentiable, and strictly convex function of distances. This result is analogous to results that have been obtained in the theory of bargaining, social choice, and fair resource allocation. [ABSTRACT FROM AUTHOR]

We consider a two-level inventory system with one warehouse and N identical retailers. Lead times (transportation times) are constant and the retailers face independent Poisson demand. In a previous paper, we derived a recursive procedure for determining the policy costs for an average item in case of one-for-one replenishment policies. In this paper, we show how these results can be used for the exact or approximate evaluation of more general policies where both the retailers and the warehouse order in batches. We compare our methods to the method recently suggested by A. Svoronos and P. Zipkin. [ABSTRACT FROM AUTHOR]

This paper presents a new multiple leader-follower model that is a consistent extension of Stackelberg's leader-follower duopoly. The development contrasts with other existing extensions by demonstrating how the leader-firms can utilize the true reaction curve of the follower-firms; it also provides sufficient conditions for some useful convexity and differentiability properties of this function. For the proposed model, we conduct a static analysis and discuss the existence, uniqueness, and computation of an equilibrium solution, as well as study certain issues regarding the relative profits of leader and follower-firms. Since the Cournot oligopoly and the Stackelberg leader-follower models are special cases of this model, the analysis in this paper hopefully provides some further insights about these types of models. [ABSTRACT FROM AUTHOR]

The general single-period optimal portfolio selection problem with a risk-free asset can be solved by a two-stage approach In the first stage, one solves a certain fractional program, and in the second, a simple stochastic program with one single variable. This paper proposes a parametric approach for the solution of the fractional program wa its equivalent linear complementarity formulation. In the latter part of the paper, we specialize the proposed method to a specific model of the portfolio problem with upper bounds and outline how the method can take advantage of the special structure arising from the model Finally, we report some computational results and a brief comparison between our method and Lemke's algorithm. [ABSTRACT FROM AUTHOR]

This paper applies the test of operational meaningfulness to the many detection laws that have been formulated and used in the mathematical optimization of search, and given as generalizations of those first developed in the United States Navy during and immediately following World War II. The word "operational" is used both in the sense of practical O.R. and in that of P. W. Bridgman's well-known requirement: that in applying mathematics to the material world, the physical preconditions implied in the quantities used, the operations for measuring them, and their laws of consistency must be set forth explicitly. It is submitted that this criterion will orient O.R. work toward useful developments in the search theory and may serve to identify as such those theories that are of chief interest as developments in pure mathematics. Finally, we note that the requirement that every numerical assumption of probability distributions in a study of the outside world must be based on objective evidence is perfectly consistent with the "subjective" conception of probability, viz., that its meaning is apprehended intuitively--the former measures what the latter defines. [ABSTRACT FROM AUTHOR]

This paper presents an analysis of time-sharing computer facilities using scheduling algorithms defined in terms of priority functions. We consider the class of algorithms in which a job's priority is defined by the difference between the time it spent in the system and an arbitrary function F of its attained service, where F is called the policy function. Our main result, the average response time for a job conditioned on its service requirement, applies to a broad class of policy functions. The derivation is based on the model of a processor-sharing M/G/1 queuing system and does not use transforms. The analysis is simplified by the decomposition of a non-Markovian process. Properties of the average response time resulting from policy function schedulers are discussed and related to those of other known time-sharing scheduling algorithms. For the examples of linear, exponential, and composite policy functions we plot the response times. We demonstrate the flexibility and the limitations of policy functions with respect to the discriminatory treatment of short jobs versus long ones and discuss the optimal selection of a policy function with respect to a given overall performance criterion. [ABSTRACT FROM AUTHOR]

This paper constructs a dynamic model of a general congestion-prone system using a nonlinear differential equation to represent the relation between throughput and the system load. Although the model is not stochastic, it can give a good approximation of the dynamics of oversaturated or undersaturated system operation. The model is used to study the stability and transient behavior of a congestion-prone system and to analyze policies for the control of congestion in a simple optimal control model. [ABSTRACT FROM AUTHOR]

This paper presents a model of a deteriorating process with imperfect information. This model, unlike many previous efforts, stipulates that the operator must pay an inspection cost to determine the state of the system. This situation presents him with three choices at every time period: repair, inspection, or inaction. Under the assumptions that the transition matrix representing the process is upper-triangular and totally positive of order two, it is shown that the state-space can be broken up into at most four regions of action and that the optimal region of repair is of a special intuitive type. [ABSTRACT FROM AUTHOR]

This paper develops new improved bounds on the optimal return function in finite state and action, infinite horizon, discounted stationary Markov decision chains. The bounds are obtained by solving a single-constraint, bounded-variable linear program. They can be used for algorithmic termination criteria and improved tests for suboptimal decisions. We show how to implement these tests so that little additional computational effort is required. We consider several transformations that can be used to convert a process into an equivalent one that may be easier to solve. We examine whether the transformations reduce the spectral radius and/or the norm (maximum row sum) of the process. Gauss-Seidel iteration and Jacobi iteration are shown to be special cases of the general transformations. Gauss-Seidel iteration is given additional consideration. Another special case not only preserves equality of the row sums and sparsity but, when applicable, can dramatically reduce the norm. It reduces each element in a column by that column's smallest element. Several possible computational approaches are applied to a small numerical example. [ABSTRACT FROM AUTHOR]

This paper presents a unified development of a surrogate duality theory that is applicable to problems in which Lagrangean duality gaps limit the usefulness of standard duality approaches. A surrogate dual is created by generating a single constraint to replace the original problem constraints, rather than by absorbing these constraints into the objective function as in the Lagrangean. We give necessary and sufficient conditions for optimality both with and without the imposition of complementary slackness, and also consider a related 'overestimating' surrogate that may be used in a strategy to bracket the optimal value of the primal. The optimality conditions invite direct comparison with those for Lagrangean duality, demonstrating not only that the surrogate approach yields smaller duality gaps than the Lagrangean (as first observed by Greenberg and Pierskalla), but also giving a precise characterization of the manner and extent to which this occurs. Concepts of parametric and relative subgradients, paralleling (and generalizing) the concept of the subgradient of ordinary duality theory, lead to easily stated results that encompass both surrogate and Lagrangean duality, as well as their composite, in a single framework. [ABSTRACT FROM AUTHOR]