bluuebunny/crossref_metadata_2025 huggingface dataset:
Approximate Analysis of a Hierarchical Queuing Network
Authors: Willemain Thomas Reed
Published: November 2008

A hierarchical queuing network is a layered network of queues in which all arrivals receive initial service from a primary server, and some customers receive additional service jointly from a primary and a secondary server. This paper considers the simplest such network, involving two levels and a single secondary server who functions as a consultant to several primary servers and always works in conjunction with the primary server who refers the customer to him. An approximate analysis of this hierarchical queuing network is carried out for three operating disciplines governing the consultation process. The analytical results compare favorably with the results of computer simulations and are therefore used to explore several important issues in the design of such networks. Hierarchical queues are common in public-service systems, including new medical-care systems known as “telemedicine.”
Technical Note—Distribution of Attained and Residual Service in General Queuing Systems
Authors: O'Donovan Thomas M.
Published: November 2008

This paper obtains the distributions of attained and residual service for a general class of queuing systems. The attained service of an incompletely serviced job is the portion of its processing time that it has already been allocated and its residual service is the portion to be allocated. An expression is found for the average total unfinished work in the system. Examples of these results are also given.
Global Maximization of a Convex Function with Linear Inequality Constraints
Authors: Zwart Philip B.
Published: November 2008

This paper presents an algorithm for the global maximization of a convex function subject to linear inequality constraints. It is computationally finite and is designed to converge rapidly on problems in which there are few local optima or the global optimum is significantly better than most of the other local optima.
Distribution-Free Approximations for Chance Constraints
Authors: Allen F. M. , Braswell R. N. , Rao P. V.
Published: November 2008

This paper concerns developing methods for approximating a chance-constrained set when any information concerning the random variables must be derived from actual samples. Such a situation has not been presented in the literature. When existing chance-constrained programming techniques are used, it is not possible to relate the accuracy of sample-based assumptions to actual constraint satisfaction. The methods presented here employ the concept of a distribution-free tolerance region to construct various sets whose elements have the common property of satisfying the chance constraint with a preassigned level of confidence. The sample size required to meet the desired confidence is readily available in tabular or graphical form.
Heuristic-Programming Solution of a Flowshop-Scheduling Problem
Authors: Krone Martin J. , Steiglitz Kenneth
Published: November 2008

This paper considers the static flowshop-scheduling problem with the objective of minimizing, as a cost function, the mean job-completion time. Within the more general framework of combinatorial optimization problems, it defines a heuristic search technique—an approach that has been successful in the past in obtaining near-optimal solutions for problems that could not be solved exactly, either for lack of theory or because of exorbitant computational requirements. The paper presents a two-phase algorithm: The first phase searches among schedules with identical processing orders on all machines; the second refines the schedule by allowing passing. Results of computer study are presented for a large ensemble of pseudorandom problems, and for two particular problems previously cited in the literature. The method is shown to provide solutions that are exceptionally low in cost, and superior to those provided by sampling techniques in the cases for which comparison is possible. Computation time is also discussed and is given in machine-independent terms.
Modeling Food Preferences Over Time
Authors: Balintfy Joseph L. , Duffy William J. , Sinha Prabhakant
Published: November 2008

This paper reports the results of experiments designed to establish the nature of the functional relations between the measure of preference for a menu item and the time history of its previous consumption. Experimental data support the hypothesis that such a relation indeed exists and a mathematical representation of the phenomenon is feasible. Evidence is presented that the preference-time function is conceived by most people as being monotonically increasing and concave. There is a distinction, however, between preference measures defined on relative and absolute time scales, with the latter one accounting for the effect of repetitiveness and providing a link between the interpretation of food preference and frequency ratings of individuals. The experimental data indicate that the preferred frequency of serving is the locus of the maximum of a function that expresses the realization of the time-averaged value of preference over absolute time. Methods are outlined for the routine estimation of these functions from the results of simple questionnaires involving only three or four questions per item. The feasibility of such questionnaires for a large population and involving a large number of menu items is also established.
Optimal Control of a Maintenance System with Variable Service Rates
Authors: Crabill Thomas B.
Published: November 2008

This paper examines a production system with variable repair-service rates. Considering costs dependent on the service rates and costs due to lost production, it seeks to minimize the long-run expected average cost of the system. The model is a continuous-time Markovian decision problem. The paper states sufficient conditions for eliminating from consideration certain service rates and for the existence of an optimal stationary policy from a “simple” class. It also gives an example of a nonsimple optimal policy.
Optimal Price and Promotion for Interdependent Market Segments
Authors: Gensch Dennis H. , Welam Ulf Peter
Published: November 2008

The model described in this paper was developed to provide guidance for price and promotion decisions in a consumer-goods division doing business in the United States marketplace. Demand is a dynamic function of price and promotion; the total market is divided into M interacting market segments that often have different needs and wants for the product and that can be sent different promotional messages; the segments usually have different price and promotion elasticities. For a given planning horizon, the model determines the optimal price to be charged in the M segments, the optimal promotional budget, and its allocation over the M segments. A convex programming formulation is utilized. The paper discusses the reality of the environment to be modeled, develops the model in relation to this reality, and then provides an empirical illustration of the model.
Production Planning for a Stochastic Demand Process
Authors: Gonedes Nicholas J. , Lieber Zvi
Published: November 2008

This paper deals with planning production of a single good over a prescribed finite interval of time [0, T]. The costs considered within the problem are production and holding costs; holding costs are incurred for negative inventory (caused by backlogged sales) and positive inventory (caused by production in excess of demand). The demand for the product is treated as a stochastic process. Problem formulation and optimization use tools from continuous-time stochastic variational calculus and control theory. Among its results, the paper proves the uniqueness of the optimal solution and provides an algorithm for the problem.
The Optimal Order of Service in Tandem Queues
Authors: Tembe Shantanu V. , Wolff Ronald W.
Published: November 2008

This paper considers tandem queues for which the order of performing service tasks can be changed, the service times being independent of this order. It determines the optimal order of service when either the service times of different tasks are nonoverlapping or, for two queues in tandem, the service time of one task is constant. For the optimal ordering, the waiting time of every customer is stochastically smaller than for any other.
The Optimality of General-Order Exponential Smoothing
Authors: Cogger K. O.
Published: November 2008

This paper derives the class of nonstationary time-series representations for which exponential smoothing of arbitrary order minimizes mean-square forecast error. It points out that these representations are included in the class of integrated moving averages developed by Box and Jenkins, permitting various procedures to be applied to estimating the smoothing constant and determining the appropriate order of smoothing. These results further permit the principle of parsimony in parameterization to be applied to any choice between exponential smoothing and alternative forecasting procedures.
A New Look at Higher-Order Exponential Smoothing for Forecasting
Authors: Goodman M. L.
Published: November 2008

This paper applies residual analysis to build up improved forecasts from exponential smoothing models. The resulting model is not unknown, but the method of achieving it is more straightforward and intuitive than existing methods. The paper also shows that the model is identical to IMA(k, k) forecasting models.
Technical Note—The Waiting Time in the Ek/M/1 Queuing System
Authors: Fischer Martin J.
Published: November 2008

In a standard M/Ek/1 queuing system, the average steady-state waiting time of an arriving customer decreases monotonically in k for a fixed arrival and service rate. This note establishes the analogous result for the dual system Ek/M/1.
Optimal Priority-Purchasing and Pricing Decisions in Nonmonopoly and Monopoly Queues
Authors: Adiri I. , Yechiali U.
Published: November 2008

An M/M/1 service station (computer center) consists of M separate queues. The ith (i = 1, 2, …, M) queue has priority over the jth iff i < j. Upon arrival, a customer receives all the information regarding the state of the system and accordingly makes an irrevocable decision as to which queue to join, or rather to balk (leave) and go to a competitor. The higher the priority of the queue, the higher the toll fee to join it but the shorter the time spent in the system. This paper considers nonmonopoly and monopoly cases, and optimal priority-purchasing or balking rules for the newly arrived customer, as well as optimal pricing policies for the service station for both preemptive-resume and non-preemptive-priority disciplines.
The Structure of Integer Programs under the Hermitian Normal Form
Authors: Bowman V. Joseph
Published: November 2008

This paper discusses the structure of integer programming under the Hermitian normal form. It shows that this formulation is akin to the simplex technique for linear programming in that there is a basis and a basic solution associated with each Hermitian normal matrix, and that this Hermitian basis forms a set of natural cutting planes; these cutting planes are strong in that they provide facets for at least one of the corner polyhedra associated with a linear programming basis B. In addition, the cofactors of the Hermitian basis are group elements under a homomorphism of the original group structure. The Hermitian basis also allows one to characterize the values of the right-hand side for which the present solution is feasible. Finally, for an optimal Hermitian basis, one can perform sensitivity analysis on the cost coefficients.
Pseudo-Boolean Solutions to Multidimensional Location Problems
Authors: Warszawski Abraham
Published: November 2008

This paper presents a pseudo-boolean formulation of location problems based on a concept of a “dummy” supply source activated outside a given distribution. First, it formulates a simple location problem as a pseudo-boolean function that can be optimized with existing boolean optimization algorithms. Later the formulation is extended to multidimensional location problems. Two such problems are analyzed: the first involves a distribution system with plants for production of different commodities; the second involves a distribution system with consumer demand and its pattern varying with time.
Technical Note—A Method for Solving Mathematical Programs with Nonlinear Programs in the Constraints
Authors: Bracken Jerome , McGill James T.
Published: November 2008

This note describes a computational procedure for solving mathematical programs with nonlinear programs in the constraints; it uses the SUMT computer program for the overall mathematical program, and a new program called INSUMT for the nonlinear programs in the constraints.
Errata
Authors: Christofides Nicos
Published: November 2008

Erratum to author's paper “Bounds for the Travelling-Salesman Problems” [Opns. Res. 20, 1044–1056 (1972)].
Insurance Exposure and Investment Risks: An Analysis Using Chance-Constrained Programming
Authors: Thompson Howard E. , Matthews John P. , Li Bob C. L.
Published: November 2008

By exposing itself to greater risks on the invested funds, the company can also increase its expected returns. Because there are risks involved with both the insurance and investment operations, a major problem for a company is to determine just how the two types of risks are to be balanced. This paper formulates the premium-volume/investment-mix problem for nonlife-insurance companies as a chance-constrained programming problem. A number of numerical examples of the model were run to assess the effects of investment risks, insurance risks, and the willingness of the company to tolerate risks. The paper derives the conclusion that risks in both investment possibilities and insurance portfolios are compensated for, to a large extent, by varying the growth rate of premiums, in addition to shifts in portfolio makeup. The two problems—growth and portfolio selection—cannot and should not be separated. The paper shows that the traditional rules of thumb—e.g., if the premium-surplus ratio is high, the common-stock portion of the investment portfolio should be low—are somewhat ambiguous and not borne out by the numerical examples.
Failure-Rate Analysis Applied to Recidivism Data
Authors: Stollmack Stephen , Harris Carl M.
Published: November 2008

This paper outlines a method for the statistical analysis of the recidivistic performance of individuals within a correctional release program, and extends the procedure to enable comparing the performances of two groups in the same or in different programs. It provides an illustration of how these techniques can be used based on actual data from the District of Columbia Department of Corrections for the period January 1, 1972, through July 1, 1973.
Experience with a Successful System for Forecasting and Inventory Control
Authors: Bishop Jack L.
Published: November 2008

The wealth of management-science literature dealing with optimal solutions to the inventory-control problem would be more impressive if there were not a dearth of evidence of successful applications of these tools. As a step into this gap, this paper describes experiences with an evolutionary approach to a system for the centralized control of inventories of finished products in several branch warehouses; it embodies forecasting and inventory ordering, and is characterized by a man-computer partnership. Both manual overrides of the computer-generated order parameters and exception reporting a Low significant cost savings with no degradation of service. A very simple inventory-control doctrine allowed the operating personnel to gain confidence in the system—and management science in general. Based on this confidence, a simple simulation model was developed to permit evaluating alternative simple algorithms.
Direct Solutions of M/G/1 Processor-Sharing Models
Authors: O'Donovan T. M.
Published: November 2008

This paper considers three well known queuing models of time-shared computer systems and the limiting case of processor sharing where the quantum of service shrinks to zero. It shows that the average response times in these models are easily evaluated as the solutions of certain differential equations.
Optimal Test Design for Reliability Demonstration
Authors: Gal Shmuel
Published: November 2008

This paper presents the optimal design of tests for demonstrating the reliability of a system, assuming that all the subsystems have a very high reliability so that no failure is expected to occur during the tests.
Strong Optimality of the Shoot-Adjust-Shoot Strategy
Authors: Barr Donald R.
Published: November 2008

This paper shows that seemingly different “adjustment” procedures are equivalent, if viewed in appropriate coordinate systems. It extends previous results concerning sequential adjustments that are constrained to be linear functions of observed impact points to the class of translation-invariant procedures. It also reviews properties of the optimal sequential adjustment procedure, including some related to stochastic approximation.
Technical Note—The Expected Number of Idle Servers in a Queuing System
Authors: Harris Robert
Published: November 2008

This note derives a simple expression for the expected number of idle servers in a queue under very general conditions.
Technical Note—Reply to Rao's Note on the Location of Emergency Service Facilities
Authors: Toregas Constantine , ReVelle Charles , Swain Ralph
Published: November 2008

A note by Rao [“Counterexamples for the Location of Emergency Service Facilities,” Opns. Res. 22, 1259–1261 (1974)] comments on a paper by Toregas, Swain, ReVelle, and Bergman [Opns. Res. 19, 1363–1373 (1971)]. This note extends the discussion by suggesting how the difficulties identified by Rao can be overcome.
Technical Note—Fault Testing for a k-out-of-n System
Authors: Halpern Jonathan
Published: November 2008

Butterworth [Opns. Res. 20, 335–343 (1972)] has presented a sufficient condition for the optimality of a sequential testing procedure for k-out-of-n systems. The condition is fairly strong and therefore excludes several cases where in fact an optimal policy exists. This note presents an optimal sequential procedure for the k-out-of-n system with equal testing costs for all components, a case where Butterworth's sufficient condition is not satisfied.
Erratum
Authors: Advani Suresh
Published: November 2008

Erratum to author's paper “A Linear-Programming Approach to Air-Cleaner Design” [Opns. Res. 22, 295–297 (1974)].
When the Greedy Solution Solves a Class of Knapsack Problems
Authors: Magazine M. J. , Nemhauser G. L. , Trotter L. E.
Published: November 2008

This paper analyzes a heuristic for the knapsack problem that recursively determines a solution by making a variable with smallest marginal unit cost as large as possible. Recursive necessary and sufficient conditions for the optimality of such “greedy” solutions and a “good” algorithm for verifying these conditions are given. Maximum absolute error for nonoptimal “greedy” solutions is also examined.
A Social Service Measurement Model
Authors: Mantel Samuel J. , Service Allan L. , Reisman Arnold , Koleski Raymond A. , Blum Arthur , Dean Burton V. , Reich Robert , Jaffee Miriam , Rieger Howard , Ronis Richard , Rubinstein Judah
Published: November 2008

The development and implementation of a service value measurement model for a system of social service agencies is discussed. The system, the Jewish Community Federation of Cleveland, is a voluntary association of sixteen human service agencies. Design and workings of the project team, analysis and structuring of the organizational system, and overall goals of the research are first presented. The measurement model itself is then delineated. Essentially, the model is a device for assembling and synthesizing information on system throughput, priorities, and indicators of “quality” of service. Finally, the information system that supports the model is examined and other issues relating to implementation are discussed.
A Priority Queue with Discounted Linear Costs
Authors: Harrison J. Michael
Published: November 2008

We consider a nonpreemptive priority queue with a finite number of priority classes, Poisson arrival processes, and general service time distributions. It is not required that the system be stable or even that the mean service times be finite. The economic framework is linear, consisting of a holding cost per unit time and fixed service reward for each customer class. Future costs and rewards are continuously discounted with a positive interest rate. Allowing general initial queue sizes, we develop an expression for the expected present value of rewards received minus costs incurred over an infinite horizon. From this we obtain the Laplace transform of the time-dependent expected queue length for each customer class.
Coordinating Aggregate and Detailed Scheduling in the One-Machine Job Shop: II—Computation and Structure
Authors: Gelders L. , Kleindorfer P. R.
Published: November 2008

A previous research report of the authors presented a formal model of the one-machine job-shop scheduling problem with variable labor capacity. This report presents some computational experience with the algorithm proposed previously and a discussion of the structural aspects of the problem. Extensions and refinements of the algorithm are introduced to deal with nonsimultaneous job arrivals and the production smoothing problem. These results provide insight into the structure of the aggregate-detailed cost trade-off problem and suggest a good heuristic decision rule for problems of realistic size and complexity.
Technical Note—A Dynamic Programming Formulation for Continuous Time Stock Control Systems
Authors: Snyder Ralph D.
Published: November 2008

Continuous review stock systems are considered in this paper. They are modeled using discrete time dynamic programming, which in contrast to previous continuous time formulations of the problem, yields a reasonable algorithm for computational purposes. The model is used to establish the optimal forms of stationary ordering policies under various cost assumptions.
The Boxstep Method for Large-Scale Optimization
Authors: Marsten R. E. , Hogan W. W. , Blankenship J. W.
Published: November 2008

A new strategy is presented for large-scale optimization. The Boxstep method creates an algorithmic continuum between feasible-directions methods and cutting-plane methods. Several specific applications are described and computational results are reported.
The Accelerated Bound-and-Scan Algorithm for Integer Programming
Authors: Faaland Bruce H. , Hillier Frederick S.
Published: November 2008

This paper presents a new implicit enumeration algorithm for solving the pure integer linear programming problem. The theory of equivalent integer programming problems is first used to reformulate the problem. A technique originally used with particular success in the bound-and-scan algorithm to deal with only a subset of the variables is extended to all of the variables in the restructured problem. In addition to the resulting basic enumeration scheme, the algorithm includes a scanning procedure and a method for identifying constraints that become redundant during the course of the algorithm. Computational experience on standard test problems is reported.
Surrogate Constraint Duality in Mathematical Programming
Authors: Glover Fred
Published: November 2008

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

This paper describes some measures commonly used to evaluate anticrime programs and proposes directions for research on improved measures. Since the police are usually seen as the main crime control agency, the paper first discusses the differences between evaluating the police and evaluating crime control programs. Five measures used to evaluate such programs are then analyzed: crime rate, clearance rate, arrest rate, police response time, and crime seriousness index. The last measure suggests the direction for the development of an improved measure of crime: the development of a more complete taxonomy of crime and the discrimination between and explication of the different types of harm caused by crime.
On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
Authors: McMahon Graham , Florian Michael
Published: November 2008

An algorithm is developed for sequencing jobs on a single processor in order to minimize maximum lateness, subject to ready times and due dates. The method that we develop could be classified as branch-and-bound. However, it has the unusual feature that a complete solution is associated with each node of the enumeration tree.
A Linear Fractional Max-Min Problem
Authors: Cook W. D. , Kirby M. J. L. , Mehndiratta S. L.
Published: November 2008

This paper is concerned with a linear fractional problem of the form: maxX minY F(X, Y) = (cX + dY + α)/(fX + gY + β), subject to [Formula: see text] This problem represents a generalization of a problem considered in the literature in which F(X, Y) is assumed to be linear. A number of results for the linear case are extended; and, in particular, it is shown that this fractional max-min problem is equivalent to a quasi-convex programming problem whose optimal solution lies at a vertex of the feasible region. Using these results, we develop an algorithm for solving this problem. The paper concludes with a numerical example.
Technical Note—A Stopping Criterion for the Golden-Ratio Search
Authors: Gottfried Byron S.
Published: November 2008

This note presents a stopping criterion for the golden-ratio search for the optimum of a one-dimensional, unimodal function. Given ϵ, the minimum separation between two points such that the corresponding values of the function remain distinguishable, we show that the search should be terminated when the interval of uncertainty is less than ϵp/(2 − p), where p is the golden ratio.
Technical Note—On the Generalized Lattice Point Problem and Nonlinear Programming
Authors: Cabot A. Victor
Published: November 2008

In this paper we consider a problem that is equivalent to the generalized lattice point problem of nonconvex programming. This problem can be expressed as the maximization of a certain convex function over a convex polyhedral set. This formulation can be used with the cutting plane algorithm of Glover and Klingman sometimes to strengthen the cuts their method generates for the generalized lattice point problem. A cut for zero-one integer programming can also be derived.
Technical Note—Multidimensional Sequencing Rule
Authors: Morin Thomas L.
Published: November 2008

This note derives a simple heuristic sequencing rule for determining a minimum discounted cost development sequence of multiple-purpose projects that simultaneously satisfy a number of increasing demands over a finite planning horizon. An evaluation of the heuristic's performance on the solution of a number of real-world water resources problems indicates that it can be an extremely effective planning aid.
Technical Note—Solving Constrained Multi-Facility Location Problems Involving lp Distances Using Convex Programming
Authors: Love Robert F. , Morris James G.
Published: November 2008

A method is described for approximating nondifferentiable convex minimization problems occurring in location theory by differentiable problems. Distances are generalized to lp distances that include rectangular and Euclidean distances as special cases. Any number of linear and/or nonlinear constraints can be accommodated. The method utilizes a hyperbolic distance function that is uniformly convergent to each lp distance. Computational results are reported.
Technical Note—Probabilistic Analysis of a Single-Server n-unit System with (n − 1) Warm Standbys
Authors: Gopalan M. N.
Published: November 2008

This paper deals with the availability and reliability of an n-unit system with (n − 1) warm standbys and a single repair facility. The failure times of the operating unit and of a standby are assumed 1o be exponentially distributed with parameters λ1 and λ2 respectively. Initially, a unit is switched on and the other units are kept as warm standbys. The system breaks down when the last operating unit foils. This paper characterizes the system by the probabilities of its being in the up or the down state, sets up integral equations for these probabilities by identifying suitable regenerative stochastic processes, and employs the Laplace-transform technique to solve these equations. It obtains the mean down-time of the system during (0, t) and the mean time to system failure explicitly. Finally it discusses the cases n = 2 and 3.
Applying a New Device in the Optimization of Exponential Queuing Systems
Authors: Lippman Steven A.
Published: November 2008

We consider the problem of controlling M/M/c queuing systems. By providing a new definition of the time of transition, we enlarge the standard set of decision epochs and obtain a preferred version of the n-period problem in which the times between transitions are exponential random variables with constant parameter. Using this new device, we are able to utilize the inductive approach in a manner characteristic of inventory theory. The efficacy of the approach is demonstrated by successfully finding the form of an optimal policy for three distinct models that have appeared in the literature, namely, those of (i) Miller and Cramer, (ii) Crabill and Sabeti, and (iii) Low of particular note is our analysis of the Miller-Cramer model, in which we show that a policy optimal for all sufficiently small discount factors can be obtained from the usual average cost functional equation without recourse to further computation.
The Output of an M/D/1 Queue
Authors: Pack Charles D.
Published: November 2008

In this paper we investigate the output process of the M/D/1 queuing system. We derive expressions for the distributions and first two moments, in both steady-state and transient conditions, of the following random variables: (1) the time until the nth departure measured from a departure epoch, T0, (2) the time between the n − 1st and nth departures after T0, and (3) the number of departures in (T0, T0 + t]. Further we study the autocorrelation functions of random variables (1) and (2) in the steady state.
Technical Note—Waiting Time in an (S − 1, S) Inventory System—Constant Service Time Case
Authors: Sherbrooke Craig C.
Published: November 2008

The purpose of this note is to provide comparable results to Higa et al. (Higa, I., A. Feyerherm, A. Machado. 1975. Waiting time in an (S − 1, S) inventory system. Opns. Res. 23 674–680.) for the constant resupply time case. Since resupply times are seldom as variable as exponential, the waiting-time distribution for constant resupply times is of interest, at least as a standard of comparison.
Technical Note—Delays in Single-Server Queues with Batch Input
Authors: Burke P. J.
Published: November 2008

Standard works on queuing theory are in error in the calculation of the equilibrium delay distribution—and even of the average delay—in a single-server system with batch input, when the batches are not of constant size. This paper corrects the error, which occurs in connection with that portion of the delay of a customer due to the service times of other members of the same batch.
Technical Note—A Note on Zero-One Programming
Authors: Padberg Manfred W.
Published: November 2008

We generalize a method for constructing facets for the convex hull of integer solutions to set packing problems to arbitrary zero-one problems having nonnegative constraint-matrices. A particular class of facets is obtained explicitly and illustrated by a numerical example.
Technical Note—On the Rate of Expansion of Gamma Search Plans
Authors: Belkin Barry
Published: November 2008

In the paper “Optimal Search With Uncertain Sweep Width” Richardson and Belkin derive the optimal search plan (gamma plan) for a stationary target with bivariate normal prior location distribution when the search sensor sweep width has a gamma distribution. The claim is then made that increasing the level of uncertainty in prior knowledge of sweep width (by increasing variance with mean fixed) slows the rate of expansion of this gamma plan. In this note we show that this statement is correct only after the search has proceeded unsuccessfully for some time. Earlier in the search, an increase in the level of sweep width uncertainty would actually accelerate the rate of expansion of the gamma plan.
An Optimum Manpower Utilization Model for Health Maintenance Organizations
Authors: Schneider Donald P. , Kilpatrick Kerry E.
Published: November 2008

This paper describes the development and validation of a set of mathematical programming models directed at optimal manpower utilization in Health Maintenance Organization (HMO's). An application of the models in a planning context for an emerging HMO is presented and the results compared to those of actual staffing patterns. Two basic models are discussed in detail: an overall planning model and a subscriber maximization model. Each model treats the interaction between effective manpower utilization, facility requirements, and available capital. The objectives used in the models pertain to either minimum cost or minimum feasible use of physicians through the substitution of physician extenders. Field trials indicate that the models accurately represent the actual system and can be used effectively as planning aids.
Generalized Utility Independence and Some Implications
Authors: Fishburn Peter C. , Keeney Ralph L.
Published: November 2008

This paper introduces the concept of generalized utility independence. Subject to various generalized utility independence assumptions, we derive three functional forms for a multiattribute von Neumann-Morgenstern utility function u. These are the additive, the multiplicative, and the quasi-additive forms, each of which expresses u as a combination of utility functions defined on the separate attributes. It is demonstrated that if u is unbounded from above and below, then given the three forms, either reversal of preferences over some attributes occurs or else the additive form must hold.
Application of a Functional Equation to a Class of Stochastic Detection Models
Authors: Belkin Barry
Published: November 2008

In a proposed class of abstract stochastic detection models, the occurrence of detection is related to the time-dependent behavior of a detection functional defined on the signal-to-noise process sample paths. We describe a potential operations-analysis application in certain sonar detection problems. The method developed for computing detection probabilities for these models requires the solution of a functional equation involving the detection functional and the weak infinitesimal operator of the signal-to-noise process, assumed Markovian with stationary transition probabilities. Two hypothetical signal-to-noise processes considered in detail are the random sampling process and the stationary Gauss-Markov (Ornstein-Uhlenbeck) process in the special case when the detection functional measures time above a constant threshold level. We compare expressions for the mean time to detect, obtained for these processes, numerically.
Technical Note—Bench Marks Comparing Transportation Codes based on Primal Simplex and Primal-Dual Algorithms
Authors: Hatch Richard S.
Published: November 2008

Specialized algorithms are required to solve transportation and assignment problems optimally and efficiently. Specialized primal simplex and primal-dual transportation codes are compared via a series of bench marks on both small and large problems.
An N-Server Stochastic Service System with Customer Preferences
Authors: Bein P. Lawrence
Published: November 2008

The Erlang loss formula is currently used to estimate the capacity of a set of N linear curb spaces for vehicle parking; but this model applies only if drivers will accept the first vacant space they come to, a condition not found in practice. This paper develops a model of service that permits customers to decline an available server (space) when the walking distance would be excessive. The results enable the calculation of not only the overall loss, but the ability of the service system to satisfy customer preferences. It evaluates the conditional loss (given the space preferred), the access time, and the expected walking distance for each preference class. We give some examples of results based upon traffic characteristics forecast at a large, modern air terminal. It is found that the Erlang formula considerably underestimates the space requirements for linear curb parking and ignores the impact of its driver-indifference assumption upon passenger walking distance. The model has been programmed in APL for rapid calculations of all pertinent factors, allowing economical interactive use for planning—a curb with 30 spaces can be evaluated in approximately 1/2 second of CPU time.
Markovian Deterioration with Uncertain Information
Authors: Rosenfield Donald
Published: November 2008

This paper presents a model of a deteriorating process with imperfect information. This model, unlike many previous efforts, stipulates that the operator most pay an inspection cost to determine the state of the system. This situation presents him with three choices at every time period: repair, inspection, or inaction. Under the assumptions that the transition matrix representing the process is upper-triangular and totally positive of order two, it is shown that the state-space can be broken up into at most four regions of action and that the optimal region of repair is of a special intuitive type.
Technical Note—A “Hard” Assignment Problem
Authors: Machol Robert E. , Wien Michael
Published: November 2008

We construct numerical examples that force Hungarian-method algorithms for the assignment problem to their worst-case time bounds. These bounds are thereby clarified.
Confidence Assessment of Military Airframe Cost Predictions
Authors: Tihansky Dennis P.
Published: November 2008

Past experience of cost overruns in weapon system acquisition programs has underscored the variation between cost estimates and actual expenses. This study analyzes the degree of confidence that can be placed in cost predictions for airframes from standard cost models. Each airframe cost observation is partitioned into six components based on phases of the development or production cycle, e.g., flight test costs and manufacturing labor wages. Confidence measures are then compared for alternative model forms and for the use of a single regression on total costs versus the aggregation of regressions on component costs. We develop statistical theory to test the independence of component models and to estimate predictive statistics for aggregated cost estimates. Component regression errors are found to be significantly correlated, thereby increasing the width of confidence intervals. To assume error independence for the sake of simplifying the confidence assessment is thus misleading.
A Lagrange Multiplier Method for Certain Constrained Min-Max Problems
Authors: Pearsall Edward S.
Published: November 2008

Constrained min-max problems are constant-sum, two-person games in which the maximizing player enjoys the advantage of moving last and both players select allocations subject to separate constraints on their use of resources. This paper presents a Lagrange multiplier method for addressing such problems where the maximizing player is permitted to mix strategies probabilistically. We derive conditions under which the method will locate optimal solutions and discuss suitable applications. A simple ABM/shelter deployment problem is solved to illustrate the essential features of the method.
Parametrically Dependent Preferences for Multiattributed Consequences
Authors: Kirkwood Craig W.
Published: November 2008

The assessment of multiattribute cardinal utility functions can be a difficult experimental problem. To aid in this assessment, we define the concept of parametric dependence of preferences for multiattributed consequences. We show the usefulness of this concept for the assessment of multiattribute utility functions by proving several representation theorems that simplify the assessment problem when parametric dependence holds.
Consistency, Superconsistency, and Dual Degeneracy in Posynomial Geometric Programming
Authors: Abrams Robert A.
Published: November 2008

This paper gives a method by which any consistent geometric programming problem may be reduced to a superconsistent or unconstrained geometric programming problem. We show that a consistent geometric programming problem is not superconsistent if and only if the dual geometric programming problem has an unbounded optimal solution set or an unattained supremum. Reduction of the dual to canonical form, i.e., reduction to an equivalent problem with a bounded optimal solution set, is shown to be dual to the reduction of a consistent primal program to an equivalent superconsistent program.
Procedures for the Solution of a Finite-Horizon, Partially Observed, Semi-Markov Optimization Problem
Authors: White Chelsea C.
Published: November 2008

This paper presents a finite-time-horizon, partially observed, stochastic optimization problem, where the core process is a controlled, finite-state, discrete-time semi-Markov process. We assume that times of control reset and noise corrupted observations of the core process occur at times of core process transition. The control employed at each time of core process transition is allowed to be functionally dependent on the sample path of the core process only through the history of corrupted observations. Conditions for optimality are stated. We show that the minimum expected cost accrued from a given time t until the terminal time is concave with respect to a sufficient statistic and satisfies a computationally useful functional form. Furthermore, if the set of values that the control vector may assume at each time of control reset is finite, then the expected cost is also piecewise linear with respect to the sufficient statistic. A numerical procedure for the finite-horizon, partially observed, Markov optimization problem is generalized to include the semi-Markov formulation. We give a result that justifies a well known technique for the determination of the optimal cost and an optimal control policy and discuss areas of application.
Technical Note—An Application of Martingale Methods to Conflict Models
Authors: Watson R. K.
Published: November 2008

We consider a model of a conflict between two forces in which members of each force are killed at a rate proportional to the number of surviving members of the other force. By constructing a martingale and applying the martingale central limit theorem, we are able to obtain approximations for the probability of winning and the distribution of the number of survivors. We note that the method can be extended to more general conflict models.
Technical Note—Conditional Response Times in M/M/1 Processor-Sharing Models
Authors: O'Donovan T. M.
Published: November 2008

We study the round-robin system in the limiting case when the quantum of service shrinks to zero. For an exponential processing-time distribution, we find an expression for the mean response time of a job conditioned on the service it requires and the number of jobs in the system on its arrival. Comparison is made with other queue disciplines.
Aircraft Missile Avoidance
Authors: Vincent Thomas L. , Sticht Douglas J. , Peng Willy Y.
Published: November 2008

The game of two cars defined by Rufus Isaacs is visualized here in terms of missile avoidance by an aircraft. With the system dynamics specified and confined to the horizontal plane, the distinctiveness between Isaacs' original problem and ours lies not only in the choice of parameters, but in the choice of assigned player rationale as well. In particular, we obtain three different capture zones. The capture zones are defined in terms of the barriers separating regions of capture from noncapture. We obtain a game barrier by assuming both the missile and the aircraft use optimal (qualitative game) control, a proportional navigation barrier by assuming the missile is using proportional navigation and the aircraft is using optimal evasive control, and a green barrier by assuming no control action by the aircraft with the missile using optimal pursuing control. The first two barriers allow for a qualitative comparison of proportional navigation guidance-to-guidance based on game theory. The green barrier gives important information when no maneuver is required to avoid the missile.
Countable-State, Continuous-Time Dynamic Programming with Structure
Authors: Lippman Steven A.
Published: November 2008

We consider the problem P of maximizing the expected discounted reward earned in a continuous-time Markov decision process with countable state and finite action space. (The reward rate is merely bounded by a polynomial.) By examining a sequence 〈pN〉 of approximating problems, each of which is a semi-Markov decision process with exponential transition rate ΛN, ΛN ↗ ∞, we are able to show that P is obtained as the limit of the PN. The value in representing P as the limit of PN is that structural properties present in each PN persist, in both the finite and the infinite horizon problem. Three queuing optimization models illustrating the method are given.
On the Output of a GI/M/N Queuing System with Interrupted Poisson Input
Authors: Heffes Harry
Published: November 2008

We consider the output process of a GI/M/N queuing system with interrupted Poisson input. The interrupted Poisson input is frequently used to characterize alternate routed traffic and may be shown to be equivalent to a mixture of two exponential distributions. We characterize the departure process as a semi-Markov process and give results for the joint distribution of the number of customers in the system and the state of the input process at service completions. We also present results relating to the interdeparture time distribution and the distribution of the nonbusy period and compare the results with some known results for single-server systems.
On the Busy Periods of Single-Server Queues with Poisson Input and General Service Times
Authors: Takács Lajos
Published: November 2008

We consider a single-server queue with Poisson input and general service times and determine the following probabilities: the probability that a busy period has length ≦ x and the maximal queue size during the busy period is ≦ k, and the probability that a busy period has length ≦ x and the maximal virtual waiting time during the busy period is ≦ y.