bluuebunny/crossref_metadata_2025 huggingface dataset:
Air-Terminal Queues under Time-Dependent Conditions
Authors: Koopman Bernard O.
Published: November 2008

The queues formed by aircraft in stacks awaiting landing clearance have usually been treated either by machine simulation, or analytically as stochastic processes with time-independent transition probabilities (possessing stationary solutions). In contrast to such methods, the present paper regards the queue-developing process in question as strongly time-dependent, often with a diurnal (24-hour) periodicity. The formulation and treatment are entirely analytic and make use of machines only to solve the equations for the probabilities, by economical deterministic steps, using the coefficients as given in tabular form. Time-varying Poisson arrivals are assumed, and also an upper limit to queue length. Two laws of servicing are used: Poisson and fixed service time; these extremes are found to lead to numerically close results in the realistic case. This situation contrasts with the much cruder approximation of deterministic flow models. The stochastic equations belong to well studied types of differential or difference equations. When the coefficients have a 24-hour period, so does just one solution, all others approaching it. Actual airport statistics are made the basis of certain revealing computations. A perturbation method for treating multiple queues is outlined. The concrete results are exhibited as graphs.
On the Set-Covering Problem
Authors: Balas Egon , Padberg Manfred W.
Published: November 2008

This paper establishes some useful properties of the equality-constrained set-covering problem P and the associated linear program P′. First, the Dantzig property of transportation matrices is shown to hold for a more general class of matrices arising in connection with adjacent integer solutions to P′. Next, we show that, for every feasible integer basis to P′, there are at least as many adjacent feasible integer bases as there are nonbasic columns. Finally, given any two basic feasible integer solutions x1 and x2 to P′, x2 can be obtained from x1 by a sequence of p pivots (where p is the number of indices j ϵ N for which xj1 is nonbasic and xj2 = 1), such that each solution in the associated sequence is feasible and integer. Some of our results have been conjectured earlier by Andrew, Hoffmann, and Krabek in a paper presented to ORSA in 1968.
Parametric Network Flows
Authors: Minieka Edward
Published: November 2008

This paper considers a directed capacitated network in which the supply at each source node and the demand at each sink node is a linear function of a parameter t. It presents two algorithms that determine the range of values for the parameter t; they correspond to the primal and dual linear-programming algorithms that solve this problem. The dual algorithm appears to have a simpler structure.
Technical Note—Equivalent Payload Nomogram
Authors: Matlin S.
Published: November 2008

This note describes a nomogram that provides a rapid approximation of equivalent yield, equivalent hard-point-target kill capability, and yield-hardness-accuracy trade-offs associated with nuclear missiles.
On Multi-Commodity Maximal Dynamic Flows
Authors: Bellmore Mandell , Vemuganti Ramakrishna R.
Published: November 2008

Ford and Fulkerson have shown that a single-commodity maximal dynamic flow can be obtained by solving a transshipment problem associated with the static network and thereby finding the maximal temporally repeated dynamic flow. This flow is known to be an optimal dynamic flow. However, this result cannot be extended to the multi-commodity maximal dynamic flow problem. This paper shows that, for sufficiently large number of time periods, the difference between the multi-commodity maximal dynamic flow and the temporally repeated multi-commodity flow is bounded by a constant. In addition, it calculates this bound.
Concave Programming Applied to a Special Class of 0-1 Integer Programs
Authors: Glover Fred , Klingman D.
Published: November 2008

This paper connects some of the recent developments in concave and integer programming. In particular, it points out parallels between the work of Hoang Tui and R. D. Young. From these methods, a finite algorithm for solving a special class of 0-1 integer programs is developed. Our approach contrasts with an earlier extension of Tui's method due to M. Raghavachari and general “intersection” or “convexity” cut approaches.
The Generalized Lattice-Point Problem
Authors: Glover Fred , Klingman D.
Published: November 2008

The generalized lattice-point problem, posed by Charnes and studied by M. J. L. Kirby, H. Love, and others, is a linear program whose solutions are constrained to be extreme points of a specified polytope. We show how to exploit this and more general problems by convexity (or intersection) cut strategies without resorting to standard problem-augmenting techniques such as introducing 0-1 variables. In addition, we show how to circumvent “degeneracy” difficulties inherent in this problem without relying on perturbation (which provides uselessly shallow cuts) by identifying nondegenerate subregions relative to which cuts may be defined effectively. Finally, we give results that make it possible to obtain strengthening cuts for problems with special structures.
The Generalized Penalty-Function/Surrogate Model
Authors: Greenberg Harvey J.
Published: November 2008

This paper combines the monotonic-penalty-function and surrogate models into a general model called the penalty-function/surrogate model. It unifies and generalizes the central theorems of earlier papers, and provides some new theorems that can be specialized to the Lagrangian penalty-function model (GLM) or to linear surrogates.
Computing Optimal Solutions for Infinite-Horizon Mathematical Programs with a Transient Stage
Authors: Grinold Richard C. , Hopkins David S. P.
Published: November 2008

This paper studies multistage mathematical programs with an arbitrary transient phase followed by an infinite stationary phase with linear constraints and objective. It presents conditions tinder which a derived linear program will determine an optimal solution to the infinite problem. These conditions are general and may be validated by simple algebraic tests (perhaps solving a finite linear program). No topological restrictions are placed on the model.
Directional Derivatives for Extremal-Value Functions with Applications to the Completely Convex Case
Authors: Hogan William
Published: November 2008

Several techniques in mathematical programming involve the constrained optimization of an extremal-value function. Such functions are defined as the extremal value of a related parameterized optimization problem. This paper reviews and extends the characterization of directional derivatives for three major types of extremal-value functions. The characterization for the completely convex case is then used to construct a robust and convergent feasible direction algorithm. Such an algorithm has applications to the optimization of large-scale nonlinear decomposable systems.
A Generalized Approach to Dantzig-Wolfe Decomposition for Concave Programs
Authors: Holloway Charles A.
Published: November 2008

The Dantzig-Wolfe decomposition procedure for concave programs can be viewed as inner linearization followed by restriction. This paper presents an approach that allows selective inner linearization of functions and utilizes a generalized pricing problem. It allows considerable flexibility in the choice of functions to be approximated using inner linearization. Use of the generalized pricing problem guarantees that strict improvement in the value of the objective function is achieved at each iteration and provides a termination criterion that is both necessary and sufficient for optimality. A specialization of this procedure results in an algorithm that is a direct extension of the Dantzig-Wolfe decomposition algorithm.
A Graph-Theoretic Equivalence for Integer Programs
Authors: Picard Jean-Claude , Ratliff H. Donald
Published: November 2008

This paper is concerned with the relation between 0-1 integer programs and graphs. An equivalence is established between solving 0-1 integer programs with quadratic or linear objective functions and solving a cut problem on a related graph.
Some Properties of Generalized Concave Functions
Authors: Thompson W. A. , Parke Darrel W.
Published: November 2008

This paper examines properties and interrelations of several concepts of generalized concavity. It shows that the class of functions that are both “generalized concave” and “generalized convex” is closely related to the class of monotone functions of a single variable. After excluding a certain small class of exceptions, the paper shows that, for arbitrary (perhaps not differentiable) functions, concave implies pseudoconcave, pseudoconcave implies strictly quasiconcave, and strictly quasiconcave implies quasiconcave. Several results characterizing the extreme values of generalized concave functions are given.
Technical Note—A Note on the Group Theoretic Approach to Integer Programming and the 0-1 Case
Authors: Balas Egon
Published: November 2008

While the group-theoretic approach is in many ways useful for 0-1 problems too, in this latter case the sufficient condition given by Gomory for a solution to the group problem to solve the initial integer program is never satisfied. This underscores the need to use information about the constraints that are slack at the linear programming optimum.
Technical Note—An Application of Witzgall’s Algorithm to a Problem in Radar Signal Design
Authors: Chapoton C. W.
Published: November 2008

The problem of finding a binary pulse-compression code with arbitrary side-lobe levels is cast as a quadratically constrained integer program. Witzgall's algorithm is then applied, after a suitable manipulation, to put the constraints into a convex form.
Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning
Authors: Faaland Bruce
Published: November 2008

The value-independent knapsack problem is solved by considering a related problem in the theory of partitions of numbers. The solution technique is compared to standard algorithms for the knapsack problem.
Technical Note—Conditions for Global Optimality in Nonlinear Programming
Authors: Falk James E.
Published: November 2008

This note presents necessary and sufficient conditions for a point x* to be a global solution of the problem of maximizing f subject to x ∈ S. The conditions are equivalent to the divergence or convergence of an infinite sequence, each of whose terms involves the integral of a power of f taken over S. A useful corollary is derived that characterizes the sequence as one that is eventually monotone increasing if and only if x* is not a global solution. A small example illustrates these results.
Technical Note—The Set-Covering Problem with Equality Constraints
Authors: Guha D. K.
Published: November 2008

The list of reduction rules in a set-covering problem with equality constraints is augmented here by additional rules. Computational experiences on the effect of these new rules along with the old ones are discussed.
Technical Note—The Use of Cuts in Complementary Programming
Authors: Ibaraki Toshihide
Published: November 2008

A complementary programming problem is a linear programming problem with the additional restriction that xp xq = 0 holds for each specified pair (xp, xq). This paper obtains constraints called C-cuts from the restriction xp xq = 0, and uses them to facilitate the computation of the branch-and-bound procedure proposed in an earlier paper [Opns. Res. 19, 1523–1528 (1971)]. Some computational results are also reported.
Technical Note—Maximal Funnel-Node Flow in an Undirected Network
Authors: Jarvis John J. , Miller Duane D.
Published: November 2008

This note formulates, examines, and solves a funnel-node maximal-flow problem for an undirected network. The solution procedure requires only applications of the single-commodity flow algorithm, and is therefore extremely efficient. Several applications are presented.
Technical Note—Comments on the “Classical” Derivation by Taha and Curry of Optimality Conditions in Linear Programming
Authors: Raike William M. , Taylor James G.
Published: November 2008

This note points out some deficiencies in a recent paper [Opns. Res. 19, 1045–1050 (1971)] concerning the classical derivation of optimality conditions in linear programming.
Technical Note—Some Comments on “Linear” Programming with Absolute-Value Functionals
Authors: Rao M. R.
Published: November 2008

This note gives simple and straightforward reasoning for obtaining the results of Shanno and Weil [Opns. Res. 19, 120–124 (1971)] for linear programming with absolute-value functionals.
An Applicable Model of Optimal Marketing Policy
Authors: Kohn Meir G. , Plessner Yakir
Published: November 2008

This paper presents a marketing model designed to find the revenue-maximizing allocation of a set of interrelated products over space and time, when demand, represented by a relation in which price at time t is a function of quantities in the same period, involves lagged prices. The technique used is the discrete maximum principle and it is proved that the solution derived using this technique is optimal. The method of application is discussed, as well as some computational aspects, and some of the results of the actual application are reviewed.
The Progress of Management-Science Activities in Large US Industrial Corporations
Authors: Radnor Michael , Neal Rodney D.
Published: November 2008

On the basis of a field survey involving a sample of 108 US firms, this paper analyzes the progress of management-science activities. In large corporations through December 1970; it extends the findings of a 1968 paper by our research team [Opnal. Res. Quart. 19, 117–141 (1968)]. Here we describe changing trends in such key areas as: types of personnel performing and leading OR/MS, organizational location of management science, project-portfolio characteristics, problems and success with implementation, formalization processes, communication problems, the role of top management, and the general diffusion of OR/MS skills within organisations. Finally, we draw a general conclusion that OR/MS is in a “success” phase of its developmental history.
The Relation between Formal Procedures for Pursuing OR/MS Activities and OR/MS Group Success
Authors: Neal Rodney D. , Radnor Michael
Published: November 2008

This paper examines the relation between the formalization of OR/MS procedures and OR/MS group success in more man 100 large US industrial organizations. The research gathered evidence on the existence of a formal charter for the OR/MS group and on the use of formalized project procedures. After developing an idealized set of ten procedural phases for projects, we used them as a guide in determining the degree of procedural elaboration followed by each OR/MS group. We recorded various measures of success and used them to show a strong correlation between proceduralization and success, in terms of these measures. We examined the effects of several other behavioral and environmental variables on this relation: the orientations of the OR/MS manager, top-management behavior, OR/MS-group age and size, and OR/MS diffusion within the organization. Finally, we note the possibility that proceduralization may be either, or both, a cause or an indicator of OR/MS success.
Maximal, Lexicographic, and Dynamic Network Flows
Authors: Minieka Edward
Published: November 2008

This paper proves two properties of maximal network flows: (1) If there exist a maximal network flow with a given departure pattern at the sources and a maximal flow with a given arrival pattern at the sinks, then there exists a flow that has both this departure pattern at the sources and this arrival pattern at the sinks. (2) There exists a maximal dynamic network flow that simultaneously has a latest (earliest) departure schedule at the sources and an earliest (latest) arrival schedule at the sinks. The paper modifies Ford and Fulkerson's maximal dynamic flow algorithm to construct a maximal dynamic network flow with a latest departure schedule and an earliest arrival schedule.
On Two-Server Poisson Queues with Two Types of Customers
Authors: Kotiah T. C. T. , Slater N. B.
Published: November 2008

This paper considers two schemes for a steady-state queue with two types of customers served by two desks, the customers arriving mixed in a Poisson stream and having negative-exponential service-time distributions, with different means characterizing the two types of customers. In Scheme I each type has a particular desk, for which he queues on arrival. In Scheme II all customers keep in a single queue and proceed indifferently to either desk. Numerical remits indicate that Scheme II reduces mean queue size and queuing times, generally with advantage to both types of customers.
A Queuing-Type Birth-and-Death Process Defined on a Continuous-Time Markov Chain
Authors: Yechiali Uri
Published: November 2008

This paper considers an n-phase generalization of the typical M/M/1 queuing model, where the queuing-type birth-and-death process is defined on a continuous-time n-state Marker chain. It shows that many models analyzed in the literature can be considered special cases of this framework. The paper focuses on the steady-state regime, and observes that, in general, closed-form results for the limiting probabilities are difficult to obtain, if at all possible. Hence, numerical methods should be employed. For an interesting special case, explicit results are obtained that are analogous to the classical solutions for the simple M/M/1 queue.
On the Ergodic Theory of Markov Chains
Authors: Marlin Paul G.
Published: November 2008

This paper presents results in the ergodic theory of Markov chains that are useful in certain cases where the well known theory of Foster and Pakes is not applicable. The paper gives the background leading to the results, describes their significance, proves two theorems, and presents an example. The conditions for ergodicity are based on the notion of conditional single transition displacement of a Markov chain due to Pakes.
Technical Note—Distribution of the Mean Queue Size for the Time-Dependent Queue
Authors: Ali H.
Published: November 2008

This paper derives the Laplace-Stieltjes transform of the mean queue size for the time-dependent GI/G/1 queue, with an arrival at t = 0. It also obtains the probability of the queue being empty at time t. These results are based on the departure process for this queue.
Technical Note—How to Win by Losing
Authors: Silverman David , Schwartz Benjamin L.
Published: November 2008

Can it ever be advantageous for a football team intentionally to lose or tie a game that it could otherwise win? This paper cites real-life examples from the 1971 NFL season when such situations apparently arose. These stem from the league rule admitting a second-place team (“wild card”) to the playoffs in each conference. Even without such a rule, however, similar paradoxes could occur. These are based on the assumption (generally conceded to be true) that team-over-team advantages in individual games are not necessarily transitive. The examples assume that tie games are omitted in figuring final standings, and ties in the standings are settled by playoffs. Using Markov-chain methods, a set of decision rules is derived to tell a team whether or not to play for a win. A convenient graphical form of presentation of these rules is given.
Optimal Stopping in a Discrete Search Problem
Authors: Chew Milton C.
Published: November 2008

In a search among m locations for an object possibly hidden in one, we are given prior probabilities of location pi, searching costs ci, and overlook probabilities αi. It is known also that an “unsearchable” location contains the object with prior probability p0, and, in addition, a penalty cost C is charged if the search is terminated unsuccessfully. Although an optimal search strategy for the problem is known, the best stopping rule is not. Under a certain constraint on C, independent of the prior probabilities pi, the optimal stopping rule is shown to be determined by the optimal m-stage look-ahead strategy.
Efficient Operation of Optional-Priority Queuing Systems
Authors: Bell Colin E.
Published: November 2008

This paper studies an M/G/1 queuing system with two classes of customers. The cost per unit time of holding a customer differs for the two classes. The server has the option of serving the first customer in line at no extra charge or paving a fee to earn the right to serve any higher-class customer further back in the queue. The paper finds an optimal policy for the simple case where this fee is independent of the position in the queue of the promoted customer. For the case where the server is restricted to serving either the first customer or the first higher-class customer further back in the queue, an appealing conjectured form of an optimal policy is shown to be invalid.
Loss Systems with Mixed Renewal and Poisson Inputs
Authors: Kuczura A.
Published: November 2008

When two independent streams of customers compete for the same servers, as happens for example when first-routed and overflow traffic streams share a single trunk-group, the state of the system seen by the two different types of arriving customers will in general be different. In a loss system with mixed renewal and Poisson inputs, the blocking experienced by the renewal-type customers can be markedly different from that seen by the Poissonian customers. This paper derives the distribution of the number of busy servers seen by the two streams, and outlines a numerical procedure for computing the distributions. Examples of blocking probabilities for two cases of the renewal stream are given.
A Comparison of Two Personnel Prediction Models
Authors: Marshall Kneale T.
Published: November 2008

This paper describes, compares, and contrasts two mathematical models of personnel movement through a hierarchical organization. The first model is a Markov chain, which is described in detail in other literature. The emphasis in this paper is on a cohort model based on people's lifetime behavior in the system. Data from student enrollments is used in comparing the models, and predictions are made and compared with numbers from real situations.
Variable-Work Models for Predicting Course Enrollments
Authors: Balachandran K. R. , Gerwin Donald
Published: November 2008

Most higher-education enrollment-forecasting models have been developed to make predictions at the university level or higher. However, this paper discusses some models for forecasting individual course enrollments within departments. They are based on the concept of work; that is, the number of students who have yet to take a given course. We first present a conceptual model that serves as a framework within which our approach can be understood, and then discuss three variations meant to be applied in actual situations. The first two variations were subjected to tests using data from a graduate-level program. Both fared better than various naive alternatives. The more sophisticated of the two demonstrated some improvement over the other, but not in all cases.
Technical Note—Minimizing Average Flow Time with Parallel Machines
Authors: Horn W. A.
Published: November 2008

This note shows that the assignment and sequencing of single-operation jobs in a parallel-machine environment can be formulated as an assignment problem. Means for reducing the size and computational difficulty of this problem are identified.
Technical Note—Elimination of Suboptimal Actions in Markov Decision Problems
Authors: Grinold Richard C.
Published: November 2008

This note points out that upper and lower bounds on the optimal value function of a finite discounted Markov decision problem can be computed easily when the problem is solved by linear programming or policy iteration. These bounds can be used to identify suboptimal actions.
Letter to the Editor—Comments on a Blood-Bank Inventory Model of Pegels and Jelmert
Authors: Jennings John B. , Kolesar Peter
Published: November 2008

A paper by C. Carl Pegels and Andrew E. Jelmert [Opns. Res. 18: 1087–1098 (1970)], entitled “An Evaluation of Blood-Inventory Policies: A Markov Chain Approach,” has drown two comments by John B. Jennings and by Peter Kolesar.
Letter to the Editor—Comments on a Letter by Woolsey
Authors: Beer Stafford , Charnes A. , Cooper W. W. , Mellon B. , Woolsey R. E. D.
Published: November 2008

A Letter by R. E. D. Woolsey [Opns. Res. 20, 729–737 (1972)] entitled “Operations Research and Management Science Today, or, Does an Education in Checkers Really Prepare One for a Life of Chess?” has drawn some responses.
Theory of Measures of Effectiveness for General-Purpose Military Forces: Part I. A Zero-Sum Payoff Appropriate for Evaluating Combat Strategies
Authors: Pugh George E. , Mayberry John P.
Published: November 2008

Difficulties encountered in a number of past force-procurement studies for general-purpose forces have been traced, in large measure, to problems in defining the objectives for such forces. In this paper, we develop a rationale for selecting a specific zero-sum payoff function to compare alternative combat strategies. The development is motivated by analogy with the Nash bargaining solution for non-zero-sum two-person games [Econometrica 21, 128–140 (1953)]. Our objectives are to relate known mathematical techniques and game-theory concepts to the problem of evaluating the effectiveness of general-purpose military forces, and thus to bridge the gap between theoreticians and practical planners. This paper is the first in a series devoted to the development of a more consistent analysis framework.
An Allocation Problem of Support Fire in Combat as a Differential Game
Authors: Kawara Yasushi
Published: November 2008

This paper analyzes as a differential game the problem of allocating support fire between two different targets (the enemy primary units and support units) in a combat. It assumes that the game begins when one side's primary units start the advance on the enemy, and that the game ends when they come in contact with the enemy primary units. The paper also examines the relation between the value of the game and its duration.
Variance Reduction by Antithetic Variates in GI/G/1 Queuing Simulations
Authors: Mitchell Bill
Published: November 2008

This paper considers the use of antithetic variates to reduce the variance of estimates obtained in the simulation of a GI/G/1 queue. Two experimental configurations are considered: in the first, 2n observations are taken in a single run; in the second, n observations are taken in each of two runs. If the sequences of uniform random variables that generate the realizations of the queuing system in the two runs are antithetic, we show that the variance of estimates of the mean and distribution of stationary waiting time and number in the queue is less in the second configuration than in the first. We also obtain sufficient conditions for the covariance of functions of a vector of uniform random variables to be nonnegative. Experimental results are given for M/M/1 queuing simulations to illustrate the magnitude of the variance reduction.
Labor Displacement and Air-Pollution Control
Authors: Kohn Robert E.
Published: November 2008

Economic efficiency and minimizing labor displacement may be mutually unattainable goals in regional air-pollution control planning. This paper develops a model in which pollution-control methods are characterized by regional labor-displacement coefficients as well as conventional cost coefficients. It employs the lexicographic technique, minimizing first the economic cost and then the labor displacement required to achieve a specific set of air-quality goals for the St. Louis airshed in 1975. Some meaningful shifts in the vector of optimal control methods are observed in this sequence. However, some limitations in the lexicographic method become apparent in the analysis.
Planning the 41st ORSA Meeting: The Visiting-Fireman Problem, I
Authors: Beckwith Richard E.
Published: November 2008

A polling technique based on subjective probabilities was employed to produce advance estimates of the number of ORSA members attending the 41st National Meeting. The predicted figures compare favorably with the actual attendance figure, tending to support the credibility of such an approach. Action taken as a consequence of the poll’s forewarning is believed to have had a significant salutary effect on the financial health of the meeting.
Asymptotic Linear Programming
Authors: Jeroslow Robert G.
Published: November 2008

This paper studies the linear programming problem in which all coefficients (even those of the stipulations matrix) are rational functions of a single parameter t called “time,” and provides an algorithm that can solve problems of the following two types: (1) Steady-state behavior [the algorithm can be used to determine the functional form x(t) of the optimal solution as a function of t, this form being valid for all “sufficiently large” values of t], and (2) sensitivity analysis [if a value t0 of “time” is given, the algorithm can be used to determine the two possible functional forms of the optimal solution for all values of t “sufficiently close” to t0 (the first functional form valid for t < t0, the second for t < t0)]. In addition, the paper gives certain qualitative information regarding steady-state behavior, including the following result: If for some one of the properties of consistency, boundedness, or bounded constraint set, there exists a sequence tn ↗ +∞ such that the linear program at n has this property for all n, then the program has this property for all “sufficiently large” values of t.
Technical Note—Decomposition Techniques for the Chebyshev Problem
Authors: Blau Roger A.
Published: November 2008

This note investigates a decomposition procedure for the problem of maximizing the minimum of a finite number of functions over a common domain. Results, in the form of nonlinear programming subproblems with linear contraints, are obtained for two different classes of functions with domains defined by convex polyhedra. The relation between the subproblems for both classes of functions is shown.
Technical Note—Maximum and Minimum Service Times for Batches of Jobs with an Unknown Number of Servers
Authors: Scheuer Ernest M.
Published: November 2008

We consider the maximum and minimum times to service all jobs in a batch of random size at a facility having an unknown number of servers, where all servers have the same service-time distribution, and the batch size N and the service times {Ti, i = 1, 2, …, N} are mutually independent random variables. For arbitrary service-time distribution and arbitrary batch-size probability mass function, the batch service time is bounded above by ∑i=1i=NTi and below by max{Ti, i = 1, 2, …, N}. We obtain the expected minimum batch service time for the special cases of exponential and uniform service-time distributions, and Poisson, binomial, and negative-binomal probability mass functions for batch size. Separate results are stated for the batch size restricted to be positive.
Optimal Replacement Rules when Changes of State are Semi-Markovian
Authors: Kao Edward P. C.
Published: November 2008

This paper investigates the use of a discrete-time semi-Markov process to model a system that deteriorates in usage. Replacement rules that are (1) state-dependent, (2) state-age-dependent, and (3) age-dependent are proposed. The system operating costs and replacement costs are functions of the underlying states. The optimization criterion is the expected average cost per unit time. Under the first two replacement rules, the paper generates semi-Markov decision processes so that optimal policies can be obtained by the policy-iteration method. Sufficient conditions for the existence of an optimal control-limit state-dependent replacement rule are derived. For the age-dependent policy, the objective function is obtained so that the minimization can be carried out over the integers. An illustrative example is given at the end.
Optimal Elimination Methods in the m × n Flow-Shop Scheduling Problem
Authors: Szwarc Wlodzimierz
Published: November 2008

For solving the flow-shop scheduling problem, this paper examines elimination techniques that reduce the set of solutions to a subset that must contain the optimal solution being sought. The paper shows (1) that the elimination method of Szwarc [Naval Res. Log. Quart. 18, 295–305 (1971)] removes at least as many solutions as any other method, and is therefore optimal, and (2) how to construct a general counterexample to any procedure that removes more sequences than this optimal method.
A Heuristic Search Procedure for Estimating a Global Solution of Nonconvex Programming Problems
Authors: Hesse Rick
Published: November 2008

This paper develops a penalty function and several techniques for searching nonconvex areas for a global optimum and presents numerical results for several small though very difficult nonconvex programming problems. No proofs of convergence have been obtained, nor has it been possible to categorize the types of problems for which these techniques are successful.
Decision Analysis and Medical Malpractice
Authors: Forst Brian E.
Published: November 2008

Normative decision theory has been applied to the problem of evaluating alternative diagnosis-treatment strategies. The courts rely on a different set of doctrines in performing the same sort of evaluation. This paper investigates the differences. It is suggested that the alleged “malpractice crisis” results largely from the application of a set of ambiguous and mutually inconsistent medico-legal principles such as “reasonable medical certainty,” “standards of good medical practice in the community,” and “proximate cause.” The expected utility criterion of decision analysis is proposed as an alternative to this melange, both for the purposes of establishing the existence of negligence and for determining the proper amount of compensation.
The Expected Number of Visits to State k before a Total System Failure of a Complex System with Repair Maintenance
Authors: Nakagawa Toshio
Published: November 2008

This paper investigates the stochastic behavior before a total system failure for a standby redundant system with repair maintenance. It derives the expected number of visits to state k before a total system failure and other measures explicitly by considering “taboo” probabilities for an imbedded Markov chain generated by the system. The transition probabilities and the first-passage distributions are also discussed. Numerical examples are presented.
Iteration Skipping in Primal Integer Programming
Authors: Arnold Larry R. , Bellmore Mandell
Published: November 2008

An examination of computational results using the simplified primal integer programming algorithm of Glover reveals the existence of long sequences of iterations following a specific pattern. This paper examines the structure of these sequences so that both the termination of a sequence and the tableau at that point can be predicted. It then constructs an algorithm that exploits this structure by performing the iterations of the sequence implicitly and presents computational results.
A Generated Cut for Primal Integer Programming
Authors: Arnold Larry R. , Bellmore Mandell
Published: November 2008

This paper develops a new cutting plane for primal integer programming. This cut, when it exists and is vised as pivot row, has the property that the minimum of the simplex evaluators of the next tableau is strictly larger (by an integer) than the minimum for the current tableau. The paper gives a sufficient condition in the form of a linear program for the existence of such a cut, and proposes an algorithm for generating such cuts. It also presents two additional sufficient conditions. The process of cut generation is then imbedded into a convergent primal algorithm to be used in an attempt to overcome the proof-of-optimality problem experienced with the primal algorithm.
A Flexible Enumeration Scheme for Zero-One Programming
Authors: Ellwein Leon B.
Published: November 2008

Each of the main enumerative methods for zero-one programming has a drawback: the branch-and-bound (multi-branch) approach may require an inordinate amount of storage capacity and the backtrack implicit-enumeration (single-branch) approach circumvents this storage problem only by restricting the flexibility of the search. This paper outlines an implicit-enumeration scheme that, while maintaining a low storage requirement, allows the same flexibility in backward branching (backtracking is no longer mandatory) as we commonly have in forward branching. Preliminary computational results are presented.
Technical Note—The Random Nature of Stock-Market Prices
Authors: Barrett J. F. , Wright D. J.
Published: November 2008

This note suggests that the behavior of stock-market prices may be modelled by using a stochastic differential equation given the interpretation due to Ito rather than that of ordinary calculus. The workings of the stock market are shown to conform intuitively to this interpretation; an important conclusion is that the observed rise in stock prices can be attributed to deterministic effects. Under ordinary calculus this rise can be explained as due to purely random disturbances.
Technical Note—The Optimal Dual Solution in Linear Fractional Decomposition Problems
Authors: Kornbluth J. S. H. , Salkin G. R.
Published: November 2008

This paper shows that the final solutions to the executive and divisional programs in a linear fractional decomposition furnish the complete primal and dual solutions; it extends the proofs already presented for the linear decomposition problem.
Errata
Authors: Erlenkotter Donald
Published: November 2008

Correction to Erlenkotter, D. 1970. The sequencing of expansion projects. Western Management Science Institute Working Paper No. 166, University of California, Los Angeles, November.
A Two-Cell Model of Search for a Moving Target
Authors: Dobbie James M.
Published: November 2008

This paper formulates a two-cell model of search for a moving target as a continuous-time Markov process with known constant transition rates and detection rates, and finds the distribution of searching effort that maximizes the probability of detection in time T, and the distribution that minimizes the expected time to detection. Although the optimization problems are difficult to solve, the solutions are simple. It appears to be possible, but difficult, to generalize this model to n cells.
An Analytical Approach to a Class of Battles
Authors: Mjelde Kåre M.
Published: November 2008

This paper shows that analytical techniques can be applied in the analysis of a wide class of combat problems by specializing the inputs of a general functional model. The generating functions of the losses, and the corresponding expected values and variances, are derived and expressed as integrals with respect to a supplementary time variable.
A Model for Managing a Family-Planning System
Authors: Urban Glen L.
Published: November 2008

This paper describes a planning model designed to be used by managers of family-planning systems to improve understanding, forecasting, and planning. The macro-flow model describes the patient movement through post-partum and nonpost-partum programs. The flows model the phenomena of: outreach recruitment, continuance, post-partum checkups, switching methods, referral, migration, contraceptive-use experience, private protection, method effectiveness, advertising response, follow up, abortion, and medical services. Strategic variables can be linked to the flow parameters to produce capacity requirements and budgetary implications. The model output includes benefit measures of total active patients, couple years of protection, “births protected,” and unwanted births prevented. The fertility aspects of births prevented are modeled through a nonstationary Markov process submodel that considers demographic phenomena without burdening the basic flow structure. The input procedures used to process patient-visit, outreach, clinic-survey, and experimental data are discussed and some empirical results are reported. The combination of data-based estimates and subjective judgment is done by “fitting” the model to past observed data. Testing and control are done by “tracking” model performance through conditional prediction, diagnosis, and updating. The model is implemented in an on-line, conversational program that facilitates evolutionary model building by allowing the user to specify his model options. The application and testing of the model in the Atlanta Area Family Planning System are discussed and the experiences of managers in using the model to gain new insights, forecasts, budgets, and plans are reported.
Markov Duels
Authors: Barfoot C. Bernard
Published: November 2008

Markov duels are a general class of stochastic duels in which each weapon has Markov-dependent fire, that is, the outcomes of shots by each weapon form a Markov process. This paper develops duel models for the situation in which the outcomes form a finite stationary Markov chain and both weapons have an unlimited supply of ammunition, fire at constant intervals of time, and duel until one is killed. Based on these assumptions, the probability of a given side winning the duel is obtained for two sets of starting conditions: (1) both weapons begin with unloaded weapons and have tactical equity, and (2) one weapon has the advantage of surprise and can fire y rounds at the other before the two-sided duel begins, where y is a random variable with a geometric distribution. The mean and variance of the number of rounds to kill a passive target are also derived and two example duels are solved. Finally, methods are indicated for obtaining the solution to a Markov duel between weapons having exponential firing times and either fixed, limited ammunition supplies or infinite supplies.
Queuing Models with Lane Selection: A New Class of Problems
Authors: Schwartz Benjamin L.
Published: November 2008

This paper presents a new class of queuing models. There are n distinct types of customers and n distinct types of service facilities. Some customers can be processed at any service facility, but other customer types can only use selected ones among the service-facility types. This class of model is named “lane selection,” abbreviated LS, since the arriving customers with some freedom of choice must select the queue, or lane, in which they are to be processed through the system. It is shown by example that many physical situations are represented more accurately by this model than by more conventional ones. However, in analysis, the LS concept raises many theoretical difficulties. For a number of special cases, this paper obtains in explicit form as functions of the model parameters the mean queue lengths and waiting times for the different classes of customers.
A Bounding Minimization Problem for Primal Integer Programming
Authors: Arnold Larry R. , Bellmore Mandell
Published: November 2008

Computational experiments with the primal integer programming algorithm indicate that in many cases the optimal value of the objective function is obtained in a very few iterations but a large number of iterations are required to establish optimality; thus, an alternative proof of optimality is needed. This paper describes an algorithm for obtaining an upper bound (such an alternative) on the value of the objective function. This bound is based on the best bound obtainable from dual solutions to a class of related linear programs. Computational results illustrating the effectiveness of this bounding technique are presented.
A Procedure for Optimal Stepwise MSAE Regression Analysis
Authors: Roodman Gary M.
Published: November 2008

This paper brings together two topics from regression analysis. One is the topic of stepwise regression, a set of commonly used procedures for exploring alternative formulations of the regression model. The other topic is regression by minimizing the sum of the absolute errors about the regression line (MSAE). This technique has been found, in a variety of circumstances, to be more attractive than the traditional least-squares method. The paper presents a procedure for selecting from among m regressors the best sets of k, k + 1, … and m regressors according to the MSAE criterion (k ≦ m). Building upon the well known linear-programming formulation of the MSAE problem, the paper develops a partial enumerative search scheme, in which a set of distinct, but related, combinatorial optimization problems (corresponding to determination of “best k,” “best k + 1,” etc.) are, in effect, solved simultaneously.
Technical Note—Parameter Estimation from Cross-Sectional Observations on an Elementary Queuing System
Authors: Aigner Dennis J.
Published: November 2008

This note reports on and compares the asymptotic sampling properties of several alternative estimators for the parameters of a simple M/M/1 queuing system, assuming that data are available on a random sample of identical systems.
Technical Note—A Multiserver Queue with No Passing
Authors: Washburn Alan
Published: November 2008

This note deals with a queuing situation where customers must leave the system in the same order in which they arrive, owing to a physical constraint that prohibits passing. Poisson input and (basically) exponential service times are assumed, and the mean waiting time in the steady state is derived.
Faculty Early-Retirement Programs
Authors: Hopkins David S. P.
Published: November 2008

This paper formulates a demographic flow model that can be used to analyze the effects of university early-retirement policies on faculty appointment rates and rank and age distributions. In addition, it discusses a specific early-retirement plan designed to induce less productive older members of a faculty into voluntary withdrawal while offering significantly less encouragement to their more productive colleagues. The model is then used to examine the extent to which this plan is likely to achieve its intended results, namely an increase in the flow rate of new appointments, a reduction in the number of older faculty members in service, and a reduction in total personnel costs. Both short-run and equilibrium effects are analyzed with specific reference to the situation at Stanford University.
Technical Note—A Note on Cost Estimation and the Optimal Bidding Strategy
Authors: Beckmann Martin J.
Published: November 2008

This note determines the optimal bid price for a firm bidding against several other firms for a contract, when each firm knows the expected value of its own cost and a probability distribution of the other firms' cost. The optimal bid price is calculated as a function of the firm's own expected cost, first for the case of two identical firms and then for several firms.
Technical Note—Price and Production Decisions with Random Demand
Authors: Thomas L. Joseph
Published: November 2008

This note studies the problem of setting price and production levels simultaneously in a series of N periods, where price is a parameter in the probability distribution of demand. It develops a simple policy characterized by two stock levels and an optimal price line in the price-inventory plane, gives an algorithm to compute such a policy and check conditions for its optimality, and presents a counterexample to the simple policy, using a small set of allowable prices, along with a discussion of both the counterexample and some characteristics of the model.