bluuebunny/crossref_metadata_2025 huggingface dataset:
Tests for the Nonergodicity of Multidimensional Markov Chains
Authors: Sennott Linn I.
Published: November 2008

A Markov chain is ergodic if it has a proper steady-state distribution. The stability of a queueing system often reduces to the ergodicity of an underlying multidimensional chain. We gave criteria for the nonergodicity of a multidimensional Markov chain and a generalization to continuous time Markov chains. We also give queueing model examples.
A New Polynomially Bounded Shortest Path Algorithm
Authors: Glover F. , Klingman D. , Phillips N.
Published: November 2008

This paper develops a new polynomially bounded shortest path algorithm, called the partitioning shortest path (PSP) algorithm, for finding the shortest path from one node to all other nodes in a network containing no cycles with negative lengths. This new algorithm includes as variants the label setting algorithm, many of the label correcting algorithms, and the apparently computationally superior threshold algorithm.
Parametric Solution of Bicriterion Linear Fractional Programs
Authors: Warburton A. R.
Published: November 2008

We show how certain bicriterion fractional programs can be reduced to a one parameter linear program and a series of one-dimensional maximizations. The resulting algorithm is easily implemented using the PARAROW option of MPSX, and has readily solved problems having up to 300 variables and 150 constraints. As an illustration, we present a simple finite procedure for maximizing the sum of two linear fractional functions subject to linear constraints.
Comparing Draws for Single Elimination Tournaments
Authors: Horen Jeff , Riezman Raymond
Published: November 2008

Tournaments are used to select a single winner from a group of participants in a sporting event or a paired-comparison experiment. This study compares different draws, or pairings, of teams in single-elimination tournaments under a set of relatively nonrestricting assumptions about the participating teams' pairwise probabilities of winning. We analyze and compare draws for four-team tournaments using various criteria, then attempt to generalize the results to eight-team tournaments. For example, only one-four team draw maximizes the probability that the best team wins for all pairwise probabilities, whereas eight draws are possibly optimal for eight-team tournaments.
The Deterministic Dynamic Product Cycling Problem
Authors: Karmarkar Uday S. , Schrage Linus
Published: November 2008

Certain manufacturing situations involve a small number of items produced sequentially on the same facility with high changeover cost. Production schedules are characterized by long runs, and individual items are produced infrequently. At the same time, seasonal demand patterns require that the items be maintained in inventory in the right mix. This paper presents alternative formulations of this problem. It uses a Lagrangean relaxation approach to decouple the problem and provide lower bounds used in a branch and bound algorithm. Some experimental computations on small problems are reported.
A Generalized Uniform Processor System
Authors: Ishii Hiroaki , Martel Charles , Masuda Teruo , Nishida Toshio
Published: November 2008

This paper considers a scheduling problem whose objective is to determine both the optimal speeds of processors and an optimal schedule in a preemptive multiprocessor environment. The jobs are independent and each processor can be assigned any speed; however, the cost associated with each processor is a function of the processor's speed. Polynomial algorithms are presented to find optimal speed assignments for a variety of cost functions.
Replacement of Systems and Components in Renewal Decision Problems
Authors: Thomas L. C.
Published: November 2008

The lifetime of some systems is virtually independent of their components. For example, a car's lifetime depends on the general corrosion of the bodywork and its avoidance of a major accident, which are independent of the condition of the battery. We consider the replacement problem when both the system and components can be replaced and the time horizon is infinite. As well as considering which type of components should we use to replace a failed one, we consider whether when a component fails, it is best to replace the whole system.
Assessment of Preferences by Conditions on Pricing-Out Amounts
Authors: Harvey Charles M.
Published: November 2008

A value function for consequences described by a monetary attribute and one or more other attributes can be determined by assessing pricing-out amounts between the monetary attribute and each of the other attributes. This willingness-to-pay procedure is restricted to decision problems in which the pricing-out amounts are independent of the decision maker's monetary position. This paper extends the procedure to decision problems in which the pricing-out amounts do depend on monetary position. It then presents new procedures by which conditions on this dependence can be used in place of multiattribute risk conditions to determine a utility function.
Technical Note—The Effect of Risk Aversion on the Expected Value of Perfect Information
Authors: Mehrez Abraham
Published: November 2008

We consider the value of information when the decision-maker is averse to risk, and identify a bound on the maximal amount that the decision-maker is willing to pay to completely reduce uncertainty. We show that, for a class of unfavorable projects with nonpositive expected monetary value, a decision-maker neutral to risk is willing to pay at least as much for perfect information as is a decision-maker who is averse to risk. Finally, we analyze the effect of shifting the mean of the a priori distribution of the project's monetary value, and calculate the value of perfect information for a family of utility functions and a class of symmetric distributions centered at zero.
Distribution Strategies that Minimize Transportation and Inventory Costs
Authors: Burns Lawrence D. , Hall Randolph W. , Blumenfeld Dennis E. , Daganzo Carlos F.
Published: November 2008

This paper develops an analytic method for minimizing the cost of distributing freight by truck from a supplier to many customers. It derives formulas for transportation and inventory costs, and determines the optimal trade-off between these costs. The paper analyzes and compares two distribution strategies: direct shipping (i.e., shipping separate loads to each customer) and peddling (i.e., dispatching trucks that deliver items to more than one customer per load). The cost trade-off in each strategy depends on shipment size. Our results indicate that, for direct shipping, the optimal shipment size is given by the economic order quantity (EOQ) model, while for peddling, the optimal shipment size is a full truck. The peddling cost trade-off also depends on the number of customers included on a peddling route. This trade-off is evaluated analytically and graphically. The focus of this paper is on an analytic approach to solving distribution problems. Explicit formulas are obtained in terms of a few easily measurable parameters. These formulas require the spatial density of customers, rather than the precise locations of every customer. This approach simplifies distribution problems substantially while providing sufficient accuracy for practical applications. It allows cost trade-offs to be evaluated quickly using a hand calculator, avoiding the need for computer algorithms and mathematical programming techniques. It also facilitates sensitivity analyses that indicate how parameter value changes affect costs and operating strategies.
A Time-dependent Stopping Problem with Application to Live Organ Transplants
Authors: David Israel , Yechiali Uri
Published: November 2008

We consider a time-dependent stopping problem and its application to the decision-making process associated with transplanting a live organ. “Offers” (e.g., kidneys for transplant) become available from time to time. The values of the offers constitute a sequence of independent identically distributed positive random variables. When an offer arrives, a decision is made whether to accept it. If it is accepted, the process terminates. Otherwise, the offer is lost and the process continues until the next arrival, or until a moment when the process terminates by itself. Self-termination depends on an underlying lifetime distribution (which in the application corresponds to that of the candidate for a transplant). When the underlying process has an increasing failure rate, and the arrivals form a renewal process, we show that the control-limit type policy that maximizes the expected reward is a nonincreasing function of time. For non-homogeneous Poisson arrivals, we derive a first-order differential equation for the control-limit function. This equation is explicitly solved for the case of discrete-valued offers, homogeneous Poisson arrivals, and Gamma distributed lifetime. We use the solution to analyze a detailed numerical example based on actual kidney transplant data.
Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming
Authors: Martin R. Kipp , Schrage Linus
Published: November 2008

We describe a method for generating cuts for mixed-integer 0/1 programs. These cuts are designed to tighten an integer program prior to applying linear programming based branch and bound algorithms. The method involves two basic ideas: subset selection and coefficient reduction. Coefficient reduction is a process of reducing the coefficients of the 0/1 variables. Subset selection is combined with coefficient reduction by applying the coefficient reduction process to the coefficients of a subset of variables from the constraints in the problem formulation. The paper exploits these two simple ideas to derive a broad class of cuts for integer programs with both 0/1 and continuous variables. It also reports on the use of this methodology in solving a variety of fixed charge problems.
An Algorithm for the Maximal Multicommodity Funnel-Node Flow in an Undirected Network
Authors: Martins Ernesto Q. V. , Rosa Mario S.
Published: November 2008

We consider the maximal multicommodity funnel-node flow problem. That is, K commodities of flow must be simultaneously defined in an undirected network so that the flow of all the commodities passes through a specified node (the funnel-node) and is maximal. For this particular problem of multicommodity flows, we present a polynomially bounded algorithm.
On the Expected Relative Performance of List Scheduling
Authors: Coffman E. G. , Gilbert E. N.
Published: November 2008

Let X̄ = (X1, …, Xn) denote an ordered list of service times required by n tasks. The service will be performed by m ≥ 2 processors working in parallel. Each processor serves one task at a time and, having once started a task, finishes it before starting another. A schedule determines how the tasks are to be served. A list schedule keeps the tasks not yet serviced listed in the order prescribed by X̄. Whenever a processor completes a service, it then takes its next task from the head of the list. The makespan of a schedule is the time required for all service to be completed. The makespan L(X̄) of a list schedule is usually longer than necessary. Reordering the tasks in an optimal way can reduce the makespan to OPT(X̄), the smallest possible makespan, but requires knowing the Xi in advance and solving an NP-complete problem. The ratio R(X̄) = L(X̄)/OPT(X̄) measures the penalty paid for serving the tasks in a predetermined order. Here, the service times Xi are treated as independent identically distributed random variables. Two distributions for Xi, uniform and exponential, are considered. Bounds on the mean ER(X̄) and on the distribution function P[R(X̄) > x] are obtained.
Optimal Inventory Policies When Ordering Prices are Random
Authors: Golabi Kamal
Published: November 2008

We consider a single-item inventory model with deterministic demands. At the beginning of each period, a random ordering price is received according to a known distribution function. A decision must be made as to how much (if any) of the item to order in each period so as to minimize total expected costs while satisfying all demands. We show that, in each period, a sequence of critical price levels determines the optimal ordering strategy, so that it is optimal to satisfy the demands of the next n periods if and only if the random price falls between the nth and the n+ 1st levels. We derive recursive expressions that describe the critical price numbers, and demonstrate the relationship of these expressions to minimal expected cost. We study finite horizon as well as infinite horizon models and show that the critical number strategy is also average-cost optimal.
The Optimal Look-Ahead Policy for Admission to a Single Server System
Authors: Nawijn W. M.
Published: November 2008

This paper considers a service system with a single server, finite waiting room, and a renewal arrival process. Customers who arrive while the server is busy are lost. Upon completing service, the server chooses between two actions: either he immediately starts a new service, provided a customer is present, or he admits the newly arrived customer to the system, but delays service pending the next arrival, whereupon he again chooses between these two actions. This process continues until either the system is full or a new service is started. Once a service has been started, all customers who arrive while the server is busy are lost. We assume that at each decision epoch the server knows the arrival epoch of the first arriving customer. We show that there exists an optimal control-limit policy that minimizes the average expected idle time per customer served (equivalently, maximizes the average number of customers served per unit of time). The special case of Poisson arrivals leads to an explicit expression for this delay that generalizes exisiting results.
Optimal Control of an M/M/S Queueing System
Authors: Szarkowicz Donald S. , Knowles Thomas W.
Published: November 2008

We consider the problem of determining optimal operating policies for an M/M/S queueing system. The system state (x1, x2) is defined by x1 the number of customers in the system, and x2 the number of active service channels. The cost structure includes customer holding and service channel operating costs as well as a linear switching cost. We use a continuous-time Markov decision process formulation to obtain an optimal control policy of the control limit form, and present an algorithm for the finite state problem. Finite-transition and infinite-transition with discounting are considered.
Radiotherapy Treatment Design Using Mathematical Programming Models
Authors: Sonderman David , Abrahamson Philip G.
Published: November 2008

The design of treatment for external beam radiation therapy of malignant tumors is a complex decision-making process. This paper introduces and develops mathematical programming models that can aid this process. After briefly discussing the necessary background material, we state our linear and mixed-integer programming models, along with some variations that can be usefully implemented in some situations. We then compare our design for a case of lung cancer with a standardized approach, and the advantages of our models become evident. We close with several comments about the potential utility of this class of models in treating other types of cancers.
ε-Approximations for Multidimensional Weighted Location Problems
Authors: Drezner Zvi , Gavish Bezalel
Published: November 2008

This paper considers the multidimensional weighted minimax location problem, namely, finding a facility location that minimizes the maximal weighted distance to n points. General distance norms are used. An ε-approximate solution is obtained by applying a variant of the Russian method for the solution of Linear Programming. The algorithm has a time complexity of O(n log ε) for fixed dimensionality k. Computational results are presented.
Consecutive Optimizers for a Partitioning Problem with Applications to Optimal Inventory Groupings for Joint Replenishment
Authors: Chakravarty A. K. , Orlin J. B. , Rothblum U. G.
Published: November 2008

We consider several subclasses of the problem of grouping n items (indexed 1, 2, …, n) into m subsets so as to minimize the function g(S1, …, Sm). In general, these problems are very difficult to solve to optimality, even for the case m = 2. We provide several sufficient conditions on g(·) that guarantee that there is an optimum partition in which each subset consists of consecutive integers (or else the partition S1, …, Sm satisfies a more general condition called “semiconsecutiveness”). Moreover, by restricting attention to “consecutive” (or “semiconsecutive”) partitions, we can solve the partition problem in polynomial time for small values of m. If, in addition, g is symmetric, then the partition problem is solvable in purely polynomial time. We apply these results to generalizations of a problem in inventory groupings considered by the authors in a previous paper. We also relate the results to the Neyman-Pearson lemma in statistical hypothesis testing and to a graph partitioning problem of Barnes and Hoffman.
Valid Linear Inequalities for Fixed Charge Problems
Authors: Padberg M. W. , Van Roy T. J. , Wolsey L. A.
Published: November 2008

Many problems in the Operations Research/Management Science literature can be formulated with both zero-one and continuous variables. However, the exact optimization of such mixed zero-one models remains a computational challenge. In this paper, we propose to study mixed problems from a mathematical point of view that is similar in spirit to recent research on purely combinatorial problems that has investigated systems of defining linear inequalities (or facets of the underlying polytope). At least two numerical studies have validated this line of research computationally, and the advances in the problem-solving capabilities are considerable. We expect that similar gains are possible for the mixed zero-one problem. More precisely, we consider the mixed integer programs whose feasible region X is composed of (i) a simple additive constraint in the continuous variables xj, for j = 1, 2, …, n and (ii) constraints 0 ≤ xj ≤ mjyj defined by binary variables yj for j = 1, 2, …, n. This type of feasible region arises in a variety of mixed integer problems, and particularly in network problems with fixed charges on the arcs. We derive two classes of facet-defining linear inequalities of the convex hull of X, and show that the second of these classes gives a complete description of the convex hull when mj = m for all j. We also develop methods to detect violated inequalities from these classes, so that these facets can be used as cutting planes to strengthen the formulations of certain mixed integer problems.
Regenerative Analysis and Steady State Distributions for Markov Chains
Authors: Grassmann Winfried K. , Taksar Michael I. , Heyman Daniel P.
Published: November 2008

We apply regenerative theory to derive certain relations between steady state probabilities of a Markov chain. These relations are then used to develop a numerical algorithm to find these probabilities. The algorithm is a modification of the Gauss-Jordan method, in which all elements used in numerical computations are nonnegative; as a consequence, the algorithm is numerically stable.
Technical Note—Some Very Easy Knapsack/Partition Problems
Authors: Orlin James B.
Published: November 2008

Consider the problem of partitioning a group of b indistinguishable objects into subgroups, each of size at least l and at most u. The objective is to minimize the additive separable cost of the partition, where the cost associated with a subgroup of size j is c(j). In the case that c(·) is convex, we show how to solve the problem in O(log u − l + 1) steps. In the case that c(·) is concave, we solve the problem in O(min(l, b/u, (b/l) − (b/u), u − l)) steps. This problem generalizes a lot-sizing result of Chand and has potential applications in clustering.
An Analytic Derivation of Blackjack Win Rates
Authors: Gottlieb Gary
Published: November 2008

We study the win rate for the game of blackjack and derive a stochastic model for the advantage (i.e., expected win) process. Assuming proportional betting, we derive an explicit formula that estimates the win rate as a function of the number of decks used and the proportion of cards dealt before reshuffling. We derive a relationship between the “aggressiveness” of betting and risk. Risk is measured as the probability of wealth dropping below a specified level before it exceeds a higher, specified level.
The Minisum and Minimax Location Problems Revisited
Authors: Hansen Pierre , Peeters Dominique , Richard Denis , Thisse Jacques-Francois
Published: November 2008

The minisum (minimax) problem consists of locating a single facility in the plane with the aim of minimizing the sum of the weighted distances (the maximum weighted distance) to m given points. We present two solution methods for generalized versions of these problems in which (i) location is restricted to the union of a finite number of convex polygons; (ii) distances are approximated by norms that may differ with the given points; and (iii) transportation costs are increasing and continuous functions of distance. Computational experience is described.
Refining the Diffusion Approximation for the M/G/m Queue
Authors: Yao David D.
Published: November 2008

Despite its many and varied applications, the M/G/m queue has yet to be solved exactly. Consequently, researchers have developed many methods for approximating its solution. We refine a diffusion approximation model developed by Kimura for the M/G/m queue, using an alternative approach to characterize and solve the diffusion equations and incorporating some known results of the queue into the model. Numerical studies indicate that the refined model provides significantly improved performance. Moreover, the model is consistent with some known heavy-traffic limit results.
Dynamic, Non-Preemptive Priority Queues with General, Linearly Increasing Priority Function
Authors: Bagchi Uttarayan , Sullivan Robert S.
Published: November 2008

This paper considers a single server queueing system that services customers from P non-preemptive priority classes. We assume independent identically distributed exponential interarrival and general service times for each class of customer. We also assume that a customer's priority in the queue is determined not only by its class, but also by the length of time it has spent in the queue; the priority for each class can be a general linearly increasing priority function. Our development gives an expression for the expected waiting time of each customer class, and gives bounds on this expression. We demonstrate the calculation of the bounds by several numerical examples, and discuss the sensitivity of the bounds to priority function parameters and system utilization. We also show that, even under the most conservative assumptions, the bounds are remarkably tight. Furthermore, for the special case of an M/M/1 system with identical service time distributions, these bounds can be substantially improved if the ordinal ranking of expected waiting times is known a priori. The results of this research enable systems designers to anticipate and consequently to control system behavior for systems with general linearly increasing priority disciplines.
Reward Revision for Discounted Markov Decision Problems
Authors: White Chelsea C. , Thomas Lyn C. , Scherer William T.
Published: November 2008

We present a numerical procedure for determining the optimal total expected discounted reward vector f* for an infinite horizon, discrete stage, finite state and action Markov decision process (MDP). This procedure exploits the fact that many MDPs generate the same vector f*. The objective of the procedure is to simultaneously construct and solve one such MDP that has a computationally attractive transition structure. The construction of this MDP requires the periodic revision of its reward structure. We then present a simple, a priori method for estimating the impact of the new procedure on operation counts as compared to standard successive approximations. This method is useful for determining whether or not the new procedure should be used and for selecting an important design parameter. We also describe two extensions of the new procedure, one generalizing a standard extrapolation and the other a modified policy iteration algorithm. A numerical evaluation indicates that for MDPs having transition structures with a small number of dominant probabilities per row, the new procedure can significantly reduce CPU time.
Establishing Consistent and Realistic Reorder Intervals in Production-Distribution Systems
Authors: Maxwell William L. , Muckstadt John A.
Published: November 2008

The objective of this paper is to present a model and algorithm that can be used to find consistent and realistic reorder intervals for each item in large-scale production-distribution systems. We assume such systems can be represented by directed acyclic graphs. Demand for each end item is assumed to occur at a constant and continuous rate. Production is instantaneous and no backorders are allowed. Both fixed setup costs and echelon holding costs are charged at each stage. We limit our attention to nested and stationary policies. Furthermore, we restrict the reorder interval for each stage to be a power of 2 times a base planning period. The model that results from these assumptions is an integer nonlinear programming problem. The optimal solution can be found using the proposed algorithm, which is a polynomial time algorithm. A real world example is given to illustrate the procedure.
A Cost Adjustment Heuristic for Dynamic Lot-Sizing with Uncertain Demand Timing
Authors: Nevison Christopher H.
Published: November 2008

We define a new heuristic, based on the adjustment of set-up costs, for the dynamic lot-sizing problem when demand timing is uncertain. Using a range of simulated problems, we compare the performance of this cost adjustment heuristic with that of a safety lead time heuristic, Zangwill's deterministic algorithm, which ignores uncertainty, and the optimal solution. Results show that the safety lead time heuristic works well for problems with high shortage costs and high probability of early demands, but poorly in other circumstances. The cost adjustment heuristic is quite robust, generally exceeds the performance of the safety lead time approach, and is relatively insensitive to variations in uncertainty.
Preemptive Scheduling to Minimize Maximum Completion Time on Uniform Processors with Memory Constraints
Authors: Martel Charles
Published: November 2008

We consider the problem of preemptively scheduling n jobs on m processors. The ith job has a processing requirement pi and a memory requirement qi. The ith processor has a speed si and a memory capacity ci. The ith job can be run on the jth processor whenever cj ≥ qi. When all jobs have a deadline Di we develop an O(n log m) time algorithm that finds a feasible schedule or determines that no such schedule exists. We then use this algorithm to find the minimum time by which all jobs can be completed in O(nm log2m) time.
The Beginnings of Operations Research in the United States
Authors: Morse Philip M.
Published: November 2008

This paper, drawn from the author's autobiography, gives an account of the events leading up to the creation of the first operations research group in the United States, and describes how it approached its first problem, improving antisubmarine warfare operations off the Atlantic coast of the United States.
OR Forum—Perspectives on Utility Theory
Authors: Bell David E. , Farquhar Peter H.
Published: November 2008

Utility theory is a branch of decision analysis that is concerned with building models to explain and guide choice behavior under uncertainty in situations in which “long run” expected values are too simplistic. Beginning with Bernoulli in the 18th century, researchers have tried to analyze how people do and how people should make decisions when risk aversion is a factor. In this paper, we review some recent developments in the area.
Errata—Correction to “Optimal Control of an M/M/S Queueing System”
Authors: Szarkowicz Donald S. , Knowles Thomas W.
Published: November 2008

Correction to Szarkowicz, D. S., T. W. Knowles. 1985. Optimal control of an M/M/S queueing system. Opns. Res. 33 644–660.
OR Practice—A Survey of Practical Applications of Examination Timetabling Algorithms
Authors: Carter Michael W.
Published: November 2008

In examination timetabling, a set of examinations must be assigned to a fixed number of periods so that no student is required to take more than one examination at a time. Each institution will normally impose a list of secondary considerations that define a “good” timetable in its environment. This paper contains a survey of actual applications of timetabling at several universities and a tutorial guide for practitioners on selecting and/or designing an algorithm for their own institutions.
A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
Authors: Tardos Éva
Published: November 2008

Khachiyan, and recently Karmarkar, gave polynomial algorithms to solve the linear programming problem. These algorithms have a small theoretical drawback; namely, the number of arithmetic steps depends on the size of the input numbers. We present a polynomial linear programming algorithm whose number of arithmetic steps depends only on the size of the numbers in the constraint matrix, but is independent of the size of the numbers in the right-hand side and objective vectors. In particular, it gives a polynomial algorithm for the minimum cost flow and multicommodity flow problems in which the number of arithmetic steps is independent of the size of the costs and capacities. The algorithm makes use of an existing polynomial linear programming algorithm. The problem of whether any algorithm has a running time that is independent even of the size of the numbers in the constraint matrix remains open.
The Reconciliation of Decision Analyses
Authors: Lindley Dennis V.
Published: November 2008

A decision problem can be structured in many different ways. This paper addresses a few of the problems that arise as a result of this diversity; for instance, is a particular structuring method worth doing: is the effort likely to be rewarding? Further considerations arise when two or more methods are used and must be combined. Any rule of combination must attach weights, that depend on errors in the analyses, to the results. Consequently, the questions of errors both at random and decision nodes require discussion. We show that errors at decision nodes produce biases. A basic idea underlying our argument is the concept of true utilities and probabilities: we include a discussion of this concept.
An Empirical Formula for Visual Search
Authors: Koopman Bernard O.
Published: November 2008

This paper presents an empirically derived formula for computing the threshold contrast C for visually detecting distant objects in search situations. The threshold contrast is the value of contrast that produces detection probability 1/2 on a single glimpse of about 1/3 to 1 second in duration. The formula allows one to compute C as a function of background luminance, target angular area A, and an empirically determined constant K. For small A, the formula reduces to Ricco's law, which says that the threshold constrast C, and Area A, are directly proportional for small values of A. The limiting threshold contrast is determined by K. Results of fitting this formula to a set of observational data are shown. The formula provides a useful approximation for determining detection capability for planning visual searches.
A Generalized Problem of Optimal Selection and Assignment
Authors: Tamaki Mitsushi
Published: November 2008

We consider the infinite version of the secretary problem. From an infinite stream of applicants, we are to select m choices and assign them, in order, to m positions to be filled. We receive a reward ck(m) for 1 ≤ k ≤ m(0 ≤ c1(m) ≤ ⋯ ≤ cm(m) = 1) if the best k applicants are selected and correctly ranked (i.e., the ith best applicant is assigned to the ith position for 1 ≤ i ≤ k). We consider two versions of the problem: (i) once an applicant is selected and assigned to some position, he cannot be promoted to a better position at a later time, and (ii) previously selected applicants can be promoted. In this paper, we concentrate on the double selection problem, m = 2, and derive, for both the promotion and nonpromotion versions of the problem, the optimal strategy that maximizes the expected reward.
Petroleum Reservoir Exploitation: Switching from Primary to Secondary Recovery
Authors: Amit Raphael
Published: November 2008

The petroleum recovery process has two potential phases: primary recovery, during which the natural drive forces the oil to the well bore, and secondary recovery, during which a producer uses artificial means to recover the resource. A producer may choose to switch from primary to secondary recovery if the desired ultimate output is more than can be obtained by exploiting the natural drive, or when the desired current extraction rate is larger than can be obtained by the natural drive. These decisions are affected by the interaction between geological, technical and market conditions. We formulate an investment and production model that incorporates the relationships between extraction rates, investment decisions and cumulative recovery, and investigate a two-phase dynamic optimization problem. We do so by defining and analyzing a more general optimization problem and applying the results to our model. The major findings relate to the timing and size of investment, the rate and duration of secondary recovery, and the optimal switching policies from primary to secondary recovery. We discuss each of these issues in detail, and outline and explain quantitative policy recommendations.
Replacement Costs Under Warranty: Cost Moments and Time Variability
Authors: Balcer Yves , Sahin Izzet
Published: November 2008

We consider a product that is sold under one of the two common warranty policies. Under the “pro rata” warranty policy, a failed item is replaced by a new one or is repaired at a cost prorated to the age of the failed item. Under the “free replacement” warranty policy, replacements or repairs during the warranty period are provided by the supplier free of charge to the buyer. Assuming that successive failure times form a renewal process, we derive moments of the total replacement cost for both policies during the product life cycle (0, t]. We also provide an extension to time-varying failure time distributions in the case of the pro rata warranty policy.
Technical Note—Advertising Models, Stochastic Games and Myopic Strategies
Authors: Dirven C. A. J. M. , Vrieze O. J.
Published: November 2008

This paper analyzes dynamic advertising models. We present conditions that imply that the payoffs under myopic strategies are linear in the state variable, which represents the number of customers for each firm. These conditions, which determine a subclass of stochastic games, are satisfied by several dynamic advertising models. We give a criterion to check whether this model contains an equilibrium point within the class of myopic strategies that is also an equilibrium point with regard to all strategies.
OR Practice—Making a Clean Sweep: Simulating the Effects of Illegally Parked Cars on New York City's Mechanical Street-Cleaning Efforts
Authors: Riccio Lucius J. , Litke Ann
Published: November 2008

On a peak day, New York City's Department of Sanitation deploys 354 mechanical sweepers to pick up a substantial portion of the 100 tons of litter deposited daily on the city's 6,000 street miles. Field studies conducted by the department indicated that the major obstacle to doing a thorough job of cleaning was the number of illegally parked cars blocking the curb. We used Monte Carlo simulations to determine the increase in sweeping effectiveness that could be expected from significant reduction in illegally parked cars. The simulations provided information that was critical to the decision making process and resulted in the redeployment of 30% of the city's mobile traffic enforcement agents. The redeployment led to fewer illegally parked cars and more curb space available for cleaning.
Using Column Generation Techniques for Treating Dynamic Multisectoral Models with Price-Dependent Coefficients
Authors: Boucher Jacqueline , Smeers Yves
Published: November 2008

Column generation has a reputation for poor convergence. We report numerical experiments conducted with large multisectoral models having price-sensitive technical coefficients. Surprisingly, we did not observe tail convergence problems or experience other difficulties that are typically ascribed to problems that contain similar columns.
Optimum Replacement of a System Subject to Shocks: A Mathematical Lemma
Authors: Puri Prem S. , Singh Harshinder
Published: November 2008

We consider a system that is subject to shocks that occur randomly over time. We assume that the system must be replaced after it has functioned for a random length of time τ, a moment of a major failure that is a stopping time with respect to the process {N(t), t ≥ 0} that models the number of shocks occurring in [0, t]. It may, however, be economical to replace the system at time min(t, τ) prior to its failure, for some fixed but optimally chosen t. Costs are due to shocks, maintenance and replacement. We introduce an optimality criterion, based on cost considerations, which we use to find an optimal replacement time t0. In the process, we prove a general mathematical lemma that helps in arriving at the optimal replacement time for general classes of processes {N(t)}, stopping times τ and the cost structures involved. We also give a discrete time version of the lemma.
On Minimizing Flow Time on Processors with Variable Unit Processing Time
Authors: Huang H. C.
Published: November 2008

This paper uses the interchange technique to prove a result of Meilijson and Tamir that the shortest processing time (SPT) schedule minimizes total flow time on parallel identical processors that have unequal starting times and nonincreasing unit processing time. The SPT schedule remains optimal for a special case when the unit processing time is increasing.
A Marginal-Cost Pricing Model for Gas Distribution Utilities
Authors: Guldmann Jean-Michel
Published: November 2008

We develop a natural gas distribution utility pricing model that includes optimization of supply mix and capacity expansion, financial analysis of revenue requirements, and design of either average-cost- or marginal-cost-based rates, and apply it using data from the East Ohio Gas Company. The results clearly point to the superiority of marginal-cost over average-cost pricing policies in terms of lesser capital requirements, better capacity utilization and higher end-use economic efficiency.
The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
Authors: Federgruen Awi , Groenevelt Henri
Published: November 2008

In many resource allocation problems, the objective is to allocate discrete resource units to a set of activities so as to maximize a concave objective function subject to upper bounds on the total amounts allotted to certain groups of activities. If the constraints determine a polymatroid and the objective is linear, it is well known that the greedy procedure results in an optimal solution. In this paper we extend this result to objectives that are “weakly concave,” a property generalizing separable concavity. We exhibit large classes of models for which the set of feasible solutions is a polymatroid and for which efficient implementations of the greedy procedure can be given.
Concave Minimization Via Collapsing Polytopes
Authors: Falk James E. , Hoffman Karla L.
Published: November 2008

We present a procedure for globally minimizing a concave function over a (bounded) polytope by successively minimizing the function over polytopes containing the feasible region, and collapsing to the feasible region. The initial containing polytope is a simplex, and, at the kth iteration, the procedure chooses the most promising vertex of the current containing polytope to refine the approximation. The method generates a tree whose ultimate terminal nodes coincide with the vertices of the feasible region, and accounts for the vertices of the containing polytopes.
Parametric Analysis in Linear Fractional Programming
Authors: Wolf Hartmut
Published: November 2008

We consider the parametric analysis for a linear fractional programming problem with a scalar parameter in the right-hand side of the restrictions. A method we develop determines the optimal value of the objective function as well as the optimal solution of the parametric problem. The method is based on a parametric analysis of a linear auxiliary program. This analysis provides the decision maker with additional parametric information not provided by previous methods.
Statistical Analysis for Use with the Schruben and Margolin Correlation Induction Strategy
Authors: Nozari Ardavan , Arnold Steven F. , Pegden C. Dennis
Published: November 2008

In 1978, L. W. Schruben and B. H. Margolin recommended a correlation induction strategy for a special class of multipopulation simulation experiments. In this paper we present methods for conducting statistical analysis when using their strategy. We give formulas for parameter estimation, hypothesis testing and confidence interval estimation. An example demonstrates the mechanics of the formulas.
Presidents' Symposium: Creating Growth in OR/MS
Authors: Pierskalla William P.
Published: November 2008

These remarks, adapted from remarks made at a symposium entitled “Perspectives on the Future of OR/MS” at the May 1984 ORSA/TIMS meeting in San Francisco, use a view of the history and current state of OR/MS as the basis for projecting possible futures for the profession, with special attention to ways of achieving growth.
Presidents' Symposium: OR Elsewhere
Authors: Machol Robert E.
Published: November 2008

This essay offers a brief, somewhat subjective, view of operations research in Old World countries; some of this material was presented at the International Federation of Operational Research Societies Conference IX and published in the proceedings of that meeting.
Optimal Time-Varying Flows on Congested Networks
Authors: Carey Malachy
Published: November 2008

This paper develops a well-behaved convex programming model for least-cost flows on a general congested network on which flows vary over time, as for example during peak/off-peak demand cycles. The model differs from static network models and from most work on multiperiod network models because it treats the time taken to traverse each arc as varying with the flow rate on the arc. We develop extensions of the model to handle multiple destinations and multiple commodities, though not all of these extensions yield convex programs. As part of its solution, the model yields a set of nonnegative time-varying optimal flow controls for each arc. We determine and discuss sufficient conditions under which some or all of these optimal flow controls will be zero-valued. These conditions are consistent with computational experience. Finally, we indicate directions for further research.
Some Optimum Algorithms for Scheduling Problems with Changeover Costs
Authors: Hu T. C. , Kuo Y. S. , Ruskey F.
Published: November 2008

We consider a production line that can produce one of n items per day. The demand schedule for all items is known in advance, and all items must be produced on or before their deadlines. We want a production schedule that meets all demand deadlines and minimizes the total changeover cost. The changeover cost has a special structure: it is (i) one dollar if the production line changes from producing item i to item j and i is less than j, and (ii) zero if i is greater than or equal to j. We also consider multiple identical production lines with all demands due at the end of every month, and assume that there is exactly enough demand at the end of every month. We obtain optimum production schedules for both the single-line and multiple-line case.
Constant Exchange Risk Properties
Authors: Farquhar Peter H. , Nakamura Yutaka
Published: November 2008

This paper develops a methodology using risk properties to characterize the functional form of a utility measure for decision making under uncertainty. The constant absolute risk property, for example, is known to be necessary and sufficient, with appropriate regularity conditions, for the utility function to have either a linear or an exponential form. A new generalization of this property, called the constant exchange risk property, gives a characterization of six utility functions: the linear function, the exponential function, the quadratic function, the sum of two exponential functions, the sum of a linear and an exponential function, and the product of a linear and an exponential function. Since all of these functional forms have been used previously as approximations, this methodology allows analysts to distinguish beforehand between alternative forms and thus properly specify the utility function in applications.
The P-Centroid Problem on an Inclined Plane
Authors: Hodgson M. John , Wong Richard T. , Honsaker John
Published: November 2008

We model a log harvesting problem as one of how to slide blocks along an inclined plane. To analyze this problem we develop and test a P-centroid location-allocation model that minimizes aggregate work. The model provides insight into the ideal shapes, locations and numbers of harvesting sites.
The Role of Cost Allocation in Locational Models
Authors: Granot Daniel
Published: November 2008

In facility locational models of public-service systems (for example, fire extinguishment, police and ambulance systems), the allocation of the system's operating cost and the locations of the service stations are in principle very closely related. The farther a user is from the service station, the lower is the cost share he should he willing to defray, and vice versa. We consider in this paper the problem of locating one facility in a tree network, T, and suggest a game theoretic approach for generating the facility location y in T and a corresponding cost allocation scheme q. The pairs (y, q) generated by our game theoretic approach are contained in a least core associated with the locational model, and they are all stable in the sense that they cannot be improved upon by any subset of users.
Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
Authors: Solomon Marius M.
Published: November 2008

This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints. Given the intrinsic difficulty of this problem class, approximation methods seem to offer the most promise for practical size problems. After describing a variety of heuristics, we conduct an extensive computational study of their performance. The problem set includes routing and scheduling environments that differ in terms of the type of data used to generate the problems, the percentage of customers with time windows, their tightness and positioning, and the scheduling horizon. We found that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.
Inventory Policy in the Presence of Market Disruptions
Authors: Chao Hung-Po
Published: November 2008

This paper presents a dynamic model concerning optimal inventory policies in the presence of market disruptions, which are often characterized by events with uncertain arrival time, severity and duration. The model is based on the framework of a continuous-time Markov decision process with a finite state space. We develop a general characterization of the optimal inventory policy, interpret it in economic terms, and then apply it to two special cases, yielding explicit analytic results.