bluuebunny/crossref_metadata_2025 huggingface dataset:
(R, r) Production/Inventory Systems
Authors: Altiok Tayfur
Published: November 2008

An (R, r) continuous review inventory policy is considered in a production/inventory environment consisting of a production facility and a finished product warehouse for one type of product. The inventory policy indicates that production starts when the stock on-hand reaches r and continues until the stock level reaches R. The demand process is assumed to be compound Poisson and processing times are phase-type. The problem of finding cost minimizing values of r and R is studied through the analysis of the inventory process for both backordering and lost sales cases. Numerical examples are given to show the computational efficiency of the approach and to show the behavior of the optimal R and r with respect to the cost parameters.
Optimal Acquisition of Automated Flexible Manufacturing Processes
Authors: Monahan George E. , Smunt Timothy L.
Published: November 2008

We formulate the problem of converting a labor-intensive batch production process to one that incorporates flexible automation as a finite-state Markov decision process. Interest rates and the level of automated technology influence both operating and acquisition costs and are treated as random variables. The model specifies the optimal level of capacity to convert to flexible automation. The optimization criterion is the minimization of the sum of expected, discounted costs incurred over a finite planning horizon. The optimal acquisition strategy depends upon the time period, the current interest rate, the current level of technology, and a measure of the remaining capacity that is not automated. We investigate the structure of optimal acquisition strategies using mathematical analysis and simulation. Our objective is to illustrate the qualitative characteristics of optimal strategies for acquiring flexible automation. As a step toward the implementation of the model, we examine the qualitative consequences associated with specifying classes of inventory and acquisition cost functions.
Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs
Authors: Lawler E. L. , Martel C. U.
Published: November 2008

Suppose that n jobs, each with a specified processing requirement and due date, are to be preemptively scheduled for processing by a number of parallel machines, with the objective of maximizing the number of jobs that are completed by their due dates. It is known that this scheduling problem is NP-hard, even for identical machines, if the number of machines is variable, that is, specified as part of the problem instance. However, if the machine environment consists of a fixed set of uniform machines, the problem can be solved in polynomial time. An O(n3) algorithm is presented for the special case of two uniform machines. The running time of this algorithm becomes O(Wn2), where W is the sum of the job weights, for the more general problem in which it is desired to minimize the weighted number of late jobs. A fully polynomial approximation scheme is also presented for the weighted case.
On a Two-Stage Birth and Death Queueing Process
Authors: Langaris Christos
Published: November 2008

A sequential two-stage service system with a single server at each stage and finite waiting space in both stages is considered. If the second stage is full, upon a service completion in stage 1, then the customer is unable to emerge from the first stage channel and this channel is blocked. An additional feature of the model is the provision of state-dependent arrival and service rates. The state probabilities pij and all moments of the waiting time of a customer in stage 1 and in the whole system are obtained. Finally, various characteristics of state-dependent tandem systems are evaluated and conclusions are drawn from numerical calculations.
Ex Ante Equity in Public Risk
Authors: Sounderpandian Jayavel
Published: November 2008

In evaluating decision alternatives that involve risk of death among members of the public, there are two types of equity that must be considered, namely, ex ante and ex post equity. Among the two, ex ante equity is more controversial. This paper suggests refinements to recent definitions of ex ante equity, based on distribution of individuals' risks across equally desirable outcomes, and historical inequity.
Methods for Designing Communications Networks with Certain Two-Connected Survivability Constraints
Authors: Monma Clyde L. , Shallcross David F.
Published: November 2008

In this paper, we consider the problem of designing a minimum cost communication network subject to certain two-connected survivability constraints. This problem was motivated by work at Bellcore on planning fiber optic communications networks. We introduce heuristics for constructing initial feasible networks, and local improvement heuristics for reducing the cost of existing network designs while preserving a feasible network. This approach is shown to be effective on data from both real-world fiber optic communications network problems and randomly generated problems.
New Sharpness Properties, Algorithms and Complexity Bounds for Partitioning Shortest Path Procedures
Authors: Glover Fred , Klingman Darwin
Published: November 2008

Building on the framework of partitioning shortest path (PSP) algorithms, we introduce two new methods that exhibit different types of sharpness properties, based on a refinement of the sharpness concept of Shier and Witzgall. We show that the first of these two methods, which we classify as globally sharp, has a complexity bound that is superior to the complexity bound for the previous PSP algorithm, THRESH-S, that exhibits the same sharpness properties. The second new method, which we classify as globally scan-sharp, has a better bound and exhibits sharpness properties that are nearly as comprehensive. Finally, we discuss methods for identifying negative cycles that possess a time-sharpness property.
OR Forum—The Next Decade in Operations Research: Comments on the Condor Report
Authors: Wagner Harvey M. , Rothkopf Michael H. , Thomas Clayton J. , Miser Hugh J.
Published: November 2008

Under the sponsorship of the Systems Theory and Operations Research (STOR) Program of the National Science Foundation, a Committee on the Next Decade in Operations Research (CONDOR) held a 3-day workshop in mid-1987. The report of this committee appeared a year later in Operations Research (pp. 619–637). In view of the importance of this subject, and because CONDOR had, a fortiori, to limit its considerations to a number of important ones of primary interest to its members, a number of other OR analysts of widely different experience were asked to comment on this report. Four of the responses are presented below.
Corrections to “Restricted Subset Selection Procedures for Simulation”
Authors: Sullivan David W. , Wilson James R.
Published: November 2008

Correction to Sullivan, D. W., J. R. Wilson. 1989. Restricted subset selection procedures for simulation. Opns. Res. 37 52–71.
Defense Before or After Bomb-Release-Line
Authors: Ravid Itzhak
Published: November 2008

We compare two alternative modes of defense against attacking aircraft: Engagement BEFORE Bomb-Release-Line (BRL), versus engagement—with a higher kill probability—AFTER BRL. The model examines what mode is preferable under various combinations of criteria, target arrays, defense systems, durations of war and morale vulnerabilities. Engagement BEFORE BRL is only justified when the defender has plenty of forces at his disposal or if the duration of war is going to be very short. Defense AFTER BRL is preferable under the more prevalent conditions of limited resources and moderate attrition rates. The value of the defended targets is relevant to the problem only in a few cases. The implications of this work bear on defense tactics and deployment, as well as on tradeoffs between parameters of defensive weapon systems under development.
A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design
Authors: Balakrishnan A. , Magnanti T. L. , Wong R. T.
Published: November 2008

The fixed-charge network design problem arises in a variety of problem contexts including transportation, communication, and production scheduling. We develop a family of dual-ascent algorithms for this problem. This approach generalizes known ascent procedures for solving shortest path, plant location, Steiner network and directed spanning tree problems. Our computational results for several classes of test problems with up to 500 integer and 1.98 million continuous variables and constraints show that the dual-ascent procedure and an associated drop-add heuristic generate solutions that, in almost all cases, are guaranteed to be within 1 to 4% of optimality. Moreover, the procedure requires no more than 150 seconds on an IBM 3083 computer. The test problems correspond to dense and sparse networks, including some models that arise in freight transport.
A Fast and Simple Algorithm for the Maximum Flow Problem
Authors: Ahuja R. K. , Orlin James B.
Published: November 2008

We present a simple sequential algorithm for the maximum flow problem on a network with n nodes, m arcs, and integer arc capacities bounded by U. Under the practical assumption that U is polynomially bounded in n, our algorithm runs in time O(nm + n2 log n). This result improves the previous best bound of O(nm log(n2/m)), obtained by Goldberg and Tarjan, by a factor of log n for networks that are both nonsparse and nondense without using any complex data structures. We also describe a parallel implementation of the algorithm that runs in O(n2 log U log p) time in the PRAM model with EREW and uses only p processors where p = ⌈m/n⌉.
An Exact Algorithm for the Quadratic Assignment Problem on a Tree
Authors: Christofides Nicos , Benavent Enrique
Published: November 2008

The Tree QAP is a special case of the Quadratic Assignment Problem (QAP) where the nonzero flows form a tree. No condition is required for the distance matrix. This problem is NP-complete and is also a generalization of the Traveling Salesman Problem. In this paper, we present a branch-and-bound algorithm for the exact solution of the Tree QAP based on an integer programming formulation of the problem. The bounds are computed using a Lagrangian relaxation of this formulation. To solve the relaxed problem, we present a Dynamic Programming algorithm which is polynomially bounded. The obtained lower bound is very sharp and equals the optimum in many cases. This fact allows us to employ a reduction method to decrease the number of variables and leads to search-trees with a small number of nodes compared to those usually encountered in problems of this type. Computational results are given for problems with size up to 25.
Using Parallel Iteration for Approximate Analysis of a Multiple Server Queueing System
Authors: Birge John R. , Pollock Stephen M.
Published: November 2008

This paper describes an iterative approach to the analysis of Markovian service systems. The method is approximate unless an assumption of independence among servers is valid. Nevertheless, useful results are attainable that hold intuitive appeal and provide a geometric reduction in the number of states (hence, computation) needed to obtain solutions. We demonstrate the usefulness of the procedure through an error analysis of a simple system. The practical utility of the approach is further justified in a comparison with simulation results for a police patrol model with over 50 million states.
On the Complexity of Scheduling with Batch Setup Times
Authors: Monma Clyde L. , Potts Chris N.
Published: November 2008

Many practical scheduling problems involve processing several batches of related jobs on common facilities where a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. We extend various scheduling models to include batch setup times. The models include the one-machine maximum lateness, total weighted completion time, and number of late jobs problems. In all these cases, a dynamic programming approach results in an algorithm that is polynomially bounded in the number of jobs, but is exponential in the number of batches. We also study the parallel machine model with preemption and show that the maximum completion time, maximum lateness, total weighted completion time, and number of late jobs problems are NP-hard, even for the case of two identical parallel machines, and sequence independent setup times.
An Interactive Multiple Criteria Approach for Parameter Selection in Metal Cutting
Authors: Malakooti B. , Deviprasad J.
Published: November 2008

Many real-world problems, particularly in manufacturing planning, can be expressed as multiple criteria problems. In this paper, we formulate a metal cutting operation, the turning operation, as a discrete multiple objective problem. The objectives are to minimize cost per part, production time per part, and roughness of the work surface, simultaneously. We discuss a heuristic, gradient-based multiple criteria decision making approach that we apply to parameter selection in metal cutting. The approach can be applied to any multicriteria problems with either discrete, integer, or continuous sets of alternatives. The approach is interactive and requires only paired comparisons of alternatives. For the metal cutting problem, we show how efficient alternatives can be generated by a discrete variable approach and how the gradient-based multiple objective approach can be implemented to obtain the most preferred alternative. We also discuss the software package for microcomputers as a decision support system for parameter selection. The newly developed Computer Aided Machine Parameter Selection (CAMPS) package is then compared to some of the recent commercial packages on the market. Some computational experiments are reported and some examples are discussed.
Generalized Dynamic Programming for Stochastic Combinatorial Optimization
Authors: Carraway Robert L. , Morin Thomas L. , Moskowitz Herbert
Published: November 2008

In stochastic versions of combinatorial optimization problems, the objective is to maximize or minimize a function of random variables. For many problems of this type, conventionally applied dynamic programming (DP) may fail to generate an optimal solution due to the potential violation of the monotonicity assumption of DP. We develop a generalization of DP that guarantees optimality even in the absence of monotonicity. We illustrate the methodology on a version of the stochastic traveling salesman problem for which a previously proposed DP algorithm (E. Kao) is potentially suboptimal due to the violation of monotonicity (M. Sniedovich). Using Generalized DP, we are able to modify the algorithm to guarantee optimality.
Sensitivity Analysis for Simulations via Likelihood Ratios
Authors: Reiman Martin I. , Weiss Alan
Published: November 2008

We present a simple method of estimating the sensitivity of quantities obtained from simulation with respect to a class of parameters. Here sensitivity means the derivative of an expectation with respect to a parameter. The class of parameters includes, for example, Poisson rates, discrete probabilities, and the mean and variance of a Normal distribution. The method is extremely well suited to regenerative simulation, and can be implemented on extant simulations with little effort, increase in running time, or memory requirements. It is based on some change-of-measure formulas derived from likelihood ratios. In addition to the theorems that underly the technique, we present some numerical examples.
Technical Note—Comment on Yao and Buzacott's “Modeling a Class of Flexible Manufacturing Systems with Reversible Routing”
Authors: Van Dijk Nico M.
Published: November 2008

Recently, in an elegant paper, D. D. Yao and J. A. Buzacott argued that Jackson's celebrated product form applies to various FMS (Flexible Manufacturing System) topologies with reversible routing. This note aims to point out the possibility of nonreversible extensions (Point 1) and the validity of their results under general nonexponential services (Point 2), as could have been concluded from the literature.
Dynamic Network Traffic Assignment Considered as a Continuous Time Optimal Control Problem
Authors: Friesz Terry L. , Luque Javier , Tobin Roger L. , Wie Byung-Wook
Published: November 2008

Two continuous time formulations of the dynamic traffic assignment problem are considered, one that corresponds to system optimization and the other to a version of user optimization on a single mode network using optimal control theory. Pontryagin's necessary conditions are analyzed and given economic interpretations that correspond to intuitive notions regarding dynamic system optimized and dynamic user optimized traffic flow patterns. Notably, we offer the first dynamic generalization of Beckmann's equivalent optimization problem for static user optimized traffic assignment in the form of an optimal control problem. The analysis further establishes that a constraint qualification and convexity requirements for the Hamiltonian, which together ensure that the necessary conditions are also sufficient, are satisfied under commonly encountered regularity conditions.
An Interpolation Approximation for the Mean Workload in a GI/G/1 Queue
Authors: Whitt Ward
Published: November 2008

This paper develops a closed form approximation for the mean steady-state workload or virtual waiting time in a GI/G/1 queue, using the first two moments of the service-time distribution and the first three moments plus the density at the origin of the interarrival-time distribution, with default values provided in case information is unavailable. The approximation is based on light and heavy traffic limiting behavior. The essential ideas are exposed by using S.L. Brumelle's formula to relate the mean workload to the mean waiting time and K.T. Marshall's formula to relate the mean waiting time to the first two moments of the idle period. Both formulas extend to general single server models without independence conditions, so this approach provides a basis for extensions, but a convenient exact expression for the second order heavy traffic term is evidently not possible even for GI/G/1. For the GI/G/1 second order heavy traffic term, an approximation is proposed, based on the relatively nice expression established for the GI/M/1 case by S. Halfin. The interpolation between light and heavy traffic limits, which can be applied to other performance measures and models whenever the limits can be determined or approximated, is chosen to satisfy differentiability and monotonicity regularity conditions.
Axiomatic Characterizations of the Raiffa and the Kalai-Smorodinsky Solutions to the Bargaining Problem
Authors: Livne Zvi A.
Published: November 2008

The Raiffa Solution to the Bargaining Problem, proposed in 1951, has several appealing properties, especially when viewed as a model of the negotiation process in an integrative bargaining situation. Unlike the well known solutions of Nash and Kalai-Smorodinsky, the Raiffa Solution has not been characterized by a set of axioms. We present two axiomatic characterizations of the Raiffa Solution. In addition, we present a new axiomatic characterization of the Kalai-Smorodinsky Solution.
Coupled Samples in Simulation
Authors: Devroye Luc
Published: November 2008

Assume that we wish to generate two samples of n independent identically distributed random variables, (X1,…, Xn) and (Y1,…, Yn), where X1 and Y1 have densities f and g, respectively. If these samples are used in a simulation, and f is close to g, it is sometimes desirable to have close simulation results. This can be achieved by insisting that both samples agree in most of their components, that is, Xi=Yi for as many i as possible under the given distributional constraints. Samples with this property are said to be optimally coupled. In this paper, we propose and study various methods of coupling two samples, a sequence of samples and an infinite family of samples.
On Arrivals That See Time Averages
Authors: Melamed Benjamin , Whitt Ward
Published: November 2008

We investigate when Arrivals See Time Averages (ASTA) in a stochastic model; i.e., when the stationary distribution of an embedded sequence, obtained by observing a continuous-time stochastic process just prior to the points (arrivals) of an associated point process, coincides with the stationary distribution of the observed process. We also characterize the relation between the two distributions when ASTA does not hold. We introduce a Lack of Bias Assumption (LBA) which stipulates that, at any time, the conditional intensity of the point process, given the present state of the observed process, be independent of the state of the observed process. We show that LBA, without the Poisson assumption, is necessary and sufficient for ASTA in a stationary process framework. Consequently, LBA covers known examples of non-Poisson ASTA, such as certain flows in open Jackson queueing networks, as well as the familiar Poisson case (PASTA). We also establish results to cover the case in which the process is observed just after the points, e.g., when departures see time averages. Finally, we obtain a new proof of the Arrival Theorem for product-form queueing networks.
Computing Nested Reorder Intervals for Multi-Item Distribution Systems
Authors: Roundy Robin O.
Published: November 2008

We consider a multistage, multi-item distribution system in which each of a number of items is stocked at each of a number of locations. The cost of placing an order at a location depends on the set of items ordered there. Demand for the items is constant, and there is a linear holding cost for each item at each location. Only nested policies are considered. A known heuristic is guaranteed to find a policy that is within 2% of optimal. However, if there are M items and L locations the running time of the heuristic is O(M4L4). We improve the running time to O(MLD log(ML)) where D is at most the maximum of the depth of the location and family arborescences.
Multiple Objective Analysis of Input-Output Models for Emergency Management
Authors: Kananen Ilkka , Korhonen Pekka , Wallenius Jyrki , Wallenius Hannele
Published: November 2008

This paper shows how a visual, interactive, dynamic multiple objective linear programming decision support system can effectively be used for analyzing input-output models. We have applied our approach to studying the quantitative effects of economic or political crises to the Finnish economy. Examples of such crises are nuclear power plant accidents, trade embargoes, and international conflicts. An input-output model of the Finnish economy with 17 industries (sectors) is employed. Our system has been implemented on a microcomputer and is being used by the National Board of Economic Defense. Several typical case situations are discussed.
Military Decision, Game Theory and Intelligence: An Anecdote
Authors: Ravid Itzhak
Published: November 2008

Some 30 years ago, O. G. Haywood, Jr. published a pioneering paper relating game theory considerations to historical cases of World War II (“Military Decision and Game Theory”). The paper has become one of the most cited in military operations research literature. Facts revealed long after its publication have shed new light upon the historical case and bear upon the core of that paper. We present the story and consider its implications.
A Bayesian Escalation Model to Predict Nuclear Accidents and Risk
Authors: Chow Tat-Chi , Oliver Robert M. , Vignaux G. Anthony
Published: November 2008

This paper designs prediction models to estimate the chance of the most severe nuclear accidents (such as complete core melts) for the population of U.S. and worldwide nuclear reactors. We formally introduce the notion of random escalation of incident severity. We then develop a class of models that views accidents of high severity as members of a subpopulation of incidents of lower severity; a random escalation model (REM) uses Bayesian methods to update unobservable failure rates and other model parameters. The priors for failure rates are based on extensive engineering judgment about the probabilities of core melt. Predictive distributions for time to time to core melt are calculated from the model, based on operational experience and accident data accumulated to date; the results are compared with those of N. C. Rasmussen, H. W. Lewis, P. C. Groer and others. The paper includes three theorems that reveal the structure of separable densities for parameter updating, the invariance of REMs under severity level classification and the reproducibility of Poisson-Binomial REMs. In an appendix, we examine the special assumptions that are required to specify the current U.S. Nuclear Regulatory Commission risk model.
A Queue with Service Interruptions in an Alternating Random Environment
Authors: Sengupta Bhaskar
Published: November 2008

This paper considers a single server queue that operates in a random environment defined by an alternating renewal process with states 1 and 2. When the random environment is in state i (i = 1, 2), the arrivals occur at a mean rate of λi and the distribution of service-time for these arrivals is Bi(t). The server is working when the random environment is in state 1 and not working when the state is 2. This model is applicable to situations in manufacturing, computer and telecommunications problems when the server is subject to random breakdown. It is also useful in modeling some priority and cyclic server queues. We analyze the problem by first examining the steady-state distribution of work in the system. We show that the work in the system is closely related to the waiting time in a special GI/G/1 queue. For the special case when the off-period is exponentially distributed, exact closed-form expressions are obtained for the performance measures of interest. For other cases, we propose an approximation and show that it works well when compared with simulations.
Optimal Spares Provisioning When Component Price Is Changing
Authors: Assaf David , Shanthikumar J. George
Published: November 2008

A system must operate for t units of time. A certain component is essential for operation of the system and must be replaced by a new component whenever it fails. The price of this component changes over time. The problem of providing the proper number of spares for this component so as to minimize the total expected cost of maintaining the system operative for t units of time is studied. In particular, we show that when the component lives are exponentially distributed and the price is strictly increasing, it is optimal to provide n spares when the time remaining until termination is between tn and tn + 1, where 0 = t0 < t1 < t2 < …. This result is then extended to the case where the price change is arbitrary.
Another Way to Solve Complex Chemical Equilibria
Authors: Heyman Daniel P.
Published: November 2008

T. W. Wall, D. Greening and R. E. D. Woolsey produced a geometric programming based technique for solving the system of nonlinear equations that arise from the kinetic approach to finding the composition of a chemical system at equilibrium. I argue that one should consider using nonlinear programming to solve these equations. This approach is illustrated by solving the example given by Wall, Greening and Woolsey. A pencil and paper solution to that problem is also given.
Infinitesimal Perturbation Analysis Estimates for Moments of the System Time of an M/M/1 Queue
Authors: Zazanis Michael A.
Published: November 2008

We consider infinitesimal perturbation analysis estimates for the derivative of moments of the system time in an M/M/1 queue in steady state. The unbiasedness of these estimates is established for derivatives with respect to the mean service time and the arrival rate. A similar result is obtained for the system time of the ith customer in a GI/G/1 queue with fixed initial conditions.
A Forward Algorithm for the Capacitated Lot Size Model with Stockouts
Authors: Sandbothe Richard A. , Thompson Gerald L.
Published: November 2008

In this paper, we consider the lot size model for the production and storage of a single commodity with limitations on production capacity and the possibility of not meeting demand, i.e., stockouts, at a penalty. The stockout option means that horizons can exist and permits the use of horizons to develop a forward algorithm for solving the problem. The forward algorithm is shown in the worst case to be asymptotically linear in computational requirements, in contrast to the case for the classical lot size model which has exponential computing requirements. Two versions of the model are considered: first, in which the upper bound on production is the same for every time period; and second, in which the upper bound on production is permitted to vary each time period. In the first case, the worst case computational difficulty increases in a cubic fashion initially, and then becomes linear. In the second case, the initial increase is exponential before becoming linear. Besides the forward algorithm, a number of necessary conditions are derived that reduce the computational burden of solving the integer programming problem posed by the model.
Preemptive Scheduling of Equal Length Jobs on Two Machines to Minimize Mean Flow Time
Authors: Herrbach Lee A. , Leung Joseph Y.-T.
Published: November 2008

We give an O(n log n) time algorithm to preemptively schedule n equal-length jobs with release times on two identical, parallel machines so as to minimize the mean flow time. The complexity of the general problem of minimizing the mean weighted flow time is also reviewed, both for nonpreemptive and preemptive scheduling.
An Integral Equation Approach to the M/G/2 Queue
Authors: Knessl C. , Matkowsky B. J. , Schuss Z. , Tier C.
Published: November 2008

We study the stationary distribution of the number of customers in M/G/2 queueing systems. The two servers are allowed to have different service time distributions. We include the elapsed service times of the customers presently served as supplementary variables and obtain the forward equations satisfied by the joint stationary distribution of the number of customers and the elapsed service times. Using a sequence of transformations, we reduce the problem of determining the marginal probabilities of the number of customers present to the solution of a pair of coupled integral equations. When the servers are identical, only a single integral equation must be solved. The solution of the integral equation(s), and with it the stationary distribution of the number of customers, is constructed for several specific service time densities (e.g., Erlang, hyperexponential, and deterministic).
Twenty Years of Routing and Scheduling
Authors: Bodin Lawrence D.
Published: November 2008

I have 20 years of experience in solving practical routing and scheduling problems, as well as the associated problems of crew scheduling. In this paper, I offer some reflections on the history and practice in this field and project some future directions for it.
Optimal Contract Period for Priority Service
Authors: Chao Hung-Po , Wilson Robert
Published: November 2008

In industries with capacity constraints and nonstorable outputs, priority service is a form of market organization in which customers subscribe in advance to the order in which they will be served from scarce supplies. The optimal duration of priority service contracts depends on a tradeoff between transaction costs and efficiency gains that, in turn, depends on the serial correlations of customers' service valuations. Using a stationary Markov process to characterize the distribution of customers' valuations, we present several simple methods that illustrate the principal determinants of the optimal contract period.
An Approach to Planning for Physician Requirements in Developing Countries Using Dynamic Programming
Authors: Ikem Fidelis M. , Reisman Arnold M.
Published: November 2008

Physician manpower requirements of most developing countries can often be met by developing local training facilities, sending indigenes to train abroad, and/or by recruiting expatriate physicians. Foreign training and having expatriates often involve expenditures of scarce foreign exchange in competition with other development projects. This paper develops a manpower planning model which coordinates physician manpower requirements of a developing country with its capacity to train such physicians along with national objectives to contain costs. The paper presents computational results from a dynamic programming model using the best data available from Nigeria.
Fixed Cycle Scheduling: A Solvable Problem with Empty Precedence Structure
Authors: Garfinkel R. S. , Plotnicki W. J.
Published: November 2008

Fixed Cycle Scheduling (FCS) is a class of job scheduling problems in which all scheduling decisions (assignment of tasks to processors) are made on a cycle. That is, if task t is assigned to processor j at period h < n, then the same assignment is made at period h + in, for all integers i, where n is the cycle length. Possible applications of FCSs are given and a special case with uniform job arrivals and empty precedence structure is shown to be solvable analytically.
A Dynamic Lot Sizing Model with Learning in Setups
Authors: Chand Suresh , Sethi Suresh P.
Published: November 2008

This paper considers the dynamic lot sizing problem of H. M. Wagner and T. M. Whitin with the assumption that the total cost of n setups is a concave nondecreasing function of n. Such setup costs could arise from the worker learning in setups and/or technological improvements in setup methods. An efficient dynamic programming algorithm is developed to solve a finite horizon problem and results are presented to find decision/forecast horizons. Several new results presented in the paper have potential use in solving other related problems.
The Joint Replenishment Problem: New Heuristics and Worst Case Performance Bounds
Authors: Joneja Dev
Published: November 2008

The joint replenishment problem involves the lot sizing of several items with nonstationary demand in discrete time. The items have individual ordering costs and linear inventory holding costs. In addition, a joint ordering cost is incurred whenever one or more items is ordered together. This problem often arises when economies can be affected by coordinated ordering or setup of the items, both in distribution and in manufacturing environments. This problem is known to be NP-complete. In this paper, we analyze the worst case performance of an existing multipass heuristic for the problem. Then a new single pass forward heuristic is proposed, and it is proved that it has a uniformly bounded worst case performance. Furthermore, a lower bound on the cost of the optimal solution is obtained once the heuristic has been used. We then discuss a number of related heuristic algorithms and their worst case performance. The behavior of our heuristics for a randomly generated set of problems is also studied.
How Errors in Component Reliability Affect System Reliability
Authors: Fishman George S.
Published: November 2008

This paper studies how sampling variation in component reliability estimates affects the computation of system reliability that uses these estimates as input. If these components are in parallel they lead to an understatement of system reliability as the number of components k increases. In series, they lead to an overstatement as k increases. For a sample component reliability based on n observations, our results show that limk → ∞ (k2/n) = 0 is required for the sample system reliability to converge in probability to the true system reliability.
Does Operations Research Address Strategy?
Authors: Kirkwood Craig W.
Published: November 2008

Several recent comments published by leading operations researchers leave the impression that OR does not address strategic business or government issues and, furthermore, that the field would have to develop new analysis methods to address these issues. In fact, however, many OR practitioners are addressing strategic issues these days, and the failure of OR commentators to recognize this explicitly carries dangers for the future development of the field.
The Solution of Large 0–1 Integer Programming Problems Encountered in Automated Cartography
Authors: Zoraster Steven
Published: November 2008

The placement of text on a map to maximize map legibility, while avoiding graphic overplotting, is a problem in combinatorial optimization. This particular optimization problem can be formulated as a multiple choice integer programming problem, and the integer programming problem has a structure that can be exploited, using a Lagrangian heuristic, to obtain a cost effective solution, even when tens of thousands of variables and thousands of constraints are involved. This paper presents the mathematical formulation of the map label placement problem and describes a computer program implemented to solve it.
Controlled Rounding of Tabular Data
Authors: Kelly James P. , Golden Bruce L. , Assad Arjang A. , Baker Edward K.
Published: November 2008

Controlled rounding is a procedure that perturbs tabular data collected from respondents in such a way as to preserve the anonymity of the respondents while maintaining the integrity of the data. The three-dimensional controlled rounding problem is NP-complete. This paper describes a binary tree search algorithm for solving three-dimensional problems based on linear programming techniques. Computational results obtained from tests with over 31,000 randomly generated tables and 292 real-life tables have shown that this algorithm can effectively find controlled roundings when they exist or determine that no solution exists. The computational results also demonstrate that the running time of the search algorithm can be cut in half by using a heuristic for initializing the simplex basis for the linear programming problems.
Single Aircraft Mid-Air Refueling Using Spherical Distances
Authors: Yamani Abdulrahman , Hodgson Thom J. , Martin-Vega Louis A.
Published: November 2008

This paper addresses the problem of a single military transport aircraft that must carry cargo from an origin base to a destination base. Refueling is required and performed by a tanker aircraft that originates from and returns to a third base. The objective is to determine the initial fuel required by each aircraft and the location of the refueling point so as to minimize the total fuel consumed subject to restrictions on the range of the transport and the tanker. Based on U.S. Air Force data, analytical relationships are derived which allow the problem to be formulated similar to a constrained spherical Weber problem with two main differences: 1) the objective function is nonlinear, and 2) some of the constraints are a function of the decision variables. Spherical convexity of both the objective function and the feasible region is shown and used to develop a solution procedure. Computational experience is given.
Refinements to Heavy Traffic Limit Theorems in Queueing Theory
Authors: Knessl Charles
Published: November 2008

We consider single server M/G/1 and GI/G/1 queues in the limit of heavy traffic. We develop a procedure for obtaining the full asymptotic series of the stationary distribution of unfinished work in powers of one minus the traffic intensity. The leading term in this series is the (exponential) density obtained from the heavy traffic limit theorem. We show that the correction terms have different forms in different regions of the state space. These corrections are constructed using the method of matched asymptotic expansions. We assume that the method of matched asymptotic expansions is valid.
Look-Ahead Policies for Admission to a Single Server Loss System
Authors: Nawijn Wim M.
Published: November 2008

Consider a single server loss system in which the server, being idle, may reject or accept an arriving customer for service depending on the state at the arrival epoch. It is assumed that at every arrival epoch the server knows the service time of the arriving customer, the arrival time of the next customer and the service time. The server gets a fixed reward for every customer admitted to the system. The form of an optimal stationary policy is investigated for the discounted and average reward cases.
The Evaluation of Normalizing Constants in Closed Queueing Networks
Authors: Gordon J. J.
Published: November 2008

Recently P. G. Harrison derived a closed form solution for the normalizing constant of a closed network of single server queues. In the present paper, we describe an alternative method of obtaining Harrison's result. The new method can usefully be applied to other closed networks of queues, particularly those in which irregular constraints bound the state space. Examples of the method are provided, and several new results are obtained.
Optimal Incentive-Compatible Priority Pricing for the M/M/1 Queue
Authors: Mendelson Haim , Whang Seungjin
Published: November 2008

Consider a system that is modeled as an M/M/1 queueing system with multiple user classes. Each class is characterized by its delay cost per unit of time, its expected service time and its demand function. This paper derives a pricing mechanism which is optimal and incentive-compatible in the sense that the arrival rates and execution priorities jointly maximize the expected net value of the system while being determined, on a decentralized basis, by individual users. A closed-form expression for the resulting price structure is presented and studied.
Optimal Dispatching in a Periodic Review Cellular Manufacturing System
Authors: Liu John J.
Published: November 2008

We examine a periodically reviewed cellular manufacturing system where parts are dispatched from a central control station to n manufacturing cells. After being processed at a cell, parts are routed back to the control station for inspection. An inspection failure will result in a feedback job order. Optimal dispatching policies are pursued to minimize the expected in-process inventory costs over a finite horizon. A dynamic programming formulation is developed for optimal dispatching. We show that the dynamic recursive functions (i.e., cost-to-go functions) are convex and monotonic under the condition of low defect rates and relative low cost material handling. From the convex and monotonic properties, it is shown that optimal dispatching calls for a combination of zero-inventory and nonzero-inventory policies. The optimal input control is proved to be in the form of a pulling system.
Near-Optimal Solution of Generalized Resource Allocation Problems with Large Capacities
Authors: Hackman Steven T. , Platzman Loren K.
Published: November 2008

We consider problems of allocating resources to activities where the allocation to each activity is restricted to a general set of admissible values, the objective function is additively-separable but not necessarily concave nor differentiable, and each activity uses at most one resource. We develop a simple algorithm, based on a nonsmooth convex relaxation, that generates a near-optimal solution whenever each allocation is a small fraction of resource capacity.
A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems
Authors: Farley A. A.
Published: November 2008

In LP problems with an extremely large number of possible structural variables, solution to optimality is not always required. A bound can be used to terminate such LPs. Such a bound is presented for a class of problem that includes most cutting stock formulations.
A Priori Optimization
Authors: Bertsimas Dimitris J. , Jaillet Patrick , Odoni Amedeo R.
Published: November 2008

Consider a complete graph G = (V, E) in which each node is present with probability p. We are interested in solving combinatorial optimization problems on subsets of nodes which are present with a certain probability. We introduce the idea of a priori optimization as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problem is solved optimally for every instance. We consider four problems: the traveling salesman problem (TSP), the minimum spanning tree, vehicle routing, and traveling salesman facility location. We discuss the applicability of a priori optimization strategies in several areas and show that if the nodes are randomly distributed in the plane the a priori and reoptimization strategies are very close in terms of performance. We characterize the complexity of a priori optimization and address the question of approximating the optimal a priori solutions with polynomial time heuristics with provable worst-case guarantees. Finally, we use the TSP as an example to find practical solutions based on ideas of local optimality.
Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Closed Network
Authors: Harrison J. Michael , Wein Lawrence M.
Published: November 2008

We consider a multiclass closed queueing network with two single-server stations. Each class requires service at a particular station, and customers change class after service according to specified probabilities. There is a general service time distribution for each class. The problem is to schedule the two servers to maximize the long-run average throughput of the network. By assuming a large customer population and nearly balanced loading of the two stations, the scheduling problem can be approximated by a dynamic control problem involving Brownian motion. A reformulation of this control problem is solved exactly and the solution is interpreted in terms of the queueing network to obtain a scheduling rule. (We conjecture, quite naturally, that the resulting scheduling rule is asymptotically optimal under heavy traffic conditions, but no attempt is made to prove that.) The scheduling rule is a static priority policy that computes an index for each class and awards higher priority at station 1 (respectively, station 2) to classes with the smaller (respectively, larger) values of this index. An analytical comparison of this rule to any other static policy is also obtained. An example is given that illustrates the procedure and demonstrates its effectiveness.
Optimal Control of a Production Process Subject to Random Deterioration
Authors: Schneider Helmut , Tang Kwei , O'Cinneide Colm
Published: November 2008

A production process exhibits a decreasing pattern in the process mean in the course of production. We address the decision problem of selecting the starting level of the process mean and the level at which the process mean should be adjusted back to the starting level. The costs to be minimized are the long-run average cost of production, adjustment and loss for defective items. In addition to the optimal solution, simple approximate solutions are developed and shown to be more cost effective than a simple linear policy often applied to this problem.
Permutation Schedules for Flow Shops with Precedence Constraints
Authors: Ewacha Kevin , Rival Ivan , Steiner George
Published: November 2008

We show that permutation schedules are always optimal for regular, symmetric measures of performance for the m-machine flow shop with precedence constraints provided that processing times are identical for noncomparable jobs.
Scheduling Interviews for a Job Fair
Authors: Bartholdi John J. , McCroan Kevin L.
Published: November 2008

We describe the design and use of a program to schedule interviews for law firms and students at a job fair. It has been used to manage the Southeastern Public Interest Job Fair for the last six years. The program uses a new scheduling algorithm that produces particularly convenient schedules.