bluuebunny/crossref_metadata_2025 huggingface dataset:
A Dynamic Programming Algorithm for Decision CPM Networks
Authors: Hindelang Thomas J. , Muth John F.
Published: November 2008

This paper proposes a dynamic programming algorithm for decision CPM (DCPM) networks. DCPM is a natural, powerful, and general way of handling the discrete-time/cost-tradeoff problem. Solution approaches developed to date have not been efficient enough to handle realistically sized problems. The main approaches have been general integer programming algorithms and the specialized branch-and-bound methods for DCPM of Crowston and Wagner. Both of these approaches have many inherent shortcomings solution times grow exponentially with the number of decision nodes, storage requirements quickly become excessive, pre-processing or decomposition of the problem must be undertaken before the algorithms themselves can be called upon to solve the problem, and large variations in solution times have been found based on differences in the structure of the problem. The algorithm presented here overcomes all of these shortcomings. Most significantly, it exhibits only a linear growth in the solution times based on the number of connections between nodes. In addition, the structure of the algorithm is such that it simultaneously determines the optimal solution for any desired number of project due dates with only a slight increase in computer time. This feature provides valuable information in performing a sensitivity analysis for the project and in preparing for negotiations about the project due date, etc. Test problem results are reported and recommendations are made for extending the algorithm to handle related problems.
Information Systems for Observing Inventory Levels
Authors: Stohr Edward A.
Published: November 2008

This paper analyzes some problems in the design of information systems for observing and reporting inventory levels. The designer has simultaneously to choose a system for observing inventory and a method for incorporating the information obtained into an estimate of inventory levels. With regard to the observation system the designer can choose to use “physical stocktaking” or the “perpetual inventory” method in any period. With regard to the estimation system the designer can choose to use the observations themselves in forming the estimates of the inventory level (conventional system), or he can process the observations to form estimates of inventory levels that are optimal in a least-squares sense. We develop techniques for information system design and provide numerical examples.
Optimal Inspection Schedules for Failure Detection in a Model Where Tests Hasten Failures
Authors: Wattanapanom N. , Shaw L.
Published: November 2008

Methods are well known for determining testing times to minimize the mean cost of testing plus mean cost of an undetected failure (linear in the mean time between failure and detection) when testing does not degrade a good system. Here, we introduce a model in which the ith test increases the remaining failure rate without changing the form of the conditional lifetime distribution. We give algorithms for finding the best testing times in cases of uniform and exponential failure time distributions. Optimization over a single cycle is considered first, and then the case with component renewals is solved using the mean-loss-per-unit-time criterion.
A Simple Method for Reducing Queuing Times in M/G/1
Authors: Matthews D. E.
Published: November 2008

In many queuing situations customers are served in order of arrival; yet if customers with shorter service times were served first, it is well known that the mean queuing time could be reduced considerably. In a comparison with the “optimal” shortest service-time rule, a simple queue discipline involving only two non-preemptive priority classes fares very well. Numerical results illustrate the practical effects of implementing this simple alternative to service in order of arrival in a variety of queuing situations.
Competitive Bidding: A Comprehensive Bibliography
Authors: Stark Robert M. , Rothkopf Michael H.
Published: November 2008

This bibliography identifies almost 500 titles, which, with a few exceptions, deal with quantitative models related to competitive bidding. The papers vary widely. They include ad hoc advice to bidders, analytical models of single and multiple auctions, evaluations of the use of auctions for allocating resources, and analyses of historical data on bidding. Some deal with competitive bidding in general while others relate to particular markets. Many of the entries are devoted to competitive bidding for construction contracts, oil exploration rights, and securities.
Technical Note—Average Costs in a Continuous Review (s, S) Inventory System with Exponentially Distributed Lead Time
Authors: Wijngaard J. , Van Winkel E. G. F.
Published: November 2008

We describe a very elementary direct numerical method to find the average number of backorders, costs and related quantities in a continuous review (s, S) inventory system with exponentially distributed lead time. This method can also be used in the study of E/M/C queues with state-dependent service and arrival rates.
Two-Period Stochastic Programs with Simple Recourse
Authors: Everitt R. , Ziemba W. T.
Published: November 2008

Stochastic programs are said to have simple recourse if the state vector in each period is uniquely determined once all previous decision and random vectors are known. This paper considers two-period problems of this nature. A number of important business and economic problems such as those concerned with inventory management, portfolio revision, cash balance management, and pension fund management can be formulated effectively as problems in this class. We present conditions that ensure that there is an equivalent deterministic convex program that has a directionally differentiable objective function. Detailed expressions enabling one to calculate the directional derivative are derived. Thus it is possible to use Hogan's modification of the Frank-Wolfe algorithm, which applies for two-stage convex programs, in the solution of these two-stage stochastic convex programs. Easily calculated bounds on the optimal objective value and the problem's Kuhn-Tucker conditions are presented. We consider the important special cases when there are no lagged state variables, discrete probability distributions, and direct reduction possibilities. We show that these cases, which frequently arise in practice, yield equivalent static problems. The problems of cash balance and pension fund management are treated in detail.
The Multiple-Choice Knapsack Problem
Authors: Sinha Prabhakant , Zoltners Andris A.
Published: November 2008

The multiple-choice knapsack problem is defined as a binary knapsack problem with the addition of disjoint multiple-choice constraints. The strength of the branch-and-bound algorithm we present for this problem resides with the quick solution of the linear programming relaxation and its efficient, subsequent reoptimization as a result of branching. An implemented version of this algorithm has performed well on a large set of test problems. We cite computational results as well as a comparison with a previously reported algorithm. Several useful applications of the multiple-choice knapsack problem are also suggested.
The Indefinite Quadratic Programming Problem
Authors: Kough Paul F.
Published: November 2008

We develop several algorithms that obtain the global optimum to the indefinite quadratic programming problem. A generalized Benders cut method is employed. These algorithms all possess ϵ-finite convergence. To obtain finite convergence, we develop exact cuts, which are locally precise representations of a reduced objective. A finite algorithm is then constructed. Introductory computational results are presented.
Estimation of Parameters of Zero-One Processes by Interval Sampling: An Adaptive Strategy
Authors: Brown M. , Solomon H. , Stephens M. A.
Published: November 2008

We have considered before the problem of estimating the parameters giving the mean time in each stage, for a two-stage Poisson process, when sampling was permitted only at equal intervals. It was impossible to get good results unless the intervals were small. We now propose an adaptive strategy in which the interval is successively halved until a suitable stage is reached; then all samples can be combined to give estimates. The strategy is examined by Monte Carlo methods, and it is shown to give a considerable improvement over the one-stage method. Figures are given to illustrate the results; they can be used also to improve estimates and give confidence intervals. We propose a technique to give an approximate confidence ellipse for the two parameters, which works well for the ranges considered.
Optimizing Advertising Expenditures in a Dynamic Duopoly
Authors: Deal Kenneth R.
Published: November 2008

The marketing problem of determining the optimal timing of advertising expenditures over a finite planning horizon in a duopoly conflict situation is portrayed as a non-zero-sum differential game. Advertising expenditures are determined which optimize multiobjective performance indices in a Nash equilibrium sense. The dynamics of the market are described by utilizing an extension of the Vidale-Wolfe model of the sales response to advertising. A numerical algorithm is used to solve the model.
A Queueing Theory, Bayesian Model for the Circulation of Books in a Library
Authors: Morse Philip M.
Published: November 2008

The use of library materials is analogous to a queueing process where an arrival is “serviced” when he finds a book on the shelf and borrows it; when service is busy the arrival is lost to the system. Circulation, rate of output of the service channel, can be measured for each book; the circulation distributions for a number of classes of related books (homogeneous collections) have been determined. Circulation rate can be changed by changing circulation rules whereas the total rate of arrival for a book, whether “serviced” or not, is less affected by changes in rules. Although this total arrival rate (called demand rate) for a book cannot be measured directly, its expected value may be calculated, using Bayes' theorem. From this is developed a self-consistent model of book circulation with inter-related probability distributions, from which one can predict the effect on circulation of a change in loan rules or of the purchase of duplicate copies of the more popular books, and can also measure the decline in demand for a book with time. Results check available data on six collections in two libraries.
On the Stationary Analysis of Continuous Review (s, S) Inventory Systems with Constant Lead Times
Authors: Sahin Izzet
Published: November 2008

We derive time-dependent and stationary distributions of inventory position and on-hand inventory under the (s, S) policy for a continuous review inventory system with general inter-arrival and demand distributions and a constant lead time. Some results are also obtained for the characterization of the optimal policies.
The Sum of Serial Correlations of Waiting and System Times in GI/G/1 Queues
Authors: Pagurek B. , Woodside C. M.
Published: November 2008

We develop an expression for the sum of the serial correlation coefficients for time in system or waiting time for successive customers in a GI/G/1 queue. In our approach the interarrival time distribution is represented in terms of a class Kr distribution with a rational Laplace-Stieltjes transform. Thus Erlang, hyperexponential, and weighted sum-of-Erlang arrivals are treated exactly and approximate results can be found for other distributions. We present computed results for some Erlang/Erlang systems.
The Two-Machine Maximum Flow Time Problem with Series Parallel Precedence Relations
Authors: Sidney Jeffrey B.
Published: November 2008

The n-job 2-machine flow shop problem with series-parallel precedence constraints is considered with the objective to minimize makespan. Recent results of Kurisu are utilized in the development of a polynomial bounded optimal algorithm.
Technical Note—A Note on the Nerlove-Arrow Model under Uncertainty
Authors: Sethi Suresh P.
Published: November 2008

This note examines the stability of an optimal control problem based on a particular stochastic extension of the Nerlove-Arrow advertising model. It is shown that depending on the parameters of the problem and the initial conditions, the optimal solution may converge monotonically or sinusoidally, or not converge at all to the optimal stationary equilibrium.
Technical Note—Constraint Qualifications for Inexact Linear Programs
Authors: Pomerol J. Ch.
Published: November 2008

By means of a new constraint qualification, we establish a duality theorem for inexact linear programs, complementing the results stated by Soyster, which, as shown by two examples, are not generally true without further assumptions. Qualifications are then discussed in this context.
Letter to the Editor—To the Editor
Authors: Kruse W. Karl
Published: November 2008

Kruse and Kaplan (Kruse, W. K., A. J. Kaplan. 1973. Comments on Simon's two echelon model. Opns. Res. 21 1318–1322.) identified a logical flaw in a paper by Simon (Simon, R. M. 1971. Stationary properties of a two-echelon inventory model for low demand items. Opns. Res. 19 761–773.), which modeled a two-echelon inventory system composed of a number of independent bases using S − 1, S replenishment policies, and a common depot using a more general R, Q type policy.
Errata
Authors: O'Donovan T. M.
Published: November 2008

Author's response to a comment about an error in his paper O'Donovan, T. M. 1974. Direct solutions of M/G/1 processor-sharing models. Opns. Res. 22 1232–1235.
Structural Results for Partially Observable Markov Decision Processes
Authors: Albright S. Christian
Published: November 2008

This paper examines monotonicity results for a fairly general class of partially observable Markov decision processes. When there are only two actual states in the system and when the actions taken are primarily intended to improve the system, rather than to inspect it, we give reasonable conditions which ensure that the optimal reward function and the optimal action are both monotone in the current state of information. Examples of maintenance systems and advertising systems for which our results hold are given. Finally, we examine the case where there are three or more actual states and indicate the difficulties encountered when we attempt to extend the monotonicity results to this situation.
Some Layout Problems on the Line with Interdistance Constraints and Costs
Authors: Chan Albert W. , Francis Richard L.
Published: November 2008

We study several facility layout problems on the line with minimum-separation constraints and costs proportional to distances between facilities. We obtain virtually closed-form solutions to the problems by applying simple ordering procedures. The solutions all have the property that the facilities most used, or of smallest sizes, are in the middle.
Bayes Estimation of Reliability Using an Estimated Prior Distribution
Authors: Padgett W. J. , Tsokos Chris P.
Published: November 2008

Suppose that the conditional failure time distribution F(t ∣ θ) depends on a random parameter θ whose probability distribution G(θ) is unknown. The unconditional failure time distribution is FG(f) = ∫F(t ∣ θ) dG(θ). In this paper we consider the estimation of G in reliability models when a priori information about the parameter θ is specified in the form of an initial guess, G0, of G. Utilizing the concepts of Dirichlet process priors on G, a Bayes estimate F̂G of FG may be obtained based on k observed lifetimes from FG. Then an estimate Ĝk of G is found from F̂G using a linear programming approach. For the Weibull failure time distribution F(t ∣ θ) with random scale parameter θ, the effect of using the estimated prior Ĝk in Bayes estimation of reliability is studied by Monte Carlo simulations.
Technical Note—Minisum Ip Distance Location Problems Solved via a Perturbed Problem and Weiszfeld's Algorithm
Authors: Morris James G. , Verdini William A.
Published: November 2008

The classical iterative algorithm originally proposed by Weiszfeld for solving minisum facility location problems is generalized to the case of Ip distances. A differentiate approximating function is used to replace the original nondifferentiable convex objective function. The approximating function is shown to be uniformly convergent to the original objective function as a smoothing constant approaches zero. Characterizations and convergence properties peculiar to the algorithm are discussed, and computational experience is presented. The straightforward extension to multifacility location problems is also developed.
Technical Note—A Generalized Maximum Entropy Principle
Authors: Thomas Marlin U.
Published: November 2008

We describe a generalized maximum entropy principle for dealing with decision problems involving uncertainty but with some prior knowledge about the probability space corresponding to nature. This knowledge is expressed through known bounds on event probabilities and moments, which can be incorporated into a nonlinear programming problem. The solution provides a maximum entropy distribution that is then used in treating the decision problem as one involving risk. We describe an example application that involves the selection of oil spill recovery systems for inland harbor regions.
Evaluating Alternatives Involving Potential Fatalities
Authors: Keeney Ralph L.
Published: November 2008

A critical aspect of many major decisions involves the possible loss of human life. Thus, in evaluating the alternatives, it is desirable to address this issue. This paper proposes a cardinal utility model for evaluating the potential fatalities and the uncertainty of their occurrence. It separates the overall consequences of fatalities into a personal direct impact and a societal indirect impact. Separate preference models are built for each impact and integrated to provide an overall evaluation of the potential fatalities. An assessment procedure is discussed and illustrated.
Clinical Decision Analysis
Authors: Fischhoff Baruch
Published: November 2008

An analogy is drawn between decision analysis and the somewhat older profession of psychotherapy. Both offer a variety of techniques designed to help people function in a difficult and uncertain environment; both developed rapidly, sustained by a coherent underlying theory and anecdotal evidence of having helped some clients. Over the past half century, psychotherapy has faced a series of crises concerned with its transformation from an art to a clinical science. These include testing the effectiveness of various forms of therapy, validating elements of treatment programs and of the assumptions underlying therapy, improving the clinical skills of individual practitioners, and considering the broader political, social, ideological and ethical issues raised by psychotherapy. It is hoped that by considering the issues that a related profession has identified, the approaches it has developed to study those issues, and the (partial) conclusions it has reached, we can facilitate the development of decision analysis.
An Assessment of Decision Analysis
Authors: Howard Ronald A.
Published: November 2008

Making decisions is what you do when you don't know what to do. Decision analysis is a process that enhances effective decision making by providing for both logical, systematic analysis and imaginative creativity. The procedure permits representing the decision-maker's information and preferences concerning the uncertain, complex, and dynamic features of the decision problem. As decision analysis has become more accepted and influential the ethical responsibility of decision analysts has increased. Analysts must be sensitive to assuming improper roles of advocacy and to participating in analyses whose means or ends are ethically repugnant. Criticisms of decision analysis are examined at three levels. Application criticisms question how much decision analysis improves actual decision making. Conceptual criticisms argue that the decomposition and recomposition of the decision analysis process may lend to a misshapen framing of the problem or to a suppression of “soft” or “fragile” considerations. Criticisms at the level of principle grant the effectiveness and comprehensiveness of decision analysis but express fear that the process may legitimize decisions otherwise questionable because of their end-state value system or their anthropocentric focus. Decision analysis is the most effective decision methodology yet advanced. Sensitivity to practical and ethical concerns about its use can only increase its effectiveness.
Decision Analysis Assessment of a National Medical Study
Authors: Shachtman Richard H.
Published: November 2008

To decide whether or not to undertake an expensive national survey to determine the effectiveness of infection control, we devised a quantitative decision model to analyze the costs and probabilities of successful study outcomes. The result allowed us to determine whether the proposed study method and design would provide sufficient statistical power to ensure meaningful conclusions from the research. The model was robust in assessing the adequacy of method accuracy and, within the range of assumptions specified, it suggested that the project should be undertaken. The results helped to secure official approval and funding for this large-scale research project. A novel approach to evaluating sensitivity analysis is included. As constructed, the model is applicable to other projects in applied research and, with some modification, to projects in basic research as well.
A Task Force Decision Analysis
Authors: Smallwood Richard D. , Morris Peter A.
Published: November 2008

This paper describes the process and content of a major decision analysis performed for a Xerox corporate task force. The decision, which crossed many traditional organizational boundaries, concerned whether new manufacturing facilities should be constructed to produce consumables for a new Xerox product; and if so, when. One of our roles as analysts for the task force was to serve as the communication channel to the many organizations involved in the decision. The paper focuses on the process by which we were able to use decision analysis to resolve the many conflicting issues surrounding the problem. The mathematical model constructed for the decision analysis was the key element in accomplishing these tasks, and several of the component models are described in some detail. Several interesting aspects of the sensitivity analysis are outlined, including a scenario analysis that eliminated the need for a detailed treatment of uncertainty. The final recommendations to the task force, which were accepted, are also described.
Evaluating the Effectiveness of a New Method for Computing Approximately Optimal (s, S) Inventory Policies
Authors: Freeland James R. , Porteus Evan L.
Published: November 2008

A new method for obtaining approximately optimal (s, S) inventory policies was presented recently as an illustration of a general approximation methodology proposed by Porteus. This paper seeks to evaluate that method numerically Our numerical work showed that when demand was normally distributed the method performed very well. The performance was good but diminished somewhat when demand followed a negative binomial distribution which was approximated by a normal distribution for purposes of the method. The empirical method of Wagner, O'Hagan and Lundh was evaluated concurrently. It also performed very well. Although its performance was not as good as that of the new method, it required less computational effort. The question of whether one of these approximate methods can provide improved performance in practical periodic review systems was raised. A partial answer was obtained by examining the performance of policies found by using a continuous review model. Both the new method and the empirical method outperformed these policies.
Bounds on the Effect of Aggregating Variables in Linear Programs
Authors: Zipkin Paul H.
Published: November 2008

This paper explores the effects of aggregating variables in large linear programs. We define a reasonable criterion for the resulting loss in accuracy, and derive bounds on this quantity. A posteriori bounds may be calculated after solving the aggregated problem, and a priori bounds before. Also, we show that standard iterative methods can be used to improve the accuracy of a given aggregated problem. A numerical example illustrates the results.
Technical Note—A Note on Quality Control under Markovian Deterioration
Authors: Hughes John S.
Published: November 2008

This note reformulates a two-action, two-state sequential quality control model as a renewal problem leading to a one-dimensional search as a solution method in place of the backward induction method of dynamic programming.
Technical Note—A Look at Finding Points of a Convex Polyhedron Using Relaxation and Subgradient Procedures
Authors: Koehler Gary J. , Kumar Surya
Published: November 2008

Subgradient optimization and relaxation are two of the common approaches to finding a point of a polyhedron when conventional procedures like the simplex method are ruled out due perhaps to the size of the problem. In this note we generalize a useful relaxation procedure and show the equivalence of this new procedure with a well known subgradient method.
A Decoupling Inventory Problem with Storage Capacity Constraints
Authors: Bell Peter C.
Published: November 2008

This paper presents a model of a two-stage production process in which the output of stage one, and the demand at stage two, are generated by independent stochastic processes. The stages are decoupled by storage of intermediate product, but there are strict limits on the available storage capacity, and the rates of flow of product into, and out of, the decoupling inventory. Product which cannot be stored is wasted. A model is formulated which enables the firm to determine the optimum capacities for the storage facility, and to determine the value of an additional supply of intermediate product. Problems of this type are common in the chemical industry, when the intermediate products are liquid or gaseous. The final part of the paper describes an application of the model in an ethylene gas complex.
Lanchester-Type Equations of Combat which Account for Multiple Killing Hits
Authors: Mangulis Visvaldis
Published: November 2008

Differential equations are derived for “aimed-fire” combat losses with multiple killing hits taken into account. The multiple killing hits arise because more than one combatant may aim at the same target. The exchanged fire may occur (1) in salvos and (2) random in time. Effects of supporting fires are included. Conditions for equally balanced forces are obtained. The equations in general differ from the usual Lanchester equations, but they do reduce to the Lanchester equations if the single shot probability of kill is small. The force balance equation for random fire does not depend on the time the weapons spend in transit to the target, but it does depend on the fraction of time during which an unfired weapon is committed to a particular target so that the aim cannot be shifted even if the target is killed, and the weapon is launched against the killed target anyway.
On Multiplicative Bidding Strategies
Authors: Rothkopf Michael H.
Published: November 2008

Some models of competitive bidding consider only bidding strategies in which the bid is a preselected multiple of an estimate of the value (or cost) of the subject of the auction. This paper examines the effect of such a restriction on these models. In order to do so, it is necessary to show that the ratio of two positive random variables (e.g., a cost and a cost estimate) cannot be statistically independent of each of them unless the ratio is always the same.
A Single Server Queueing Loss Model with Heterogeneous Arrival and Service
Authors: Niu Shun-Chen
Published: November 2008

A heterogeneous arrival and service single server queueing loss model is analyzed. The arrival process of customers is assumed to be a nonstationary Poisson process with an intensity function whose evolution is governed by a two-state continuous time Markov chain. Different service distributions for different types of customers are allowed. The explicit loss formula for the model considered is obtained. In a special case, it is shown that as the arrival process becomes more regular the loss decreases. For single server loss systems with renewal arrivals, counterexamples are given to show that regularity of arrival and service distributions do not work to good effect in general. Two sufficient conditions for it to be true are given.
Technical Note—A Transient Solution to the Multistage Poisson Queueing System with Infinite Servers
Authors: Jackson R. R. P. , Aspden P.
Published: November 2008

This paper gives an alternative method of deriving the time dependent solution of a multistage nonqueueing process, with random arrivals into the first stage of the system, sufficient servers at each stage and exponential service time distributions. In the standard notation, the system is a finite number of M/M/∞ queues in series (tandem). This method has the advantage over previous methods of being able to solve the case when any of the stage average service times are equal. The solution was obtained during a project concerned with developing a mathematical model of Acute Myeloid Leukemia patient progress.
A Method to Overcome the Ill-Conditioning Problem of Differentiable Penalty Functions
Authors: Charalambous Christakis
Published: November 2008

In recent years there has been considerable interest in the method of modified Lagrangian to solve the nonlinear programming problem. The main reason is that the modified Lagrangian approach overcomes the ill-conditioning problem and the slow convergence of the penalty methods. The purpose of this paper is to present a simple modification to the existing differentiable penalty functions for solving the nonlinear programming problem. This modification overcomes the ill-conditioning problem resulting from the controlling parameter being either too small or too large. Numerical experience is also presented.
Duality in the Cent-Dian of a Graph
Authors: Halpern Jonathan
Published: November 2008

Almost all facility location models seek to minimize either the average distance traveled by all customers to the facility (the median problem), or the distance of the furthest customer from the facility (the center problem). In practice the two objectives are usually antagonistic and yet in many cases both criteria are important (called the cent-dian problem). For such cases the paper presents two possible approaches to model formulation. First is to minimize a function which is a (convex) combination of the furthest (center) and the average (median) objective functions. Second is to minimize one of the criteria, subject to an upper bound on the value of the other criterion. For facility location on a network, it is shown that the first approach is a special case of the second. Furthermore, the two different constrained problems, which exist under the second approach, are dual problems in a well defined sense. Finally the paper provides several features of the tradeoff between the two criteria.
Inspection Procedures when Failure Symptoms Are Delayed
Authors: Sengupta Bhaskar
Published: November 2008

A system fails at time T but does not display any symptoms of failure until time T + S; both T and S are random variables. Detection of failure is possible either because the system displays symptoms of failure or by means of an inspection before the appearance of symptoms. A cost c is associated with each inspection and a cost-rate v is incurred after failure until detection. For a restricted class of failure densities, the inspection procedure that minimizes the total expected cost can be found by means of an iterative algorithm.
A Characterization of Waiting Time Performance Realizable by Single-Server Queues
Authors: Coffman E. G. , Mitrani I.
Published: November 2008

In this paper we study the problem of designing scheduling strategies when the demand on the system is known and waiting time requirements are pre-specified. This important synthesis problem has received little attention in the literature, and contrasts with the common analytical approach to the study of service systems. This latter approach contributes only indirectly to the problem of finding satisfactory scheduling rules when the desired (or required) response-time performance is known in advance. Briefly, the model studied assumes a Markov queueing system with M (priority) classes of jobs. For each class, a desired mean waiting time is given in advance. Making use of a well known conservation law, we prove a necessary and sufficient condition for the existence of a scheduling strategy that achieves the desired performance. We also give a constructive procedure for checking the condition and, if a solution exists, a procedure for finding one such strategy. Our assumptions are discussed and the possibility of relaxing them is explored.
Technical Note—Some Remarks on Scheduling Nursing Personnel
Authors: Roglin Otto
Published: November 2008

In an earlier issue of this journal, Warner published a mathematical programming approach to scheduling nursing personnel. Some inconsistencies in the formulation of his mathematical program are identified, and an alternative objective function for this problem is proposed.
Technical Note—Equivalence of the 0-1 Integer Programming Problem to Discrete Generalized and Pure Networks
Authors: Glover Fred , Mulvey John M.
Published: November 2008

We show how to formulate a 0-1 integer programming problem as a “mixed integer” generalized network and as a discrete “0-U” pure network problem. Special integer programming structures allow convenient simplifications. The usefulness of these formulations is in providing new relaxations for integer programming that can take advantage of recent advances in the development of efficient computer programs for network problems. We cite three practical applications in which these ideas have led to marked improvement in solution efficiency.
Technical Note—Generalized Efficient Solutions for Sums of Sets
Authors: White D. J.
Published: November 2008

Moskowitz developed a useful algorithm for finding admissible decision functions by viewing the expected utility vectors over a finite number of states as the sum of component vectors and developing a recurrence approach. This paper generalizes the results to sum set situations and corrects Moskowitz's proof.
Technical Note—A Note on Computational Modifications to the Gilmore-Gomory Cutting Stock Algorithm
Authors: Haessler Robert W.
Published: November 2008

This note describes modifications to the Gilmore-Gomory cutting stock algorithm that improve the characteristics (other than trim loss) of the solutions generated. Changes are proposed for the procedures that generate the initial solution and subsequent basis entering patterns. The major point is that controlling the pattern generation by using a more restrictive and therefore less efficient formulation of the knapsack problem may reduce rounding problems and pattern changes, and generally broaden the scope of applications of the algorithm. A set of sample problems is solved and computational times are provided.
Technical Note—Duality Theory for Generalized Linear Programs with Computational Methods
Authors: Thuente David J.
Published: November 2008

This paper presents a duality theory for generalized linear programs which parallels the usual duality results for linear programming. The duals are a form of inexact linear programs and can be solved by the simplex method. Computational methods with examples and applications are given.
Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
Authors: Fox Kenneth R. , Gavish Bezalel , Graves Stephen C.
Published: November 2008

A new formulation of the time-dependent salesman problem is presented which uses n3 variables and only n constraints.
Sequencing to Minimize the Maximum Job Cost
Authors: Monma Clyde L.
Published: November 2008

Consider the problem of sequencing a set of jobs in order to minimize the maximum job cost. Examples of such a problem include the one-machine maximum lateness and maximum earliness problems, the maximum cumulative cost problem, and Johnson's two-machine maximum completion time flow-shop problem. The relationships among various maximum cost problems are explored. One such result is that the first three examples cited above are special cases of the final one; even though they appear to be quite different on the surface. A consequence of this fact is that the two-machine maximum completion time flow-shop problem is NP-hard when general precedence constraints are allowed. A maximum cost problem is formulated and shown to generalize the above-mentioned problems. An extension of Lawler's back-to-front sequencing algorithm efficiently solves the unconstrained version of this problem. Finally, two insertion properties, which were motivated by Smith's adjacent pairwise interchange (API) property, lead to efficient algorithms for sequencing with general precedence constraints.
Feature Article—Survey of Nonlinear Programming Applications
Authors: Lasdon Leon S. , Waren Allan D.
Published: November 2008

Several factors imply an increase in the use of nonlinear optimization models. We face serious problems of declining productivity and increasingly scarce, expensive raw materials. Computers are becoming cheaper and faster, and more efficient nonlinear programming (NLP) algorithms are being developed. This paper attempts to illustrate the potential of NLP by describing the application of nonlinear programming models to three classes of problems: petrochemical industry applications, nonlinear networks, and economic planning. Problems in the petrochemical industry ranging from product blending, refinery unit optimization, and unit design to multiplant production, and distribution planning are discussed. The nonlinear networks topic includes electric power dispatch, hydroelectric reservoir management, and problems involving traffic flow in urban transportation networks. In economic planning, we describe NLP applications involving large dynamic econometric models, a variety of static equilibrium models, and submodels of larger planning systems. In each area we consider the problem and its nonlinear model, the various algorithms and software systems which have been applied, and (where available) the benefits derived. Some obstacles are identified which currently inhibit the effective use of nonlinear optimization models, and research aimed at overcoming these obstacles is suggested. A comprehensive bibliography is included.
An Algorithm for Large Zero-One Knapsack Problems
Authors: Balas Egon , Zemel Eitan
Published: November 2008

We describe an algorithm for the 0-1 knapsack problem (KP), which relies mainly on three new ideas. The first one is to focus on what we call the core of the problem, namely, a knapsack problem equivalent to KP, defined on a particular subset of the variables. The size of this core is usually a small fraction of the full problem size, and does not seem to increase with the latter. While the core cannot be identified without solving KP, a satisfactory approximation can be found by solving the associated linear program (LKP). The second new ingredient is a binary search-type procedure for solving LKP which, unlike earlier methods, does not require any ordering of the variables. The computational effort involved in this procedure is linear in the number of variables. Finally, the third new feature is a simple heuristic which under certain conditions finds an optimal solution with a probability that increases with the size of KP. Computational experience with an algorithm based on the above ideas, on several hundred randomly generated test problems with 1,000–10,000 variables and with coefficients ranging from between 10 and 100 to between 10 and 10,000, indicates that for such problems the computational effort grows linearly with the number of variables and less than linearly with the range of coefficients. Average time per problem was less than a second, and the maximum time for any single problem was 3 seconds. Value-independent 0-1 knapsack problems (also randomly generated), were solved with a specialized version of the code in less than one-third of the time required for general 0-1 knapsack problems. To conclude, we identify a class of hard knapsack problems.
Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine
Authors: Vickson R. G.
Published: November 2008

This paper treats the problem of minimizing the total weighted flow cost plus job-processing cost in a single machine sequencing problem for jobs having processing costs which are linear functions of processing times. The optimal job sequence and processing times are obtainable from the solution of an associated problem of optimal row and column selection in a symmetric matrix. Some sufficient conditions for expediting certain jobs are proved. In order to handle cases in which these conditions fail to complete the solution to the problem a heuristic algorithm with a provable performance bound is developed. The heuristic solutions are compared with optimal solutions obtained by branch and bound in numerous randomly generated problems and are found to be optimal in most cases.
Selective Incapacitation Strategies Based on Estimated Crime Rates
Authors: Chaiken Jan M. , Rolph John E.
Published: November 2008

Methods for estimating the crime commission rates of criminal offenders are discussed in the context of a potential selective incapacitation strategy that would assign different sentence lengths according to whether the estimated crime rate is above or below a specified threshold. Any such strategy is subject to error because the true crime rate of an offender may differ from his estimated crime rate. For two strategies having the same cost, one of them is favored over the other if it has a higher expected number of crimes averted or if it has a lower probability of assigning long sentences to offenders with low crime rates. Both of these criteria are met by using a Bayes estimate of the crime rate rather than a maximum likelihood estimate. This is demonstrated by calculating the distribution of true crime rates for offenders whose estimates are above a threshold.
A Queueing System in Which Customers Require a Random Number of Servers
Authors: Green Linda
Published: November 2008

We consider a multiserver queueing system in which customers request service from a random number of identical servers. In contrast to batch arrival queues, customers cannot begin service until all required servers are available. Servers assigned to the same customer may free separately. For this model, we derive the steady-state distribution for waiting time, the distribution of busy servers, and other important measures. Sufficient conditions for the existence of a steady-state distribution are also obtained.
A Natural Gas Flow Model under Uncertainty in Demand
Authors: Levary Reuven R. , Dean Burton V.
Published: November 2008

Storage and purchasing policies that minimize expected shortages of natural gas in the service area supplied by a single natural gas utility are developed. The problem is formulated and solved using a multiperiod linear programming model. The model takes into consideration the variability of weather conditions and its effects on the demand for natural gas. Forecasts of future weather conditions are updated several times during the model planning period. Also, the optimal flows of natural gas are determined at the time that the forecasts are updated. The optimal storage quantities at the beginning of each time period and the consequences of contracting for additional storage facilities on the natural gas shortage are derived by using the model. The natural gas planning strategy is to plan natural gas flows based on forecasted future demand. The optimal flows should be recalculated for future time periods at several computational stages of the model, honoring the orders placed during previous time periods.
A Maxmin Location Problem
Authors: Dasarathy B. , White Lee J.
Published: November 2008

The problem considered is to locate a point in a given convex polyhedron which maximizes the minimum Euclidean distance from a given set of points. The paper describes several possible application areas and shows the existence of a finite set of candidates for the optimal solution. A combinatorial algorithm is presented for the problem in three dimensions, and it is compared with existing nonconvex programming algorithms.
Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
Authors: Potts C. N.
Published: November 2008

The single machine sequencing problem is considered in which each job has a release date, a processing time and a delivery time. The objective is to find a sequence of jobs which minimizes the time by which all jobs are delivered. A heuristic is presented which never deviates by more than 50% from the optimum.
Technical Note—Generalized Covering Relaxation for 0-1 Programs
Authors: Granot Daniel , Granot Frieda
Published: November 2008

We construct in this paper a general purpose cutting-plane algorithm for solving the 0-1 polynomial programming problem of finding a 0-1 n vector x = (xj) that maximizes cTx subject to f(x) ≤ b where f(x) = (fi(x)) is an m vector of polynomials. The algorithm consists of solving a nested sequence of linear generalized covering problems, i.e., covering problems involving both the original variables x and their complements x̄ = 1 − x. Each problem in the sequence is a relaxation of the original 0-1 polynomial program, and is obtained by adding to its predecessor a small number of generalized covering constraints that are violated by the optimal solution for the preceding generalized covering problem. Over 95% of more than 800 randomly generated problems with up to 70 variables and 50 constraints and mostly up to 5 terms in each constraint were solved by our method in less than 90 seconds of CPU time on an AMDAHL 470 V-6 computer.
Concurrent Task Systems
Authors: Lloyd Errol L.
Published: November 2008

We study minimum execution time scheduling of computer task systems where each task may require control of several processors during each step of its execution. Such a task system consists of: m identical processors, tasks T1, …, Tn, and a partial order on those tasks which represents precedence constraints. Associated with each task T1 is a positive integral execution time τ1 and a degree of concurrency q1 ∈ 𝒞 where 𝒞 ⊆ {1, …, m}. Task T1 must execute for τ1, steps and for each of those τ1 steps it requires q1 processors. Minimum length schedules for systems in which all task execution times are equal (concurrent UET task systems) are studied. Three sets of results are given. First, we show that scheduling concurrent UET task systems is NP-complete even if there are only three processors and each task has a degree of concurrency of either 1 or 2. Secondly, given any concurrent UET task system let r be the maximum degree of concurrency of any task. We show that the ratio of the length of an arbitrary list schedule for that system compared to the length of an optimal schedule is bounded above by (2m − r)/(m − r + 1). We also show that the ratio ⌊(2m − r)/(m − r + 1 )⌋ is achievable. Finally, we give an algorithm which produces optimal schedules for concurrent UET task systems on two processors.