bluuebunny/crossref_metadata_2025 huggingface dataset:
Stochastic Control of Competition Through Prices
Authors: Deshmukh S. D. , Winston Wayne
Published: November 2008

We assume that the price of a product set by a firm affects its immediate profit rate as well as the probabilistic rate of arrival of new firms into the industry. Therefore, the firm's optimal dynamic pricing strategy must balance the increased current profits from setting a high price against the expected dilution of future profits due to additional competition. We provide a continuous-time Markov decision model and characterize the structure of the optimal control strategy and its sensitivity to the problem parameters. We also indicate the relationship of our problem to the queue control literature.
Markov Models of Advertising and Pricing Decisions
Authors: Albright S. Christian , Winston Wayne
Published: November 2008

This paper uses Markov decision analysis to study the properties of optimal advertising and pricing decisions in a dynamic, stochastic environment. We are primarily concerned with exhibiting and interpreting properties of the Markovian transition probabilities and one-period reward functions that imply that the optimal advertising levels and optimal prices always increase or always decrease as a function of the firm's market position. This is done in both non-competitive and competitive situations. In the former, total discounted reward for a single firm is the objective, whereas in the latter we use the concept of stochastic games to construct what is known as a discounted equilibrium point for two competing firms.
Infinite-Horizon Dynamic Programming Models—A Planning-Horizon Formulation
Authors: Morton Thomas E.
Published: November 2008

Two major areas of research in dynamic programming are optimality criteria for infinite-horizon models with divergent total costs and forward algorithm planning-horizon procedures. A fundamental observation for both problems is that the relative cost of two possible initial actions for a given initial state may be quite insensitive to structural information in all but the first few periods of a multiperiod model. Recently Lundin and Morton have developed a unified machinery for the dynamic lot size model that provides a general optimality criterion for the infinite horizon problem and complete planning-horizon procedures. Here those ideas are extended to provide a formal infinite-horizon/planning-horizon framework for a reasonably general form of the dynamic programming problem. Several examples and illustrations are provided. The approach provides a good vehicle for investigating the non-stationary stochastic inventory problem; this work will appear elsewhere.
Bounding Global Minima with Interval Arithmetic
Authors: Mancini Louis J. , McCormick Garth P.
Published: November 2008

We show how techniques of interval arithmetic can be used to give bounds on the global minima of unconstrained optimization problems. We illustrate the techniques using the design of a hypothetical chemical plant.
Queues Solvable without Rouché's Theorem
Authors: Neuts Marcel F.
Published: November 2008

We give a novel analysis of the steady-state probabilities of a class of infinite Markov chains. Markov chains of this type appear in the study of bulk queues and a variety of other stochastic models. We present algorithms that involve only real arithmetic and avoid the traditional analysis based on Rouché's theorem.
The Two-Machine Maximum Flow Time Problem with Series-Parallel Precedence Constraints: An Algorithm and Extensions
Authors: Monma Clyde L.
Published: November 2008

This note contains an 0(n log n) time-bounded implementation and extentions for a procedure developed by Sidney for the two-machine maximum flow time problem with series-parallel precedence constraints.
An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
Authors: Fisher M. L. , Nemhauser G. L. , Wolsey L. A.
Published: November 2008

We give bounds on heuristics and relaxations for the problem of determining a maximum weight hamiltonian circuit in a complete, undirected graph with non-negative edge weights. Three well-known heuristics are shown to produce a tour whose weight is at least half of the weight of an optimal tour. Another heuristic, based on perfect two-matchings, is shown to produce a tour whose weight is at least two-thirds of the weight of an optimal tour. Assignment and perfect two-matching relaxations are shown to produce upper bounds that are, respectively, at most 2 and 3/2 times the optimal value. By defining a more general measure of performance, we extend the results to arbitrary edge weights and minimization problems. We also present analogous results for directed graphs.
Letter to the Editor—To the Editor
Authors: Nair S. S.
Published: November 2008

The model studied in Taube-Netto, M. 1977. Two queues in tandem attended by a single server. Opns. Res. 25 140–147, was studied previously in the following papers: Nair, S. S. 1969. On certain priority queues. Mimeo Series 214, Department of Statistics, Purdue University. Nair, S. S. 1970. Semi-Markov analysis of two queues in series attended by a single server. Bull. Soc. Math. Belgique 22 355–367. Nair, S. S. 1971. A single server tandem queue. J. Appl. Probab. 8 95–109. Nair, S. S. 1973. Two queues in series attended by a single server. Bull. Soc. Math. Belgique 25 99–114.
Simulation of Nonhomogeneous Poisson Processes with Degree-Two Exponential Polynomial Rate Function
Authors: Lewis P. A. W. , Shedler G. S.
Published: November 2008

A new method for simulating a nonhomogeneous Poisson process with rate function λ(t) = exp{α0 + α1t + a2t2} in a fixed time interval (0, t0] is given. The method is based on a decomposition of the process, it employs a rejection technique, in conjunction with a method for simulating the nonhomogeneous Poisson process with rate function exp {γ0 + γ1t} by generation of gap statistics from a random number of exponential random variables with suitably chosen parameters. The proposed method for the degree-two exponential polynomial model is more efficient than time-scale transformation of a homogeneous Poisson process, and should be applicable to other rate function models.
Consistent Assessment Procedures Using Conditional Utility Functions
Authors: Bell David E.
Published: November 2008

We consider the assessment of two-attribute von Neumann-Morgenstern utility functions. The use of conditional utility functions is suggested and motivated. We derive a new independence relation between attributes that decomposes the utility function into four single-attribute utility functions. This independence condition is weaker than but may be specialized to utility independence. We examine the class of utility functions that may be assessed by use of conditional utility functions without danger of inconsistencies and derive a decomposition that is a simple generalization of joint utility independence. Implications for group utility functions are considered.
Preemptive Scheduling with Due Dates
Authors: Sahni Sartaj
Published: November 2008

An 0(n log mn) algorithm is presented to preemptively schedule n tasks on m identical machines. The tasks are assumed to have due dates. All tasks are initially available. The objective is to obtain a preemptive schedule that meets all due dates (when possible). Our algorithm generates schedules with at most n − 2 preemptions. The algorithm may also be used to schedule a set of n tasks all having the same due date but having different release dates.
The Effect of Long Term Dependence on Risk-Return Models of Common Stocks
Authors: Greene Myron T. , Fielitz Bruce D.
Published: November 2008

In a previous paper the authors have shown that common stock returns are characterized by a phenomenon called long term dependence. The present paper discusses the implications of the presence of long term dependence for existing risk-return models in finance. Specifically, it is shown that (1) risk rankings of stocks or portfolios tend to vary with the differencing interval chosen to measure security returns, (2) efficient portfolios vary with the differencing interval selected, and (3) the unrealistic, homogeneous time horizon assumption of the capital asset pricing model must be retained in order for the model to hold.
A Dynamic Priority Queue with General Concave Priority Functions
Authors: Netterman A. , Adiri I.
Published: November 2008

This paper analyzes mathematically a queueing model where a single server dispenses service to several, m, non-preemptive priority classes. It is assumed that the arrival process of customers who belong to the k class (k customers) is Poisson, and their service times are independent, identical, arbitrarily distributed random variables. The priority degree of a customer at a certain moment is not only a function of his class, but is also a general concave function of the time he has already spent in the system. (The discipline is termed “dynamic-priority.”) Upon departure the server selects for service, from the customers present, the one with the highest instantaneous priority degree, breaking ties by the FIFO rule. An implicit function as well as upper and lower bounds on the expected waiting time of k customer are found. The effectiveness of the bounds is demonstrated by a numerical example.
Technical Note—Response Time Distribution of the M/M/m/N Queueing Model
Authors: Wong J. W.
Published: November 2008

We analyze the M/M/m/N queueing model with a first-come, first-served discipline and show that the distribution of response time (i.e., queueing time + service time) is asymptotically normal as N increases. The mean and variance of this normal distribution are both simple functions of the model parameters.
Approximations and Sensitivity in Multiobjective Resource Allocation
Authors: Keefer Donald L. , Pollock Stephen M.
Published: November 2008

This paper addresses the modeling of resource allocation planning problems having uncertainties, multiple competing objectives, organizational constraints, and continuous decision variables. The application of multiobjective decision analysis leads to a nonlinear programming formulation in which the objective function is the expectation of a multiattribute utility function. If a set of independence conditions holds, this function can be decomposed into appropriately scaled sums and products of one-dimensional expected utility functions. Approximations that greatly simplify the data acquisition for, and the construction of, the one-dimensional expected utility functions are discussed. Sensitivity analyses indicate that optimal solutions to such models are robust with respect to changes in the required data, but may be seriously in error if certain popular, but overly simplified, forms for the objective function are assumed.
Preference Conditions for Multiattribute Value Functions
Authors: Kirkwood Craig W. , Sarin Rakesh K.
Published: November 2008

This paper examines conditions on preferences that simplify the assessment of multiattribute value functions for use in the analysis of multiobjective decision problems. It is shown that when these conditions hold the value function must have a simple analytic form. A procedure is presented for testing whether the conditions hold and determining the value function when the conditions are found to be valid.
The Almost Regenerative Method for Stochastic System Simulations
Authors: Gunther F. L. , Wolff R. W.
Published: November 2008

The regenerative method for simulations of stochastic systems allows data collection at the entry times to a single recurrent state of the process of interest. Estimates of estimator variance are then easily computed since the generated observations have the desirable property of being independent and identically distributed. Relative to a fixed run length, however, the mean time between entries into this single state may be excessively long for complicated stochastic systems (e.g., a congested network of queues), thus providing few observations and poor variance estimates. The almost regenerative method, a relaxation of the regenerative method, can, under frequently encountered conditions, alleviate this problem by allowing data collection at the entry times to a set of states of the process of interest. Empirical evidence from simulations of simple queueing networks supports the intuitive notion that the almost regenerative method can provide more accurate estimates of estimator variance than the regenerative method. Similar results hold when the almost regenerative method is compared to the frequently used fixed time increment method for event-oriented simulations.
Letter to the Editor—The History of Two-Class Rules for Reducing Queueing Times in M/G/1
Authors: Maxwell William L. , Miller Louis W.
Published: November 2008

Comment on Matthews, D. W. 1979. A simple method for reducing queueing times in M/G/1. Opns. Res. 27 318–323.
Letter to the Editor—Author's Rejoinder
Authors: Matthews D. E.
Published: November 2008

Rejoinder to comments by William L. Maxwell and Louis W. Miller [Maxwell, W. L., L. W. Miller. 1980. The history of two-class rules for reducing queueing times in M/G/1. Opns. Res. 28(2) 440].
Statistical Acceptance Sampling in a Competitive Environment
Authors: Dresher Melvin , Moglewer Sidney
Published: November 2008

This paper presents a model and its solution for a statistical acceptance sample inventory problem in a competitive environment. The model is based upon the theory of games and is applied to a nuclear material accounting example. A game is formulated between a diverter who might deliberately steal valuable nuclear material and a defender who must make inferences based upon inventory difference. The diverter controls the mean of the inventory difference distribution which is not known by the defender. The solution presents a policy for the defender to estimate this distribution mean as well as other information to be used as the basis for additional statistical inferences.
A Two-Fold Tandem Net with Deterministic Links and Source Interference
Authors: Kaplan Michael
Published: November 2008

The problem is to quantify the effect of flow interference on waiting-times in a two-fold tandem network of queues. Specifically, there are two deterministic servers (I0, I1) and two Poisson sources (S0, S1). So tasks are submitted first to Io and then to I1; S1 tasks proceed directly to I1. The two flows thus interfere at I1. Service is in order-of-arrival at both servers, and there are no defections at either server. In the case that I1 is no faster than I0, we compute the following quantities: (1) the network utilization factor; (2) the stationary moment-generating function of virtual waiting-time in I1; (3) the joint stationary moment-generating function for S0 waiting-time at each of I0, I1. The problem in the complementary case is still unsolved; a relevant difference-differential equation is presented, and an approximation technique is described.
Conservation Equations and Variance Reduction in Queueing Simulations
Authors: Carson John S. , Law Averill M.
Published: November 2008

We consider the efficient estimation of mean delay in queue, d, mean wait in system, w, time average number in queue, Q, time average number in system, L, and time average amount of work in system, V, for simulated queueing systems. We prove for the regenerative GI/G/s queue that it is more efficient to estimate w, Q, L, and V from an estimate of d than it is to estimate them directly. This generalizes previous results for the M/G/1 queue and also confirms empirical studies on other GI/G/s queues.
Equilibrium Linear Bidding Strategies
Authors: Rothkopf Michael H.
Published: November 2008

Symmetric bidding models are considered in which all bidders start with the same prior distribution on the value of the subject of the auction. In addition, each bidder is assumed to develop his own independent estimate. Each bidder's strategy must be a preselected linear function of his estimate. Closed form expressions are obtained for equilibrium sets of such strategies and the resulting expected profit to each bidder when the estimates are drawn from a Weibull distribution. These equilibrium linear strategies approach equilibrium multiplicative strategies as the estimating accuracy improves relative to the common prior information.
Technical Note—A Comparison of the Method of Bounding Distributions (MBD) and Monte Carlo Simulation for Analyzing Stochastic Acyclic Networks
Authors: Sullivan Robert S. , Hayya Jack C.
Published: November 2008

The method of bounding distributions and Monte Carlo simulation are compared for efficiency in estimating the mean and cumulative distribution of network completion time. Efficiency is measured in terms of computation time and the precision of the estimates. The results of this study indicate that simulation is more efficient than bounding distributions, and that the relative efficiency of simulation is further enhanced as networks become larger.
Dynamic Loading and Unloading of Liquids into Tanks
Authors: Christofides Nicos , Mingozzi Aristide , Toth Paolo
Published: November 2008

We consider the problem appearing in the loading and unloading of crude oil into storage tanks at an oil terminal or port. The numbers, sizes and initial condition of the storage tanks are known and what is required is to perform a given sequence of loading and unloading operations involving several types of crude into and out of these tanks. The different types of crude cannot be mixed, and what is required is to decide which crude is to be loaded (unloaded) into (out of) which tanks so as to minimize the value of an objective function. The objective considered is a general integral criterion and includes a criterion based only on the terminal state of the tanks as a special case. The problem is formulated as a mixed integer program in which the continuous variables are only involved in a subproblem with a network-flow structure. A branch-and-bound algorithm is described which makes use of graph theoretic lower bounds and dominance conditions to limit the search. The algorithm was tested on a number of real-world problems involving up to 45 loading and/or unloading operations, 11 types of crude and 20 storage tanks.
A Stochastic Allocation Problem
Authors: Mendelson Haim , Pliskin Joseph S. , Yechiali Uri
Published: November 2008

A given quantity of a resource is to be allocated to several activities. The amount of the resource allocated to each activity is used to supply stochastic demands occurring randomly. The system operates as long as all the demands can be met. Whenever the demand of any one activity exceeds its allotment the system fails. The problem is to find the allocation which maximizes the expected time until failure. It is shown that when the available quantity of the resource is large, the optimal allocation is proportionate to the expected demand rate of each activity. An application to a multi-installation inventory problem is presented.
Capacity Expansion when Demand Is a Birth-Death Random Process
Authors: Freidenfelds John
Published: November 2008

When demand is assumed to be a birth-death process, and capacity expansion costs are assumed to occur instantaneously at the time of expansion, it is shown that an “equivalent” deterministic-demand problem can readily be generated. The derived problem is equivalent in the sense that its solution by ordinary deterministic capacity expansion methods would also yield the solution of the stochastic problem. It is shown that the “equivalent deterministic demand” is always greater than the “expected demand,” where the latter is defined by the expected time to first reach various levels of demand, and is not the expected number of customers. In addition to general formulas for the discrete-customer case, equations are also derived for the “equivalent deterministic demand” when demand is based on a diffusion process.
Restricted Bayes Strategies for Programs with Simple Recourse
Authors: Nadeau Raymond , Theodorescu Radu
Published: November 2008

When using linear stochastic programs one generally assumes that the joint probability distribution of the random variables involved is known. However, in practice, for example in manpower planning problems, the knowledge of this distribution is incomplete. Consequently this paper presents a linear stochastic program with partial information, where the confidence in this joint probability distribution is expressed by a parameter varying from 0 to 1. Explicit solutions are given for programs with simple recourse.
Successive Approximation Methods in Undiscounted Stochastic Games
Authors: Federgruen Awi
Published: November 2008

This paper considers undiscounted two-person, zero-sum sequential games with finite state and action spaces. Under conditions that guarantee the existence of stationary optimal strategies, we present two successive approximation methods for finding the optimal gain rate, a solution to the optimality equation, and for any ϵ > 0, ϵ-optimal policies for both players.
Technical Note—Geometric Interpretation of Generalized Lagrangian Multiplier Search Procedures in the Payoff Space
Authors: Widhelm William B.
Published: November 2008

Recent limited computational results have indicated that the normed Generalized Lagrangian Multiplier (GLM) search performs better than the standard non-normed procedure equivalent to the Dantzig-Wolfe (D-W) approach. Previous arguments for the superiority of the normed procedure were based on multiplier-space considerations where the normed approach yields a more geometrically centered cut. In this note, the payoff-space geometry is investigated. Here, the normed procedure weights the search in accordance with the closeness of the constraint values to the requirements vector whereas the D-W approach ignores this information.
Technical Note—A New Norm for Measuring Distance Which Yields Linear Location Problems
Authors: Ward J. E. , Wendell R. E.
Published: November 2008

We propose a new norm, called the one-infinity norm, for characterizing distance in facility location problems. This new norm, which is a hybrid version of the rectilinear and Tchebycheff norms, not only gives a good characterization of distance (as compared, for example, to results by Love and Morris) but also has two alternate interpretations of travel. Furthermore, it yields linear programming formulations of location problems.
Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem
Authors: Cornuejols Gerard , Nemhauser George L. , Wolsey Laurence A.
Published: November 2008

We consider a location problem whose mathematical formulation is maxs{z(S): S ⊆ N, |S| = K}, where z(S) = ∑i∈I maxj∈scij and C = (cij) is any non-negative m × n matrix with row index set I and column index set N. We show that any procedure which uses matrix C only to calculate values of the function z(S) cannot, with a number of values polynomial in n, guarantee to find an optimal solution. However when C is the edge-vertex incidence matrix of a graph, we show that if n is suitably large and K is fixed or does not grow too rapidly with n, the K vertices of largest degree nearly always constitute an optimal solution.
A Resource Allocation Algorithm (ALCOT) for Controlling Mine Drainage Pollution
Authors: Clark Gordon M. , Ranganathan Anbil N.
Published: November 2008

The algorithm is a means for analyzing a network of mines producing pollutants in a watershed. Treatment of mine effluents or abatement procedures reducing mine pollutant outputs can control pollutant inputs to streams from individual mine sources. In addition, treatment sites in the streams can remove pollutants flowing from upstream sites. The determination of least-cost decisions at mine sources and instream treatment sites for achieving a quality standard throughout a watershed constitutes a discrete nonlinear programming problem. A modification and extension to the partial enumeration method formulated by Lawler and Bell resulted in an efficient algorithm for solving this problem. An application illustrates the operation of the algorithm.
A Parametric Linear Complementarity Technique for Optimal Portfolio Selection with a Risk-Free Asset
Authors: Pang Jong-Shi
Published: November 2008

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 via 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.
Optimal Challenges for Selection
Authors: Degroot Morris H. , Kadane Joseph B.
Published: November 2008

This paper generalizes the problems of optimal selection considered by Roth, Kadane and DeGroot by allowing a set of J items to be chosen by two decision makers, the first of whom has A challenges and the second has B challenges. The two decision makers each have an opportunity to challenge each item before it is accepted, in some arbitrary fixed order. We assume that the decision makers know the utility function of the other side as well as their own over sets of J items, and that they know the subjective distribution, assigned by the other side, of characteristics of potential items that will be observed, as well as their own. Under these conditions the other side's response to each potential item can be predicted with certainty, and backward induction defines an optimal strategy. We study an important special case we call regular, and show that it is never disadvantageous to go first in the regular case. The use of peremptory challenges in jury trials motivates our model. The basic model in which jurors are challenged one at a time is extended to a more general class of problems that includes the group system and the struck jury system.
Technical Note—Computational Comparison among Three Multicommodity Network Flow Algorithms
Authors: Ali A. , Helgason R. , Kennington J. , Lall H.
Published: November 2008

This note presents our computational experience using specialized techniques for solving multicommodity network flow problems. The algorithms investigated include a price-directive decomposition procedure, a resource-directive decomposition procedure using subgradient optimization, and a primal partitioning procedure.
The Distribution of Security Price Changes: A Test of a Volume-Mixture Model with Cauchy Disturbances
Authors: Epps Thomas W.
Published: November 2008

This paper considers a time-series model for changes in security prices from one transaction to the next, in which they are viewed as depending on previous price changes, on transaction volume, and on a random disturbance. The dependence on transaction volume implies that the marginal distribution of price changes is a mixture of distributions, the form of which is determined by the behaviors of volume and the disturbance. Even when the disturbance follows a finite-variance distribution, such as the normal, the volume-mixture model implies a marginal distribution for price changes with the characteristic thick tails that are observed in practice. An alternative hypothesis, however, is that volume plays no role and that the disturbance itself is appropriately described by an infinite-variance probability law. Parametric tests of these two hypotheses are conducted by estimating the volume parameter in the mixture model under the alternative assumptions that the disturbance follows Gaussian and Cauchy laws.
Technical Note—Enforcing Constraints on Expanded Networks
Authors: Denardo Eric V. , Fox Bennett L.
Published: November 2008

Any pure integer program can be cast as a shortest-route problem in an expanded network, subject to a set of side constraints. Here we select side constraints and alter the network to enforce them or surrogates for them. Logical constraints prove especially amenable to this treatment; we handle generalized upper bounds, variable upper bounds, and others simply by reconnecting arcs. Enforcing such constraints increases the fidelity of the expanded network to the integer program and tightens the relaxations that occur when the integer program is solved by implicit enumeration of the expanded network's paths.
Technical Note—A Note on the Ingargiola-Korsh Algorithm for One-Dimensional Knapsack Problems
Authors: Martello Silvano , Toth Paolo
Published: November 2008

Corrections that should be made to the paper by Ingargiola and Korsh (Ingargiola, G. P., J. F. Korsh. 1977. A general algorithm for one-dimensional knapsack problems. Opns. Res. 25 752–759.) on a general algorithm for one-dimensional knapsack problems.
Technical Note—A One-Product Production/Inventory Problem under Continuous Review Policy
Authors: Gavish Bezalel , Graves Stephen C.
Published: November 2008

A single production facility is dedicated to producing one type of product with completed units going directly into inventory. The demand for the product is governed by a Poisson process and is supplied directly to inventory when available, or is backordered until it is produced by the production facility. Relevant costs are a linear inventory holding cost, a linear backorder cost, a fixed setup cost for initiating a production run. The objective is to find a control policy to minimize the expected cost per time unit. It is shown that the problem may be modeled as an M/D/1 queueing system with the optimal policy being a two-critical-number policy. Cost expressions are derived as functions of the policy parameters, and based on a convexity property of these cost expressions, an efficient search procedure is proposed for finding the optimal policy. In computational tests that were performed on an IBM 360/65, optimal policies were computed in less than 1/8 second of CPU time.
Technical Note—A Solvable Cyclic Scheduling Problem with Serial Precedence Structure
Authors: Garfinkel R. S. , Plotnicki W. J.
Published: November 2008

Jobs arrive at a facility in a periodic way, each requiring the same set of tasks with a serial precedence structure. Only a fixed number of tasks can be performed in any period. The number of periods is also given so that jobs not completed in the final period are continued in the first. The problem of minimizing total delay is shown to be solvable analytically. The model is motivated by the application of scheduling courses to quarters to minimize student delay in an academic program.
Optimal Search for a Moving Target in Discrete Time and Space
Authors: Brown Scott Shorey
Published: November 2008

We consider optimal search for a moving target in discrete space. A limited amount of search effort is available at each of a fixed number of time intervals and we assume an exponential detection function. We show that a search plan maximizes the overall probability of detection if and only if for each time interval i the search conducted at time i maximizes the probability of detecting a stationary target with the probability that the stationary target occupies cell c equal to the probability that the moving target occupies cell c at time i and is not detected by the search at any time interval other than i. This characterization gives an iterative algorithm to compute optimal search plans. These plans are compared with incrementally optimal plans.
Optimal Stopping in a Partially Observable Markov Process with Costly Information
Authors: Monahan George E.
Published: November 2008

A problem of optimal stopping in a Markov chain whose states are not directly observable is presented. Using the theory of partially observable Markov decision processes, a model which combines the classical stopping problem with sequential sampling at each stage of the decision process is developed. Several results which characterize the optimal expected value function in terms of its parameters are given. An example is given which indicates that the best action to take as a function of the information currently available may not be of the intuitively appealing control limit type. The set of states at which it is optimal to purchase information need not be convex. The expected value of information as a function of the decision maker's knowledge is related to nonmonotone optimal policies.
Hard Knapsack Problems
Authors: Chvátal Vasek
Published: November 2008

We consider a class of algorithms which use the combined powers of branch-and-bound, dynamic programming and rudimentary divisibility arguments for solving the zero-one knapsack problem. Our main result identifies a class of instances of the problem which are difficult to solve by such algorithms. More precisely, if reading the data takes t units of time, then the time required to solve the problem grows exponentially with the square root of t.
Ambushing Random Walks III: More Continuous Models
Authors: Ruckle William H. , Reay John R.
Published: November 2008

We continue our study of the following game theory problem: a traveler (BLUE) wishes to choose a path across a rectangle from left to right in such a way to avoid certain obstacles in the rectangle (called ambushes) which are chosen by his antagonist (RED). The game theoretic payoff might depend upon whether BLUE's path and the ambushes have a common point, or the payoff may be a function of how far the path proceeds before meeting the first ambush. These ambush games have analogous search games.
Scheduling Jobs with Linear Delay Penalties and Sequence Dependent Setup Costs
Authors: Barnes J. Wesley , Vanston Lawrence K.
Published: November 2008

We discuss the problem of minimizing the sum of the setup costs and linear delay penalties when N jobs, arriving at time zero, are to be scheduled for sequential processing on a continuously available machine. The delay penalty for each job is a nondecreasing linear function of the sum of the various processing times for preceding jobs. The setup cost for each job is dependent only upon the job that immediately precedes it. The equivalence of the traveling salesman problem to the setup portion of this problem creates a special challenge. The application of several Branch-and-Bound algorithms using various branching rules is discussed. Since the problem has a highly attractive Dynamic Programming formulation, a hybrid algorithm analogous to Morin and Marsten's Dynamic Programming/Branch-and-Bound approach to the traveling salesman problem is also utilized. This technique, detailed in the paper, applies a fathoming criterion to the states of the Dynamic Program in order to drastically reduce memory and computational requirements. We report computational results for a set of randomly generated problems that endorse the effectiveness of one heuristic approach and show the superiority of the hybrid approach over pure Branch-and-Bound methods in yielding confirmed optimal solutions for that set of problems.
On Single-Machine Scheduling with Precedence Relations and Linear or Discounted Costs
Authors: Glazebrook K. D. , Gittins J. C.
Published: November 2008

Some results of Sidney (Sidney, J. B. 1975. Decomposition algorithms for single machine sequencing with precedence relations and deferral costs. Opns. Res. 23 283–298.) concerning order-constrained deterministic scheduling with linear costs are extended to the more complex discounted costs case. Further, certain order-constrained stochastic scheduling problems are shown to have optimal strategies which are nonpreemptive. When this is so, results for the deterministic case may be utilized to obtain these optimal strategies. The models discussed are of interest in computer and job-shop scheduling and research planning.
Technical Note—Waiting Time in a Continuous Review (s, S) Inventory System with Constant Lead Times
Authors: Kruse W. Karl
Published: November 2008

The waiting time distribution in an (s, S) continuous review inventory system with constant lead times is derived in this paper. The demand times are assumed to constitute a renewal process, and demand sizes are independent identically distributed (i.i.d.) integer valued random variables. Some relationships are given between waiting time and some common inventory measures.
Technical Note—Integer Allocation Problems of Min-Max Type with Quasiconvex Separable Functions
Authors: Zeitlin Zeev
Published: November 2008

The paper treats the problem of integer resource allocations using the min-max criterion. The objective function is assumed to be strictly quasiconvex (in the integer sense) and separable. The optimality conditions are used to obtain a solution algorithm which may be simplified in the case of strict monotonicity.
Allocation of a Perishable Product Inventory
Authors: Prastacos Gregory P.
Published: November 2008

A perishable product is periodically produced and allocated among n locations in a region. It is assumed that costs are charged for units short or outdated at any location, and the excess demand at any location is satisfied from outside sources. We prove that the optimal allocation policy minimizes both the expected average shortages and the expected average outdates in the region, and we discuss the management implications of this result. We present the myopically optimal policy M and show that it has similar properties to the optimal policy π*. We prove that π* cannot be “very different” from M; we derive analytic bounds for the performance of π*, and show that the long-run performance of M lies always within these bounds. Finally, some computational results are presented.
The Stationary Distribution of a Stochastic Clearing Process
Authors: Whitt Ward
Published: November 2008

This research grew out of an investigation of utilization in capacity expansion. The utilization at any time is the demand divided by the capacity. When there is uncertainty about the evolution of demand, it is appropriate to model the demand as a stochastic process, and thus the utilization also becomes a stochastic process. It was found that a utilization stochastic process associated with exponentially growing stochastic demand is closely related to the stochastic clearing processes introduced and investigated by Stidham. Interest in the impact of uncertainty on utilization led to this study of the impact of uncertainty on the stationary distribution of a stochastic clearing process. Stidham showed for a large class of clearing processes that the stationary distribution is never the uniform distribution, which is characteristic of deterministic models with continuous linear input. Here it is shown for a larger class of clearing processes that the stationary distribution is always stochastically less than or equal to the uniform distribution in the sense of second-order stochastic dominance (characterized by the expected value of all nondecreasing concave functions). For various special cases, stronger stochastic order relations are established. For a related capacity expansion model, it is shown that greater uncertainty lowers the expected utilization.
Technical Note—Precedence Relations of the Flow-Shop Problem
Authors: Szwarc Wlodzimierz
Published: November 2008

A theory based on the precedence relation (dominance condition with no fixed presequence) concept has been developed and applied to the flow-shop problem. The nature and scope of two major precedence relations have been explored. The paper offers a natural generalization of the Johnson algorithm for the general case, and proves sufficient conditions for optimality of the resulting sequence.
A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering
Authors: Bartholdi John J.
Published: November 2008

The problem of cyclic staff scheduling is solved by a linear programming round-off heuristic for which a bound on the absolute error is established. The quality of the bound is independent of the resource requirements. Moreover, the quality of the bound improves as the matrix of resource availability approximates the property of consecutive ones. The appropriateness of the heuristic is further established by showing that cyclic staff scheduling is NP-complete.
Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
Authors: Cho Yookun , Sahni Sartaj
Published: November 2008

We study the problem of obtaining feasible preemptive schedules for independent jobs. It is assumed that each job has associated with it a release and due time. No job can begin before its release time. All jobs must be completed by their respective due times. It is shown that determining the existence of feasible preemptive schedules for two processor flow and job shops is NP-hard in the strong sense even when all jobs have the same due time. A linear programming formulation for the open shop problem is obtained. Also, a fast polynomial time algorithm is obtained for a restricted class of open shop problems.
On Locating a Facility to Service Areas within a Network
Authors: Slater Peter J.
Published: November 2008

Problems involving the selection of a site in a network at which to locate a facility, such as a station for a security guard force, generally fall into one of two categories, depending upon the nature of the facility to be established. One may be interested in minimizing the maximum travel time from the facility to any node in the network, or one may wish to minimize the sum of the distances from the facility to all the nodes in the network. In this paper problems involving travel time from the facility to areas within the network (that is, collections of points as opposed to individual points) are considered. This generalization of the problems appears not to alter their nature, and similar techniques for solutions can be used.
The Machine Repair Problem with Heterogeneous Populations
Authors: Gross Donald , Ince John F.
Published: November 2008

The classic machine repair with spares (finite source) queueing model assumes all calling units are identical in failure and repair characteristics. This paper develops, for a first-come first-served discipline, a procedure for treating nonhomogeneous populations, specifically, a population with two types of items, each with exponential failure and repair times but with different mean values. Exact solutions are obtained for small population sizes and compared to approximate procedures using the classical theory. The exact model is essentially a two-stage cyclic queue with two classes of customers. Extensions of the model to N stages and M customer classes, priority disciplines, and other disciplines, including blocking, are discussed.
Models for Time-Sharing Computer Systems with Heterogeneous Users
Authors: Lehoczky John P. , Gaver Donald P.
Published: November 2008

Models for time-sharing computer systems are presented. The models are of the repairman type and involve more than one type of customer demanding service from a single server queue. The models studied do not admit a product form stationary distribution, thus approximation methods designed to study the queue length processes are introduced. Of particular importance is the introduction of an approximation method which allows for the queue discipline to be varied parametrically. The associated diffusion approximation allows one to study system performance as a function of queue discipline.
Using a Stochastic Model to Investigate Time to Absorption Distributions
Authors: Shachtman Richard H. , Schoenfelder John R. , Hogue Carol J.
Published: November 2008

This paper demonstrates that, after being tested for goodness of fit, Markov chain models may be used in epidemiological investigations to compute the time to absorption distributions useful in designing follow-up studies. Also illustrated is the use of these models to compare distinct cohorts with respect to stochastic movement among states. Using data from a historical prospective study conducted in Skopje, Yugoslavia, we employ a Markov chain model of women's reproductive paths to compare the stochastic behavior of first pregnancy aborters and first pregnancy deliverers. We estimate the time to next delivery distribution within each of these cohorts, constructs useful in determining the required sample size for future studies of the effects of induced abortion.
Technical Note—The Multiperiod Knapsack Problem
Authors: Faaland Bruce H.
Published: November 2008

In the multiperiod knapsack problem the decision maker faces a horizon of m periods. Associated with each period are a number of types of items, each with a value and weight. Subject to the requirement that the cumulative capacity of the knapsack in each period i cannot be exceeded by items chosen in periods 1, …, i, the decision maker chooses the most valuable knapsack possible. A branch and bound algorithm exploits the special structure of the multiperiod knapsack problem by calculating bounds by the direct solution of linear programs with m constraints in 0(m) operations. Computational experience is reported on problems ranging in size up to 200 constraints and 1,000 general integer variables.
Technical Note—Equivalence between the Direct Search Approach and the Cut Approach to the Rectilinear Distance Location Problem
Authors: Kolen Antoon
Published: November 2008

Picard and Ratliff recently proposed a cut approach to the rectilinear distance location problem and claimed it is fundamentally different from the direct search approach as developed by Pritsker and Ghare, Rao, Juel and Love, and Sherali and Shetty. Our objective is to show that the cut approach is essentially a direct search approach.
Operations Planning with VERT
Authors: Moeller Gerald L. , Digman Lester A.
Published: November 2008

The Venture Evaluation and Review Technique (VERT) is a computerized, mathematically oriented network-based simulation technique designed to analyze risks existing in three parameters of most concern to managers in new projects or ventures—time, cost, and performance. As such, the VERT technique is more powerful than techniques such as GERT, which are basically time and cost oriented. VERT has been successfully utilized to assess the risks involved in new ventures and projects, in the estimation of future capital requirements, in control monitoring, and in the overall evaluation of ongoing projects, programs, and systems. It has been helpful to management in cases where there is a requirement to make decisions with incomplete or inadequate information about the alternatives. An example describing the application of VERT to an operational planning problem—the evaluation of electric power generating methods—is illustrated.
The Customer Contact Approach to Services: Theoretical Bases and Practical Extensions
Authors: Chase Richard B.
Published: November 2008

This paper reviews the underlying theory of the customer contact approach to services and suggests specific ways in which this approach can be applied to a wide range of service systems. The approach holds that the potential efficiency of a service system is a function of the degree of customer contact entailed in the creation of the service product. Based upon this conceptualization, a number of propositions about high contact systems are identified and some simple heuristics for service system design and operation are proposed. Other approaches to operations management in services are reviewed and suggestions for further development of the contact approach are offered.
Hierarchical Production Planning: A Single Stage System
Authors: Bitran Gabriel R. , Haas Elizabeth A. , Hax Arnoldo C.
Published: November 2008

This paper presents a hierarchical approach to plan and schedule production in a manufacturing environment that can be modeled as a single stage process. Initially, the basic tradeoffs inherent to production planning decisions are represented by means of an aggregate model, which is solved on a rolling horizon basis. Subsequently, the first solution of the aggregate plan is disaggregated, considering additional cost objectives and detailed demand constraints. Several improvements in the methodology related to hierarchical production planning are suggested. Special attention is given to alternative disaggregation procedures, problems of infeasibilities, and the treatment of high setup costs. Computational results, based on real life data, are presented and discussed.