bluuebunny/crossref_metadata_2025 huggingface dataset:
On a GI/M/c Queue with Bounded Waiting Times
Authors: Swensen Anders Rygh
Published: November 2008

We derive the asymptotic distribution of the remaining load, virtual waiting time and actual waiting time for a multiserver queueing system with exponentially distributed service times and bounded waiting times. Interarrival distributions are Coxian, with m stages. This model has application to telephone exchange operations and to perishable inventory. The explicit derivation of the distributions involves determining the eigenvalues of m-dimensional matrices and solving linear equations in m unknowns. We give a few numerical illustrations.
OR Forum—ORSA as Viewed by its Members
Authors: Balut Stephen J. , Armacost Robert L.
Published: November 2008

The Operations Research Society of America is healthy and strong by most measures and continues to make important contributions to the profession. However, the Society is not without serious challenges. Full and Associate membership levels have been shrinking since 1970, and many members have raised concerns about the readability and content of our journals. At the ORSA Council's request, the Membership Committee conducted a large-scale survey to provide information needed to deal with these and other challenges. This survey revealed who members are, why we joined and continue to renew, and what we think of Society products. Findings, briefly summarized here, are now being used by the Council and committees in strategic planning that will shape the future of the Society.
Computing Optimal Policies for Controlled Tandem Queueing Systems
Authors: Ohno Katsuhisa , Ichiki Kuniyoshi
Published: November 2008

This paper discusses the use of modified policy iteration algorithms for finding the optimal control for the service rate for a tandem queueing system that has a general cost structure. It compares several variants of the algorithms and shows that the optimal control problem can be solved within a reasonable computation time.
Technical Note—Recognizing Unbounded Integer Programs
Authors: Byrd R. H. , Goldman A. J. , Heller Miriam
Published: November 2008

If an integer program (IP) has an unbounded continuous relaxation, is the IP also unbounded? We find the answer to be “no” in general but “yes” when the IP is feasible and has rational data. We also discuss related geometrical and algorithmic considerations.
Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
Authors: Warburton Arthur
Published: November 2008

We study methods for approximating the set of Pareto optimal paths in multiple-objective, shortest-path problems. Known generalizations of standard shortest-path methods will compute this set, but can suffer from rapidly increasing computational and storage demands as problem size increases. In an effort to avoid such difficulties, we develop approximation methods that can estimate the Pareto optima to any required degree of accuracy. The approximation methods are “fully polynomial”; that is, they operate in time and space bounded by a polynomial in problem size and accuracy of approximation—the greater the accuracy, the more time required to reach a solution. We show how approximation methods may be applied to yield fully polynomial approximation schemes for a variety of NP-complete, single-objective problems.
OR Practice—A Utility Fuel Inventory Model
Authors: Morris Peter A. , Sandling M. James , Fancher Richard B. , Kohn Michael A. , Chao Hung-Po , Chapel Stephen W.
Published: November 2008

The Utility Fuel Inventory Model (UFIM) is an inventory modeling system designed to help electric utilities set long-term fuel inventory strategy. It is currently in use by more than 50 utilities. This paper describes the model, its use and one of its first applications. The paper has several objectives: (i) to illustrate the value of integrating different model forms—both analytical and simulation—to solve a complex multiple-issue decision problem; (ii) to illustrate a process for using the model to help the user understand the inventory problem; (iii) to illustrate the use of auxiliary simplified models to build insight and to complement judgment; and (iv) to document an application demonstrating significant cost savings for the electric utility industry.
Technical Note—An Improved Lower Bound for Minimizing Weighted Completion Times with Deadlines
Authors: Bagchi Uttarayan , Ahmadi Reza H.
Published: November 2008

We consider the NP-hard, one-machine scheduling problem whose objective is to minimize the weighted sum of completion times, subject to meeting deadlines. We propose a new lower bound that dominates the bounds found in the literature.
98%-Effective Lot-Sizing for One-Warehouse, Multi-Retailer Inventory Systems with Backlogging
Authors: Mitchell Joseph S. B.
Published: November 2008

Robin Roundy has analyzed a stationary, one-warehouse, N-retailer inventory system that permits no shortages or backlogging, that has a constant demand rate per unit time at each retailer, and that incurs setup and unit storage costs at each facility. By reducing the problem with backlogging to an equivalent problem with no backlogging, we extend Roundy's results to permit backlogging. This approach permits us to use Roundy's results to find a 98%-effective policy for the backlogging problem in O(N log N) time.
Interstage Transportation Planning in the Deterministic Flow-Shop Environment
Authors: Langston Michael A.
Published: November 2008

In the well-known flow-shop model, we are given a k-stage processing facility and a collection of jobs, each comprising k tasks to be processed in order, one per stage. At every stage, one or more machines are available for processing tasks. We assume that the jobs are independent and that the processing of a task, once begun, cannot be interrupted. In this paper we focus our attention on a critical but largely ignored aspect of flow-shop utilization, namely, that of planning the efficient transportation of work between stages. We therefore assume the existence of a transport, used to ferry jobs from one stage to the next. We devise and formally analyze effective transportation strategies for various situations in this environment that are dependent on the amount of time needed for transportation relative to the amount required for task processing.
The Economic Lot-Scheduling Problem: Achieving Feasibility Using Time-Varying Lot Sizes
Authors: Dobson Gregory
Published: November 2008

This paper considers the Economic Lot Scheduling Problem: that is, the problem of scheduling several products on a single facility so as to minimize holding and setup costs. We develop a formulation that provides feasible schedules by allowing the lot sizes and thus the cycle times for each product to vary over time and by explicitly taking into account setup times. Our main results characterize when feasible schedules exist, quantify the insensitivity of the schedules' costs to minor adjustments, and thus show how close the schedules will be to ones with optimal equal cycle times. We also present a heuristic for finding good feasible schedules.
The Fixed Job Schedule Problem with Spread-Time Constraints
Authors: Fischetti Matteo , Martello Silvano , Toth Paolo
Published: November 2008

We consider a generalization of the fixed job schedule problem in which each processor is available only for a prefixed time interval from the release time of the earliest task assigned to it. The problem can arise in bus driver scheduling. We show that the problem is NP-hard, and introduce polynomial procedures to determine lower bounds, dominance criteria and reductions. We also develop a branch-and-bound algorithm for obtaining the optimal solution of the problem and analyze the algorithm’s average performance in a series of computational experiments. Finally, we investigate the preemptive case and other polynomial special cases.
The “Largest Variance First” Policy in Some Stochastic Scheduling Problems
Authors: Pinedo Michael , Weiss Gideon
Published: November 2008

We consider a situation in which n jobs, requiring random amounts of processing, all with the same mean, are to be scheduled on m parallel machines with respect to one of two objectives: expected flowtime and expected makespan. We discuss optimality of the rule that says to schedule the jobs with the largest variance first (LVF). We show that for some very simple job length distributions, LVF minimizes both the expected flowtime and the expected makespan.
Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems
Authors: Bertsekas Dimitri P. , Tseng Paul
Published: November 2008

We propose a new class of algorithms for linear cost network flow problems with and without gains. These algorithms are based on iterative improvement of a dual cost and operate in a manner that is reminiscent of coordinate ascent and Gauss-Seidel relaxation methods. We compare our coded implementations of these methods with mature state-of-the-art primal simplex and primal-dual codes, and find them to be several times faster on standard benchmark problems, and faster by an order of magnitude on large, randomly generated problems. Our experiments indicate that the speedup factor increases with problem dimension.
Sequencing of Insertions in Printed Circuit Board Assembly
Authors: Ball Michael O. , Magazine Michael J.
Published: November 2008

Manufacturability of printed circuit boards is a fertile area for operations researchers to aid in productivity improvements for the electronics industry. A class of such problems is described, and a particular problem that arises from an application to a middle sized electronics firm is modeled and solved. The specific problem to determine the best sequence of insertion operations is formulated as a type of directed postman problem. An algorithm is developed for the problem that yields an optimal solution under certain conditions and approximate solutions, with a constant performance bound, when these conditions are relaxed.
A Quality Control Model with Learning Effects
Authors: Fine Charles H.
Published: November 2008

We present a model that extends a variant of the classic quality control/machine maintenance model by adding the concept of quality-based learning. The extension captures the idea that operators of a production process may be able to discover and eliminate defects in the system if, during an inspection, they find the process to be “out of control.” Thus, the distinguishing feature of the model is that one inspects the process not only for the purpose of repairing the machine, but also in the hope that the machine will be caught in the act of producing defective output, so that a source of problems is uncovered and eliminated. The paper provides a characterization of optimal inspection policies and suggests the managerial implications: Ignoring the learning benefits of inspection and quality control activities may lead to under-investment in quality improvement activities, which, in turn, may hinder both cost and quality competitiveness.
Simple Bounds for Finite Single-Server Exponential Tandem Queues
Authors: Van Dijk Nico M. , Lamond Bernard F.
Published: November 2008

Tandem queue configurations naturally arise in multistage stochastic systems such as assembly lines in manufacturing or multiphase transmissions in telecommunications. As finite capacity or storage constraints (buffers) are usually involved, the celebrated closed product form expression is generally not applicable. In this paper, a new bounding methodology for nonproduct form systems is applied to finite single-server exponential tandem queues. The methodology is based on modifying the original system into product form systems that provide bounds for some performance measure of interest. The product form modifications given for this finite tandem queue propose a computationally attractive and intuitively obvious lower and upper bound for the call congestion and throughput. Numerical results indicate that the bounds are reasonable indicators of the order of magnitude. This can be useful for quick engineering purposes as will be illustrated by an optimal design example. A formal proof of the bounds is given. This proof extends standard techniques for comparing stochastic systems and is of interest in itself.
Stochastic Optimization Models for Lake Eutrophication Management
Authors: Somlyódy László , Wets Roger J.-B.
Published: November 2008

We develop a general framework for the study and the control of the eutrophication process of (shallow) lakes. The randomness of the environment (variability in hydrological and meteorological conditions) is an intrinsic characteristic of such systems that cannot be ignored in the analysis of the process or by management in the design of control measures.
OR Forum—Operations Research: A Global Language for Business Strategy
Authors: Wagner Harvey M.
Published: November 2008

Based on the author's observations and experience, this paper argues that the concepts and vocabulary of operations research have become a pervasive part of the thinking of modern American industrial managers, and that the related models are playing important roles in informing the decisions that they make. Since any model is only a partial representation of reality, this fact—and the criticisms that it has evoked—present the operations research and management communities with continuing challenges for improving their work.
What are the Risks of Risky Sex? Modeling the AIDS Epidemic
Authors: Kaplan Edward H.
Published: November 2008

This paper employs mathematical models to examine the epidemic of AIDS among gay men. The approach allows consideration of arbitrary probability distributions for risky sex rates, the duration of sex lives, and the incubation time of AIDS following HIV infection, thus quite general models can be constructed. The analysis suggests what must happen for the epidemic to subside (barring a cure) by generalizing known formulas for the reproductive rate of HIV infection. This result shows that the simplifying assumption of exponential sex lives found in most other AIDS models is pessimistic relative to more realistic sex life distributions. It is also shown that under the assumption of random partner selection, the likelihood that a selected partner is infected exceeds the fraction of the population that is infected. Several scenarios illustrating the timeframe necessary for changes to occur in the AIDS case rate and the prevalence of HIV infection are presented. These scenarios are driven by assumptions regarding reduction in risky sex rates, or by the development of an imperfect immunizing vaccine, and are parameterized via data from recent AIDS cohort studies. Even under optimistic scenarios (such as abstinence from risky sex or the administration of a perfect vaccine), the model predicts that it would take over 15 years to eradicate AIDS in gay communities such as San Francisco where HIV prevalence is currently near 50%. Less optimistic scenarios force the conclusion that such communities will be living with AIDS for decades to come.
A Partially Observable Model of Decision Making by Fishermen
Authors: Lane Daniel E.
Published: November 2008

This paper presents an application of a partially observable Markov decision process for the intraseasonal decisions of fishing vessel operators. Throughout each fishing season, independent vessel operators must decide in which zone or fishing ground of the fishery to fish during each period to catch the most fish with the highest return to fishing effort. Fishermen's decisions are assumed to be made to maximize net operating income. The decision model incorporates the potential fish catch, the cost of the fishing effort, and the unit price of fish. Catch potential is modeled by considering the abundance of the fish stock and the catchability of the fishing technique. Abundance dynamics not observed directly are modeled as a Markov chain with a parsimonious state-space representation, which renders the problem practicable. Dynamic decision policies are computed by the method of optimal control of the process over a finite horizon. The resultant policies are used to simulate distributions of fishermen's net operating income, fishing effort dynamics, and catch statistics. The model may be used as a decision aid in the regulation of the common property fisheries resource.
Technical Note—A Generalized Bounding Method for Multifacility Location Models
Authors: Love Robert F. , Dowling Paul D.
Published: November 2008

This paper develops a new lower bound for multifacility location problems with lp distances. We prove that the method produces superior results to other known procedures. The new bound is also computationally efficient.
Uncapacitated Lot-Sizing Problems with Start-Up Costs
Authors: Wolsey Laurence A.
Published: November 2008

We consider the uncapacitated economic lot-sizing problem with start-up costs as a mixed integer program. A family of strong valid inequalities is derived for the class as well as a polynomial separation algorithm. It is then shown how equivalent, or possibly stronger, formulations are obtained by the introduction of auxiliary variables. Finally, some limited computational results for a single item model and a multi-item model with changeover costs are reported.
Monotonicity of the Throughput of a Closed Queueing Network in the Number of Jobs
Authors: Adan Ivo , Van der Wal Jan
Published: November 2008

Using a sample path argument, it is shown that the throughput of a closed queueing network with general service times is nondecreasing in the number of jobs.
Technical Note—Single Machine Scheduling with Controllable Processing Times and Number of Jobs Tardy
Authors: Daniels Richard L. , Sarin Rakesh K.
Published: November 2008

Most scheduling research has treated individual job processing times as fixed parameters. In many practical situations, however, a manager may exert processing time control through the allocation of a limited resource. We consider the problem of joint sequencing and resource allocation when the scheduling criterion of interest is the number of tardy jobs. Theoretical results are derived that aid in developing the tradeoff curve between the number of tardy jobs and the total amount of allocated resource.
Solving a Freight Transport Problem Using Facility Location Techniques
Authors: Klincewicz John G.
Published: November 2008

Use of consolidation terminals to transport products from various sources to various destinations can take advantage of economies of scale in transportation costs. Instead of making direct shipments, each source can ship in bulk to one or more consolidation terminals. There, shipments can be broken down, and material bound for the same destination can be combined. We consider such a freight transport problem (FTP). For each source–destination pair, it must be decided whether to ship the product directly or via a consolidation terminal. Shipping costs are piecewise linear concave functions of the volume shipped. Shipping via a terminal can also incur a linear inventory holding cost. We seek a minimum cost pattern of direct and indirect (i.e., via a terminal) shipments. This is a type of concave cost multiproduct network flow problem. We can solve this problem optimally if either the source-to-terminal or the terminal-to-destination shipping costs are linear. In this case, FTP decomposes into a set of concave cost facility location problems (CFLP). In more general cases, heuristic methods that solve sequences of linear problems can be used. Some computational results are presented.
A Decision Support System for Prioritizing Oil and Gas Exploration Activities
Authors: Dyer James S. , Lund Richard N. , Larsen John B. , Kumar V. , Leone Robert P.
Published: November 2008

This paper describes a decision support system developed to prioritize oil and gas exploration activities. During each budgeting cycle, the exploration division of a major oil company must review a number of potential oil and gas plays, and assign personnel to the most promising ones. These personnel are teams of geologists and geophysicists who are responsible for the exploration activities on the site. The number of interesting plays always exceeded the available exploration budget and manpower, so management was concerned about the development of a consistent ranking system of oil and gas plays that could be used to guide the budgeting and manpower decision. The development of the ranking system was based on familiar concepts from decision theory, specifically, multiattribute models and the value of information. Linear approximations to more complex mathematical functions were developed to simplify the model. However, this system was designed to be used on a routine basis by personnel unfamiliar with these technical issues, so they were masked from the user. The successful implementation of the proposed decision support system is described.
Optimizing Simulation for Policy Analysis in a Residential Energy End-Use Model
Authors: Hamblin Daniel M. , Johnson Jeannie C. , Killen Judith
Published: November 2008

This paper describes an end-use energy forecasting model for the residential sector. The technology-choice component dynamically optimizes capital and energy inputs to achieve economic efficiency within policy constraints. A policy example contrasts the marginal social costs—from both a private and a social perspective—of a building conservation standard with marginal social costs for investments in electric-power generation alternatives. The standard reduces electric space heat consumption in new houses to approximately one-third of the level predicted under current building codes. The policy analysis assumes that the builder and homeowner bear the full cost and risks of the conservation measure. The standard is shown not to be cost effective relative to power generation alternatives available for the Bonneville Power Administration, a U.S. government power distributor in the Pacific Northwest. However, because the policy is a cost effective social investment, the paper recommends an alternative financing scheme.
Multilocation Facility Modernization: Models and Heuristics
Authors: Mason L. G. , Girard A. , Gu X. D.
Published: November 2008

The problem of multilocation facility modernization is described. An integer multicommodity flow formulation is presented. Because of the problem size, exact solutions are not practical, and approximate solution methods are examined. Upper bounds are obtained by LP and Lagrangian relaxation. Near-optimal feasible solutions are obtained by heuristic procedures. The relaxation methods and the heuristics are compared in terms of the computation cost and the quality of the modernization policies produced, where quality is measured by the net present value of cash flows for a number of test problems. Also included is an evaluation of an aggregate modeling approach to multilocation planning, where average costs are employed in a single-location model to determine a homogeneous multilocation modernization policy. This assessment is important, as aggregate models have been employed widely in practice.
A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs
Authors: Magnanti T. L. , Vachani R.
Published: November 2008

Changeover costs (and times) are central to numerous manufacturing operations. These costs arise whenever work centers capable of processing only one product at a time switch from the manufacture of one product to another. Although many researchers have contributed to the solution of scheduling problems that include changeover costs, due to the problem's combinatorial explosiveness, optimization-based methods have met with limited success. In this paper, we develop and apply polyhedral methods from integer programming for a dynamic version of the problem. Computational tests with problems containing one to five products (and up to 225 integer variables) show that polyhedral methods based upon a set of facet inequalities developed in this paper can effectively reduce the gap between the value of an integer programming formulation of the problem and its linear programming relaxation (by a factor of 94 to 100%). These results suggest the use of a combined cutting plane/branch-and-bound procedure as a solution approach. In a test with a five product problem, this procedure, when compared with a standard linear programming-based branch-and-bound approach, reduced computation time by a factor of seven.
Convexity Properties of the Erlang Loss Formula
Authors: Harel Arie
Published: November 2008

We prove that the throughput of the M/G/x/x system is jointly concave in the arrival and service rates. We also show that the fraction of customers lost in the M/G/x/x system is convex in the arrival rate, if the traffic intensity is below some Ρ* and concave if the traffic intensity is greater than Ρ*. For 18 or less servers, Ρ* is less than one. For 19 or more servers, Ρ* is between 1 and 1.5. Also, the fraction lost is convex in the service rate, but not jointly convex in the two rates. These results are useful in the optimal design of queueing systems.
On the Limitations of Multivariate Phase-Type Families
Authors: O'Cinneide Colm A.
Published: November 2008

Consider a finite set of independent phase-type random variables. Suppose that we construct a random vector, each component of which is a total over a subset of this set. In 1984, D. Assaf et al. conjectured that such a vector need not have a multivariate phase-type distribution, and they provided a sufficient condition for the distribution to be of that type. We confirm their conjecture, and show that their sufficient condition is also essentially necessary. An open question of V. G. Kulkarni is whether or not his extension of the multivariate phase-type family is closed under familiar operations arising in reliability. This question is answered here in the negative.
Graphical Methods for Evaluating and Comparing Confidence-Interval Procedures
Authors: Kang Keebom , Schmeiser Bruce
Published: November 2008

We discuss various coverage-surface plots and scatter plots for evaluating and comparing confidence-interval procedures.
Estimating the Impact of Efficiency Standards on the Uncertainty of the Northwest Electric System
Authors: Ford Andrew
Published: November 2008

The uncertainty of the Northwest electric system was the subject of a recent study for the Bonneville Power Administration. System uncertainty was described along two dimensions over a twenty year planning period. One dimension was uncertainty in the demand for electricity; the second dimension was uncertainty in the price of electricity. The study focused on the impact of efficiency standards that would reduce the electricity used in new buildings and appliances. Many planners expect that the standards would reduce the long-term uncertainty in electricity demand. Some planners have come to realize that the standards could also reduce the long-term uncertainty in the price of electricity. This paper explains the case study approach to estimating the magnitude of these reductions in uncertainty. I describe the analytical approach and the key findings of the study, and conclude with a discussion of the study's impact on decision making in the region.
Monopolistic Pricing and the Learning Curve: An Algorithmic Approach
Authors: Dada Maqbool , Srikanth K. N.
Published: November 2008

This paper analyzes a multiperiod production planning model which incorporates pricing decisions and learning effects. We provide a partial characterization of the optimal policy. This result, combined with a simple algorithm, is used to find the optimal solution in special cases and near-optimal solutions for the general case.
A Capacity Improvement Lower Bound for Fixed Charge Network Design Problems
Authors: Lamar Bruce W. , Sheffi Yosef , Powell Warren B.
Published: November 2008

Network design problems concern flows over networks in which a fixed charge must be incurred before an arc becomes available for use. The uncapacitated, multicommodity network design problem is modeled with aggregate and disaggregate forcing constraints. (Forcing constraints ensure logical relationships between the fixed charge-related and the flow-related decision variables.) A new lower bound for this problem—referred to as the capacity improvement (CI) bound—is presented; and an efficient implementation scheme using shortest path and linearized knapsack programs is described. A key feature of the CI lower bound is that it is based on the LP relaxation of the aggregate version of the problem. A numerical example illustrates that the CI lower bound can converge to the optimal objective function value of the IP formulation.
A High-Low Search Algorithm for a Newsboy Problem with Delayed Information Feedback
Authors: Reyniers Diane
Published: November 2008

This paper outlines a new approach to the problem of demand uncertainty. It deals with setting optimal supply levels when demand is unknown. The novel feature of this approach is that information is obtained by observing sales. This information is used to determine future supply levels. Thus, supply levels are chosen with a view to current profit and future information. The technical apparatus is based on an extension of the theory of high-low search. We derive an algorithm to determine a sequence of supply quantities which minimizes total costs of over- and undersupply in the most adverse demand conditions. We calculate the value of perfect information, indicating how much a rational risk averse decision maker would be willing to pay to know demand exactly.
A Continuous Approach to Oligopolistic Market Equilibrium
Authors: Flåm Sjur D. , Ben-Israel Adi
Published: November 2008

We provide an algorithm for computing Cournot-Nash equilibria in a market that involves finitely many producers. The algorithm amounts to following a certain dynamical system all the way to its steady state, which happens to be a noncooperative equilibrium. The dynamics arise quite naturally as follows. Let each producer continuously adjust the planned production, if desired, as a response to the current aggregate supply. In doing so, the producer is completely guided by myopic profit considerations. We show, under broad hypothesis, that this adjustment process is globally, asymptotically convergent to a Nash equilibrium.
Rationalizing Tool Selection in a Flexible Manufacturing System for Sheet-Metal Products
Authors: Daskin Mark , Jones Philip C. , Lowe Timothy J.
Published: November 2008

Substantial simplification of existing processes and designs may be required before the potential benefits of modern manufacturing technology can be realized. This paper analyzes implementation problems associated with a flexible system that produces flat sheet-metal parts with interior holes. The paper makes three main contributions. First, we formulate the problem of selecting tooling and design standards as an optimization model and demonstrate that the model yields insight by applying it to one manufacturer's problem, thereby reducing substantially the required tooling. Second, we show that the model has a totally balanced constraint matrix, and hence, there are polynomial time algorithms for various versions of the problem. Third, we provide new algorithms with substantially improved performance bounds for two important versions of the problem.
Interpolation Approximations of Sojourn Time Distributions
Authors: Fleming Philip J. , Simon Burton
Published: November 2008

We present a method for approximating sojourn time distributions in open queueing systems based on light and heavy traffic limits. The method is consistent with and generalizes the interpolation approximations for moments previously presented by M. I. Reiman and B. Simon. The method is applicable to the class of systems for which both light and heavy traffic limits can be computed, which currently includes Markovian networks of priority queues with a unique bottleneck node. We illustrate the method of generating closed-form analytic approximations for the sojourn time distribution of the M/M/1 queue with Bernoulli feedback, the M/M/1 processor sharing queue, a priority queue with feedback and the M/Ek/1 queue. Empirical evidence suggests that the method works well on a large and identifiable class of priority queueing models.
Optimal Data Verification Tests
Authors: Avenhaus R. , Battenberg H. P. , Falkowski B. J.
Published: November 2008

The problem of data verification may be described as two sides that have concluded a contract stipulating that one side (the inspectee) is to report a set of data to the other (the inspector). The inspector has to decide on the basis of his own measurements whether to accept the data reported by the inspectee as correct or to assume they have been falsified. This situation is modeled as a statistical game, and practical solutions are supplied. We consider the verification of n data with a sample of size k, and prove that the traditional D-test is optimal for both maximum and minimum sample sizes (k = n and k = 1, respectively). These outcomes are, of course, to be expected; however, optimal falsification strategies are also obtained in these cases. In the special case in which two out of three data sets are verified, strong numerical evidence indicates that the D-test is no longer optimal if the total falsification is high. By applying the results obtained for k = 1 to an arbitrary sample size k, however, we show that the D-test is optimal in the case of low total falsification.
Finding Optimal (s, S) Policies Is About As Simple As Evaluating a Single Policy
Authors: Zheng Yu-Sheng , Federgruen A.
Published: November 2008

In this paper, a new algorithm for computing optimal (s, S) policies is derived based upon a number of new properties of the infinite horizon cost function c(s, S) as well as a new upper bound for optimal order-up-to levels S* and a new lower bound for optimal reorder levels s*. The algorithm is simple and easy to understand. Its computational complexity is only 2.4 times that required to evaluate a (specific) single (s, S) policy. The algorithm applies to both periodic review and continuous review inventory systems.
Structural Conditions for Perturbation Analysis Derivative Estimation: Finite-Time Performance Indices
Authors: Glasserman Paul
Published: November 2008

In recent years, there has been a surge of research into methods for estimating derivatives of performance measures from sample paths of stochastic systems. In the case of queueing systems, typical performance measures are mean queue lengths, throughputs, etc., and the derivatives estimated are with respect to system parameters, such as parameters of service and interarrival time distributions. Derivative estimates potentially offer a general means of optimizing performance, and are useful in sensitivity analysis. This paper concerns one approach to derivative estimation, known as infinitesimal perturbation analysis. We first develop a general framework for these types of estimates, then give simple sufficient conditions for them to be unbiased. The key to our results is identifying conditions under which certain finite-horizon performance measures are almost surely continuous functions of the parameter of differentiation throughout an interval. The sufficient conditions we introduce are formulated in the setting of generalized semi-Markov processes, but translate into readily verifiable conditions for queueing systems. These results substantially extend the domain of problems in which infinitesimal perturbation analysis is provably applicable.
A Comment on “Buffer Space Allocation in Automated Assembly Lines”
Authors: McClain John O. , Moodie Douglas R.
Published: November 2008

Counterintuitive optimal buffer capacity allocation patterns appeared in a 1988 paper by J. M. Smith and S. Daskalaki. This comment explains those patterns with examples and a simple diagram. Intuition gained from this explanation should be of use for researchers and practitioners alike.
A Queueing Network Model for Analyzing a Class of Branch-and-Bound Algorithms on a Master–Slave Architecture
Authors: Boxma O. J. , Kindervater G. A. P.
Published: November 2008

Partitioning methods lend themselves very well to implementation on parallel computers. In recent years, branch-and-bound algorithms have been tested on various types of architectures. In this paper, we develop a queueing network model for the analysis of a class of branch-and-bound algorithms on a master–slave architecture. The analysis is based on a fluid flow approximation. Numerical examples illustrate the concepts developed. Finally, related branch-and-bound algorithms are studied using a machine repair queueing model.
Driving Frequency Selection for Frequency Domain Simulation Experiments
Authors: Jacobson Sheldon H. , Buss Arnold H. , Schruben Lee W.
Published: November 2008

Frequency domain methodology has been applied to discrete-event simulations to identify terms in a polynomial model of the simulation output. In this paper, the problem of optimally selecting input frequencies is studied. A fast algorithm is presented that closely approximates the optimal solution. The results obtained from the algorithm are compared to known optimal solutions. Tables of input frequencies for various experiments are presented in an appendix.
Shake-and-Bake Algorithms for Generating Uniform Points on the Boundary of Bounded Polyhedra
Authors: Boender C. G. E. , Caron R. J. , McDonald J. F. , Kan A. H. G. Rinnooy , Romeijn H. E. , Smith R. L. , Telgen J. , Vorst A. C. F.
Published: November 2008

We present a class of shake-and-bake algorithms for generating (asymptotically) uniform points on the boundary of full-dimensional bounded polyhedra. We also report results of simulations for some elementary test problems.
A Strongly Polynomial Algorithm for a Special Class of Linear Programs
Authors: Adler I. , Cosares S.
Published: November 2008

We extend the list of linear programming problems that are known to be solvable in strongly polynomial time to include a class of LPs which contains special cases of the generalized transshipment problem. The result is facilitated by exploiting some special properties associated with Leontief substitution systems and observing that a feasible solution to the system, Ax = b, x ≥ 0, in which no variable appears in more than two equations, can be found in strongly polynomial time for b belonging to some set Ω.
Routing Printed Circuit Cards Through an Assembly Cell
Authors: Lofgren Christopher B. , McGinnis Leon F. , Tovey Craig A.
Published: November 2008

The process planning problem is described for a class of flexible assembly systems for printed circuit cards. The general problem of minimizing the number of station visits is shown to be NP-complete, and two classes of heuristics are shown to have arbitrarily bad worst case performance. Implications for design and operating discipline are discussed.
Waiting-Line Theory as a Management Tool
Authors: Van Voorhis W. R.
Published: November 2008

According to recent figures published by the U.S. Department of Commerce, approximately $28 billion were invested in new facilities and equipment by industries in this country during the year 1955. This large expenditure undoubtedly reflects the need for increased output in this country's rapidly expanding economy. But how have decisions been made in arriving at the amount and distribution of this additional productive effort? What proportion of this vast sum can be attributed to decisions based on intuition, judgment, and hunches? To what extent have expenditures been based upon sound scientific analysis? A great deal of inefficiency and waste of resources could certainly be avoided if management were to employ the many scientific techniques and tools that are currently available. In particular, waiting-line theory can be used to determine how many facilities one ought to have in a process or system for which output requirements can be specified. However, the theory has general applicability to a wide variety of problems not only in production areas but also in many other situations where service facilities of one kind or another must be coordinated with demands for service.
A Study of Sales Operations
Authors: Brown Arthur A. , Hulswit Frank T. , Kettelle John D.
Published: November 2008

This is a case study of sales operations for a client, paraphrased as a printing company, it begins with a market survey revealing a strong concentration of business among larger customers, and a tendency for individual customers to concentrate their business with a single printer. These results lead to the execution of an experiment to determine customer responses to various levels of effort. The experiment shows how much effort should be assigned to get customers, and how much to hold customers. The effort required, and the probabilities of success, determine the proper allocation of accounts to salesmen. By referring to the graph of customer size distribution, sizes of sales forces resulting from various allowed percentages for sales expense are derived. In addition, one method is presented for evaluating the expected profits from improved customer service.
Weapon-System Cost Analysis
Authors: Fisher G. H.
Published: November 2008

A method of estimating cost inputs for weapon-systems analyses is discussed. The major characteristics of the method are (1) Total cost concept, which provides for accumulation of “support” as well as “direct” costs to the tactical unit of capability (e.g., wing or squadron in the case of the Air Force) (2) Distinction between investment and annual operating costs (3) Incremental costing, which provides for taking into account “inheritance value” of existing assets when a new weapon system is phased in to replace an existing one (4) Time phasing of weapon systems and the costs related thereto (5) Emphasis on consistency in costing alternative weapon proposals, which, for purposes of systems analysis, is perhaps more important than striving for a high degree of accuracy. In addition to the application to formal weapon-systems analysis, use of the method as a tool in military planning and programming of future weapon systems is also discussed.
Operations Research in the American Thread Company
Authors: McGee Charles G.
Published: November 2008

Operations research in The American Thread Company is centered in the production planning department. This department has advantages as base for operations because of its intimate contact with other phases of the company's operations. The modest size of the company allows easy and informal communication. Two production-scheduling schemes are described. The first involves the scheduling of many small orders to the finishing mill, where a purely arithmetic scheme is used. The second scheme is used to schedule the rate of production of grey yarn for items produced on a continuous basis. This scheme is algebraic. Both of these schemes have decreased inventories substantially.
Sequential Arrays of Waiting Lines
Authors: Hunt Gordon C.
Published: November 2008

The problem considered in this paper is that in which a sequence of service operations must be performed on the units to be serviced. Poisson arrivals and exponential service times are assumed. Four particular cases of service facilities in series are treated, involving infinite storage space between stages, no storage space between stages, finite storage space between stages, and the case of the unpaced belt-production line. A comparison is given for two stages, and the maximum possible utilization is obtained for all cases discussed.
The Solution of the Single-Channel Queuing Equations Characterized by a Time-Dependent Poisson-Distributed Arrival Rate and a General Class of Holding Times
Authors: Luchak George
Published: November 2008

The single-channel queuing equations considered in this paper are characterized by a Poisson-distributed arrival rate and a general class of holding-time distributions. General solutions of the equations are obtained for the case in which the traffic intensity i is a continuous function of time and possesses continuous derivatives of all orders. The following particular cases are considered in detail (a) i constant and the holding-time distribution Pearson type-III (in this case the general solution is obtained in closed form in terms of a newly introduced function Ink(z), many of the properties of which are derived in the Appendix), (b) i directly proportional to time and the holding time exponentially distributed.
Optimal Dispatch of Interruptible and Curtailable Service Options
Authors: Caves Douglas W. , Herriges Joseph A.
Published: November 2008

Service options for the electric utility industry are increasingly including provisions to dynamically dispatch prices or service interruption calls to customers. When the number of such calls is contractually limited, then the issue of optimally dispatching the calls must be addressed. In this paper, an algorithm for optimally dispatching interruptible and curtailable (I/C) service options is developed within a stochastic dynamic programming (SDP) framework. The solution yields thresholds for calling load curtailments as a function of: 1) the number of days remaining in the period, 2) the available number of interruptions, and 3) the level of uncertainty regarding future price and cost fluctuations. The SDP approach also provides a framework for optimally designing the I/C program parameters. An illustration of the dispatching routine is provided using data from Niagara Mohawk Power Corporation (NMPC). The algorithm developed in the paper is currently being employed by NMPC as part of its I/C program for industrial and commercial customers.
A Model for Continuous-Review Pull Policies in Serial Inventory Systems
Authors: Badinelli Ralph D.
Published: November 2008

In this paper, we construct a model of the steady-state values of on-hand inventory and backorders for each facility of a serial inventory system in which each facility follows a (Q, R) policy based on installation stock. Such policies are represented by the popular kanban systems as well as more conventional applications of (Q, R) policies. The descriptive model presented here is intended for optimizing the parameters of such a policy and for obtaining theoretical results about the behavior of the system. We also illustrate the potential of the model for providing insights into system performance.
Reformulation of the Multiperiod MILP Model for Capacity Expansion of Chemical Processes
Authors: Sahinidis N. V. , Grossmann I. E.
Published: November 2008

The problem of selecting processes and capacity expansion policies for a chemical complex consisting of continuous chemical processes can be formulated as a multiperiod, mixed integer linear programming (MILP) problem. Based on a variable disaggregation technique which exploits lot sizing substructures, we propose two reformulations of the conventional MILP model. The first one is an NLP reformulation which very quickly yields good suboptimal solutions. The second is an MILP reformulation for exact solutions which leads to up to an order of magnitude faster computational results for large problems due to its tighter linear programming relaxation.
Habitat Dispersion in Forest Planning and the Stable Set Problem
Authors: Barahona Francisco , Weintraub Andrés , Epstein Rafael
Published: November 2008

We present a model for forest planning with habitat dispersion constraints. The problem is reduced to a linear program that is solved by a column generation approach. Generating one column reduces to a stable set problem in a graph; this is solved with linear programming techniques based on a partial description of the stable set polytope. We report computational experience with medium sized problems.