bluuebunny/crossref_metadata_2025 huggingface dataset:
Subproblem and Overall Convergence for a Method-of-Centers Algorithm
Authors: Mifflin Robert
Published: November 2008

This paper considers convergence of a method-of-centers algorithm for solving nonlinear programming problems. An upper bound is derived for the number of steps needed to solve each subproblem, defined by the algorithm, when the method of steepest ascent is employed. Also, an upper bound is found for the total number of subproblem steps needed to solve all of the subproblems required to find a feasible point having an objective value with a prescribed maximum deviation from the optimal value.
Technical Note—Stopping Rules for War Games or Combat Simulations with Exponential Life-Times
Authors: Shuford John H. , Grubbs Frank E.
Published: November 2008

Present war game simulations on computers must be run many times because of random outcomes of two-sided conflict that might obscure or not be very sensitive to engineering changes or design objectives for military equipment. Thus, there is a need for stopping rules that will control risks of erroneous judgments in war game simulations or computer games. In view of a new formulation of basic Lanchester combat theory, it is now possible, when games are analyzed in terms of time-to-kill data, to formulate stopping rules in terms of hypothesis testing procedures and reliability theory. This paper develops procedures that not only give explicit stopping rules, but also control the risks of erroneous judgments to acceptable levels for exponential life-times of combat elements.
Approximating the Behavior of Nonstationary Single-Server Queues
Authors: Moore S. C.
Published: November 2008

This paper presents computationally efficient techniques for approximating several behavioral aspects of the Mx(t)/EY/1 queue. The nonstationary arrival stream allows demands for service to follow different distributions over different time intervals. Specific performance characteristics evaluated are the first two moments of queue length, virtual waiting time, and system utilization. These are based on approximating the distribution of Q(t) at the time points E[Tn] by the distribution of Qn, where Tn is the epoch of the nth departure and Qn = Q(Tn + 0). The results are in agreement with those obtained by simulation but require much less computing time. Sample results are presented for both stationary and nonstationary examples.
On-Line and Adaptive Optimum Advertising Control by a Diffusion Approximation
Authors: Tapiero Charles S.
Published: November 2008

We formulate a diffusion approximation to a stochastic advertising model of the Vidale-Wolfe type. This formulation allows solution of problems of optimum and on-line sales forecasting, parameter identification, and advertising control under uncertainty. For practical solutions, we suggest approximations and use simulation to forecast the probabilistic response of sales to an advertising program. Examples contrasting the stochastic process and the diffusion approximations approaches are included.
A Model for Allocating Retail Outlet Building Resources across Market Areas
Authors: Lilien Gary L. , Rao Ambar G.
Published: November 2008

Many factors affect retail outlet profitability, including market potential, distribution and product costs, market pricing levels, cost (and availability) of land or space, and the relation between share of outlets and share of market. This paper presents a model that was used to plan building decisions for outlets for a consumer product across time and market areas. The model has been in use for a number of years and has provided important input for budgeting and planning decisions. The implementation process for this model is also discussed. The model and its use provide an example of what we believe to be a “successful” management science application—the characteristics of and reasons for this success are discussed.
Technical Note—Sufficient Conditions for Insensitivity in Linear Models
Authors: Rosenthal Robert W.
Published: November 2008

This note describes sufficient conditions such that small perturbations in the coefficients of a nonsingular system of linear equations have no effect on some components of the solution vector. Applications in linear programming and game theory are discussed.
Technical Note—Statistical Measures for Linear Functions on Polytopes
Authors: Charnetski Johnnie R. , Soland Richard M.
Published: November 2008

This note presents a technique for obtaining a random sample from an arbitrary N-dimensional bounded convex polyhedral set (polytope). The need for computing the expected value and variance measures for linear functions defined on such sets arises in multiattribute decision problems and in certain classes of linear programming problems. We develop the method and produce formulations for estimating the statistical measures for linear functions. A simple example is presented.
An Actual Application of Collective Choice Theory to the Selection of Trajectories for the Mariner Jupiter/Saturn 1977 Project
Authors: Dyer James S. , Miles Ralph F.
Published: November 2008

This paper describes the use of decision analysis to facilitate a group decision-making problem in the selection of trajectories for the two spacecraft of the Mariner Jupiter/Saturn 1977 Project. This NASA project includes the participation of some eighty scientists, divided by specialization among eleven science teams. A set of thirty-two candidate trajectory pairs was developed by the Project, in collaboration with the science teams. Each science team then ordinally ranked and assigned cardinal utility function values to the trajectory pairs. The scientists used these data and statistics derived from collective choice rules in selecting the preferred trajectory pair.
Ambushing Random Walks I: Finite Models
Authors: Ruckle William , Fennell Robert , Holmes Paul T. , Fennemore Charles
Published: November 2008

We consider a two-person competitive problem in which one player (blue) wishes to move across a rectangular lattice in such a way as to avoid being ambushed by his opponent (red), who has placed obstacles in blue's path. Under some conditions, optimal strategies for blue and red are obtained and the value of the game is computed.
Maintenance Policies When Deterioration Can be Observed by Inspections
Authors: Luss Hanan
Published: November 2008

In this paper we examine maintenance policies for systems in which the degree of deterioration can be observed through inspections. We develop a Markovian model in which the holding times in the various states are exponentially distributed. The costs incurred include costs of inspections, state occupancy costs, costs of preventive repairs, and the costs for repairing a failed system either at an inspection event or immediately after the occurrence of a malfunction. The policies examined include the scheduling of inspections and preventive repairs so that the total expected cost per time unit is minimized.
Dynamic Modeling and Control of Congestion-Prone Systems
Authors: Agnew Carson E.
Published: November 2008

This paper constructs a dynamic model of a general congestion-prone system using a nonlinear differential equation to represent the relation between throughput and the system load. Although the model is not stochastic, it can give a good approximation of the dynamics of oversaturated or undersaturated system operation. The model is used to study the stability and transient behavior of a congestion-prone system and to analyze policies for the control of congestion in a simple optimal control model.
Minimization of a Non-Separable Objective Function Subject to Disjoint Constraints
Authors: Wendell Richard E. , Hurter Arthur P.
Published: November 2008

We consider an important class of mathematical programs, in which the vector variable can be partitioned into two subvectors corresponding to independent constraint sets. Necessary and sufficient conditions for optimal solutions are developed, and two approaches for obtaining solutions are reviewed. We present an enumeration approach, reducing the problem to a finite number of subproblems, and show that duality makes the solution of many of the subproblems unnecessary. Next, we develop an alternating approach, wherein the problem is solved for one of the subvectors while the other is held constant, and then the subvector roles are reversed. This procedure is observed to converge to partial optimum solutions. A widely applicable subclass of problems includes a linear program in one of the subvectors. For this subclass a sufficient condition for local optimality is determined. The condition is easily testable and fails to hold, in many cases, only if a better solution is obtained. Also, this condition shows that partial optimum solutions are almost always local optima.
A Consumer Preference Approach to the Planning of Rural Primary Health-Care Facilities
Authors: Parker Barnett R. , Srinivasan V.
Published: November 2008

A problem in planning the expansion of a rural primary health-care delivery system is to determine the set of facilities to be added to an existing system so as to maximize the incremental benefit to the community subject to a cost constraint. The proposed approach involves the following five steps: (1) identification of facility attributes relevant to patients in their choice of health-care facilities, (2) modeling of an individual's overall preference for alternate facilities as a weighted linear function of these facility attributes, (3) transformation of each consumer's preference model into a benefit function expressing the individual's benefit in dollars/year for an existing or potential facility, (4) provision of a method for determining the total incremental benefit to the community from a set of proposed health-care facilities, and (5) use of a heuristic procedure to determine a set of facilities that yields near-optimum total incremental benefit subject to the cost constraint. A practical application of the proposed approach reveals that the consumer preference model has substantial reliability and predictive validity.
The Assortment Problem with Nonlinear Cost Functions
Authors: Pentico David W.
Published: November 2008

The early work done on the assortment problem assumed a linear production cost and a substitution cost based only on the difference in value of the item used and the item required. The research reported in this paper extends the analysis by considering concave production cost functions and substitution cost functions that add either a unit fixed cost or a unit-independent fixed charge to the previously considered “scrap” cost. The form of an optimal stocking policy is developed for each case and horizon theorems are proved to aid in the computations. Algorithms for finding optimal policies are described.
Technical Note—Surrogate Constraints and the Strength of Bounds Derived from 0-1 Benders' Partitioning Procedures
Authors: Rardin Ronald L. , Unger V. E.
Published: November 2008

One commonly employed branch-and-bound approach to 0-1 mixed-integer programming problems is to use bounds obtained from the Benders' partitioning of the problem as a device to restrict the enumeration. We investigate the strength of such bounds through the development of a Geoffrion-type strongest surrogate constraint for the Benders' problems. We show that such a surrogate constraint can be developed for the complete Benders' integer problem without explicit enumeration of any of the extreme-point constraints. The bound obtained from this surrogate constraint is then shown to be as strong as that obtained from any of the more common Benders-based approaches, but yet exactly equal to the bound obtained from the linear relaxation of the original mixed-integer program.
Sharp Bounds on the Value of Perfect Information
Authors: Huang C. C. , Vertinsky I. , Ziemba W. T.
Published: November 2008

We present sharp bounds on the value of perfect information for static and dynamic simple recourse stochastic programming problems. The bounds are sharper than the available bounds based on Jensen's inequality. The new bounds use some recent extensions of Jensen's upper bound and the Edmundson-Madansky lower bound on the expectation of a concave function of several random variables. Bounds are obtained for nonlinear return functions and linear and strictly increasing concave utility functions for static and dynamic problems. When the random variables are jointly dependent, the Edmundson-Madansky type bound must be replaced by a less sharp “feasible point” bound. Bounds that use constructs from mean-variance analysis are also presented. With independent random variables the calculation of the bounds generally involves several simple univariate numerical integrations and the solution of several similar nonlinear programs. These bounds may be made as sharp as desired with increasing computational effort. The bounds are illustrated on a well-known problem in the literature and on a portfolio selection problem.
Technical Note—Cost/Completion-Date Tradeoffs in the Transportation Problem
Authors: Glickman Theodore S. , Berger Paul D.
Published: November 2008

The transportation problem is reconsidered to include the objective of minimizing the date at which all shipments are completed, in addition to the usual objective of minimizing total shipping cost. After proposing an algorithm requiring reoptimization of the previously determined solution to obtain the next one, we offer an illustration and address the question of tradeoffs between the two objectives.
A Survey of Scheduling Rules
Authors: Panwalkar S. S. , Iskander Wafik
Published: November 2008

In the past two decades researchers in the field of sequencing and scheduling have analyzed several priority dispatching rules through simulation techniques. This paper presents a summary of over 100 such rules, a list of many references that analyze them, and a classification scheme.
Optimal Two-Machine Orderings in the 3 × n Flow-Shop Problem
Authors: Szwarc Wlodzimierz
Published: November 2008

Consider the 3 × n flow-shop problem with machines A, B, and C. By AB and BC optimum we mean optimal solutions produced by Johnson's method for the two-machine problems AB and BC, respectively. Although not every permutation that is an AB and BC optimum simultaneously is an optimal solution of the entire problem, the set P of such permutations does contain an ABC optimum whenever it is not empty. We summarize known analytical results and solution procedures for the 3 × n flow-shop problem.
Intuition in Mathematical Operations Research
Authors: Koopman Bernard O.
Published: November 2008

The object is to understand how to surmount many of the roadblocks encountered in operations research by viewing the subject against the background of science in general. After disposing of some preliminary issues of logic concerning the sufficiency of a body of knowledge to determine the truth (or the probabilities) of statements made in its terms, the scientific method is examined, as based on three processes: A, experimental observation; B, deductive—often mathematical—reasoning; C, “concept formation”—that creative act which (as noted by H. Poincaré) transcends the others. It is the special form of intuition known to the innovative mind, perceiving “order,” “unity,” “harmony,” and leading inductively to general principles. It is not to be confused with mechanical pattern recognition; nor is it just “gut feeling.” Examples are outlined from the mathematical sciences—as well as the counter-example of sterile analyses, dear to officialdom, often unable to see that the whole is greater than the sum of its parts. Finally, historical examples in operations research are given, showing how its road-blocks were overcome by the creative application of concept formation.
Information Theory and the Optimal Detection Search
Authors: Barker William H.
Published: November 2008

This paper establishes a connection between information theory and search theory. In the case of an exponential detection function we show that the search that maximizes the probability of detection also minimizes the information content of the posterior distribution. We also show that if the search plan that maximizes the probability of detection also minimizes the information content of the posterior distribution, then the detection function is exponential. We prove our results in both the continuous and discrete cases.
On the Optimal Operating Policy for the Machine Repair Problem When Failure and Repair Times Have Erlang Distribution
Authors: Coleman Goheen Lola
Published: November 2008

In the machine repair problem we are given m + n identical machines, m operating and n spares. All machines are independent of one another. When an operating machine fails, it is immediately sent to one of K repair facilities and immediately replaced by a spare machine, if one is available. Repair facility i has sj independent and identical repairmen, 1 ≦ i ≦ k. Repairmen work on machines on a one-to-one basis. The cost of repairing a failed machine is a constant depending upon the facility performing the repair. Moreover, if the number of operating machines falls below m, a penalty is accrued at a rate depending on the shortage.

This paper treats the following decision problem: to assign (at the time of each failure) the failed machine to a repair facility so as to minimize the long-run average cost when K ≧ 2 and failure and repair times have Erlang distribution. We show that determining a stationary policy to minimize long-run average cost and long-run average expected cost is equivalent to solving a certain nonlinear program. The nonlinear program has a simple structure and an optimal solution.
On Optimal Dividend, Reinvestment, and Liquidation Policies for the Firm
Authors: Porteus Evan L.
Published: November 2008

We consider the liquid asset management problem of a firm with a fixed business. Two questions are addressed: How much, if any, of the firm's liquid assets should be paid to the owners as dividends? If the liquid asset level is negative (resulting from a net loss in the previous period), should sufficient funds be raised to pay off the corresponding short-term debts, or should the benefit of limited liability be applied by liquidating the firm (declaring it bankrupt)? These questions are addressed in a multiperiod environment under uncertainty. The owners seek to maximize the present expected value of the after-tax returns from dividends less funds invested over the lifetime of the firm. Since the owners must pay income taxes on dividends they receive but cannot deduct the expenses of paying off short-term debts when needed, they have an incentive to have the firm retain some liquid assets as a hedge against having to raise funds to pay off such short-term debts. The form of the optimal policy in the general case is found to be surprisingly complex. A numerical example is used to illustrate the possible complexities. The main thrust of the paper is the presentation of three sets of conditions that are sufficient to prove that there exists an optimal policy with a certain intuitively pleasing and simple form.
Bounds and Approximations in Queuing through Monotonicity and Continuity
Authors: Stoyan Dietrich
Published: November 2008

This paper is a survey of recent research on the monotonicity and continuity of queuing systems and their application to obtain bounds and approximations.
Optimal Search of a Moving Target
Authors: Kan Y. C.
Published: November 2008

There are n boxes. A target is initially in box i with a given probability pı, where pı ≧ 0, ∑pı = 1. Then at discrete time t = 1, 2, …, it moves from box to box. If at time t the target is in box i, then it will be in box i with probability pij at time t + 1, where pij ≧ 0, ∑j pij = 1. A search of box i costs Cı(cı > 0) and finds the target with probability αı if the target is in that box. A sequential search is made. The objective is either to maximize the probability of finding the target in a given number of searches or to minimize the expected searching cost before finding the target. Optimal strategies are characterized for special types of probability matrices [pij] for the n-box model.
Planning Horizons for a Stochastic Lead-Time Inventory Model
Authors: Liberatore Matthew J.
Published: November 2008

The planning-horizon literature has thus far focused on the analysis of deterministic lead-time inventory systems. We show that under certain conditions several planning-horizon theorems hold in the stochastic lead-time case as well. Specifically, demands are assumed non-interchangeable and deterministic; thus production runs are assigned to sets of specific demands and can only be used in the satisfaction of those demands. When holding, backlogging, setup (ordering), and variable production costs are stationary over time, and when the lead-time distribution is invariant over time, it is always optimal to produce for sets of consecutive integral demands. Production dates for specific shipments follow from convexity properties. Building upon these results, we prove several planning-horizon theorems (of the Wagner-Whitin and Zabel varieties). A forward dynamic programming recursion is given. These results are shown to generalize those of the basic dynamic lot-size model. We present a numerical example that illustrates the sensitivity of the optimal policy to changes in lead-time variance.
Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks
Authors: Baker Kenneth R. , Schrage Linus E.
Published: November 2008

We discuss the dynamic programming approach to finding an optimal sequence of a set of tasks when the tasks are related by precedence restrictions. We describe how to use this approach in problems where no explicit precedence relations exist. Computer implementation considerations played an important role in its development. Computational results indicate that, when the curse of dimensionality can be dispelled, dynamic programming can be a useful procedure for large sequencing problems.
Minimization of Time-Varying Costs in Single-Machine Scheduling
Authors: Lawler E. L. , Sivazlian B. D.
Published: November 2008

Suppose n jobs are to be processed consecutively by a single machine, without interruption and without idle time. Each job j has a known processing time pj and has associated with it a time-varying cost density function cj. The cost of processing job j in the time interval [t − pj, t] is Cj(t) = ∫t−pjtcj(u) du. We show that if the cost density functions of the jobs satisfy certain simple conditions, a sequence minimizing total cost is easily obtained. This result generalizes the well-known “ratio rule” of W. E. Smith for minimizing total weighted completion time and is applicable to problems involving discounted linear delay costs, discounted linear processing costs, discounted resetting and processing costs, and linear combinations of these costs. Moreover, we show that for such costs, sequences that are optimal subject to series parallel precedence constraints can be found in 0(n log n) time.
An Analytical Treatment of Policy Function Schedulers
Authors: Ruschitzka Manfred
Published: November 2008

This paper presents an analysis of time-sharing computer facilities using scheduling algorithms defined in terms of priority functions. We consider the class of algorithms in which a job's priority is defined by the difference between the time it spent in the system and an arbitrary function F of its attained service, where F is called the policy function. Our main result, the average response time for a job conditioned on its service requirement, applies to a broad class of policy functions. The derivation is based on the model of a processor-sharing M/G/1 queuing system and does not use transforms. The analysis is simplified by the decomposition of a non-Markovian process. Properties of the average response time resulting from policy function schedulers are discussed and related to those of other known time-sharing scheduling algorithms. For the examples of linear, exponential, and composite policy functions we plot the response times. We demonstrate the flexibility and the limitations of policy functions with respect to the discriminatory treatment of short jobs versus long ones and discuss the optimal selection of a policy function with respect to a given overall performance criterion.
Technical Note—Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties
Authors: Lakshminarayan Sankaran , Lakshmanan Ram , Papineau Robert L. , Rochette Rene
Published: November 2008

We consider a single-machine scheduling problem where penalties occur for jobs that either commence before their target start date or are completed after their due date. The objective is to minimize the maximum penalty subject to certain assumptions on the target start times, due dates, and penalty functions. A more efficient algorithm than the existing one is presented for this problem. The number of computations in the proposed algorithm is of the order of n log n, while in the existing algorithm it is of the order of n2.
Concomitant Control Variables Applied to the Regenerative Simulation of Queuing Systems
Authors: Lavenberg S. S. , Moeller T. L. , Sauer C. H.
Published: November 2008

We investigate using multiple concomitant control variables to reduce the width of confidence intervals when estimating steady-state response variables via the regenerative method of simulation. A concomitant control variable is an estimator of a known quantity, defined with respect to the system being simulated, that is believed to be correlated with the response variable estimator. We give examples of such control variables for two regenerative queuing systems, the stable GI/G/1 queue and a closed queuing system. An estimator that uses multiple control variables involves unknown coefficients; one wishes to choose these coefficients to minimize the variance of the estimator. We establish the asymptotic validity of confidence intervals constructed using control variables when the coefficients themselves are estimated via regenerative simulation. For the response variables and control variables in our examples we compute the variance reduction that could be obtained if the optimum coefficients were known and empirically investigate the variance reduction obtained in practice using various methods for estimating the coefficients. We find that when the coefficients are estimated from a small fraction of the simulated tours the controlled estimators yield confidence intervals whose width is less than and whose coverage is comparable to that obtained without using control variables.
Technical Note—Estimating the Probability Distribution of Travel Times for Urban Emergency Service Systems
Authors: Chelst Kenneth , Jarvis James P.
Published: November 2008

We describe an extension of Larson's hypercube queuing model to enable it to calculate the probability distributions of travel times. In addition, we discuss the general need for this capability in emergency service models as a prerequisite for developing second-generation models that may relate direct outcome measures such as damage, loss of life, and arrests to the managerial decisions.
Analysis of a Single-Buffer Loss-Delay System
Authors: Arthurs E. , Stuck B. W.
Published: November 2008

Tasks arrive at a finite-capacity buffer according to a Markov counting process conditioned on the number in the buffer. A processor visits the buffer at a random time epoch, serves up to a given maximum number of tasks, leaves, and repeats this process. The probability of buffer overflow, and the waiting time of a task until it is processed are studied as a function of model parameters.
Optimal Commitment of Forces in Some Lanchester-Type Combat Models
Authors: Taylor James G.
Published: November 2008

This paper shows that by considering the instantaneous casualty-exchange ratio one can determine whether it is beneficial for the victor to commit as many forces as possible to battle initially in Lanchester-type combat between two homogeneous forces. It considers the initial-commitment decision as a one-sided static optimization problem and examines this nonlinear program for each of three decision criteria (victor's losses, loss ratio, and loss difference) and for each of two different battle-termination conditions (given force-level breakpoint and given force-ratio breakpoint). The main contribution is to show how to determine the sign of the partial derivative of the decision criterion with respect to the victor's initial force level for general combat dynamics without explicitly solving the Lanchester-type combat equations. Consequently, the victor's optimal initial-commitment decision may often be determined from how the instantaneous casualty-exchange ratio varies with changes in the victor's force level and time. Convexity of the instantaneous casualty-exchange ratio is shown to imply convexity of the decision criterion so that conditions of decreasing marginal returns may be identified also without solving the combat equations. The optimal initial-commitment decision is shown to be sensitive to the decision criterion for fixed force-ratio breakpoint battles.
Multidimensional Line Search Using a Binary Preference Relation
Authors: Wehrung Donald
Published: November 2008

A number of interactive algorithms involving line searches have recently been suggested for use when the decision-maker's preferences take the form of a binary relation rather than the standard criterion function. This study examines the extension of well-known line-search procedures based on a criterion function to binary representations for preference and briefly outlines why some procedures are not extendible. Extensions of uniform and golden section line-search procedures are examined in detail. Knowledge of these extensions should assist the user of interactive algorithms to select a line-search procedure that is appropriate for his needs.
Technical Note—An Improved Computational Procedure for Optimal Allocation of Aircraft Sorties
Authors: Schwartz Eleanor L.
Published: November 2008

This note presents a revision to the OPTSA model for optimal allocation of aircraft sorties that shortens its running time. The new procedure uses the fact that not all payoff entries of a game matrix need be known to determine the game solution, and that the computer time spent in simplex operations is insignificant compared to the time spent computing payoff entries. Estimates of the computational savings are given. When the procedure was implemented in a three-stage behavioral game, computational savings of up to 95% over the original model were observed.
Measurable Multiattribute Value Functions
Authors: Dyer James S. , Sarin Rakesh K.
Published: November 2008

This paper presents a theory of measurable multiattribute value functions. Measurable value functions are based on the concept of a “preference difference” between alternatives and provide an interval scale of measurement for preferences under certainty. We present conditions for additive, multiplicative, and more complex forms of the measurable multiattribute value function. This development provides a link between the additive value function and multiattribute utility theory.
Stochastic Models for Pensionable Service
Authors: Sahin Izzet , Balcer Yves
Published: November 2008

This paper investigates the effects of vesting rules and termination rates on the accumulation of pensionable service. First, a theoretical framework is developed, through stochastic models in continuous time, to characterize the cumulative pensionable service with reference to its moments, under an arbitrary age-service vesting rule. In the most general case, the rate of employment termination is allowed to be a function of both age and time spent in an employment. Next, a discrete computational model is presented for the determination of the distribution of pensionable service and of related measures, using age and service-dependent termination rates as input. This model is applied to Canadian Public Service and the results are discussed. Also considered are the employer's perspective and passage from pensionable service to pension benefits.
A Multi-Type Production System for Perishable Inventories
Authors: Deuermeyer Bryan L.
Published: November 2008

This paper develops a one-period model for investigating the properties of the optimal production policy for a system composed of two production processes called types A and B. These in turn produce two perishable stock items called products 1 and 2, having independent random demands and different lifetimes. Type A produces both products in amounts governed by a fixed set of production coefficients. Type B can be used only to manufacture product 2. The optimal starting inventory level is characterized for the one-period problem using the criterion of minimized expected total cost. The optimal production levels are characterized in terms of the starting inventory levels. Results show that the decision space is partitioned into four distinct regions whose boundaries are defined by a point and four hypersurfaces.
A Branch-and-Bound Method for Reversed Geometric Programming
Authors: Gochet Willy , Smeers Yves
Published: November 2008

A general or signomial geometric program is a nonlinear mathematical program involving general polynomials in several variables both in the objective function and the constraints. A branch-and-bound method is proposed for this extensive class of nonconvex optimization programs guaranteeing convergence to the global optimum. The subproblems to be solved are convex but the method can easily be combined with a cutting plane technique to generate subproblems which are linear. A simple example is given to illustrate the technique. The combined method involving linear subproblems has been coded and numerical experience with this code will be reported later.
A Method of Decomposition for Integer Programs
Authors: Sweeney Dennis J. , Murphy Richard A.
Published: November 2008

A method of decomposing integer programs with block angular structure is presented. It is based on the notion of searching for the optimal solution to an integer program among the near-optimal solutions to its Lagrangian relaxation. An optimality theorem is obtained and a generic decomposition algorithm is presented. An application of this approach is discussed and some computational results are reported.
Qualitative Properties and Bounds for the Serial Covariances of Waiting Times in Single-Server Queues
Authors: Bergmann Reinhard
Published: November 2008

For the stationary waiting time process of a GI/G/1 queue we prove the empirically obvious fact that if the service times are increased and the interarrival times decreased, then the correlation of waiting times of successive customers is increased. If the service and interarrival times are respectively larger or smaller than for given exponential service or interarrival times, then the serial covariances of waiting times are bounded by the known covariances for the given exponential case. Also, some general bounds for the covariances are given, and the heavy traffic case is considered. The results are very useful in simulation problems where the mean stationary waiting time is estimated by a sample and it is sought to determine the mean square error of the sample mean.
Technical Note—An Adjustment to the Norman-White Approach to Approximating Dynamic Programs
Authors: Porteus Evan L.
Published: November 2008

This note considers an adjustment to the Norman-White approach of approximating stochastic dynamic problems by using expectations. The expectations are used only in approximating the transition mechanism. The original expected returns are left intact. The adjustment also involves eliminating the policy improvement step proposed by Norman and White. The approach appears to work surprising well on the examples considered. It may turn out to be a competitive practical approach to approximating solutions to the (s, S) inventory model.
Technical Note—A Note on “Queueing Models with Lane Selection”
Authors: Roque Diego R.
Published: November 2008

An article in Operations Research introduced a new class of queueing models, “Queueing Models with Lane Selection.” The author offered solutions based on an erroneous analysis. This note points out where the analysis went wrong.
Development of a Rating System for All Tennis Players
Authors: Blackman Samuel S. , Casey James W.
Published: November 2008

A mathematically based method for evaluating the ability of tennis players is recommended to replace the ad hoc methods now followed. This method involves deriving a numerical rating (TCAP) for each player by utilizing match scores. Such ratings can be put to many uses, such as tournament placement, handicapping, match and tournament result prediction, and player progress evaluation. Extensive results have been obtained for both professional and amateur players, and indications are that eventually all serious tennis players may be rated by the same system. Finally, these results lead to insights into the game, including the conclusion that the professionals have nearly the same variability within their group as do the amateurs within theirs.
Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem
Authors: Jonker R. , De Leve G. , Van Der Velde J. A. , Volgenant A.
Published: November 2008

For the distance matrix of symmetric traveling salesman problems a simple transformation into an equivalent asymmetric one is given. Assignment algorithms yield sharper lowerbounds and less subtours from the transformed distance matrix. This implies a better performance for traveling salesman algorithms based on the assignment relaxation.
An Investment Staging Model for a Bridge Replacement Problem
Authors: Garcia-Diaz Alberto , Liebman Judith S.
Published: November 2008

This paper discusses the formulation and solution of a mathematical model of the selection and staging of bridge replacements in rural road networks. Both relaxation and decomposition strategies are used. First, a relaxation of the problem into a decomposable shortest path problem allows the identification of the bridge replacement alternatives which are most promising with respect to user cost. Next, the planning horizon is divided into time periods which are then ordered according to their relative importance. Finally, another decomposition in the form of a lexicographic optimization is used to select and schedule the bridge replacements. Within this lexicographic optimization a sequence of computationally feasible integer programming problems is solved.
Determining Optimal Use of Resources among Regional Producers under Differing Levels of Cooperation
Authors: Rovinsky Robert B. , Shoemaker Christine A. , Todd Michael J.
Published: November 2008

We determine optimal allocation of means of production between a principal and alternative commodities under varying degrees of cooperation among producers. Producers are grouped into subsets with stipulated efficiencies, costs of production and demand prices. These producers collectively control the production of the principal commodity whose price depends upon total supply. Optimal allocation is determined under conditions of (1) pure competition, (2) cooperation within subsets, and (3) cooperation among all producers. The latter problem is modeled as a nonconcave quadratic programming problem. A very efficient algorithm for solving this problem is presented. This algorithm has been used to determine the optimal distribution of cotton production among 300 regions.
Cyclic Scheduling via Integer Programs with Circular Ones
Authors: Bartholdi John J. , Orlin James B. , Ratliff H. Donald
Published: November 2008

A fundamental problem of cyclic staffing is to size and schedule a minimum-cost workforce so that sufficient workers are on duty during each time period. This may be modeled as an integer linear program with a cyclically structured 0-1 constraint matrix. We identify a large class of such problems for which special structure permits the ILP to be solved parametrically as a bounded series of network flow problems. Moreover, an alternative solution technique is shown in which the continuous-valued LP is solved, and the result rounded in a special way to yield an optimum solution to the ILP.
The Secretary Problem with an Unknown Number of Options
Authors: Stewart T. J.
Published: November 2008

A method of selecting the best element from a random sequence of unknown length is investigated. By assuming that the arrival times of the elements are independent identically distributed (i.i.d.) exponential random variables, a procedure is established that maximizes the probability of selecting the best element. Asymptotically for large values of the actual length of the sequence, the optimal probability is 1/e, which is also the corresponding asymptotic optimal value when the length is known. It is shown that the method behaves well even when the actual number of options is comparatively small, and that it is not particularly sensitive to errors in the specification of the arrival rate of the process.
An M/M/1 Dynamic Priority Queue with Optional Promotion
Authors: Kofman Ehud , Lippman Steven A.
Published: November 2008

We consider an M/M/1 queue with two types of customers: priority customers and regular customers. They arrive at the service facility according to two independent Poisson streams and form a single queue according to the order in which they arrive. The two types of customers are distinguished by the holding costs charged per unit time that each of them resides in the queue. The server can either serve customers according to the order in which they arrive or pay a fixed fee R and promote a priority customer, bypassing the customers ahead of him. The server selects the customers to be served so as to minimize the expected average cost per unit of time of operating the system. We show that whenever the number of regular customers bypassed in a promotion, times the expected holding costs per priority customer per service period, is greater than or equal to R, promotion is strictly optimal. Moreover, for each state there exists a value of R—with R exceeding the number of regular customers bypassed in a promotion, times the expected holding costs per priority customer per service period—for which promotion is optimal. This result contradicts previous work in the literature. In addition, we demonstrate that the set of states from which promotion is optimal decreases in the sense of set inclusion as R increases. This fact is the key to an efficient algorithm.
Optimal Policies for Data Base Reorganization
Authors: Mendelson Haim , Yechiali Uri
Published: November 2008

One of the problems faced by a Data Base Administrator is the determination of a file reorganization policy. The Data Base Administrator has to balance the benefits of a reorganization, which restores processing efficiency and hence reduces operating costs, against the extra expenditures involved (unloading and reloading the files, system unavailability costs, etc.). In this paper we consider both policies of state-dependent reorganization and reorganization at fixed time intervals. We prove that the optimal state-dependent policy belongs to the class of control-limit rules, and show how the optimal control-limit can be evaluated. We then consider the policy of reorganization at fixed time intervals, and show that, when the record arrival process is Poisson, this policy is always inferior to the optimal control-limit rule (for the average-cost criterion). We conclude with an example where operating and reorganization costs increase linearly with system occupancy.
Convergence of the Weiszfeld Algorithm for Weber Problems Using a Generalized “Distance” Function
Authors: Morris James G.
Published: November 2008

This paper considers a generalization of the single and multisource Weber problem for the case when the “distance” function is some power K of the usual Ip distance. Properties of the generalized problem are established, and an appropriate generalization of the Weiszfeld iterative approach is given. A convergence proof is supplied for an ϵ-approximation to the original problem, under certain restrictions on p and K.
A Generalized Decision Support System Using Predicate Calculus and Network Data Base Management
Authors: Bonczek Robert H. , Holsapple Clyde W. , Whinston Andrew B.
Published: November 2008

In view of the growing prominence of corporate modeling, an important area of research concerns techniques for facilitating the design and utilization of models. In this paper we show how first-order predicate calculus can be used as a language for formally stating modeling knowledge. Furthermore, knowledge stated in this manner can be subjected to the resolution principle. The result is that application specific modeling knowledge need not be embedded in a computer program. Rather, it can be stored in a data base and utilized as needed by a problem processing system employing resolution techniques. Advantages of a decision support system taking an approach of this sort are considerable modeling flexibility, capacity for automating the model formulation and execution processes, and compatibility with a high-level user interface language.
On the One-Dimensional Space Allocation Problem
Authors: Picard Jean-Claude , Queyranne Maurice
Published: November 2008

The One-Dimensional Space Allocation Problem (ODSAP) arises when locating rooms along a corridor, when setting books on a shelf, when allocating information items among the “cylinders” of a magnetic disk, or when storing products in certain warehouses. The rooms (objects) to be located have a known length (or width) and, for each pair of rooms, there is a given number of “trips” between them; the problem is to find a sequencing of the rooms which minimizes the total traveled distance. This paper deals first with two particular cases. In the rooted tree case, previous results obtained by Adolphson and T. C. Hu for the Linear Ordering Problem are extended and provide efficient solution methods. In addition, it is shown that most of the assumptions made by Adolphson and Hu are necessary, since relaxing any of them leads to an NP-complete problem. In the case of independent destinations (solved by Bergmans and Pratt when all lengths are equal), a unimodality property is shown for an optimum solution, but this is not sufficient to lead to a “good” algorithm and the problem is shown to be NP-complete. For the general problem, an exact algorithm using dynamic programming is described and computationally tested.
Feature Article—Organizational Design: A Survey and an Approach
Authors: Hax Arnoldo C. , Majluf Nicolas S.
Published: November 2008

The purpose of this paper is to review the major concepts underlying the proper design of an organizational structure for a business firm. It provides a review of the various managerial processes to support decision making in an organization. It discusses the major organizational archetypes (functional, divisional, and matrix organizational forms); presents a brief historical overview of various organizational theories; and finally concludes with recommendations of steps to be undertaken in the design of an organizational structure.
Budget Constrained Optimization of Simulation Models via Estimation of Their Response Surfaces
Authors: Daughety Andrew F. , Turnquist Mark A.
Published: November 2008

This paper is concerned with optimizing simulation models under the condition that a budget on simulation runs exists. A multistage search procedure is developed that allocates the total experimental budget across stages so as to maximize the expected gain in information. At each stage the experiments are allocated to the search region so as to maximize the amount of information provided. A response surface is estimated and used to reduce the search region and predict the optimum, which is then used in the next stage. The procedure continues until the experimental budget is exhausted or a stopping criterion is met.