bluuebunny/crossref_metadata_2025 huggingface dataset:
Multicommodity Network Flows with Safety Considerations
Authors: Chen Y. L. , Chin Y. H.
Published: November 2008

Previous research on the multicommodity minimum cost flow problem (MMCFP) has assumed that there are two types of values associated with an arc. The first is the capacity of the arc and the second is the unit flow cost along the arc. This paper adds the third attribute—the degree of difficulty—into the conventional model of the MMCFP. In this way, a new problem, which is more general and difficult than the conventional MMCFP, is formed. However, we show that these two problems are indeed polynomially equivalent. With the equivalence, the techniques developed for solving the conventional MMCFP can be used to solve the new but more general problem.
m-Median and m-Center Problems with Mutual Communication: Solvable Special Cases
Authors: Chhajed Dilip , Lowe Timothy J.
Published: November 2008

In this paper, we consider the network version of the m-median problem with mutual communication (MMMC). We reformulate this problem as a graph theoretic node selection problem defined on a special graph. We give a polynomial time algorithm to solve the node selection problem when the flow graph (graph that denotes the interaction between pairs of new facilities in MMMC) has a special structure. We also show that with some modification in the algorithm for MMMC, the m-center problem with mutual communication can also be solved when the flow graph has a special structure.
On the Optimal Stochastic Scheduling of Out-Forests
Authors: Coffman E. G. , Liu Zhen
Published: November 2008

This paper presents new results on the problem of scheduling jobs on K ≥ 1 parallel processors to stochastically minimize the makespan. The jobs are subject to out-forest precedence constraints, i.e., each job has at most one immediate predecessor, and job running times are independent samples from a given exponential distribution. We define a class of uniform out-forests in which all subtrees are ordered by an embedding relation. We prove that an intuitive greedy policy is optimal for K = 2, and that if out-forests satisfy an additional, uniform root-embedding constraint, then the greedy policy is optimal for all K ≥ 2.
Fixed Job Scheduling with Two Types of Processors
Authors: Dondeti V. R. , Emmons Hamilton
Published: November 2008

We consider a scheduling problem that involves two types of processors, but three types of jobs. Each job has a fixed start time and a fixed completion time, and falls into one of three types. Jobs of type 1 can be done only by type-1 processors, type-2 jobs only by type-2 processors, and type-0 jobs by either type of processors. We present a polynomial algorithm for finding the minimal cost combination of the two types of processors required to complete all jobs. The steps of the algorithm consist of constructing a job schedule network, transforming it into a single-commodity flow problem and finding the maximal flow through it.
Technology, Human Interaction, and Complexity: Reflections on Vehicular Traffic Science
Authors: Herman Robert
Published: November 2008

This paper is based on the second Philip McCord Morse Lecture given May 14, 1991, at the TIMS/ORSA Joint National Meeting in Nashville. It traces the author's involvement in the development of vehicular traffic science over the last 35 years. After some historical background, the paper discusses highlights of this work: developing and testing car-following theory, traffic theory for multilane highways, the behavior of traffic in towns, the relationship of trip decisions to traffic-system dynamics, and fuel consumption in urban areas. Throughout these discussions, particular attention is paid to the role of complexity and collective effects. The paper continues with comments on the importance of viewing traffic in the context of the overall infrastructure as well as its technology and environment. It concludes with some reflections on the state of the scientific enterprise in our society.
A Bi-Reference Procedure for Interactive Multiple Criteria Programming
Authors: Michalowski Wojtek , Szapiro Tomek
Published: November 2008

The paper presents an interactive procedure to search the set of nondominated outcomes of a multiple criteria linear programming problem. The procedure requires the decision maker to specify the worst outcome. Then, the ideal outcome is identified, and the improvement direction from the worst to ideal outcomes is constructed. A trial solution is found by moving from a current solution along the improvement direction, while maximizing the step size. For a trial solution, the decision maker is requested to partition the set of objective functions into three categories: those to be improved, those which may remain unchanged, those which may be relaxed. Based on this partition, the procedure displaces the worst and ideal outcomes, calculates the new improvement direction, and the entire process is repeated. The method terminates when two successive trial solutions are reasonably similar.
A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
Authors: Desrochers Martin , Desrosiers Jacques , Solomon Marius
Published: November 2008

The vehicle routing problem with time windows (VRPTW) is a generalization of the vehicle routing problem where the service of a customer can begin within the time window defined by the earliest and the latest times when the customer will permit the start of service. In this paper, we present the development of a new optimization algorithm for its solution. The LP relaxation of the set partitioning formulation of the VRPTW is solved by column generation. Feasible columns are added as needed by solving a shortest path problem with time windows and capacity constraints using dynamic programming. The LP solution obtained generally provides an excellent lower bound that is used in a branch-and-bound algorithm to solve the integer set partitioning formulation. Our results indicate that this algorithm proved to be successful on a variety of practical sized benchmark VRPTW test problems. The algorithm was capable of optimally solving 100-customer problems. This problem size is six times larger than any reported to date by other published research.
The Joint Replenishment Problem with General Joint Cost Structures
Authors: Federgruen Awi , Zheng Yu-Sheng
Published: November 2008

We consider inventory systems with several distinct items. Demands occur at constant, item specific rates. The items are interdependent because of jointly incurred fixed procurement costs: The joint cost structure reflects general economies of scale, merely assuming a monotonicity and concavity (submodularity) property. Under a power-of-two policy each item is replenished with constant reorder intervals which are power-of-two multiples of some fixed or variable base planning period. Our main results include a proof that, depending upon whether the base planning period is fixed or variable, the best among all power-of-two policies has an average cost which comes within either 6% or 2% of an easily computable lower bound for the minimum cost value. We also derive two efficient algorithms to compute an optimal power-of-two policy. The proposed algorithms generate as a by-product, a specific cost allocation of the joint cost structure to the individual items. With this specific allocation, the problem with separable costs is in fact equivalent to the original problem with nonseparable joint costs in the sense that the two problems share the same sets of optimal power-of-two policies with identical associated long-run average costs.
Joint Production Planning and Product Delivery Commitments with Random Yield
Authors: Henig Mordechai I. , Levin Nissan
Published: November 2008

We consider a producer who turns a raw material into a product. Before embarking upon production, the producer has to consider the quantity of raw material to order and the finished product delivery commitments; the actual amount produced is a random multiple of the amount of raw material ordered. A concave expected profit function is introduced which gives rise to simple formulas for determining the optimal quantities to order and to commit for delivery. We also analyze the relations between the optimal quantities to order and to commit, the expected amount received and production capacity. We show that among several vendors of the raw material, there exists a preferred one, no matter what the producer's cost parameters, if and only if the random multiple associated with that vendor is dominant in the sense of the second-degree stochastic order.
A Note on “Inventory Models with Cost Increases”
Authors: Goyal S. K.
Published: November 2008

In this note, a simple procedure is given for determining the optimal ordering policy for an item for which an increase in the price has been announced. The procedure eliminates the need for evaluation and comparison of the total costs of alternate ordering policies for determining the optimal ordering policy.
Optimization of Purchase, Storage and Transmission Contracts for Natural Gas Utilities
Authors: Avery William , Brown Gerald G. , Rosenkranz John A. , Wood R. Kevin
Published: November 2008

Natural gas utilities supply about a quarter of the energy needs of the United States. From wellhead to consumer, operations are governed by an astounding diversity of purchase, transport, and storage contract agreements which prepare a complex physical distribution system to meet future demands no more predictable than next year's weather. We present a decision support system based on a highly detailed optimization model used by utilities to plan operations which minimize cost while satisfying regulatory agencies. Applications at Southwest Gas Corporation are presented along with a case study at Questar Pipeline Corporation.

“But thou, contracted to thine own bright eyes,

Feed'st thy light's flame with self-substantial fuel”

William Shakespeare, First Sonnet
An Alternative Approach to Modeling Recidivism Using Quantile Residual Life Functions
Authors: Ellermann Raymond , Sullo Pasquale , Tien James M.
Published: November 2008

Empirical estimates of quantile residual life functions can be employed effectively to obtain properties of recidivism and to help screen parametric mixture models. In this manner, the Burr model is demonstrated to be an appropriate model for characterizing recidivism. When applied to certain data, the model suggests that while the observed declining recidivism rate can be explained by population heterogeneity, individual recidivism rates may in fact be increasing. The quantile residual life function approach to modeling recidivism is applied to two often-referenced data sets, as well as to an extensive data set obtained from the State of New York which is new to the criminal justice literature.
A Vehicle Routing Problem with Stochastic Demand
Authors: Bertsimas Dimitris J.
Published: November 2008

We consider a natural probabilistic variation of the classical vehicle routing problem (VRP), in which demands are stochastic. Given only a probabilistic description of the demand we need to design routes for the VRP. Motivated by applications in strategic planning and distribution systems, rather than resolving the problem when the demand becomes known, we propose to construct an a priori sequence among all customers of minimal expected total length. We analyze the problem using a variety of theoretical approaches. We find closed-form expressions and algorithms to compute the expected length of an a priori sequence under general probabilistic assumptions. Based on these expressions we find upper and lower bounds for the probabilistic VRP and the VRP re-optimization strategy, in which we find the optimal route at every instance. We propose heuristics and analyze their worst case performance as well as their average behavior using techniques from probabilistic analysis. Our results suggest that our approach is a strong and useful alternative to the strategy of re-optimization in capacitated routing problems.
Inventory Control with an Exponential Utility Criterion
Authors: Bouakiz Mokrane , Sobel Matthew J.
Published: November 2008

A base-stock policy is shown to be optimal when a dynamic version of the “news vendor” model is optimized with respect to an exponential utility criterion.
Sensitivity of Weights in Combining Forecasts
Authors: Winkler Robert L. , Clemen Robert T.
Published: November 2008

In the combination of forecasts, weighted averages that attempt to take into account the accuracy of the forecasts and any dependence among forecasts tend to perform poorly in practice. An important factor influencing this performance is the sensitivity, or instability, of the estimated weights used to generate the combined forecast. The intent of this paper is to look at this instability via graphs and the sampling distribution of the weights. Results are developed for the combination of two forecasts and extended to the m-forecast case by viewing the m-forecast case as a sequence of two-forecast combinations.
The Effect of Externalizing Setups in the Economic Lot Scheduling Problem
Authors: Gallego Guillermo , Moon Ilkyeong
Published: November 2008

This paper considers the Economic Lot Scheduling Problem with Reducible Setup Times (ELSP-RS), that is, determining a multiple product, single facility cyclic schedule to minimize holding and setup costs when setup times can be reduced, at the expense of setup costs, by externalizing setup operations. We develop an efficient algorithm that finds an optimal or near-optimal production schedule. Computational results indicate that dramatic savings are possible for highly utilized facilities.
Rolling Horizon Procedures in Nonhomogeneous Markov Decision Processes
Authors: Alden Jeffrey M. , Smith Robert L.
Published: November 2008

By far the most common planning procedure found in practice is to approximate the solution to an infinite horizon problem by a series of rolling finite horizon solutions. Although many empirical studies have been done, this so-called rolling horizon procedure has been the subject of few analytic studies. We provide a cost error bound for a general rolling horizon algorithm when applied to infinite horizon nonhomogeneous Markov decision processes, both in the discounted and average cost cases. We show that a Doeblin coefficient of ergodicity acts much like a discount factor to reduce this error. In particular, we show that the error goes to zero for any fixed rolling horizon as this Doeblin measure of control over the future decreases. The theory is illustrated through an application to vehicle deployment.
Computational Results of Multiserver Bulk-Arrival Queues with Constant Service Time MX/D/c
Authors: Chaudhry M. L. , Templeton J. G. C. , Medhi J.
Published: November 2008

We present an algorithm for numerically finding the limiting distribution of the number in the system for the bulk-arrival, multiserver queueing system MX/D/c. Sample numerical results and graphs of various quantities of interest are also presented. In all cases, the proposed method is computationally efficient, accurate and reliable for both high and low values of the model parameters. The procedure is adaptable to other queueing models in discrete and continuous time, to problems in inventory control, the theory of dams, etc. Exact results found here will also be found useful by people dealing with inequalities, bounds, and approximations.
On the Additional Delay in an M/G/1 Queue with Generalized Vacations and Exhaustive Service
Authors: Leung Kin K.
Published: November 2008

We analyze an M/G/1 queue with generalized vacations and exhaustive service. This system has been shown to possess a stochastic decomposition property. That is, the customer waiting time in this system is distributed as the sum of the waiting time in a regular M/G/1 queue with no vacations and the additional delay due to vacations. In this paper, a general formula for the additional delay is derived for a wide class of vacation policies. The formula is also extended to cases with multiple types of vacations. Using these new formulas, existing results for certain vacation models as well as head-of-line priority queues are easily rederived and unified. More importantly, they enable us to obtain the waiting times for many complex vacation policies, which would otherwise be difficult to analyze. These new results are also applicable to other related queueing models, if they conform with the basic model considered in this paper.
An Approach to Analyzing the Behavior of Some Queueing Networks
Authors: Tay Y. C.
Published: November 2008

Several researchers have reported difficulties in analyzing the behavior of single queues and networks of queues. This is so even in the case of closed product-form networks, for which an exact solution and efficient solution algorithms are known. The difficulty arises because the exact solution could not, by itself, be used for such analysis as proving properties of the network, relating performance measures to one another, and characterizing some interesting behavior. This paper proposes an approach to surmounting such difficulties. The idea is to analyze an approximate solution based on Schweitzer's approximation, and interpret the results as approximate relationships among the exact performance measures. This approach is applied to three problems concerning the interaction among job classes, the mean arrival and variance of queue length, and thrashing. The reliability of the approach is tested by applying it to an optimal routing problem, for which the exact solution is known. The results are illustrated with problems drawn from computer systems.
Scheduling Networks of Queues: Heavy Traffic Analysis of a Multistation Network with Controllable Inputs
Authors: Wein Lawrence M.
Published: November 2008

Motivated by a factory scheduling problem, we consider the problem of input control (subject to a specified input mix) and priority sequencing in a multistation, multiclass queueing network with general service time distributions and a general routing structure. The objective is to minimize the long-run expected average number of customers in the system subject to a constraint on the long-run expected average output rate. Under balanced heavy loading conditions, this scheduling problem can be approximated by a control problem involving Brownian motion. Linear programming is used to reduce the workload formulation of this control problem to a constrained singular control problem for a multidimensional Brownian motion. The finite difference approximation method is then used to find a linear programming solution to the latter problem. The solution is interpreted in terms of the original queueing system to obtain an effective scheduling policy. The priority sequencing policy is based on dynamic reduced costs from a linear program, and the workload regulating input policy releases a customer into the system whenever the workload process enters a particular region. An example is provided that illustrates the procedure and demonstrates its effectiveness.
A Note on Socially Optimal R&D Programs and Their Inducement
Authors: Posner M. J. M. , Zuckerman Dror
Published: November 2008

This paper considers optimal public policies regarding R&D programs in a random environment. For a stochastic R&D decision model without rivalry, we investigate and derive the privately and the socially optimal policies. The study focuses on the socially optimal R&D program and its inducement by governmental incentives. The appropriate instruments that should be employed in supporting R&D projects are examined. Our proposed R&D model provides a theoretical economic justification for public intervention in support of private R&D activities. Furthermore, some of the results shed light on practical issues in designing a functional and efficient R&D project support system.
Dynamic Scheduling of a Multiclass Make-to-Stock Queue
Authors: Wein Lawrence M.
Published: November 2008

Motivated by make-to-stock production systems, we consider a scheduling problem for a single server queue that can process a variety of different job classes. After jobs are processed, they enter a finished goods inventory that services customer demand. The scheduling problem is to dynamically decide which job class, if any, to serve next in order to minimize the long-run expected average cost incurred per unit of time, which includes linear costs (which may differ by class) for backordering and holding finished goods inventory. Under the heavy traffic condition that the server must be busy the great majority of the time in order to satisfy customer demand, the scheduling problem is approximated by a dynamic control problem involving Brownian motion. The Brownian control problem is solved, and its solution is interpreted in terms of the queueing system to obtain a scheduling policy. A simulation experiment is performed that demonstrates the policy's effectiveness.
The Cyclic Lot Scheduling Problem with Sequence-Dependent Setups
Authors: Dobson Gregory
Published: November 2008

In this paper, we formulate the cyclic lot scheduling problem on a single facility with sequence-dependent setup costs and times and provide a heuristic solution procedure. A Lagrangian relaxation of the formulation leads to a partial separation of the embedded lot sizing and traveling salesman problems. The relaxation results in a new combinatorial problem related to the minimum spanning tree problem. The information about frequency of production, gained from the solution to this relaxation, is used to find heuristic solutions for the entire problem. Computational work on randomly generated problems shows that the problem becomes more difficult as the diversity in the sequence-dependent parameters increases.
On the Effect of Demand Randomness on Inventories and Costs
Authors: Gerchak Yigal , Mossman David
Published: November 2008

We explore analytically cardinal effects of the extent of demand randomness on optimal inventory levels and the associated expected costs. To model changes in demand randomness, we make extensive use of a mean-preserving transformation commonly used in probabilistic microeconomics, as well as the notion of risk-pooling (aggregating independent demands). For the single period (news vendor) model, the order quantity and associated costs are shown to depend on the randomness parameter in a simple and highly interpretable manner. We show by a simple example that in some situations risk pooling might neither reduce inventories, nor move them closer to the mean or median demand. The managerial relevance of such analyses is discussed.
A Taxonomy and Research Overview of Perishable-Asset Revenue Management: Yield Management, Overbooking, and Pricing
Authors: Weatherford Lawrence R. , Bodily Samuel E.
Published: November 2008

This paper proposes the term perishable-asset revenue management to denote the field that combines the areas of yield management, overbooking, and pricing for perishable assets. After summarizing the characteristics common to problems in this field, the paper discusses the objectives and constraints faced by decision makers. Then it offers a comprehensive taxonomy with 14 different elements and reviews the research that has been done related to each element. Finally, it suggests some important areas of future research that can help bridge the gap between theory and application.
A Model for Making Project Funding Decisions at the National Cancer Institute
Authors: Hall Nicholas G. , Hershey John C. , Kessler Larry G. , Stotts R. Craig
Published: November 2008

This paper describes the development of a model for making project funding decisions at The National Cancer Institute (NCI). The American Stop Smoking Intervention Study (ASSIST) is a multiple-year, multiple-site demonstration project, aimed at reducing smoking prevalence. The initial request for ASSIST proposals was answered by about twice as many states as could be funded. Scientific peer review of the proposals was the primary criterion used for funding decisions. However, a modified Delphi process made explicit several criteria of secondary importance. A structured questionnaire identified the relative importance of these secondary criteria, some of which we incorporated into a composite preference function. We modeled the proposal funding decision as a zero-one program, and adjusted the preference function and available budget parametrically to generate many suitable outcomes. The actual funding decision, identified by our model, offers significant advantages over manually generated solutions found by experts at NCI.
Large Population Approximations of a General Stochastic Traffic Assignment Model
Authors: Davis Gary A. , Nihan Nancy L.
Published: November 2008

Recent interest in stochastic traffic assignment models has been motivated by a need to determine the stationary probability distribution of a network's traffic volumes and by the possibility of using time-series of traffic counts to fit and test travel demand models. Because of the way traffic volumes are generated as the sum of path flows from different origin-destination pairs, and because of the nonlinear nature of the process relating traffic conditions to traveler route selection, most plausible assignment models tend to be intractable. In this paper, we first pose a general stochastic assignment model that includes as special cases most models which have appeared in the literature, and then verify that the probability distributions of an equivalent Markovian model converge to a stationary distribution. We next verify that as the number of individual travelers becomes large, the general model can be approximated by the sum of a nonlinear deterministic process and a time-varying linear Gaussian process. The stationary distribution of this approximation is readily characterized, and the approximation also provides a means for employing linear system methods to estimate model parameters from a set of observed traffic counts. For the case where the route choice probabilities are given by the multinomial logit function, computationally feasible procedures for implementing the approximate model exist.
Cost-Based Scheduling of Workers and Equipment in a Fabrication and Assembly Shop
Authors: Faaland Bruce , Schmitt Tom
Published: November 2008

Many manufacturing firms that use Material Requirements Planning (MRP) cannot deliver products on schedule and within budget. Faced with bewildering bottlenecks, erratic process flows, and unrealistic due dates, they are unable to develop accurate schedules for their raw material acquisitions, workforce, and equipment. Their MRP plans must be translated into a workable schedule, one which determines when individual tasks will be performed by workers at work centers. There is a clear need for such an enhancement to MRP, a means to operate on detailed task data, yet capable of producing a schedule that directly relates to the MRP plan, the master production schedule, and the resource plan. We describe a method for determining feasible and cost-effective schedules for both labor and machines in a job shop. The method first sequences tasks at resources and then minimizes overall earliness and lateness cost by solving a series of maximum flow problems. By using the model as an enhancement to a company's MRP system, we simulated the cost effects of redeploying its workforce. Although the model was not used for real-time scheduling, it served a strategic role in workforce expansion and deployment decisions.
Scheduling Medical Residents to Rotations: Solving the Large-Scale Multiperiod Staff Assignment Problem
Authors: Franz Lori S. , Miller Janis L.
Published: November 2008

The resident scheduling problem is a specific case of the multiperiod staff assignment problem where individuals are assigned to a variety of tasks over multiple time periods. As in many staffing and training situations, numerous limitations and requirements may be placed on those assignments. This paper presents a procedure for addressing two major problems inherent in the determination of a solution to this type of problem: infeasibilities that naturally occur in the scheduling environment but are obscured by complexity; and the intractable nature of large-scale models with this structure. The procedure developed describes a systematic approach that allows decision makers to resolve system-inherent infeasibilities, and a heuristic based on rounding to develop good feasible solutions to the model. The procedure is illustrated via a case example of resident assignments for teaching and training modules in a university affiliated teaching hospital.
Structuring Conditional Relationships in Influence Diagrams
Authors: Smith James E. , Holtzman Samuel , Matheson James E.
Published: November 2008

An influence diagram is a graphical representation of a decision problem that is at once a formal description of a decision problem that can be treated by computers and a representation that is easily understood by decision makers who may be unskilled in the art of complex probabilistic modeling. The power of an influence diagram, both as an analysis tool and a communication tool, lies in its ability to concisely summarize the structure of a decision problem. However, when confronted with highly asymmetric problems in which particular acts or events lead to very different possibilities, many analysts prefer decision trees to influence diagrams. In this paper, we extend the definition of an influence diagram by introducing a new representation for its conditional probability distributions. This extended influence diagram representation, combining elements of the decision tree and influence diagram representations, allows one to clearly and efficiently represent asymmetric decision problems and provides an attractive alternative to both the decision tree and conventional influence diagram representations.
A Model for Allocating Budgets in a Closed System Which Simultaneously Computes DRG Allocation Weights
Authors: Woodbury Max A. , Manton Kenneth G. , Vertrees James C.
Published: November 2008

This paper presents a quadratic programming model for allocating a global budget to individual hospitals. In the model, allocation weights are estimated for Diagnosis Related Groups (DRGs) which reflect the average historical costs of treating an additional case in each of nine DRG systems. The model is illustrated using data from the Department of Defense (DoD). Allocated budgets and DoD specific DRG marginal cost weights are estimated using information on three factors; the facility designated functions in the military health care system; hospital output; and sets of price structures used in other systems. The model's weights are used to allocate the DoD's global budget to its treatment facilities under constraints. The model minimizes the difference (in a least squares sense) between the facilities' current budgets and their computed budgets, while constraints are designed to produce budgets representing differences in the type and volume of patients and to preserve certain specialized institutional capabilities.
Efficient, Effective Lot Sizing for Multistage Production Systems
Authors: Roundy Robin O.
Published: November 2008

We consider a multistage, multiproduct production/inventory system in discrete time. When an order is placed for a component it is instantly delivered, and the required amounts of the components consumed in producing the given component are simultaneously withdrawn from their respective inventories. External demand occurs for a single component. We assume that the external demand for the component is nonconstant, deterministic, and must be met without backlogging. We propose two new cluster-based heuristics for this problem. We will show that the first of these heuristics has a worst-case relative cost that is between 1.44 and 2, and the second of these heuristics has a worst-case relative cost of 2. Computational tests indicate that, on the average, these heuristics are within 0.7% and 1.3% of optimal, respectively, and that their performance is very insensitive to the size of the system and to other input parameters.
New Approximations for the Event Count Distribution for Superimposed Renewal Processes at the Time Origin with Application to the Reliability of New Series Systems
Authors: Blumenthal Saul
Published: November 2008

When n independent identical renewal processes are superimposed, the number of events in (0, s) is approximately Poisson distributed for large n. For small to moderate n, this approximation is inaccurate. If no component process has more than one event in (0, s), the probability of exactly r events for the superimposed process is given by a binomial-like expression where the p and q do not sum to one. Several approximations have been derived from this observation and compared to the exact probability for small n, when the underlying distribution of time between events is gamma. One of these binomial approximations gives excellent results for small n. The following application is discussed. When k new series systems, each consisting of m identical components, are tested for time s and failed components are replaced upon failure, a superimposed renewal process results. To design an acceptance sampling scheme for new series systems using exact probability computations is cumbersome. The Poisson approximation is convenient, but may give misleading estimates of the O.C. curve for small n. The new binomial approximation is a compromise: It is easier to use for test design than the exact computation and more accurate than the simpler Poisson approximation.
Suboptimal Policies, with Bounds, for Parameter Adaptive Decision Processes
Authors: Lovejoy William S.
Published: November 2008

A parameter adaptive decision process is a sequential decision process where some parameter or parameter set impacting the rewards and/or transitions of the process is not known with certainty. Signals from the performance of the system can be processed by the decision maker as time progresses, yielding information regarding which parameter set is operative. Active learning is an essential feature of these processes, and the decision maker must choose actions that simultaneously guide the system in a preferred direction, as well as yield information that can be used to better prescribe future actions. If the operative parameter set is known with certainty, the parameter adaptive problem reduces to a conventional stochastic dynamic program, which is presumed solvable. Previous authors have shown how to use these solutions to generate suboptimal policies with performance bounds for the parameter adaptive problem. Here it is shown that some desirable characteristics of those bounds are shared by a larger class of functions than those generated from fully observed problems, and that this generalization allows for iterative tightening of the bounds in a manner that preserves those attributes. An example inventory stocking problem demonstrates the technique.
Worldwide Nuclear Coalition Games: A Valuation of Strategic Offensive and Defensive Forces
Authors: Bracken Jerome , Shubik Martin
Published: November 2008

Methods are proposed for the valuation of strategic offensive and defensive force structures, with emphasis on the consideration of incentives for the formation of coalitions. Coalitions consist of subsets of the nuclear weapons states, together with the nonnuclear weapons states taken as components of the total value target inventory. The basic approach is to formulate and solve two worldwide nuclear coalition games. In the first game, the first striking coalition is retaliated against by the surviving weapons of the second striking coalition, minimizing the objective function of the first striking coalition. In the second game, the surviving weapons of the second striking coalition are used to maximize its own objective function. The objective function in both models is the percent of surviving value. The games differ substantially. Computational results are presented for all possible coalitions of nuclear weapons states and neutrals. Offensive weapons, defensive weapons, and value target data bases are varied. Results are very sensitive to coalition composition, the number of value targets, and the number of offensive and defensive weapons.
A Randomization Rule for Selecting Forecasts
Authors: Foster Dean P. , Vohra Rakesh V.
Published: November 2008

We propose a randomized strategy for selecting/combining forecasts that is better than the forecasts used to produce it in a sense made precise in this paper. Unlike traditional methods this approach requires that no assumptions be made about the distribution of the event being forecasted or the error distribution and stationarity of the constituent forecasts. The method is simple and easy to implement.
A Family of Search Directions for Karmarkar's Algorithm
Authors: Anstreicher Kurt M. , Watteyne Patrick
Published: November 2008

We consider a new family of search directions for the standard form variant of Karmarkar's projective linear programming algorithm. The family includes the usual projected gradient direction, and also a direction first proposed by Mike Todd. We prove that any choice from the family preserves the algorithm's polynomial-time complexity. We then examine the computational behavior of the algorithm using different choices of directions. Although the theoretical complexity is the same for the different directions, in practice we find wide variations in algorithm performance. One particular choice consistently requires about 20% fewer iterations than the usual direction, while another requires a number of iterations which grows rapidly with problem size. Our computational results also demonstrate that a small number of monotonic steps on early iterations may considerably improve the performance of the algorithm.
Local Drug Markets' Response to Focused Police Enforcement
Authors: Caulkins Jonathan P.
Published: November 2008

This paper introduces a model that describes how local drug markets might respond to intensive local enforcement operations known as crackdowns. The model supports the intuition of some drug policy analysts and makes concrete suggestions for how crackdowns should be managed.
Cyclic Transfer Algorithm for Multivehicle Routing and Scheduling Problems
Authors: Thompson Paul M. , Psaraftis Harilaos N.
Published: November 2008

This paper investigates the application of a new class of neighborhood search algorithms—cyclic transfers—to multivehicle routing and scheduling problems. These algorithms exploit the two-faceted decision structure inherent to this problem class: First, assigning demands to vehicles and, second, routing each vehicle through its assigned demand stops. We describe the application of cyclic transfers to vehicle routing and scheduling problems. Then we determine the worst-case performance of these algorithms for several classes of vehicle routing and scheduling problems. Next, we develop computationally efficient methods for finding negative cost cyclic transfers. Finally, we present computational results for three diverse vehicle routing and scheduling problems, which collectively incorporate a variety of constraint and objective function structures. Our results show that cyclic transfer methods are either comparable to or better than the best published heuristic algorithms for several complex and important vehicle routing and scheduling problems. Most importantly, they represent a novel approach to solution improvement which holds promise in many vehicle routing and scheduling problem domains.
Stochastic Analysis of Cyclic Schedules
Authors: Bowman R. A. , Muckstadt J. A.
Published: November 2008

A cyclic schedule is a sequence of tasks on a set of machines that is repeated indefinitely. We model cyclic schedules as Markov chains and use ergodic theory to analyze and improve the performance of cyclic schedules in environments with machine breakdowns, yield losses, and other sources of variability. The concept of cyclic task criticality is developed as a natural extension of task criticalities in PERT networks. We show that cyclic task criticalities can and should be used to guide the management of cyclic schedules.
R&D Project Appraisal at the Gas Research Institute: Part II
Authors: Burnett William M. , Silverman Barry G. , Monetta Dominic J.
Published: November 2008

The Project Appraisal Methodology (PAM) was originally developed in 1975 and first run at the Gas Research Institute (GRI) in 1978 to help upper management select portfolios of research and development (R&D) projects to fund. Since that time, GRI has had 132 successful project commercializations and has achieved a success rate of 30% or over twice the documented industry average. GRI attributes its success to several decision making principles founded in management science. PAM is the cornerstone of GRI's R&D decision making process. In particular, GRI's projects are generating benefits for natural gas consumers and suppliers (savings plus sales increases) of $7–15 billion per year on an annual investment of about $1.6 billion and netting almost a 7 to 1 annual rate of return on their investment. Just in 1985–1989 these new technologies contributed to a savings of $70 billion ($78 billion, NPV, 1990$s) in the wellhead price of natural gas in the USA. Additionally, the application of management science at GRI has led to increases in available natural gas supplies (valued at $10–35 billion), a corresponding reduction in dependence on imports, major environmental and safety benefits, and vital changes in the position of the gas industry in the home heating, commercial cooking, and numerous other markets.
Optimal Scheduling of a Flexible-Duration Rest Period for a Work Group
Authors: Bechtold Stephen E. , Thompson Gary M.
Published: November 2008

All previous modeling research involving optimization of performance associated with work-rest cycles has focused upon individual employees working independently. We extend this earlier research by considering the choices of placement for and duration of a single rest period that must be taken simultaneously by all employees in a work group. Assuming linear work-rate decay and recovery functions for individual employees within the group, we show that an appropriate model can be formulated as a mixed-binary, cubic programming problem. We develop an efficient optimal solution procedure with a computational time that appears to be a linear function of the number of employees considered. We report on a preliminary simulation experiment that evaluates the productivity loss that occurs when the rest break policy is determined based on the work characteristics of a randomly selected subset of employees in the work group, and provides an initial exploration of the nature of optimal policy variables. Finally, we offer suggestions for future research.
Two Simple Control Policies for a Multicomponent Maintenance System
Authors: van der Duyn Schouten Frank A. , Vanneste Stephan G.
Published: November 2008

Optimal group maintenance policies for a set of M identical machines subject to stochastic failures are considered. The control of the system is not based on the complete age configuration of all components, nor on the number of failed components only. We compromise between these two extreme cases by introducing four possible states for each component: good, doubtful, preventive maintenance is due, and failed. Two types of control policies are considered, both based on the number of doubtful components at component failure epochs. Starting from a general model with general (but identical) lifetime distributions for the individual components, we introduce an approximate model in which the four possible states are identified with certain age intervals for each individual component. The sojourn times in the good and the doubtful state are supposed to be exponentially distributed. For this resulting approximate model, explicit expressions are derived for various performance measures, like the time to system replacement and the average costs per unit time. By making use of the results obtained for the approximate model several approximations for the performance measures of the original model are presented. Validation of these approximations is performed by simulation.
Implicit Enumeration for the Pure Integer 0/1 Minimax Programming Problem
Authors: Diaby Moustapha
Published: November 2008

We present an implicit enumeration procedure for solving pure integer 0/1 minimax problems which arise in the context of Benders decomposition for mixed integer 0/1 linear programming problems, or in various practical settings such as the location of facilities and assembly line balancing. The procedure is an extension of the additive algorithm of E. Balas for pure integer 0/1 programming problems. We solve minimax problems directly (i.e., as minimax problems, not as mixed integer programming problems). A numerical example is used to illustrate the procedure. Extensions of the basic algorithm are discussed.
Sequential Bottleneck Decomposition: An Approximation Method for Generalized Jackson Networks
Authors: Dai J. G. , Nguyen Viên , Reiman Martin I.
Published: November 2008

In heavy traffic analysis of open queueing networks, processes of interest such as queue lengths and workload levels are generally approximated by a multidimensional reflected Brownian motion (RBM). Decomposition approximations, on the other hand, typically analyze stations in the network separately, treating each as a single queue with adjusted interarrival time distribution. We present a hybrid method for analyzing generalized Jackson networks that employs both decomposition approximation and heavy traffic theory: Stations in the network are partitioned into groups of “bottleneck subnetworks” that may have more than one station; the subnetworks then are analyzed “sequentially” with heavy traffic theory. Using the numerical method of J. G. Dai and J. M. Harrison for computing the stationary distribution of multidimensional RBMs, we compare the performance of this technique to other methods of approximation via some simulation studies. Our results suggest that this hybrid method generally performs better than other approximation techniques, including W. Whitt's QNA and J. M. Harrison and V. Nguyen's QNET.
On the Busy Period of an M/G/1/K Queue
Authors: Takagi Hideaki , Lamaire Richard O.
Published: November 2008

The joint distribution of the length of a busy period and the number of customers served during that busy period in an M/G/1 queue with a finite capacity is expressed as coefficients of a power-series expansion of an explicit function. This new result is related to the previous result by T. J. Harris (1971). An error in his result is found and corrected.
Staging Problem of a Dual Delivery Pick-and-Place Machine in Printed Circuit Card Assembly
Authors: Ahmadi Reza H. , Kouvelis Panagiotis
Published: November 2008

This paper addresses a material staging problem arising from a dual delivery pick-and-place machine that is used for the assembly of printed circuit boards where components are attached using “surface mount technology.” The staging problem of such machines involves allocation of component feeders to its two-feeder carriers along with the corresponding sets of vacuum nozzles to dispense the components. The usual managerial objective for the staging problem is minimization of the total time required to populate the circuit boards, i.e., the pick-and-place machine's cycle time. For the dual delivery pick-and-place machines this implies minimization of the workload imbalance between the two carriers and reduction of the number of vacuum nozzle changes required. In this paper, we develop algorithms to optimally solve the single and multiple product staging problem for the above managerial objectives.