bluuebunny/crossref_metadata_2025 huggingface dataset:
Optimal Maintenance Policies for Single-Server Queueing Systems Subject to Breakdowns
Authors: Federgruen Awi , So Kut C.
Published: November 2008

We consider a single-server queueing system with Poisson arrivals and general service times. While the server is up, it is subject to breakdowns according to a Poisson process. When the server breaks down, we need to repair the server immediately by initiating one of two available repair operations. The operating costs of the system include customer holding costs, repair costs and running costs. The objective is to find a corrective maintenance policy that minimizes the long-run average operating costs of the system. The problem is formulated as a semi-Markov decision process. Under some mild conditions on the repair time and service time distributions and the customer holding cost rate function, we prove that there exists an optimal stationary policy which is monotone, i.e., which is characterized by a single threshold parameter: The stochastically faster repair is initiated if and only if the number of customers in the system exceeds this threshold. We also present an efficient algorithm for the determination of an optimal monotone policy and its average cost. We then extend the problem to allow the system to postpone the repair until some future point in time. We provide a partial characterization of an optimal policy and show that monotone policies are, in general, not optimal. The latter problem also extends the authors' previous work.
Customer Delay in M/G/∞ Repair Systems with Spares
Authors: Berg M. , Posner M. J. M.
Published: November 2008

The exchangeable-item repair systems considered here are characterized by customers who bring failed items to the system, and are prepared to take in return any serviceable item of the same kind. This exchangeability feature enables the system to keep spare items, either those repaired by the facilities the system operates or newly acquired ones. Rather than only considering the common number of backorders as a measure, the focus of this research is on the delay experienced by customers in an “ample-service” repair system, where repair of a failed item commences upon arrival at the system. The stationary and the nonstationary distributions of this delay are obtained in an analytic closed form in terms of the basic model parameters—the (Poisson) arrival rate, the (arbitrary) repair distribution of an item, and the initial number of spares in the system. The results are applicable to a variety of models that incorporate factors such as item scrapping, replenishment of new items, different modes of failure, and customers bringing several failed items. Successive use of the formulas can extend the spectrum of potential applications to multiechelon systems.
Stimulating Job Search Through the Unemployment Insurance System
Authors: Ben-Horim Moshe , Zuckerman Dror
Published: November 2008

This note extends the model of unemployment insurance reported by D. Zuckerman in 1985. The following extensions are incorporated into the model: The government's objective function is now formulated in a more economically appealing fashion; the search process is allowed to continue beyond the coverage period; the time value of money is explicitly incorporated; and the individual's search strategy is compared with the socially optimal policy. Using techniques and concepts from game theory, we investigate the socially and individually optimal strategies and derive an unemployment insurance strategy that best suits the government's objective.
Deterministic Minimal Time Vessel Routing
Authors: Papadakis Nikiforos A. , Perakis Anastassios N.
Published: November 2008

We develop general methodologies for the minimal time routing problem of a vessel moving in stationary or time dependent environments, respectively. Local optimality considerations, combined with global boundary conditions, result in piecewise continuous optimal policies. In the stationary case, the velocity of the traveling vessel within each subregion depends only on the direction of motion. Variational calculus is used to derive the geometry of piecewise linear extremals. For the time dependent problem, the speed of the vessel within each subregion is assumed to be a known function of time and the direction of motion. Optimal control theory is used to reveal the nature of piecewise continuous optimal policies.
A Comparative Study of Algorithms for Matrix Balancing
Authors: Schneider Michael H. , Zenios Stavros A.
Published: November 2008

The problem of adjusting the entries of a large matrix to satisfy prior consistency requirements occurs in economics, urban planning, statistics, demography, and stochastic modeling; these problems are called Matrix Balancing Problems. We describe five applications of matrix balancing and compare the algorithmic and computational performance of balancing procedures that represent the two primary approaches for matrix balancing—matrix scaling and nonlinear optimization. The algorithms we study are the RAS algorithm, a diagonal similarity scaling algorithm, and a truncated Newton algorithm for network optimization. We present results from computational experiments with large-scale problems based on producing consistent estimates of Social Accounting Matrices for developing countries.
Scheduling Deteriorating Jobs on a Single Processor
Authors: Browne Sid , Yechiali Uri
Published: November 2008

N jobs are to be processed sequentially on a single machine. While waiting for processing, jobs deteriorate, causing the random processing requirement of each job to grow at a job-specific rate. Under such conditions, the actual processing times of the jobs are no longer exchangeable random variables and the expected makespan is no longer invariant under any scheduling strategy that disallows idleness. In this paper, we analyze the effects of different deterioration schemes and derive optimal scheduling policies that minimize the expected makespan, and, for some models, policies that minimize the variance of the makespan. We also allow for random setup and detaching times. Applications to optimal inventory issuing policies are discussed and extensions are considered.
Minimum Cost Routing on Stochastic Networks
Authors: Corea G. A. , Kulkarni V. G.
Published: November 2008

In this paper, we consider the minimum cost transshipment problem in a directed network, having a single source node s with supply S and multiple demand nodes. The arc lengths are independent and exponentially distributed random variables. The cost of shipping is $1/unit flow/unit length, and T is the minimum cost of shipping the S units so as to satisfy all the demands. We construct a continuous time Markov chain with an upper triangular generator matrix such that T equals a particular first passage time in this chain. This fact is used to derive numerically stable algorithms for computing the exact distribution and moments of T.
Efficient Shortest Path Simplex Algorithms
Authors: Goldfarb Donald , Hao Jianxiu , Kai Sheng-Roan
Published: November 2008

We consider the specialization of the primal simplex algorithm to the problem of finding a tree of directed shortest paths from a given node to all other nodes in a network of n nodes or finding a directed cycle of negative length. Two efficient variants of this shortest path simplex algorithm are analyzed and shown to require at most (n − 1)(n − 2)/2 pivots and O(n3) time.
Simple Approximations for the Batch-Arrival Mx/G/1 Queue
Authors: Van Ommeren J. C. W.
Published: November 2008

In this paper we consider the Mx/G/1 queueing system with batch arrivals. We give simple approximations for the waiting-time probabilities of individual customers. These approximations are checked numerically and they are found to perform very well for a wide variety of batch-size and service-time distributions.
On the Single Resource Capacity Problem for Multi-Item Inventory Systems
Authors: Rosenblatt Meir J. , Rothblum Uriel G.
Published: November 2008

In this paper, we study multi-item inventory systems under a single resource capacity constraint. In contrast to most previous approaches, we treat the capacity as a decision variable, and not as given data. This is consistent with many practical cases where additional capacities/resources can be acquired/rented at some cost/profit. Two solution procedures are developed for deriving an optimal policy within the class of policies that has a fixed cycle for all items with phasing of orders within the cycle. These solution procedures can be applied to various types of cost functions, as illustrated by an example.
Optimal Control of the Vacation Scheme in an M/G/1 Queue
Authors: Kella Offer
Published: November 2008

In this article the M/G/1 queue with server vacations is considered with the assumption that the decision whether or not to take a new vacation, when the system is empty, depends on the number of vacations already taken through a random outcome. Both descriptive and optimization issues are considered, where the latter is done under the expected long-run average cost criterion with linear holding costs, fixed setup costs and a concave piecewise linear reward function for being on vacation. The optimization problem results in an infinite dimensional fractional program of which the solution yields a (deterministic) policy of the control limit type.
A Two-Phase Decomposition Approach for Electric Utility Capacity Expansion Planning Including Nondispatchable Technologies
Authors: Sherali Hanif D. , Staschus Konstantin
Published: November 2008

This paper presents a model and a two-phase algorithm for incorporating nondispatchable technologies or energy sources as decision variables in long-range electric utility capacity expansion plans. The first phase uses a deterministic model to quickly obtain a near-optimal expansion plan. This model employs a step approximation to the time-dependent availabilities of the nondispatchable technologies, and a derating technique to represent forced outages of conventional units. Specialized algorithms that exploit the structure of this deterministic problem are developed. The second phase refines the resulting solution toward the probabilistic optimum. It employs accurate probabilistic production costing techniques to account for forced outages of conventional generators, and uses hour-by-hour simulation to represent the contributions of nondispatchable technologies. This second phase requires few additional iterations in our computational experience. The proposed approach suggests a modification for the existing state-of-the-art methodology electric generation expansion analysis system (EGEAS), particularly for situations in which the cumulant approximation used in EGEAS may be inadequate, and it suggests an improved technique for accelerating Bloom's Generalized Benders' Decomposition algorithm for the conventional equipment capacity expansion planning problem.
Bias Properties of Budget Constrained Simulations
Authors: Glynn Peter W. , Heidelberger Philip
Published: November 2008

This paper addresses the bias characteristics of estimators produced from Monte Carlo simulations. If the computer time allocated to the simulation is t, then N(t), the number of replications completed by time t, is a renewal process. The simulation implications of a known exact expression for the expected value of a sample mean based on N(t) replications are explored and a similar exact expression for a sample mean based on N(t) + 1 replications is derived. Bias expansions for a sample mean based on N(t) or N(t) + 1 replications are obtained. The bias in the sample mean based on N(t) replications is at most of order o(1/t). Under suitable moment conditions, the bias decreases at a much faster rate than o(1/t); on the other hand, the estimator based on N(t) + 1 replications has bias of order 1/t. The exact expressions also lead to simple and totally unbiased estimators. Using Taylor series, the bias expansions of a general function of means based on N(t) or N(t) + 1 replications are determined. The leading terms in these expansions are of order 1/t, although the coefficients are different. Based on these expansions, a Tin-style adjusted estimator is proposed to reduce the bias. These expansions are specialized to the case of ratio estimation in regenerative simulation. Due to a cancellation effect, the ratio estimator based on N(t) + 1 cycles is biased only to order o(1/t) providing confirmation and reinterpretation of a result of M. Meketon and P. Heidelberger.
Measuring Risk Reduction Benefits with Discounted Longevity
Authors: Bordley Robert F.
Published: November 2008

There are many ways to assess the benefits and costs of risk-reduction policies. This paper shows that discounted longevity as a measure of benefits and the negative of net output as a measure of costs can be deduced from the Shepard and Zeckhauser utility-maximization model.
Existence of Forecast Horizons in Undiscounted Discrete-Time Lot Size Models
Authors: Chand Suresh , Sethi Suresh P. , Proth Jean-Marie
Published: November 2008

We are concerned with a discrete-time undiscounted dynamic lot size model in which demand and cost parameters are constant for an initial few periods. As our main result, we obtain an upper bound on the number of these periods which guarantees the optimality of the Economic Order Quantity (EOQ) as the size of the production lot to be produced in the first period. The upper bound is given and the optimality holds for every problem with an horizon not less than the upper bound and for the infinite horizon problem. The data beyond the upper bound are allowed to be specified arbitrarily. In the context of forecast horizon theory, we obtain conditions for a finite forecast horizon to exist in the undiscounted dynamic lot size model. Furthermore, existence results for forecast horizons in an undiscounted optimization problem are obtained for the first time in this paper.
Stochastic Minimization of the Makespan in Flow Shops with Identical Machines and Buffers of Arbitrary Size
Authors: Kijima Masaaki , Makimoto Naoki , Shirakawa Hiroshi
Published: November 2008

Stochastic permutation flow shops of m identical machines and n jobs are considered. There exist buffers of arbitrary size between two consecutive machines. For particular types of job processing times, we present optimal schedules which minimize the makespan in the stochastic sense. Moreover, it will be shown that the optimal schedules are closely related to those of the no buffer case. Finally, our results are recaptured in the context of tandem queues.
A Dynamic Inventory Model with Periodic Auditing
Authors: Flynn James , Garstka Stanley
Published: November 2008

Consider a single-item, periodic review, stationary inventory model with stochastic demands, proportional ordering costs, and convex holding and shortage costs, where shortages are backordered and Veinott's well known terminal condition holds. Orders can be scheduled for any period, but the actual inventory level is determined every T periods through an audit. This leads to a dynamic programming model where stage n contains periods (n − 1)T + 1 through nT. For both discounted and averaging criteria, a simple rule optimally describes the orders for the T periods of a stage as a function of the state (beginning inventory level) and the cumulative T-period order. The latter is optimally determined by a base stock policy with two base stock levels: one for the final stage, another for the rest. (The horizon may be finite or infinite.) Methods are presented for computing optimal policies, together with bounds on the costs of (suboptimal) myopic policies. Models with proportional costs and continuous demands are studied in detail. Computational experiments indicate that myopic policies perform quite well for such models. The selection of a best review period T is covered briefly. Applications of our model include just in time settings where audit decisions play a negligible role.
How Many Parts to Make at Once
Authors: Harris Ford W.
Published: November 2008

Reprinted from Factory, The Magazine of Management, Volume 10, Number 2, February 1913, pp. 135–136, 152.

Interest on capital tied up in wages, material and overhead sets a maximum limit to the quantity of parts which can be profitably manufactured at one time; “set-up” costs on the job fix the minimum. Experience has shown one manager a way to determine the economical size of lots.
Modeling Equity of Risk in the Transportation of Hazardous Materials
Authors: Gopalan Ram , Kolluri Krishna S. , Batta Rajan , Karwan Mark H.
Published: November 2008

In this paper, we develop and analyze a model to generate an equitable set of routes for hazardous material shipments. The objective is to determine a set of routes that will minimize the total risk of travel and spread the risk equitably among the zones of the geographical region in which the transportation network is embedded, when several trips are necessary from origin to destination. An integer programming formulation for the problem is proposed. We develop and test a heuristic that repeatedly solves single-trip problems: a Lagrangian dual approach with a gap-closing procedure is used to optimally solve single-trip problems. We report a sampling of our computational experience, based on a real-life routing scenario in the Albany district of New York State. Our findings indicate that one can achieve a high degree of equity by modestly increasing the total risk and by embarking on different routes to evenly spread the risk among the zones. Furthermore, it appears that our heuristic procedure is excellent in terms of computational requirements as well as solution quality. We also suggest some directions for future research.
Finite Dominating Sets for Network Location Problems
Authors: Hooker J. N. , Garfinkel R. S. , Chen C. K.
Published: November 2008

A research theme involving location on networks, since its inception, has been the identification of a finite dominating set (FDS), or a finite set of points to which an optimal solution must belong. We attempt to unify and generalize results of this sort. We survey the literature and then prove some theorems that subsume most previous results and that are, at the same time, more general than previous results. The paper is aimed primarily at investigators who wish to know whether an FDS exists for a specific problem.
Structured Partitioning Problems
Authors: Anily S. , Federgruen A.
Published: November 2008

In many important combinatorial optimization problems, such as bin packing, allocating customer classes to queueing facilities, vehicle routing, multi-item inventory replenishment and combined routing/inventory control, an optimal partition into groups needs to be determined for a finite collection of objects; each is characterized by a single attribute. The cost is often separable in the groups and the group cost often depends on the cardinality and some aggregate measure of the attributes, such as the sum or the maximum element. An upper bound (capacity) may be specified for the cardinality of each group and the number of groups in the partition may either be fixed or variable. The objects are indexed in nondecreasing order of their attribute values and within a given partition the groups are indexed in nondecreasing order of their cardinalities. We identify easily verifiable analytical properties of the group cost function under which it is shown that an optimal partition exists of one of three increasingly special structures, thus allowing for increasingly simple solution methods. We give examples of all the above listed types of planning problems, and apply our results for the identification of efficient solution methods (wherever possible).
A Rapid Method for Optimization of Linear Systems with Storage
Authors: Bannister C. H. , Kaye R. J.
Published: November 2008

A new method for optimizing the operation of a single storage connected to a general linear memoryless system is presented. The model is shown to cover a wide variety of practical situations where a deterministic approximation is valid. The method combines linear and dynamic programming concepts to produce a fast but exact optimization.
Some Facets for an Assignment Problem with Side Constraints
Authors: Aboudi Ronny , Nemhauser George L.
Published: November 2008

This paper presents a class of facet-defining inequalities for an assignment problem with the additional constraints that specified variables are required to be equal to each other. In a special case, the complete polyhedral description is given.
A Secretary Problem with Uncertain Employment and Best Choice of Available Candidates
Authors: Tamaki Mitsushi
Published: November 2008

A finite number of candidates appear one-by-one in random order with all permutations equally likely. We are able, at any time, to rank the candidates that have so far appeared according to some order of preference. Each candidate may be classified into one of two types independent of the other candidates: available or unavailable. An unavailable candidate does not accept an offer of employment. The goal is to find a strategy that maximizes the probability of employing the best among the available candidates based on both the relative ranks and the availabilities observed so far. According to when the availability of a candidate can be ascertained, two models are considered. The availability is ascertained only by giving an offer of employment (MODEL 1), while the availability is ascertained just after the arrival of the candidate (MODEL 2).
An Algorithm for Solving Dynamic Capacitated Plant Location Problems with Discrete Expansion Sizes
Authors: Shulman Alexander
Published: November 2008

In the Dynamic Capacitated Plant Location Problem (DCPLP) the task is to find a time schedule and sizes for installing facilities at plant locations to minimize the discounted cost of capital expenditures over the planning horizon. The costs include setup costs for establishing facilities, volume dependent operational costs, and transportation costs for distributing demand from facilities to customers. We consider a class of the DCPLP in which the available facilities have finite capacities and the number of facility types is relatively small so that the expansion sizes cannot be modeled by continuous variables. The DCPLP is formulated as a combinatorial optimization problem that allows consideration of more than one fatality type and finds the optimum mix of facilities in each location. We describe an optimization algorithm for solving the DCPLP based on the Lagrangian relaxation technique. Algorithms for converting infeasible optimal solutions of the Lagrangian to a feasible solution of the DCPLP are presented. The procedure has been tested on both randomly generated and real-life based problems. Computational results indicate that the algorithm produces solutions within 3% of the lower bounds for a wide range of input data.
Capacitated Two-Stage Multi-Item Production/Inventory Model with Joint Setup Costs
Authors: Anily S. , Federgruen A.
Published: November 2008

We analyze a continuous-time, two-stage production/inventory system. In the first stage, a common intermediate product is produced in batches, and possibly stored. In the second phase, the intermediate product is fabricated into n distinct finished products. Several finished products may be included in a single production batch of limited capacity to exploit economies of scale. We propose a planning methodology to address the combined problem of joint setup costs and capacity limits (per setup). We restrict ourselves to a class of replenishment strategies with the following properties: a replenishment strategy specifies a collection of families (subsets of items) covering all end-items, if an item belongs to several families a specific fraction of its sales is assigned to each family. Each time the inventory of one item in a family is replenished, the inventories of all other items in the family are replenished as well. We derive a simple (roughly 0(n log n)) algorithm that results in a strategy whose long-run average cost comes within a few percentage points of a lower bound for the minimum achievable cost (within the above class of strategies).
Multi-Echelon Assembly Systems with Nonstationary Demands: Heuristics and Worst Case Performance Bounds
Authors: Joneja Dev
Published: November 2008

In a multi-echelon assembly system, each production stage has inputs from a number of preceding stages, and supplies at most one succeeding stage. The product of the final stage is used to satisfy external demand in discrete time. There are fixed setup costs and linear inventory holding costs at each stage. The objective is to minimize the cost of operating the system over a finite time horizon. We consider the common case of nonstationary demands, and propose an extremely fast and simple single-pass approximation algorithm for this problem. We prove that in the worst case the performance of the algorithm is uniformly bounded.
How Many Forecasters Do You Really Have? Mahalanobis Provides the Intuition for the Surprising Clemen and Winkler Result
Authors: Morrison Donald G. , Schmittlein David C.
Published: November 2008

How to combine expert opinions is an issue that has many aspects and even more “answers.” The problem addressed here is the incremental information an additional expert brings when he or she is correlated with the existing experts. R. T. Clemen and R. L. Winkler derive an algebraic formula that gives the surprising answer—usually very little. In this paper, we provide the geometrical intuition behind the Clemen and Winkler result. We also show how the Clemen and Winkler formula breaks down (i.e., gives bizarre results) as the error covariance structure approaches singularity.
Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
Authors: Hochbaum Dorit S. , Shamir Ron
Published: November 2008

A high multiplicity scheduling problem consists of many jobs which can be partitioned into relatively few groups, where all the jobs within each group are identical. Polynomial, and even strongly polynomial, algorithms for the standard scheduling problem, in which all jobs are assumed to be distinct, become exponential for the corresponding high multiplicity problem. In this paper, we study various high multiplicity problems of scheduling unit-time jobs on a single machine. We provide strongly polynomial algorithms for constructing optimal schedules with respect to several measures of efficiency (completion time, lateness, tardiness, the number of tardy jobs and their weighted counterparts). The algorithms require a number of operations that are polynomial in the number of groups rather than in the total number of jobs. As a by-product, we identify a new family of nxn transportation problems which are solvable in O(n log n) time by a simple greedy algorithm.
Commonality Analysis Using Clustering Methods
Authors: Thomas Lawrence Dale
Published: November 2008

The application of commonality in a system represents an attempt to reduce costs by reducing the number of unique components. A formal method for conducting commonality analysis has not been established. This paper characterizes commonality analysis as a partitioning problem for which the solution may be approximated by the application of clustering methods. A clustering algorithm is developed and applied to a commonality analysis of Space Station water tanks. The success in applying a clustering method in this problem indicates a significant potential for application of clustering methods to commonality analysis.
On Finite Delay-Moment Conditions in Queues
Authors: Wolff Ronald W.
Published: November 2008

We review the Kiefer–Wolfowitz conditions for finite delay moments at a GI/G/s queue, which are independent of moment conditions on the arrival process. Through examples, we show that for nonrenewal arrivals, some additional conditions on the arrival process are necessary. We discuss the question of whether some known sufficient conditions for finite delay moments at “downstream” stations in a tandem queue are really necessary. We then show how to decouple conditions on the arrival process from conditions on service times. Finally, we obtain sufficient conditions for queues with regenerative arrivals.
Analysis of a Kanban Discipline for Cell Coordination in Production Lines, II: Stochastic Demands
Authors: Mitra Debasis , Mitrani Isi
Published: November 2008

We describe and analyze a discipline called kanban for the control and coordination of cells in large-scale manufacturing facilities. There are many cells in tandem and also a process of arriving consumers; each consumer queues as long as necessary before departing with a product finished by the last cell. The coordination scheme relies on the circulation of a fixed number of cards (or kanbans) in each cell. This paper differs from our earlier paper in that here the process of consumers modulates the production process. Our results are in three parts. First, the kanban is compared to the classical production discipline and its (sample path) dominance in terms of the consumers' waiting time is proven. Second, we give an analytic scheme for approximating the performance of the stochastic kanban system by examining a single cell in isolation and then combining these through fixed-point equations. Ergodicity is equivalent in our approximation to the existence and uniqueness of a solution to the fixed-point equations and a complete, finite procedure for its resolution is obtained. Third, we report on experiments involving simulations and our method of analysis.
A New Methodology for Military Force Structure Analysis
Authors: Gallagher Mark A. , Kelly Elizabeth J.
Published: November 2008

A new methodology provides military decision makers with information on the aggregate effectiveness of large-scale conventional (nonnuclear) and combined nuclear and conventional force structures against a wide range of targets. This methodology coupled a generic data base of representative targets, to which real-world targets can be mapped, with a nuclear force-exchange model that uses goal programming techniques to determine optimal allocations of weapons to targets. This methodology enabled military strategists to analyze the effectiveness of existing and proposed weapon systems against a variety of targets and to study a number of force structures constrained by proposed force reduction treaties and tight defense budgets.
Algorithms for Multiplex Bundling in a Telecommunications Network
Authors: Doverspike R. D.
Published: November 2008

The function of a digital telecommunications network is to transport demand of digital signals between pairs of locations. To achieve this economically, multiplex equipment packs lower rate digital signals into higher rate signals for routing over transmission facility links. Given a multiperiod demand forecast and demand routing plan, the multiplex bundling problem minimizes equipment and transmission costs by demultiplexing the higher rate signals into their lower rate components at various nodes along paths to allow lower rate signals from different sources and sinks to be combined. However, exact solution of the multiplex bundling problem is intractable, and therefore this paper presents a heuristic two-phased approach. Phase 1 formulates a single-period, capacitated routing model. The Phase 1 solution method is to first solve a problem with relaxed capacity constraints and then solve a 0–1 multiconstraint knapsack problem to obtain feasibility. Computational results show that the Phase 1 heuristic produces near-optimal results. Phase 2 exactly solves a multiperiod problem for each demand re-routing chosen in Phase 1 by using a single-stage dynamic programming algorithm. The Phase 2 algorithm reduces the state space by taking advantage of state conditions at optimality.
A State Aggregation Approach to Manufacturing Systems Having Machine States with Weak and Strong Interactions
Authors: Jiang J. , Sethi S. P.
Published: November 2008

A hierarchical approach to control a manufacturing system, subject to multiple machine states modeled by a Markov process with weak and strong interactions, is suggested. The idea is to aggregate strongly interacting or high transition probability states within a group of states and consider only the transition between these groups for the analysis of the system in the long run. We show that such an aggregation results in a problem of reduced size, whose solution can be modified in a simple way to obtain an asymptotically optimal feedback solution to the original problem. Also, an example is solved to illustrate the results developed in the paper.
Production Scheduling by the Transportation Method of Linear Programming
Authors: Bowman Edward H.
Published: November 2008

With fluctuating sales, a manufacturer must have fluctuating production, or fluctuating inventory, or both. Penalties are associated with either type of fluctuation. Several papers place this problem into a conventional linear-programming framework. This paper suggests that the same problem may be placed into a transportation-method framework and, further, that many transportation problems may be extended to include multiple time periods where this is meaningful. A generalized scheduling problem is placed here into the standard form of the transportation table.
A Competitive-Bidding Strategy
Authors: Friedman Lawrence
Published: November 2008

A method is presented that determines optimum bids in a competitive-bidding situation where each competitor submits one closed bid. The number of bidders may be large or may be unknown. This method makes use of the previous “bidding patterns” of all possible opposition bidders and in the case where the bidding is on contracts, the estimated probability distribution of the cost of fulfilling the contract. The case where a number of bids are to be submitted simultaneously is also discussed.
Letter to the Editor—The Process of Operations-Research Accomplishment
Authors: Hitchman Norman
Published: November 2008

A humorous note about Operations Research projects.
Operations Research in Production Control—A Progress Report
Authors: Vazsonyi A.
Published: November 2008

The case history of a continuing operations-research study in a manufacturing firm is given. The problem of making decisions on the release of production orders and the development of decision rules for the solution of this problem are presented. Some experiences on the problems of implementing the results of the study are described.
Shock Waves on the Highway
Authors: Richards Paul I.
Published: November 2008

A simple theory of traffic flow is developed by replacing individual vehicles with a continuous “fluid” density and applying an empirical relation between speed and density. Characteristic features of the resulting theory are a simple “graph-shearing” process for following the development of traffic waves in time and the frequent appearance of shock waves. The effect of a traffic signal on traffic streams is studied and found to exhibit a threshold effect wherein the disturbances are minor for light traffic but suddenly build to large values when a critical density is exceeded.
A Graphical Solution of the Transportation Problem
Authors: Vidale Marcello L.
Published: November 2008

This paper presents a simple graphical technique applicable to a wide variety of transportation problems involving a large number of production centers and market areas. The assumption is made that transportation costs are monotonically increasing as one moves out from a given production center, but the rate of increase need not be constant or uniform in all directions.
The Operations Research Society of America—Report of the Secretary
Authors: Ernst Martin L.
Published: November 2008

The membership of the Society on December 31, 1955 was 1383, as compared with 1204 in April of that year. Of the December 1955 membership, 103 were Fellows, 373 were Members, 827 were Associate Members, and 80 were Student Associate Members. Subsequently, at its meeting on January 9, 1956, the Council elected the following 8 new Fellows and 44 additional Members.
On Staff Organization
Authors: Roy Robert H.
Published: November 2008

Modern organizations, as is well known to everyone, have been characterized by growth to large size. They also have been characterized—and this has been less often remarked—by the proliferation of staff elements. No doubt these developments have been interdependent to some degree.

This paper was presented as an invited address to the session on Operations Research and the Firm at the Fourth Annual Meeting of the Society, Washington, D.C., May 10, 1956.
A Method of Computing Survival Probabilities of Several Targets Versus Several Weapons
Authors: Robertson Jane Ingersoll
Published: November 2008

Infantry squad weapons are evaluated against the background of a rifle squad attacking a position defended by riflemen. The behavior of Attackers and Defenders is characterized by simultaneous action within each squad. The Defenders, acting independently of one another, each choose at random an Attacker as target and all Defenders fire simultaneously. The process is repeated in a sequence of volleys. As independent variables there are the original number, T, of Attackers, the number of Defenders, the single-shot hit probability, and the number of volleys fired. After each volley there is defined a set of probabilities of the survival of 0, 1, …, T Attackers. Taken as a sequence, these sets form a Markov chain, which is the basis for weapons comparison. All results of this paper are applications of the Markov theory. This technique is most useful for squads with a maximum of 15 men, some numerical examples are included. There are suggested ways in which tactical features can be reflected in the independent variables.
Inventory Management of Slow-Moving Parts
Authors: Heyvaert A. C. , Hurt A.
Published: November 2008

We present in this paper a simple, fast, and accurate method for determining optimal stock levels for slow-moving parts which we worked out in March 1955. Independently of our work, Whitin and Youngs studied the same problem and published their results in a recent paper. “A Method for Calculating Optimal Inventory Levels and Delivery Time” in the Naval Research Logistics Quarterly, September 1955. While both studies are basically the same, our solution seems to be the more practical. Essential differences are the use of a second criterion (not so complete as the “costs,” but more easily accepted by managers)—the customer's satisfaction, and the graphical presentation, which allows the immediate determination of the optimal level. For practical reasons we assumed that the distribution of demand is Poisson, conceptually the distribution may be arbitrary. The method is restricted to slow-moving, non-seasonal parts with fairly long replenishment periods.
Letter to the Editor—Comments on “Expectancy of Multiple Vehicular Breakdowns in a Tunnel”
Authors: Dobbie James M.
Published: November 2008

This paper by Leslie C. Edie appeared in the November 1955 issue of this Journal (vol. 3, p. 513). The problem is that of predicting the frequency of multiple breakdowns to be expected at a future time under conditions somewhat different from those prevailing when the data were collected. Unfortunately, Edie's method contains several errors in addition to the error which he found and eliminated.
The Queuiac: An Electromechanical Analog for the Simulation of Waiting-Line Problems
Authors: Dunn Paul F. , Flagle Charles D. , Hicks Philip A.
Published: November 2008

Of interest to the Operations Research Office for several years has been the problem of improving the efficiency of Army communications systems. Involved in these studies, besides obvious problems of communications equipments, are problems of organization and human handling operations. To understand and offer solutions to these latter problems, electromechanical simulation equipment has been developed that displays the network of handling operations and provides estimates of congestion at any or all points in the system. In the analog each node consists of a display and register unit upon which columns of lights represent items in a waiting line. Distributions of arrival times of input items and servicing times are programmed on standard teletype tape fed to the analog by teletype transmitters. The register unit at each point of the network displays the queue, computes state occupancy times, and provides estimates of state probabilities. Continuous records of the system states are maintained by pen recorders so that individual delay times and empirical estimates of their distributions may be obtained. The register units may be connected in parallel or tandem, representing various sequential or parallel operations. Available as important queue disciplines are the handling of multiple inputs on a priority basis and the automatic adjustment of servicing rates according to transient loads.
Air Weapons Systems Analysis
Authors: Precoda Norman
Published: November 2008

Continuous demands for improved performance plus broad technological advances have greatly increased the difficulties of determining the optimum design specifications for complex weapons systems. Difficulties arise from (1) the far-reaching effects of the initial specifications, (2) the long time interval between initial specifications and operational readiness, (3) the large number of major parameters involved and their complex interrelationships. A method for determining the design objectives most likely to optimize systems performance is described, the system a strategic-type bomber. This approach considers the bomber in terms of its military mission and the individual bomber characteristics in terms of their contributions to mission performance. Current results of past analysis are illustrated by the contemporary strategic bombers of the U.S., U.K., and U.S.S.R.—the final arbiters of the soundness of weapons-systems analysis and the engineering decisions based thereon.
The Power-Series Algorithm Applied to the Shortest-Queue Model
Authors: Blanc J. P. C.
Published: November 2008

An iterative numerical technique for the evaluation of queue length distribution is applied to multiserver systems with queues in parallel in which customers join (one of) the shortest queues upon arrival. The technique is based on power-series expansions of the state probabilities as functions of the load of the system. The convergence of the series is accelerated by applying a modified form of the epsilon algorithm. The shortest-queue model lends itself particularly well to a numerical analysis by means of the power-series algorithm due to a specific property of this model. Numerical values for the mean and the standard deviation of the total number of customers and the waiting times in stationary symmetrical systems are obtained for practically all values of the load for systems with up to ten queues and for a load not exceeding 75% for systems with up to 30 queues. Data are also presented for systems with four queues and unequal service rates.
Corrections to “Finding Optimal (s, S) Policies is About as Simple as Evaluating a Single Policy”
Authors: Zheng Yu-Sheng , Federgruen Awi
Published: November 2008

Correction to Zheng, Y.-S., A. Federgruen. 1991. Finding optimal (s, S) policies is about as simple as evaluating a single policy. Opns. Res. 39 654–665.
Games of Boldness, Where the Player Performing the Hardest Task Wins
Authors: Henig Mordechai , O'Neill Barry
Published: November 2008

In a game of boldness a player chooses one from a group of tasks, each having a known probability of success. The player attempts the task, and wins if it succeeds and has the lowest probability of any that succeed. Y. Gerchak and M. Henig (1986) showed that sports competitions that take this form and have players perform sequentially with full information are biased, in that the order of play helps later competitors. We discuss six game variants embodying different types of information possessed by the players before they choose, and different rules about the sequence of choice. Our results suggest that contests would be fairer if players were told others' task difficulties but not told their successes. Y. Gerchak and M. Kilgour's proposal to make later players choose tasks no easier than previous ones, also does well in regard to fairness and practicality.
Validation of Simulation Analysis Methods for the Schruben-Margolin Correlation-Induction Strategy
Authors: Tew Jeffrey D. , Wilson James R.
Published: November 2008

To analyze simulation experiments performed under the Schruben-Margolin strategy for assigning random number streams to individual runs, A. Nozari, S. Arnold, and C. Pegden developed special statistical methods for estimating a general linear metamodel (that is, a regression model) of a selected response variable expressed in terms of design variables (regressors) relevant to the target system. This paper describes a three-stage procedure for validating the use of these simulation analysis methods. Each stage of the validation procedure tests a key assumption about the behavior of the response across all points in the experimental design. The first stage checks for multivariate normality in the overall set of responses, the second stage checks for the Schruben-Margolin covariance structure among those responses, and the third stage checks for adequacy (goodness of fit) of the user-specified metamodel. To handle simulation experiments that display significant departures from the Schruben-Margolin covariance structure, we present alternative versions of the goodness-of-fit test and the follow-up analysis for the postulated metamodel that merely requires jointly normal responses. A numerical example illustrates the application of this validation procedure.
A Linearization Procedure for Quadratic and Cubic Mixed-Integer Problems
Authors: Oral Muhittin , Kettani Ossama
Published: November 2008

Several techniques of linearization have appeared in the literature. The technique of F. Glover, which seems to be the most efficient, linearizes a binary quadratic integer problem of n variables by introducing n new continuous variables and 4n auxiliary linear constraints. The new technique proposed in this paper is not only useful in linearizing binary quadratic and cubic integer problems, but also applicable to the case of quadratic and to a certain class of cubic “mixed-integer” problems. It is shown that the new technique further reduces the number of auxiliary linear constraints from 4n to n, while keeping the number of new continuous variables at n for the binary quadratic integer problem of n variables. And, it requires, in the case of a certain class of cubic mixed-integer problems having 2n of 0–1 variables, only 3n auxiliary linear constraints and the same number of new continuous variables. The analytical superiority of the new linearization technique has also been observed, in terms of the number of iterations and execution times, through a computational experiment conducted on a set of randomly generated binary quadratic integer problems.
One-Half Approximation Algorithms for the k-Partition Problem
Authors: Feo Thomas , Goldschmidt Olivier , Khellaf Mallek
Published: November 2008

The k-partition problem seeks to cluster the vertices of an edge-weighted graph, G = (V, E), into k sets of |V|/k vertices each, such that the total weight of the edges having both endpoints in the same cluster is maximized. Bottom-up type heuristics based on matchings are presented for this problem. These heuristics are shown to yield solutions that are at least one-half the weight of the optimal solution for k equal to |V|/3 and |V|/4.
A New Lower Bound for the Quadratic Assignment Problem
Authors: Carraresi Paolo , Malucelli Federico
Published: November 2008

We introduce a new lower bound for the quadratic assignment problem based on a sequence of equivalent formulations of the problem. We present a procedure for obtaining tight bounds by sequentially applying our approach in conjunction with the A. Assad and W. Xu bound and the N. Christofides and M. Gerrard bound.