bluuebunny/crossref_metadata_2025 huggingface dataset:
Minimizing the Cost of Servicing an End Product Subject to a Completion Time Constraint
Authors: Falk James E. , Rose Marshall
Published: November 2008

This paper describes a problem in which end products, such as aircraft, are periodically serviced, owing to the failure or preventive maintenance of reparable items. Given the required sequence of item reinstallations, the item resupply times, and item repair probabilities, a relation between the item resupply times and the expected end-product service time is derived. We present an exact algorithm designed to minimize the total cost of repair subject to a constraint on the expected service time. A heuristic algorithm yielding the entire “minimum cost per expected service time” curve is also described.
Duality and Sensitivity Analysis for Fractional Programs
Authors: Bitran Gabriel R. , Magnanti Thomas L.
Published: November 2008

In this paper we consider algorithms, duality and sensitivity analysis for optimization problems, called fractional, whose objective function is the ratio of two real-valued functions. We discuss a procedure suggested by Dinkelbach for solving the problem, its relation to certain approaches via variable transformations, and a variant of the procedure that has convenient convergence properties. The duality correspondences that are developed do not require either differentiability or the existence of an optimal solution. The sensitivity analysis applies to linear fractional problems, even when they “solve” at an extreme ray, and includes a primal-dual algorithm for parametric right-hand-side analysis.
Analysis of Single Critical Number Ordering Policies for Perishable Inventories
Authors: Cohen Morris A.
Published: November 2008

We consider the problem of finding the optimal solution from the class of single critical number order policies for an m-period lifetime perishable product. The objective function is expected cost per period, Accordingly, the steady-state characteristics of the inventory process induced by the order restriction are analyzed. We demonstrate the existence of an invariant measure for an inventory related process, which provides information sufficient for cost minimization. Particular results for the two- and three-period-lifetime cases are given.
Technical Note—A Reduced Tableau for Primal Integer Programming
Authors: Zalkind Julie Herman
Published: November 2008

We reformulate the Glover-Young algorithm for primal integer programming, using a smaller tableau and updating information only as needed.
Preface
Authors: Pierskalla William P. , Urban Glen L.
Published: November 2008

The first publication in Operations Research specifically dealing with health appeared in June 1957 (Blumberg [Blumberg, M. S. 1957. Evaluating health screening procedures. Opns. Res. 5 351–360]). Since that time the management of health services has received substantial attention from operations researchers. This activity has been reflected in the many health-care delivery papers published individually and in special collections in Operations Research and other related journals. Another indicator of the large interest of operations research professionals in health care is that the Health Applications Section of ORSA has had over 500 members annually for the past five years. Because of these strong research and membership interests, the editor of Operations Research authorized this special issue.
Bibliography of Operations Research in Health-Care Systems
Authors: Fries Brant E.
Published: November 2008

This paper presents a bibliography of the articles that were published before March 1976 and that describe applications of operations research techniques to health-care delivery systems.
Nurse Scheduling Using Mathematical Programming
Authors: Miller Holmes E. , Pierskalla William P. , Rath Gustave J.
Published: November 2008

This paper formulates the nurse-scheduling problem as one of selecting a configuration of nurse schedules that minimize an objective function that balances the trade-off between staffing coverage and schedule preferences of individual nurses, subject to certain feasibility constraints on the nurse schedules. The problem is solved by a cyclic coordinate descent algorithm. We present results pertaining to a six-month application to a particular hospital unit and draw comparisons between the algorithm and hospital-generated schedules.
A Stochastic Model for an Optimal Priority Bed Distribution Problem in a Hospital Ward
Authors: Esogbue Augustine O. , Singh Amar J.
Published: November 2008

Ward beds are a primary resource under the control of hospital management. We develop a method for determining an optimum distribution of beds in a ward by assuming that ward patients can be classified into two categories, that admissions follow Poisson distribution, and that length of stay in the ward follows the negative exponential distribution. After defining a cut-off level as “the number of beds beyond which type 2 (non-serious) patients are not admitted,” we develop a system of differential and difference (birth and death process) equations for the process. An objective function made up of shortage and holding costs is then developed and optimized for various values of cut-off priority level. An application of this model to a university teaching hospital in Cleveland is illustrated. The model is then extended to a situation where overflows are temporarily housed in a buffer accommodation or inappropriate ward.
Application of Multidimensional Utility Theory in Determining Optimal Test-Treatment Strategies for Streptococcal Sore Throat and Rheumatic Fever
Authors: Giauque William C. , Peebles Thomas C.
Published: November 2008

In medical decision making one must usually deal with a number of objectives, many of which conflict, under conditions of uncertainty. Multidimensional utility theory offers a methodology for dealing with such situations. This paper describes the analysis of a medical problem, the determination of optimal test and treatment strategies for streptococcal sore throat and rheumatic fever, in which the formulation and assessment of a multidimensional utility function were a central part. We determine optimal diagnostic and treatment strategies, comment on the usefulness of the procedure, and summarize some potential applications.
Utility Structure of a Medical Decision-Making Problem
Authors: Krischer Jeffrey P.
Published: November 2008

This paper investigates the utility structure of decision outcomes in the treatment of cleft lip and cleft palate. Utilities are assessed by questionnaire from 119 individuals representing 13 clinical specialties, as well as members of the families of cleft lip and palate children. The results of the survey demonstrate the validity of certain utility independence assumptions used to simplify the assessment of multiattribute utility functions. We found significant differences in utilities among clinicians, grouped according to their specialty and the treatment facility to which they are affiliated. Members of the families of cleft lip and palate children also differed with certain clinical specialty groups. The paper concludes with a discussion of the differences in the assessed utility functions and their implications for clinical decision making.
Analytical Approach to Marketing Decisions in Health-Care Organizations
Authors: Wind Yoram , Spitz Lawrence K.
Published: November 2008

We discuss the potential applicability of a new choice model and scaling procedure to the marketing decisions of health-care organizations. After a brief exposition of this analytical procedure the paper focuses on an illustrative application to the hospital selection decision under two scenarios—surgery with a rapid recovery period and serious surgery that requires a long hospitalization period. The paper concludes with some suggestions for future use of conjoint measurement and related techniques in marketing studies of health care organizations.
Technical Note—On the Estimation of Smuggling in a “Gray Market” Commodity
Authors: Maltz Michael D.
Published: November 2008

This note develops a method for estimating the amount of cigarette smuggling occurring among the various states. This particular organized crime is termed a “gray market” activity because the commodity is not illegal but is differentially taxed by the states, thus leading to illegal importing from low-tax states to high-tax states. Sales tax, demographic, and geographic data are combined in a mathematical model of the smuggling operation, which is used to estimate the amount of smuggling into a state and its impact on the state's revenue. It should be useful in determining the effectiveness of programs aimed at reducing cigarette smuggling.
Technical Note—On Mitten's Axioms for Branch-and-Bound
Authors: Rinnooy Kan A. H. G.
Published: November 2008

The axiomatic characterization of branch-and-bound methods proposed by L. G. Mitten contains a number of inaccuracies. We develop a closely related, revised system of axioms that allows the deduction of a number of attractive properties.
The Completion Time of PERT Networks
Authors: Robillard Pierre , Trahan Michel
Published: November 2008

PERT and critical path techniques have exceptionally wide applications. These techniques and their applications have contributed significantly to better planning, control, and general organization of many programs. This paper is concerned with a technical improvement in PERT methodology by introducing a new approach to approximating, in a computationally efficient way, the total duration distribution function of a program. It is assumed that the activity durations are independent random variables and have a finite range. The first part of the paper considers PERT networks and deals with the lower bound approximation to the total duration distribution function of the program. Then we use this approximation and CPM to propose bounds for the different moments of the distribution function. We illustrate this with numerical examples. In the second part of the paper we adapt our results to PERT decision networks.
An Algorithm for Two-Dimensional Cutting Problems
Authors: Christofides Nicos , Whitlock Charles
Published: November 2008

We present a tree-search algorithm for two-dimensional cutting problems in which there is a constraint on the maximum number of each type of piece that is to be produced. The algorithm limits the size of the tree search by deriving and imposing necessary conditions for the cutting pattern to be optimal. A dynamic programming procedure for the solution of the unconstrained problem and a node evaluation method based on a transportation routine are used to produce upper bounds during the search. The computational performance of the algorithm is illustrated by tests performed on a large number of randomly generated problems with constraints of varying “tightness.” The results indicate that the algorithm is an effective procedure for solving cutting problems of medium size.
Triangular Factorization and Generalized Upper Bounding Techniques
Authors: Kallio Markku , Porteus Evan L.
Published: November 2008

We develop a compact inverse method for linear programming problems having block triangular or sparse constraint matrices. Special cases of the method are, for example, the generalized upper bounding technique and its extensions. For these methods we show how a triangular factorization can be used for the working basis and block bases. In this case (and even if the constraint matrix has no special structure) our method becomes a variation of the revised simplex method using a single triangular factorization of the basis. However, the updating procedure of the triangular factors differs from existing ones in a way that implies that certain structures are exploited naturally.
ORSA Twenty-Five Years Later
Authors: Morse Philip M.
Published: November 2008

This brief article compares some early developments in operations research with directions for the future. It is recommended that operations research workers be more actively involved in empirical studies. A fruitful area for new applications is less developed countries.
Bounds on the Expectation of a Convex Function of a Random Variable: With Applications to Stochastic Programming
Authors: Huang C. C. , Ziemba W. T. , Ben-Tal A.
Published: November 2008

This paper is concerned with the determination of tight lower and upper bounds on the expectation of a convex function of a random variable. The classic bounds are those of Jensen and Edmundson-Madansky and were recently generalized by Ben-Tal and Hochman. This paper indicates how still sharper bounds may be generated based on the simple idea of sequentially applying the classic bounds to smaller and smaller subintervals of the range of the random variable. The bounds are applicable in the multivariate case if the random variables are independent. In the dependent case bounds based on the Edmundson-Madansky inequality are not available; however, bounds may be developed using the conditional form of Jensen's inequality. We give some examples to illustrate the geometrical interpretation and the calculations involved in the numerical determination of the new bounds. Special attention is given to the problem of maximizing a nonlinear program that has a stochastic objective function.
Technical Note—Insurance Exposure and Investment Risks: A Comment on the Use of Chance-Constrained Programming
Authors: Kahane Yehuda
Published: November 2008

This note criticizes the chance-constrained programming model suggested by Thompson, Matthew, and Li for the balancing of investment and underwriting risks of a non-life-insurance company. We show that the optimal solution derived from such a model is based on contradictory utility assumptions. Moreover, the chance-constrained programming model is more restrictive than a full mean-variance quadratic programming model, which yields the same results.
Technical Note—The One-Dimensional Generalized Lagrange Multiplier Problem
Authors: Greenberg Harvey J.
Published: November 2008

We develop a unified approach for a generalized Lagrange multiplier problem with one multiplier. The major result is a convergence theorem for interval reduction. Comparative analysis of bisection, linear interpolation, and tangential approximation reveals the relative advantages of tangenital approximation.
Technical Note—On Intersection Cuts in Interval Integer Linear Programming
Authors: Charnes A. , Granot Daniel , Granot Frieda
Published: November 2008

In this note we use the concept of intersection cut, introduced by Balas for integer programming problems, to develop a cutting-plane algorithm for solving integer interval linear programming problems. The idea is to apply the cutting-plane algorithm directly on the interval problem without transforming the problem into an equivalent standard integer problem. Such a transformation would significantly increase the effective size of the problem.
Technical Note—Optimal Service Policies, Just after Idle Periods, in Two-Server Heterogeneous Queuing Systems
Authors: Seth Kiran
Published: November 2008

We consider a two-server queuing system in which the service time distributions of the two servers are different. Customer arrivals are Poisson distributed. Customers renege if their wait in queue exceeds T (a random time). Customers arriving when the system is empty can be served by either of the two servers. Under policy i, they are served by server i, i = 1, 2. Our objective is to find the policy that maximizes the number of customers served. Let server 1's service time be stochastically less than server 2's service time. Intuitively, the optimal policy is policy 1; a counter-example shows that this is not always true.
Technical Note—Some Special Cases of Stochastic Programs with Recourse
Authors: Hansotia Behram
Published: November 2008

The purpose of this note is to work out in detail some specific instances of stochastic programming problems with simple recourse. We assume specific structure and specific distribution functions for the random elements and develop closed-form expressions for the objective functions.
Turfing
Authors: Segal M. , Weinberger D. B.
Published: November 2008

We discuss both the analytical methods and some implementation considerations involved in enriching the job of telephone repairpersons/installers by letting each take full responsibility for all jobs within his own territory, or “turf.” For the problem of carving the region into turfs, which bears a great similarity to the political districting problem, we use a highly interactive software system at the heart of which is a heuristic algorithm combining shortest path, minimum cost flow, and enumerative techniques. We also discuss a stochastic model of the work backlog in a turf, based on the variability of the demand for service. Preliminary experience seems to indicate that this mode of operation is both workable and desirable. It should therefore be noted that, while the discussion takes place in the context of telephone repairpersons/installers, it is of considerably wider applicability.
An Application of Lagrangian Relaxation to Scheduling in Power-Generation Systems
Authors: Muckstadt John A. , Koenig Sherri A.
Published: November 2008

Two major decisions are made when scheduling the operations of a fossil-fuel power-generating system over a short time horizon. The “unit commitment” decision indicates what generating units are to be in use at each point in time. The “economic dispatch” decision is the allocation of system demand among the generating units in operation at any point in time. Both these decisions must be considered to achieve a least-cost schedule over the short time horizon. In this paper we present a mixed integer programming model for the short time horizon power-scheduling problem. The objective of the model is to minimize the sum of the unit commitment and economic dispatch costs subject to demand, reserve, and generator capacity and generator schedule constraints. A branch-and-bound algorithm is proposed using a Lagrangian method to decompose the problem into single generator problems. A sub gradient method is used to select the Lagrange multipliers that maximize the lower bound produced by the relaxation. We present computational results that indicate the technique is capable of solving large problems to within acceptable error tolerances.
A Convergent Duality Theory for Integer Programming
Authors: Bell David E. , Shapiro Jeremy F.
Published: November 2008

We present a constructive procedure for generating a finite sequence of increasingly stronger dual problems to a given integer programming problem. The last dual problem in the sequence yields an optimal solution to the integer programming problem. We show that this dual problem approximates the convex hull of the feasible integer solutions in a neighborhood of the optimal solution it finds. The theory is applicable to any bounded integer programming problem with rational data.
Assignment of Customers to Servers in a Heterogeneous Queuing System with Switching
Authors: Winston Wayne L.
Published: November 2008

We consider a discrete time queuing system composed of a set of servers in parallel in which both customers and servers may be of several types. Customers in service may be switched from one server to another at the beginning of each period. We consider dynamic assignment rules and derive conditions that ensure that it is optimal (in a very strong sense) always to assign customers with longer service times to faster servers.
Technical Note—An Effective Heuristic for the M-Tour Traveling Salesman Problem with Some Side Conditions
Authors: Russell Robert A.
Published: November 2008

This note presents a heuristic for determining very good solutions for the symmetric M-tour traveling salesman problem with some side conditions. These side conditions' pertain to load, distance and time, or sequencing restrictions. The heuristic is an extension of the highly successful one of Lin and Kernighan for the single traveling salesman problem. Computational experience with widely tested vehicle dispatch problems indicates that the proposed heuristic consistently yields better solutions than existing heuristics that have appeared in the literature. Run times grow approximately as N2.3, where N is the number of cities. The heuristic is generally slower than the modified SWEEP heuristic except on problems having a large number of points per route.
Technical Note—Improved Conditions for Convergence in Undiscounted Markov Renewal Programming
Authors: Platzman Loren
Published: November 2008

In a simply connected Markov renewal problem, each state is either transient under all policies or an element of a single chain under some policy. This property is easily verified; it implies invariance of the maximal long-term average return (gain) with respect to the initial state, which in turn assures convergence of Odoni's bounds in the damped value-iteration algorithm due to Schweitzer, even when the maximal-gain process is multiple-chained and/or periodic.
Computation of Optimal Poker Strategies
Authors: Zadeh Norman
Published: November 2008

In this paper we discuss aspects of the solution of an eight-person draw poker game. Best strategies against perfect players (game-theoretic strategies) and against lesser players are presented. These strategies generally are functions of pot odds, the positions of relavant opponents, and their playing habits. For example, if player A opens with a pair of kings or better (his habit), player B should call with a minimum of aces when second from last to act (his position) and the pot equals twice the bet (pot odds are 2 to 1). Strategies of this type are given for opening, calling, and raising. We study the percentage of time one should raise as a bluff before the draw. A simple explanation is given for previously known results concerning optimal bluffing and calling after the draw.
Mathematical Programming and the Location of Fire Companies for the Denver Fire Department
Authors: Plane Donald R. , Hendrick Thomas E.
Published: November 2008

An operations research study of fire company location in Denver, Colorado, has been conducted, resulting in recommendations that may reduce annual costs by more than one million dollars without a substantial change in the level of fire-suppression capability. One development resulting from this study is a hierarchical objective function for the set-covering problem; this objective function permits the simultaneous minimization of the number of fire stations and the maximization of the number of existing fire stations within the minimum total number of stations. This paper includes discussions of the use of mathematical programming, station configuration information models, the synergism of judgment and analysis, and the action that resulted from the recommendations.
Capacity Design and Service Quality Control in a Queuing System
Authors: Deshmukh S. D. , Jain Suresh
Published: November 2008

We consider a finite-capacity single-server queuing system in which the problems of capacity design and service quality control are integrated. The amount of time spent on servicing a customer is used as a measure of the quality of service provided. The expected reward from servicing is assumed to be a nondecreasing function of the service duration, while a linear holding cost is assumed for customers waiting in the system. We maximize the long-run average return per unit time by optimally controlling the quality of service to be provided as a function of the workload facing the server for different waiting-room capacities. We show that the optimal control policy for a given capacity is monotone and also examine the effect of varying the system capacity on the optimal control policy. Furthermore, we analyze the design problem of selecting an optimal capacity by assuming that an optimal service control policy will be followed for each system capacity.
An Algorithm for Solving Interval Linear Programming Problems
Authors: Charnes A. , Granot Frieda , Phillips F.
Published: November 2008

This paper presents an algorithm for solving interval linear programming (IP) problems. The algorithm is a finite iterative method. At each iteration it solves a full row rank, (IP) problem with only one additional constraint.
Dynamic Optimal Pricing to Deter Entry under Constrained Supply
Authors: Lieber Zvi , Barnea Amir
Published: November 2008

In this paper we construct an optimal pricing strategy for a monopoly with a finite level of a resource (a supply constraint) and competition induced by monopolistic selling price (a demand constraint). The model is first formulated as a general differential game problem. Then, after assumptions regarding competitors' strategy are specified, the problem becomes and is solved as an optimal control problem. It appears that the joint effect of both constraints generates an optimal price trajectory that may only have a local minimum; that is, if it is not monotonic, it will initially decrease and eventually increase.
Technical Note—A Note on the Nonparametric Analysis of the Stollmack-Harris Recidivism Data
Authors: Turnbull Bruce W.
Published: November 2008

We show how quantitative methodology from the field of medical trials can be applied to the analysis of recidivism data from correctional release programs. The methods used are nonparametric and so do not depend on any assumptions concerning an underlying model. The data of Stollmack and Harris are used for illustration.
Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
Authors: Garfinkel Robert S.
Published: November 2008

We address the problem of wallpapering a room so as to minimize the paper wasted. We show that the problem is equivalent to finding a shortest hamiltonian chain in a highly structured graph. When the chain connects two equivalent nodes (traveling salesman problem), the “nearest-neighbor” technique yields an optimal solution.
An Algorithm for the Vertex Packing Problem
Authors: Houck David J. , Vemuganti R. Rao
Published: November 2008

This paper presents several properties of the vertex packing problem and develops an algorithm for its solution. We show a relationship between the vertex packing problem on the original graph and on a class of related bipartite graphs. This can be used to generate good initial solutions, which in some cases are known to be optimal. We also show that the group-theoretic approach to integer programming, when applied to vertex packing, yields a trivial group problem regardless of the determinant of the associated basis matrix. These ideas are incorporated into an algorithm and computational experience is presented.
An Algorithm for Some Special Nondifferentiable Optimization Problems
Authors: Smeers Yves
Published: November 2008

We present an algorithm for a special class of nonlinear optimization problems with a nondifferentiable objective function and prove its convergence. The method does not use the notion of subgradient and no convexity assumption is made. We discuss the application of the method to an exact penalty function and to an environmental noise-management problem.
Technical Note—An Importance Ranking for System Components Based upon Cuts
Authors: Butler David A.
Published: November 2008

Measures and rankings of a system's components relative to their importance to the system reliability have been developed by a number of authors to aid in the identification of those components on which to concentrate the resources for reliability improvement. This note proposes a new definition of component importance that is based upon minimal cuts and compares it with earlier definitions. We conclude that the new definition has distinct advantages when the system is composed of highly reliable components.
Technical Note—Optimal Strategy for the One-against-Many Battle
Authors: Friedman Yoram
Published: November 2008

Very often during the course of a battle one unit finds itself in a situation in which it has to face many hostile units. This note deals with this situation and presents a method for optimizing the order in which hostile units are attacked, for situations in which the times required to kill individual units are exponentially distributed.
Errata
Authors: Fries Brant E.
Published: November 2008

Erratum to Fries, B. E. 1975. Optimal ordering policy for a perishable commodity with fixed lifetime. Opns. Res. 23 46–61.
Sequencing Competitive Expansion Projects
Authors: Erlenkotter Donald , Rogers J. Scott
Published: November 2008

We develop a solution approach for finding the sequencing of a finite set of capacity expansion projects that minimizes total discounted operating and investment costs. Variable operating costs are specified through a general continuous-time function that requires projects to be competitive in a certain sense. This definition for operating costs allows the use of an optimization submodel, such as a multilocation distribution problem, to determine operating decisions. The general formulation includes several simple sequencing problems as special cases. The solution approach addresses a relaxed problem formulation that incorporates economic criteria for determining project timing decisions, and we show that a properly defined solution to the relaxed formulation solves the original problem. We also develop several refinements to the basic solution approach.
Multicriteria Choice Functions Based on Binary Relations
Authors: Fishburn Peter C.
Published: November 2008

This paper discusses methods of determining choices from sets of alternatives on the basis of one or more binary relations defined on the alternatives. Although the binary relations will be ordering relations in many practical contexts, most of the methods for determining choices do not assume that the relations are transitive. Choices based on a single binary relation are discussed first, followed by choices based on a set of binary relations. The latter methods are divided into post-choice methods, pre-choice methods, and hybrids. Post-choice methods determine choice sets for the several relations and then aggregate these choice sets. Pre-choice methods first combine the relations into one aggregate relation and then determine choices on the basis of the aggregate relation.
An Algorithm for the Space-Shuttle Scheduling Problem
Authors: Fisher Marshall L. , Jaikumar Ramchandran
Published: November 2008

The mission scheduling problem of the NASA space-shuttle program requires a selection of mission launch times that minimize the number of missions flown late and that satisfy early start time and resource constraints. We present an algorithm for this problem that is easy to program, requires little computation and, under certain restrictive assumptions, provides an optimal solution. Computational experience with a test case is discussed.
Scheduling Boats to Sample Oil Wells in Lake Maracaibo
Authors: Cunto Elio
Published: November 2008

Sampling oil wells is a routine operation that involves withdrawing, near the wellhead, a fraction of the liquid that flows from the well. This operation is not performed at fixed intervals, but with a frequency that varies from well to well and that also changes in time. Lagoven, S. A. operates some 3,000 oil wells in Lake Maracaibo, Venezuela, for a production capacity of approximately a million barrels of oil a day. Since its implementation in April 1975, a computer system determines which of these wells require a sample and also schedules the routes for the launches that visit the selected wells. The launch-scheduling algorithm is a heuristic that schedules up to 400 points in several routes, each having up to 106 points. This algorithm solves a special case of the vehicle dispatch problem, where the constraints for using the launches are their traveling times and the number of points on their routes. The impact of the system on field operations has been an improvement in the timing of the samples and a reduction in the overall effort of gathering samples.
Technical Note—Improved Dominance Conditions for the Three-Machine Flowshop Scheduling Problem
Authors: Gupta J. N. D. , Reddi S. S.
Published: November 2008

Existing combinatorial (or elimination) approaches for solving the three-machine flowshop scheduling problem are not applicable for the situation where the jobs have their least processing time on the second machine. We present improved dominance conditions that extend the applicability of combinatorial approaches to this situation. To derive these conditions we use Johnson's two-machine results as well as the nature of unscheduled jobs.
Technical Note—Dominance Conditions for the Three-Machine Flow-Shop Problem
Authors: Szwarc Wlodzimierz
Published: November 2008

This note examines the mathematical structure and applicability of a dominance condition of Gupta and Reddi for the three-machine flow-shop problem. It shows that this condition may eliminate fewer sequences than another dominance condition. A sequential procedure of the combined strength of the two conditions is presented. We also derive necessary conditions for the Gupta-Reddi condition.
Performance Guarantees for Scheduling Algorithms
Authors: Garey M. R. , Graham R. L. , Johnson D. S.
Published: November 2008

One approach to coping with the apparent difficulty of many schedule-optimization problems, such as occur in machine shops and computer processing, is to devise efficient algorithms that find schedules guaranteed to be “near-optimal.” This paper presents an introduction to this approach by describing its application to a well-known multiprocessor scheduling model and illustrating the variety of algorithms and results that are possible. The paper concludes with a brief survey of what has been accomplished to date in the area of scheduling using this approach.
Flowshop and Jobshop Schedules: Complexity and Approximation
Authors: Gonzalez Teofilo , Sahni Sartaj
Published: November 2008

We show that finding minimum finish time preemptive and non-preemptive schedules for flow shops and job shops is NP-complete. Bounds on the performance of various heuristics to generate reasonably good schedules are also obtained.
Technical Note—Dynamic Generalized Upper Bounding
Authors: McBride Richard D.
Published: November 2008

We develop a factored basis inverse for linear programming problems with generalized upper bound (GUB) constraints. The method allows both +1's and −1's in inequality GUB constraints. We then present a dynamic factorization GUB algorithm that seeks to reduce the size of the working inverse. Finally, a comparison of algorithms used to locate GUB structures is mentioned.
On the Optimum Use of Incarceration for Crime Control
Authors: Blumstein Alfred , Nagin Daniel
Published: November 2008

In recent years serious attention has been given to the potential of imprisonment to reduce crime by “general deterrence,” which discourages criminal behavior in the general population through the threat of punishment and by “incapacitation,” which involves physically separating criminals from the rest of society. Also of fundamental importance to the use of prison is evidence that suggests that the imprisonment rates (prisoners per capita) in the U.S. fluctuates only within very narrow limits. This apparent constraint suggests the need for an overall framework for reducing crime that best uses the limited resource, man-years of imprisonment. In this paper we develop a model that estimates total crime rate as a function of imprisonment policies, incorporating estimates of deterrent and incapacitative effects. Using imprisonment rate as a constraint, we develop an optimization framework to minimize crime rate and use it to explore implications of alternative incarceration policies. An illustrative example, using data from 1970, is provided.
Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
Authors: Schrage Linus , Baker Kenneth R.
Published: November 2008

Consider a set of tasks that are partially ordered by precedence constraints. A subset of tasks is called feasible if, for every task in the subset, all predecessors are also in the subset. The major results are (1) a method for enumerating all feasible subsets and (2) a method for assigning to each feasible subset an easily computed label that can be used as a physical address for storing information about the subset. These two results permit a very compact computer implementation of a dynamic programming algorithm for solving one-machine sequencing problems with precedence constraints. This algorithm appears to be much more efficient than previous ones for certain one-machine sequencing problems.
Maximum Return from a Collection of Standard and Special Appreciating Assets
Authors: Lembersky Mark R.
Published: November 2008

In a variety of circumstances, a portion of the items in a collection of appreciating assets (such as a collection of forest stands or fine wines) are “special” in that their value growth with age follows a different pattern than the “standard” assets. Of interest is the order of selling, harvesting, or otherwise converting the assets that maximizes the total discounted return accrued. For a zero interest rate and no special assets, the situation is analogous to an inventory depletion model for which FIFO (“first in, first out”) is known to be optimal. However, we show by example that FIFO is not optimal when special assets are present. We introduce SAFO (“smallest appreciation, first out”) and prove it is the optimal ordering under all interest rates and for any number of special assets.
A Computer-Assisted System for the Routing and Scheduling of Street Sweepers
Authors: Bodin Lawrence D. , Kursh Samuel J.
Published: November 2008

This paper discusses a computer-assisted method for routing and scheduling street sweepers in a municipality. We present the basic structure of this vehicle routing and scheduling problem, formulate the street-sweeper routing problem, and explain the algorithm. The computer implementation based on this algorithm is then described. Computational experience with the system in New York City and Washington, D.C., is presented and the obstacles to and successes with implementation are discussed.
Distance Constraints for Tree Network Multifacility Location Problems
Authors: Francis Richard L. , Lowe Timothy J. , Ratliff H. Donald
Published: November 2008

We consider the problem of finding locations for new facilities in an imbedded tree network with respect to existing facilities, with upper bounds imposed on distances between all pairs of facilities. We obtain necessary and sufficient conditions, termed separation conditions, for the distance constraints to be consistent. We find string models useful in obtaining insight into the conditions. These separation conditions involve shortest paths through an associated network that has as arc lengths the upper bounds on pair-wise facility distances. Also, we give an algorithm that constructs a feasible solution to the distance constraints if one exists. As an application of the separation conditions, we solve a multifacility minimax location problem. Most of the results obtained in this paper are also true when distances are Tchebyshev between facilities in Rp, p ≥ 1, or are rectilinear between facilities in R2. Further, the results of this paper should be useful in addressing “nonlinear” minimax location problems and multiobjective, multifacility location problems.
On the Convergence of a Class of Iterative Methods for Solving the Weber Location Problem
Authors: Ostresh Lawrence M.
Published: November 2008

The location problem is to find a point M whose sum of weighted distances from m vertices in p-dimensional Euclidean space is a minimum. The best-known algorithm for solving the location problem is an iterative scheme devised by Weiszfeld in 1937. The procedure will not converge if some nonoptimal vertex is an iterate, however. This paper solves the problem of vertex iterates and presents a general proof permitting a variable step length (within certain bounds). This property is used, in particular, to show the convergence of a modified gradient Newton-Raphson type of procedure.
Evaluating Offensive Performance in Baseball
Authors: Pankin Mark D.
Published: November 2008

We introduce a new statistic for evaluating offensive performance in baseball: the offensive performance average (OPA). The OPA is based on the increase in expected runs caused by the batter and includes the contributions of his stolen bases. This paper also discusses some other averages used for offensive evaluations and ranks the averages by means of correlation coefficients using team data for 1965–1975. Some variations on the OPA are given and the OPA is used to provide a list of the ten best major-league offensive players of all time.
Existence of Optimal Simple Policies for Discounted-Cost Inventory and Cash Management in Continuous Time
Authors: Constantinides George M. , Richard Scott F.
Published: November 2008

We formulate a continuous-time, infinite-horizon, discounted-cost cash management model with both fixed and proportional transactions costs and with linear holding and penalty costs. We model the cumulative demand for cash by a Wiener process with drift and use the optimal control technique of “impulse control” to find sufficient conditions under which an optimal policy exists. We show that these conditions are always met. Therefore, we prove that there always exists an optimal policy for the cash management problem and that this policy is of a simple form. When the proportional transactions cost of decreasing the cash balance is sufficiently high, it is never optimal to decrease the cash balance. Then the cash management model degenerates to the inventory model. We prove that there always exists an optimal policy for the inventory model and that this policy is of a simple form. Under special cases of the cash management model we obtain analytic expressions for the parameters of the optimal policy.
A Dynamic Optimization Model for Distributed Databases
Authors: Levin K. Dan , Morgan Howard Lee
Published: November 2008

We present a dynamic programming formulation for solving the problem of locating files in heterogeneous, distributed computer networks. The model presented permits the access rates for information from files to vary over time, takes into account the fact that programs accessing files may only be permitted at certain nodes, and solves this general T-period problem. Special features are used to limit the growth of the state space so that a computationally feasible algorithm results. Finally, we present an example to illustrate the use of the algorithm.
A Class of FIFO Queues Arising in Computer Systems
Authors: Coffman Edward G. , Hofri Micha
Published: November 2008

We model secondary memory devices as single-server queuing systems. The non-random access to data within these devices is explicitly accounted for as “set-up” times. Requests are typed by the location of the desired record. No distinction is made between “read” and “write” requests. Each request is assumed to be satisfiable from one location on the device (e.g., a single directory search may result in a number of distinct requests). Requests arrive according to a homogeneous Poisson process. The types of successive requests form a first-order Markov chain, which is an approximation of reality. Alternative computational procedures and closed expressions are given for queue length, waiting times, and device utilization. We present some specializations to disks and drums. Only FIFO service is considered.
A Processor Utilization Model for a Multiprocessor Computer System
Authors: Nance Richard E. , Bhat U. Narayan
Published: November 2008

Using a G/M/s/N queuing system model, we develop a processor utilization model for a simplified multiprocessor computer system. Jobs are assumed to arrive according to a general input process, and each job is assigned randomly to an available processor. A finite capacity input buffer is used if no processor is available. The mathematical model is based on the busy period analysis, and two utilization measures are derived: processor utilization (the fraction of processor occupation time during a busy cycle) and system utilization (the fraction of actual utilization time for all processors). A computational model for these utilization measures is developed through an imbedded Markov chain approach. Experimentation with the computational model reveals the sensitivity of the model to variability in the arrival process. Comparison of 2-processor and 4-processor systems from the operator perspective indicates a qualified preference for the behavior of the 2-processor system. This preference must be carefully interpreted since processor costs, the increase in overhead with an increase in processors, and behavioral variables reflecting the user perspective are excluded.
Simulation of Response Times in Finite-Capacity Open Networks of Queues
Authors: Iglehart Donald L. , Shedler Gerald S.
Published: November 2008

We extend to two types of finite-capacity open networks a previously developed technique for the estimation by simulation of job response time characteristics in closed queuing network models of multiprogrammed computer systems. Particular stochastic point processes associated with a Markov renewal process generate arrivals to the networks. Such arrival patterns are useful for representation of the work load of the computer system being modeled. The regenerative method for simulation of stochastic systems and the idea of tracking a marked job in the network form the basis for the estimation technique. We also report illustrative simulation results.
Some Experimental Observations on the Behavior of Composite Random Number Generators
Authors: Nance Richard E. , Overstreet Claude
Published: November 2008

We describe a series of experiments with composite random number generators using shuffling tables. The research explores the issues of improvement in statistical behavior claimed for composite generators and the overhead incurred by shuffling. On the basis of the limited experimental work, three observations are warranted: (1) Shuffling does not effect significant improvement in the statistical behavior of good simple generators implemented on large-word-length machines (with large periods). (2) Shuffling can significantly improve the behavior of generators on small-word-length machines, at least partly by increasing the maximum period obtained. (3) A table size of two leads to results comparable with larger tables and incurs less overhead.
Design of a Computerized Message-Switching Center
Authors: Stashevsky S. , Adiri I.
Published: November 2008

This paper deals with the design of a computerized message-switching center using a mini-computer. We use two complementary approaches: an approximate mathematical model and more realistic simulations. Results are compared and discussed.
A Preference Order Dynamic Program for a Stochastic Traveling Salesman Problem
Authors: Kao Edward P. C.
Published: November 2008

Consider a traveling salesman problem with stochastic travel times. Our objective is to find a tour with maximum probability of completion by a specified time. This paper presents a preference order dynamic program for solving the problem. To facilitate computation, we introduce a branch-and-bound strategy in the solution procedure. Finally, we propose an implicit enumeration algorithm as an alternative approach.
Errata
Authors: Cover Thomas M.
Published: November 2008

Errata to Cover, T., C. Keilers. 1977. An offensive earned-run average for baseball. Opns. Res. 25 729–740.
Criteria for Proportional Representation
Authors: Balinski M. L. , Young H. P.
Published: November 2008

We investigate methods to allocate seats in proportional representation systems in terms of several underlying common-sense properties. In particular, the idea of stability is introduced, and the method of Jefferson (or d'Hondt) is characterized.