bluuebunny/crossref_metadata_2025 huggingface dataset:
A Decision Rule for Producing Christmas Greeting Cards
Authors: Goyal S. K.
Published: November 2008

Christmas greeting cards are produced in batches, with several designs printed on a sheet simultaneously. The number of cards printed for a design is constrained to be an integer multiple of the number of sheets printed for the set of plates containing the design. The demand for the cards is met by two production runs: a limited number is produced in the first run, primarily as samples for display at the pre-Christmas shows; at the time of initiating the second production run, a more realistic estimate of the demand for each design is available and a significant increase in profits can be obtained by producing the cards economically. This paper presents a simple deterministic model for improving a company's profit in the Christmas-greeting-card trade.
A Control Policy for a Priority Queue with Removable Server
Authors: Tijms Henk
Published: November 2008

This paper studies a control policy for an M/G/1 nonpreemptive-priority queuing system with removable server and two priority classes. This policy turns off the server when the system is empty and turns him on when a given linear combination of the numbers of class 1 and class 2 customers in the system exceeds a certain value. Expressions for the long-run average numbers of class 1 and class 2 customers in the system are derived.
Work Rates in Closed Queuing Networks with General Independent Servers
Authors: Chang A. , Lavenberg S. S.
Published: November 2008

Closed queuing networks are composed of interconnected service stages serving a fixed number of customers. Each stage consists of a queue and identical parallel servers. The path of a customer’s progress throughout the network is described by a finite Markov chain over the stage names. Service times are assumed to be mutually independent with arbitrary distribution functions. The work rate for a stage, defined as the long-run time-average amount of service time rendered by the stage, is shown to exist with probability one. Explicit expressions relating the work rates of different stages and explicit expressions for the asymptotic work rates as the number of customers becomes large are derived. Work rates are shown to depend continuously on the service-time distributions.
A New Look at Brown’s Dynamic Inventory System
Authors: Howe William G.
Published: November 2008

Robert G. Brown's Statistical Forecasting for Inventory Control sketched out a dynamic inventory-control system with random demand and random lead time. For some reason, the system has had neither wide use nor further scrutiny. To rectify the situation, this paper puts both a more mathematical and a more meaningful basis under the system, and then discusses its actual operation and some possible extensions.
Exponential Smoothing as a Special Case of a Linear Stochastic System
Authors: Pandit S. M. , Wu S. M.
Published: November 2008

This paper derives a uniformly-sampled-autoregressive-moving-average (USAM) model for a second-order linear stochastic system, shows that exponential smoothing is a limiting case of the USAM model, and discusses the optimal value of the exponential-smoothing parameter and its sensitivity to mean-squared error of prediction. The USAM model is interpreted as a first-order system with first-order feedback; its limiting behavior explains why many business, economic, and quality-control systems are predicted well by exponential smoothing. The results are illustrated by examples of real-life data from IBM stock prices, and quality-control measurements of an automatic screw-machine operation.
Technical Note—A Counterexample for an Optimal Search-and-Stop Model
Authors: Kan Y. C.
Published: November 2008

The idea of policy regions is very useful in characterizing an optimal strategy for problems in dynamic programming. However, there are occasions when intuition suggests that an optimal strategy may be characterized by some structure of policy regions, and yet it is extremely difficult to prove or disprove this conjecture. This paper presents a counterexample showing an intuitive conjecture to be wrong.
A Probabilistic Model for Analyzing Campus Parking Policies
Authors: Narragon E. A. , Dessouky M. I. , DeVor R. E.
Published: November 2008

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

Bracken and McGill have discussed the theory, computations, and an example of mathematical programming models with optimization problems in the constraints [Opns. Res. 21, 37–44 (1973)], and have presented a computer program for solving such models with nonlinear programs in the constraints [Opns. Res. 22, 1097–1101 (1974)]. Bracken, Falk, and McGill have given a procedure for transforming mathematical programs with two-sided optimization problems in the constraints into mathematical programs with nonlinear programs in the constraints [Opns. Res. 22, 1102–1104 (1974)], thus enabling their solution by the computer program. This paper formulates models of defense problems that are convex programs having the mathematical properties treated in the previous papers. The models include several strategic-force-planning models and two general-purpose-force planning models.
Technical Note—A Method for Combining Three-Valued Predictions
Authors: Sutherland William H.
Published: November 2008

This note shows a method for finding readily the distribution of the sum or product of variables for which predictions are available in three-valued form: a most likely value together with high and low values that each have specified probabilities of occurrence. It is assumed that the variables have a Weibull distribution. Using dimensionless graphs entered with an “asymmetry quotient” found arithmetically from the original prediction values, the first, second, and third moments of each Weibull distribution are found. Then the moments of the individual distributions are combined to find the three moments of the overall distribution. If desired, these combined moments can be converted to the three-value form of the original estimates—a low, most likely, and high figure. The method described can be used instead of Monte Carlo methods, avoids their possible uncertainties, and does not require a computer. It is generally more accurate than another alternative, the approximations used in summing PERT critical paths.
Technical Note—Numerical Investigation of Optimal Parallel Redundancy in Series Systems
Authors: McLeavey Dennis W.
Published: November 2008

This note presents a numerical investigation of various techniques reported in the branch-and-bound literature applied to the specific problem of optimal redundancy allocation. It compares two common backtracking strategies, deep and broad search, along with a zero-one versus direct problem formulation. Also reported are some highly successful modifications exploiting the specific problem structure.
Technical Note—An Improved Feasibility Test for Gorenstein's Algorithm
Authors: Bennington G. E. , McGinnis L. F.
Published: November 2008

The purpose of this note is to propose a simpler feasibility criterion for the disjunctive-graph model proposed by Balas and implemented by Gorenstein in an algorithm for resource-constrained project scheduling.
Operations Research in the Insurance Industry: I. A Survey of Applications
Authors: Jewell William S.
Published: November 2008

This paper surveys and interprets the applications of operation research in the insurance industry.
Operations Research in the Insurance Industry: II. An Application in Claims Operations of Workmen's Compensation Insurance
Authors: Jewell William S. , Johnston Tom L. , Leavitt Stephen S.
Published: November 2008

This paper presents an application of operations-research techniques to managing claims in workmen's compensation insurance. It describes the investigative studies and their conclusions, outlines the systems design and implementation, and gives a sample of the validation studies. Implementation of the proprietary claims-management system described has provided dramatic reductions in case durations and paid dollar losses, while returning the injured worker to his ultimate level of rehabilitation in a shorter time.
The Long-Term Effects of Merit-Rating Plans on Individual Motorists
Authors: Ferreira Joseph
Published: November 2008

This paper examines the effects over an individual's driving lifetime of being charged annual premiums for automobile bodily-injury insurance in accordance with particular merit rating plans. Individual accident involvement is modeled as a compound Poisson process and the annual premium amounts as a Markov process. For each plan, the model examines (1) how well an individual's lifetime premium payments reflect his accident likelihood, (2) the discount that is provided for accident-free drivers, (3) the probability that a driver pays a very high annual premium, and (4) the number of years that lapse before a previous accident no longer affects a driver's premium.
Technical Note—A Production-Scheduling Problem with Batch Processing
Authors: Dorsey Robert C. , Hodgson Thom J. , Ratliff H. Donald
Published: November 2008

This note considers a multiple-facility, multiple-product, production-scheduling problem with backordering over a finite planning horizon that consists of discrete production periods during each of which at most one product can be assigned to each facility. Product demands in each period are assumed to be known but not necessarily the same in all periods. The problem objective is to determine an assignment of products to facilities that meets all product demands on a first-come, first-served basis and minimizes the sum of production, inventory, and backordering charges over the horizon. This problem is formulated as a linear, mixed integer program and then transformed into an all-integer program that can be solved using any of the very efficient algorithms for finding minimal-cost network flows.
Erratum
Authors: Soyster A. L.
Published: November 2008

Erratum to author's paper “A Duality Theory for Convex Programming with Set-Inclusive Constraints” [Opns. Res. 22, 892–898 (1974)].
The Probability Distribution Function of the Optimum of a 0-1 Linear Program with Randomly Distributed Coefficients of the Objective Function and the Right-Hand Side
Authors: Zimmermann H.-J. , Pollatschek M. A.
Published: November 2008

This paper proposes and discusses exact and approximate methods for solving the distribution problem of a linear 0-1 program with stochastic b and c. It shows that, in decision-making situations, severe errors can arise when mathematical expectations are substituted for the stochastic coefficients and the problem is treated as a deterministic one. Thus, a knowledge of the distribution function of the optimal value of the objective function as a function of the distributions of the coefficients—or close bounds on it—is a genuine help for the decision maker in situations of risk or uncertainty.
A Cutting-Plane Algorithm for the Quadratic Set-Covering Problem
Authors: Bazaraa Mokhtar S. , Goode Jamie J.
Published: November 2008

This paper develops an algorithm to solve certain quadratic set-covering problems where the constraint set is of the inequality type. It extends one of Bellmore and Ratliff for linear set-covering problems with involutory bases where cutting planes that exclude both integer and noninteger solutions are generated at each iteration. The new algorithm can be used to solve problems of the equality and mixed types by introducing a penalty term in the objective function. Computational experience with the new algorithm is presented.
Technical Note—Probabilistic Analysis of a Two-Unit System with a Single Service Facility for Preventive Maintenance and Repair
Authors: Gopalan M. N. , D'Souza C. A.
Published: November 2008

This note deals with the availability and the reliability of a two-unit system with a cold standby and a single service facility for the performance of preventive maintenance and repair. Explicit expressions for the Laplace transform of the mean downtime of the system during (0, t) and for the mean time to system failure have been obtained under the assumption that the repair time and the preventive maintenance time of a unit are exponentially distributed. The case of no preventive maintenance is also considered as a special case.
Simulating Stable Stochastic Systems: III. Regenerative Processes and Discrete-Event Simulations
Authors: Crane Michael A. , Iglehart Donald L.
Published: November 2008

This paper shows that a previously developed technique for analyzing simulations of GI/G/s queues and Markov chains applies to discrete-event simulations that can be modeled as regenerative processes. It is possible to address questions of simulation run duration and of starting and stopping simulations because of the existence of a random grouping of observations that produces independent identically distributed blocks in the course of the simulation. This grouping allows one to obtain confidence intervals for a general function of the steady-state distribution of the process being simulated and for the asymptotic cost per unit time. The technique is illustrated with a simulation of a retail inventory distribution system.
A Comparative Study of Flow-Shop Algorithms
Authors: Baker Kenneth R.
Published: November 2008

This paper describes an experimental comparison of flow-shop algorithms, motivated by the need to consolidate recent research on this topic. Using a set of test problems, it investigated various branch-and-bound and elimination strategies in a comparative study and then combined them to produce a new and efficient solution algorithm.
On the Set-Covering Problem: II. An Algorithm for Set Partitioning
Authors: Balas Egon , Padberg Manfred
Published: November 2008

In an earlier paper [Opns. Res. 20 1153–1161 (1972)] we proved that any feasible integer solution to the linear program associated with the equality-constrained set-covering problem can be obtained from any other feasible integer solution by a sequence of less than m pivots (where m is the number of equations), such that each solution generated in the sequence is integer. However, degeneracy makes it difficult to find a sequence of pivots leading to an integer optimum. In this paper we give a constructive characterization of adjacency relations between integer vertices of the feasible set that enables us to generate edges (all, if necessary) connecting a given integer vertex to adjacent integer vertices. This helps overcome the difficulties caused by degeneracy and leads to a class of algorithms, of which we discuss two.
A Branch-and-Bound Algorithm for Pagination
Authors: Duncan John , Scott Lawrence W.
Published: November 2008

The paper presents an algorithm for partitioning the nodes of a weighted graph in order to minimize the interset weights. The algorithm is patterned after the branch-and-probabilistic-bound procedures of Graves and Whinston. Final partitions or solutions are characterized by probability statements like: “the probability is greater than α that a randomly selected solution is inferior to the final.” The algorithm can be used to segment computer programs and data libraries when statistics on the transition or reference rates among program or data elements are known. Numerical results demonstrate the feasibility of efficiently partitioning 50-node graphs.
A Lower Bounding Structure for Lot-Size Scheduling Problems
Authors: Kleindorfer P. R. , Newson E. F. P.
Published: November 2008

This paper discusses efficient methods for determining optimal lower bounds (and concomitant dual variables) for lot-size problems of both fixed and variable capacity. The approach unifies lower bounding procedures for several common forms of the problem on the basis of generalized duality theory. Through the optimal (lower bounding) dual solution, a production plan can be generated that when “rounded” to feasibility may be optimal or near optimal for problems of appropriate configuration.
An M/M/m/n Queue for the Shortest Distance Priority Machine Interference Problem
Authors: Reynolds Gary H.
Published: November 2008

A mathematical model is developed for the machine interference problem with the priority of servicing the nearest machine in need of repair. The walking distance to a repair can be very significant in such large scale problems as law enforcement and guerrilla warfare where a first-in-first-out priority would, most likely, yield meaningless results. Compared with other models depicting the problem as a Markov process, the shortest distance priority yields the largest number of operating machines under steady-state conditions.
Strategic Weapons Exchange Models
Authors: Arms R. L. , Grissmer D. W. , Bracken J. , Lyons L. A. , Miercort F. A. , Smith N. M.
Published: November 2008

Two strategic weapons exchange models have been developed, an allocation model and a cost optimization model. The allocation model is designed to allocate the fixed strategic arsenal of one side against the population and retaliatory forces of the other side in some optimal fashion. The cost optimization model is designed to choose a strategic arsenal at minimum cost in order to achieve a specified objective. The models developed accept a wide variety of weapons systems with their detailed characteristics. The size of the models generally depends on the type of problem being investigated but can be as large as desired within necessary limitations of computer capacity and running time.
Technical Note—A Note on Integer Maximization of Unimodal Functions
Authors: Washburn Alan
Published: November 2008

This note points out that it is often useful to solve an integer maximization problem in one variable through the equation f(x + 1) − f(x) = 0, even though the solution of the equation may not be an integer.
Technical Note—Computational Experience with Normed and Nonnormed Column-Generation Procedures in Nonlinear Programming
Authors: O'Neill Richard P. , Widhelm William B.
Published: November 2008

Nemhauser and Widhelm have suggested a normed variant of the Dantzig-Wolfe convex programming algorithm. The normalization explicitly occurs in the multiplier-space. There the interior point used to generate the next cut is one that maximizes the minimum slack from the present cuts to that point. Nemhauser and Widhelm suggested this normalization for two reasons. First, since the corresponding cut at worst includes the generating point, choosing that point “centered” in some geometric sense should result in a generally efficient reduction in the feasible search region. Second, cuts not active in defining the present feasibility region can affect the choice of the interior-point if norming is not applied. This note demonstrates how primal feasible points can be generated at each iteration and cites limited computational results indicating that the normed procedure is generally more efficient than the original algorithm from the standpoint of both the number of iterations and computational time.
Controlling Cutting Pattern Changes in One-Dimensional Trim Problems
Authors: Haessler Robert W.
Published: November 2008

This paper develops a formulation of the one-dimensional trim problem when there is a fixed charge associated with using a cutting pattern. The purpose of the fixed charge is to limit the number of pattern changes that must be made. Because of the large number of possible cutting patterns, the resulting problem is a combinatorial program that is far beyond the capability of existing algorithms. As a result, we develop a heuristic procedure that can be experimentally tuned to balance the potentially conflicting objectives of minimizing both trim loss and pattern changes. The heuristic procedure is organized around a sequential search that relies on descriptors of the unscheduled orders to set goals on factors such as trim loss and pattern usage for the next pattern to enter the solution. A sample problem is presented along with a discussion of the scope of the application of the heuristic procedure.
A Chance Constrained Multiple Choice Programming Algorithm
Authors: Armstrong Ronald D. , Balintfy Joseph L.
Published: November 2008

This paper considers multiple choice programming problems in which the elements of the activity matrix can be normally distributed random variables or random vectors. The truncated block enumeration method of multiple choice programming is described and used in the development of an algorithm to solve problems of this type. Deterministic inequalities computed from the means and variances are employed by the block pivoting algorithm to assure fast convergence to a (sub)optimal solution. The solution will satisfy each constraint with the required marginal probabilities, but a lower bound of the joint probabilities is also computed. As an option, problems can be solved when the lower bound of the joint probability that all the constraints are satisfied is specified alone.
Force-Ratio Considerations for Some Lanchester-Type Models of Warfare
Authors: Taylor James G. , Parry Samuel H.
Published: November 2008

This paper studies the Riccati equation satisfied by the force ratio of two homogeneous forces in deterministic Lanchester combat. This study provides qualitative insight as to the “direction” in which combat is moving (in the sense that the force ratio is changing to the advantage of one of the combatants). “Instantaneous” linear and square laws that are “local” conditions for winning are shown to apply for Lanchester-type formulations with time-varying system effectiveness. The value of considering the force-ratio equation lies in one's ability to determine the outcome of battle without explicitly solving the force-level equations, an important feature for variable-coefficient formulations. Moreover, in some cases observation of the initial time-behavior of the force ratio in a battle allows one to predict the outcome, sometimes even without explicit knowledge of attrition-rate coefficients. By additionally considering the instantaneous loss ratio, one gains insight into the consequences of concentration of forces in aimed-fire combat between two homogeneous forces with superimposed effects of supporting fires (which are not subject to attrition).
Technical Note—Optimality Conditions and Recession Cones
Authors: Abrams Robert A. , Ben-Israel Adi
Published: November 2008

Recession cones of functions and sets are characterized as intersections of directions of decrease and feasible directions, respectively. Relations between local optimality conditions and global conditions for the existence of optimal points are then studied.
Technical Note—Turning Off a Server with Customers Present: Is This Any Way to Run an M/M/c Queue with Removable Servers?
Authors: Bell Colin E.
Published: November 2008

The form of optimal policy is investigated in an average cost, infinite horizon M/M/c problem where the number of servers working can be adjusted at arrival or service completion epochs. The costs considered are linear holding costs, linear servers' wages and set-up (shut-down) charges per server turned on (off). We show that an optimal policy may call for turning one or more servers off even when there are customers for him to serve.
Technical Note—On the Stochastic Ordering of Markov Chains
Authors: Derman Cyrus , Ignall Edward
Published: November 2008

Sufficient conditions are given for one Markov chain to dominate another stochastically at all points in time.
Technical Note—Comment on “The Random Nature of Stock-Market Prices” Authored by Barrett and Wright
Authors: Aucamp Donald
Published: November 2008

The purpose of this note is to examine the notion offered by J. F. Barrett and D. J. Wright that the calculus of Ito as applied to Osborne's model of stock market price relatives leads to a more “realistic” representation of stock market behavior than does the classical calculus.
A Queuing System with Heterogeneous Servers and Autonomous Traffic Control
Authors: Lemoine Austin J.
Published: November 2008

This paper considers a multiserver queue with heterogeneous servers in which arriving customers are assigned to servers according to an autonomous Markov chain. Under conditions ensuring stability, stationary distributions are computed for the waiting times and the system response times of successive customers. Limits are also obtained for the expected system workload and the expected number of customers in the system.
Planning Horizons for the Dynamic Lot Size Model: Zabel vs. Protective Procedures and Computational Results
Authors: Lundin Rolf A. , Morton Thomas E.
Published: November 2008

Forward algorithms that solve successively longer finite horizon problems and that possess good stopping rules (such as a planning horizon) seem better suited to the needs of a manager facing a partial information environment than the more common procedure of selecting a horizon [0, T] in advance. In this light, the Wagner and Whitin forward algorithm with a planning horizon procedure for the dynamic lot size model goes far beyond computational savings. Building on additional results due to Zabel, we develop new planning horizon procedures and near planning horizon procedures. (A brief sketch of how to develop similar results for the production smoothing problem suggests that the basic methodology developed possesses some generality.) We present an extensive empirical study that reports that Wagner-Whitin planning horizons were found for a reasonably small subset of problems within 500 periods, while planning horizons, or at least near planning horizons, were found universally by the modified procedure. (The Zabel procedure was intermediate in power.) The number of periods until a “near” horizon seems to be given empirically by [Formula: see text] for the linear stationary case, where K is the setup cost, h the holding cost, and D the average demand rate. Extensions useful for a broad subset of the general concave cost case are also given.
Bounds and Transformations for Discounted Finite Markov Decision Chains
Authors: Porteus Evan L.
Published: November 2008

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

In this paper we study sensitive discount optimality criteria for finite state and action, discrete time parameter, stationary generalized Markov decision chains. We extend previous results obtained by Miller and Veinott and Veinott for substochastic transition matrices to arbitrary non-negative matrices with spectral radius not exceeding one. In particular, we generalize their policy improvement algorithm for finding a stationary policy maximizing the expected discounted reward for all sufficiently small positive interest rates.
Optimal Network Capacity Planning: A Shortest-Path Scheme
Authors: Doulliez P. J. , Rao M. R.
Published: November 2008

The sequential decision problem considered in this paper consists of finding an optimal policy for increasing the capacity of a multi-terminal network with requirements increasing over a planning period and arcs subject to failure. This problem is formulated as a shortest-route problem in a very large network and solved by Dijkstra's algorithm. Computational experience is also presented.
Technical Note—The Queue M/G/1 When Jobs Are Scheduled within Generations
Authors: O'Donovan T. M.
Published: November 2008

This note studies queuing systems in which jobs are scheduled for service within generations. Mean conditional waiting times are derived for systems where the queue discipline within each generation is shortest processing time first or processor-shared round robin.
Letter to the Editor—Remarks
Authors: Szwarc Wlodzimierz
Published: November 2008

Remarks about author's paper (Szwarc, W. 1973. Optimal elimination methods in the m × n flow-shop scheduling problem. Opns. Res. 21 1250–1259.)
Letter to the Editor—Errata
Authors: Kotiah T. C. T.
Published: November 2008

Correction of some misprints in author's paper “‘On Two-Server Poisson Queues with Two Types of Customers’ co-authored with N. B. Slater, Opns. Res. 21, 597–603 (1973).”
Minimizing Total Costs in One-Machine Scheduling
Authors: Rinnooy Kan A. H. G. , Lageweg B. J. , Lenstra J. K.
Published: November 2008

Suppose we have n jobs that arrive simultaneously to be processed on a continuously available machine that can handle only one job at a time. Each job has a fixed processing time and a cost function that is nondecreasing in its finishing time. We want to find a schedule that minimizes total costs. After reviewing the relevant work on this problem, we present a new algorithm for a general cost function. The algorithm is tested for the well known case of a weighted tardiness criterion.
Infinite Linear Programming in Games with Partial Information
Authors: Cook W. D. , Field C. A. , Kirby M. J. L.
Published: November 2008

An area of considerable recent research interest has involved the extension and modification of the basic model for two-person zero-sum game theory. One particular type of extension found in the literature involves the introduction of risk and uncertainty into the model by allowing the m × n payoff matrix A = (aij) to be a discrete random matrix that can assume a finite set of values. This paper considers both one- and two-person games and investigates the situation in which A is a discrete random matrix that can assume a countably infinite set of values {A(k)}k=1∞. We assume that the players possess certain partial information about P, the distribution of A, in which case the game problems for players 1 and 2 can be reduced to programming equivalents. We prove minimax theorems for both semi-infinite and infinite games, and give some properties of optimal mixed strategies. The paper also develops some extensions of a theorem due to Caratheodory.
A Queuing-Linear Programming Approach to Scheduling Police Patrol Cars
Authors: Kolesar Peter J. , Rider Kenneth L. , Crabill Thomas B. , Walker Warren E.
Published: November 2008

In any city the arrival rate of calls for police patrol-car service varies considerably through the day. Using queuing theory and integer linear programming, we present a method for scheduling patrol cars so that specified service standards are met at each hour of the day. Two models are used. The first is an M/M/n queuing model with time-dependent parameters that is solved numerically. The second is an integer linear program in which the decision variables are the number of patrol cars working each tour and the times at which they go out of service for meals. The program's constraints are determined by the output of the queuing model. Use of the method with data from the New York City Police Department indicates that it can lead to substantial improvements in police service.
Optimal Doubling in Backgammon
Authors: Keeler Emmett B. , Spencer Joel
Published: November 2008

This paper shows that the optimal betting strategy for a continuous model of backgammon is to double when you have an 80 percent chance of winning. We discuss the differences with the published literature on the real game and the problem of infinite expectations. The optimal strategy for a simulation of the end game is computed by dynamic programming.
Optimal Bidding in Sequential Auctions
Authors: Oren Shmuel S. , Rothkopf Michael H.
Published: November 2008

A bidder's strategy in one auction may affect his competitors' behavior in subsequent auctions. When this occurs, bidding in a sequence of auctions can be modeled fruitfully as a multistage control process. This paper presents such a model. In it the control is the bidder's strategy, the state characterizes the competitors' behavior and the state transition represents the competitors' reaction to the bidder's strategy. Dynamic programming is used to derive the infinite horizon optimal bidding strategy. We show that in steady state this optimal strategy generalizes a previous result for equilibrium bidding strategy in “one-shot” auctions.
A Stochastic Sequential Allocation Model
Authors: Derman C. , Lieberman G. J. , Ross S. M.
Published: November 2008

This paper considers the following model, described in terms of an investment problem. We have D units available for investment. During each of N time periods an opportunity to invest will occur with probability p. As soon as an opportunity presents itself, we must decide how much of our available resources to invest. If we invest y, then we obtain an expected profit P(y), where P is a nondecreasing continuous function. The amount y then becomes unavailable for future investment. The problem is to decide how much to invest at each opportunity so as to maximize total expected profit. When P(y) is a concave function, the structure of the optimal policy is obtained (§1). Bounds on the optimal value function and asymptotic results are presented in §2. A closed-form expression for the optimal value to invest is found in §3 for the special cases of P(y) = log y and P(y) = yα, for 0 < α < 1. §4 presents a continuous-time version of the model, i.e., we assume that opportunities occur in accordance with a Poisson process. Other applications of the model are also considered.
A Discrete Time Inventory Model with Arbitrary Interval and Quantity Distributions of Demand
Authors: Kao Edward P. C.
Published: November 2008

This paper considers a discrete time inventory model in which the times between successive demands and the sizes of those demands are respectively independent and identically distributed random variables. Costs considered are fixed ordering costs and proportional costs of purchase, holding, and shortage. Three types of replenishment policies are formulated as Markov renewal programs and compared. We give an illustrative example.
Technical Note—Capacity Expansion in Convex Cost Networks with Uncertain Demand
Authors: Leondes Cornelius T. , Nandi Ranjit K.
Published: November 2008

The purpose of this investigation is to suggest a simple algorithm for solving capacity expansion problems in networks with uncertain demand. We assume that the cost of expanding the capacity of each arc is a convex function and that there is a concave salvage value each arc is a convex function and that there is a concave salvage value associated with excess capacity. We adopt the two-stage programming approach but with the essential difference that our independent variable is an assumed first-stage demand. We show that the objective function of the equivalent convex program is a convex function of the assumed first-stage demand and use this fact to propose an algorithm.
Technical Note—A Vertex Ranking Procedure for Solving the Linear Fixed-Charge Problem
Authors: McKeown Patrick
Published: November 2008

Murty has suggested that the linear fixed-charge problem can be solved by ranking the vertices of the polyhedral constraint set according to their continuous objective values and then adding the fixed charges to determine an optimal solution. Several problems involving degeneracy and inequality constraints arise when one attempts to implement Murty's method directly. This note describes a method that uses the vertex ranking approach in conjunction with procedures that resolve these difficulties. We also give computational results.
A Stochastic Model of a Repairable-Item Inventory System with Attrition and Random Lead Times
Authors: Richards F. Russell
Published: November 2008

This paper examines an inventory model for a repairable-item inventory system with attrition. We allow for random demands and random lead times and, for a class of simple procurement policies, derive an exact expression for the stationary distribution of the on-hand inventory. Various measures of performance are determined, and an example is given. The model allows a variety of repair doctrines to be considered.
Technical Note—A Single-Server Queue with Service Times Depending on the Order of Services
Authors: Mine Hisashi , Ohno Katsuhisa , Koizumi Takatsugu
Published: November 2008

This note deals with a GI/G/1 queuing system with service times depending on the order of services in each busy period. We derive a sufficient condition under which the length of the first busy period starting with an arbitrary initial state is almost surely finite.
Technical Note—On the Comparison of Waiting Times in GI/G/1 Queues
Authors: Rolski Tomasz , Stoyan Dietrich
Published: November 2008

Let W1, W2 be the distribution functions of the waiting time in two queuing systems. We develop sufficient conditions for the stochastic inequalities W1(x) ≧ W2(x) and ∫0∞xdW1(x) ≦ ∫0∞xdW2(x) when both systems are of the type GI/G/1, GI/M/1 or M/G/1.
Utility Independence on Subsets of Product Sets
Authors: Fishburn Peter C.
Published: November 2008

This paper investigates conditions for utility independence in the von Neumann-Morgenstern utility context when the set of consequences is an arbitrary subset of the Cartesian product of two sets. The strongest of three increasingly stronger conditions on preferences between gambles is shown to be necessary and sufficient for utility independence when the consequence set is finite. Examples show that this condition is not generally sufficient when the number of consequences is infinite.
Technical Note—Facets and Strong Valid Inequalities for Integer Programs
Authors: Wolsey Laurence A.
Published: November 2008

We give a general result showing when a valid inequality or facet of an integer polytope can be obtained from a valid inequality or facet in a subset of the variables.
Technical Note—The Silver Anniversary of an Optimization Result in Rolling-Mill Practice
Authors: Finucan H. M.
Published: November 2008

In cutting beams or candy or rulers to a specified length, it is often sensible to make a first rough cut comfortably long and then a second exact cut. This certainly applies to the hot-rolling of steel beams, where the first cut is made as the continuous beam emerges from the rolls and the second made after straightening and cooling. The waste from odd ends is reduced if the first cut is close to the specified length, but this procedure involves the risk of an occasional beam being too short, which is serious if such a short beam is completely wasted. This last assumption is often realistic, for example, where recycling or sale as a remnant is excluded by reason of secrecy, safety, or price. The problem we solve is how to control the rough length so as to minimize the total waste. A graphical solution for a normal distribution of the rough length was published 25 years ago. Here we give an analytic solution for any distribution and a numerical realization, using standard tables, for a normal distribution.
Technical Note—A Simple Concavity Condition for a Class of Chance-Constrained Programming Problems with Joint Constraints
Authors: Bawa V. S.
Published: November 2008

We obtain a simple sufficient condition for concavity for a class of chance-constrained programming problems with joint constraints that holds for most probability distributions of interest. Our result implies that for this class of chance-constrained problems, a global optimum can be obtained by using any one of several available concave programming algorithms.
Duality in Fractional Programming: A Unified Approach
Authors: Schaible Siegfried
Published: November 2008

This paper presents a unified method for obtaining duality results for concave-convex fractional programs. We obtain these results by transforming the original nonconvex programming problem into an equivalent convex program. Known results by several authors are related to each other. Moreover, we prove additional duality theorems, in particular, converse duality theorems for nondifferentiable as well as quadratic fractional programs.
Rates of Stability in Nonlinear Programming
Authors: Stern Michael H. , Topkis Donald M.
Published: November 2008

We give conditions on a nonlinear programming problem for the set of feasible solutions to have stability on the order of a Lipschitz condition. These results then imply conditions for the optimal value of the objective function to satisfy a Lipschitz condition with respect to the right-hand side vector as well as for the set of ϵ-optimal solutions to have stability on the order of a Lipschitz condition. Results are obtained both with and without convexity assumptions.
Probabilistic Analysis of a Multicomponent Series-Parallel System under Preemptive Repeat Repair Discipline
Authors: Kodama Masanori
Published: November 2008

This paper considers a system consisting of two subsystems connected in series with a single repair facility. One subsystem consists of M identical units connected in parallel, while the other consists of several different units connected in series. The units' failure times are exponentially distributed, whereas repair times are distributed quite generally. Initially, the system is in any one of the operative states. The system breaks down if all the units in the parallel group are simultaneously in failed states or if any failure occurs in the series group. The availability and reliability function of the system are obtained simultaneously. We use a suitable transformation to deduce the reliability from the availability function. Explicit expressions for the steady-state availability of the system and the mean time to system failure are obtained. The mean time to system failure and the mean down time as new measures in equilibrium are defined and then obtained explicitly.
Cyclic Queue Models of Fleet Operations
Authors: Koenigsberg Ernest , Lam Richard C.
Published: November 2008

Fleets of liquid natural gas vessels operating between one loading and one or two discharge ports are an example of vehicles that operate in closed cycles between a small number of terminals. We extend previous work to develop a cyclic queue model that represents such fleet operations. For any specific system we obtain the expected number of vessels in each stage, the expected number waiting in each stage, and, most important, the expected waiting time in port. Exponential service time distributions are assumed, but a series of parallel simulation computations examines the effects of other distributions. The results for exponential service are obtained in closed form, so that the simulation model can be tested and the confidence interval of the simulations estimated. Both analytic and simulation results are presented for the exponential service case under several sets of system parameters. Simulation results for the same sets are presented for normally distributed service and travel times. We restrict the detailed analysis to balanced systems but discuss extensions to more general systems.
Busy Period Control of Queues Based on Waiting Times at Arrivals
Authors: Shaw Leonard
Published: November 2008

System maintenance and vehicular traffic control problems have motivated the queue control systems studied here. This article presents results for optimal assignment of servers or rejection of customers, on the basis of arriving customers' waiting times wn, when the objective function is the mean of a control penalty plus a variable such as busy period duration, number served in a busy period, or total delay to all customers in a busy period. Under the first two criteria, we generalize previous results for M/M/1 queues to similar results for the M/G/1 case. We show that the optimal customer rejection (vehicle diversion) to minimize total delay to accepted and rejected (detoured) customers is of the control-limit form for the M/G/1 case and give an explicit expression for the optimal threshold for the M/M/1 case.
Technical Note—Optimal Initial Conditions for a Simulation Problem
Authors: Madansky Albert
Published: November 2008

Suppose one simulates the M/M/1 queue for finite amount of time t, replicating the simulation N times, each time with an initial condition of n in the queue. An estimate of the mean of the steady-state distribution is the average (across replications) number in the queue at time t. We show that for large enough t an initial condition of n = 0 (in contrast to the often-conjectured initial condition n = λ/μ, the steady-state mean) minimizes mean-square error of the estimate. An example illustrates that the “large enough” t need not be very large—one-quarter the relaxation time in the example studied. An approximate tradeoff between N and t when n = 0 is also developed.
Letter to the Editor—Acknowledgment
Authors: Derman Cyrus , Ignall Edward
Published: November 2008

Professor Richard Serfozo has pointed out to us that our theorem (Derman, C., E. Ignall. 1975. On the stochastic ordering of Markov chains. Opns. Res. 23 574–576.) is not new, being essentially equivalent to theorem 2 of Kalmykov, G. I. 1962. On the partial ordering of one-dimensional Markov processes. Theor. Probab. Appl. 7 456–459.
Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/LP Approach
Authors: Geoffrion A. M. , Graves G. W.
Published: November 2008

Production orders for a number of products must be scheduled on a number of similar production lines so as to minimize the sum of product-dependent changeover costs, production costs, and time-constraint penalties. We treat the problem by a quadratic assignment algorithm with a linear programming adjustment, and describe a successful practical application for chemical reactor scheduling.
Convex Location Problems on Tree Networks
Authors: Dearing P. M. , Francis R. L. , Lowe T. J.
Published: November 2008

This paper studies problems of finding optimal facility locations on an imbedding of a finite, undirected network having positive arc lengths. We establish that a large class of such problems is convex, in a well defined sense, for all choices of the data if and only if the network is a tree. A number of useful properties of related convex functions end convex sets are identified.