bluuebunny/crossref_metadata_2025 huggingface dataset:
Linear Control of a Markov Production System
Authors: Denardo Eric V. , Tang Christopher S.
Published: November 2008

This paper presents a model of a facility that processes many jobs. Each job requires a sequence of activities. The sequence of activities required by a job is random because each activity ends with a test, and the outcome of that test determines the activity that must be performed next. Evolution from activity to activity is Markovian, i.e., is determined by transition probabilities. A few (e.g., six) different types of job can share this facility, each type having its own transition probabilities between the activities. Each activity takes place in a designated sector. Several activities can share a sector. Each sector has a capacity, and buffers of inventory serve to decouple the sectors. In this paper, we introduce a family of linear control rules that smooth the flow through each sector and regulate the amount of inventory in each buffer. The operating characteristics of each linear control rule are computed. These include the mean and variance of the flow into each sector, the inventory in each buffer, the throughput of the systems, and the cycle time. These operating characteristics are optimized by a convex nonlinear program.
Asymptotic Formulas for Markov Processes with Applications to Simulation
Authors: Whitt Ward
Published: November 2008

The simulation run length required to achieve desired statistical precision for a sample mean in a steady-state stochastic simulation experiment is largely determined by the asymptotic variance of the sample mean and, to a lesser extent, by the second-order asymptotics of the variance and the asymptotic bias. The asymptotic variance, the second-order asymptotics of the variance, and the asymptotic bias of the sample mean of a function of an ergodic Markov process can be expressed in terms of solutions of Poisson's equation, as indicated by positive recurrent potential theory. We review this positive recurrent potential theory, giving special attention to continuous-time Markov chains. We provide explicit formulas for birth-and-death processes and diffusion processes, and recursive computational procedures for skip-free chains. These results can be used to help design simulation experiments after approximating the stochastic process of interest by one of the elementary Markov processes considered here.
Derivative Estimates from Simulation of Continuous-Time Markov Chains
Authors: Glasserman Paul
Published: November 2008

Countable-state, continuous-time Markov chains are often analyzed through simulation when simple analytical expressions are unavailable. Simulation is typically used to estimate costs or performance measures associated with the chain and also characteristics like state probabilities and mean passage times. Here we consider the problem of estimating derivatives of these types of quantities with respect to a parameter of the process. In particular, we consider the case where some or all transition rates depend on a parameter. We derive derivative estimates of the infinitesimal perturbation analysis type for Markov chains satisfying a simple condition, and argue that the condition has significant scope. The unbiasedness of these estimates may be surprising—a “naive” estimator would fail in our setting. What makes our estimates work is a special construction of specially structured parameteric families of Markov chains. In addition to proving unbiasedness, we consider a variance reduction technique and make comparisions with derivative estimates based on likelihood ratios.
Characterization of the Stochastic Median Queue Trajectory in a Plane with Generalized Distances
Authors: Brandeau Margaret L.
Published: November 2008

We characterize the trajectory of the Stochastic Queue Median (SQM) location problem in a planar region with discrete demands and a general Lp travel metric (1 < p < ∞). The location objective is to minimize expected response time to customers (i.e., travel time plus queue delay). We use an ε-perturbed version of the SQM objective function (to account for points of nondifferentiability) to show that for the ε-perturbed problem the optimal SQM location occurs in a region bounded by the point minimizing the first and second moments of service time (s*∣ε and s2*∣ε, respectively); all optimal locations can be characterized by a simple ratio condition relating the derivatives of the first and second moments of service time; and the trajectory as a function of the customer call rate moves monotonically along a path from s*∣ε toward s2*∣ε, then turns and retraces the same path back to s*∣ε. Finally, we establish convergence of the ε-optimal solution to an optimal SQM solution as ε approaches zero, as well as a general condition under which we can solve the SQM problem directly, with no perturbation.
Performance Evaluation of Service Territories
Authors: Agnihothri Saligrama R. , Karmarkar Uday S.
Published: November 2008

Field service support is important for certain products, such as computer systems and copiers, for which service performance has a significant impact on market share. In this paper, the problem of field service operations and its important characteristics are described. Models are developed to assist the field service manager in the evaluation of performance of a given service territory with heterogeneous machines scattered (typically, nonuniformly) over a region, repaired by a traveling serviceman. Given the probability distributions of machine uptimes and repair times, and travel times between machine locations, models are developed to approximate the overall travel time distribution. This is used in existing queueing models to determine the performance measures, such as mean downtime per machine and server utilization. The results of the models are tested by simulation and observed to provide good estimates for the measures of interest. These models are eventually intended to help in making decisions on territory design and staffing levels.
Single Machine Scheduling Problem When the Machine Capacity Varies Stochastically
Authors: Hirayama Tetsuji , Kijima Masaaki
Published: November 2008

We consider single machine scheduling problems when the machine capacity varies stochastically over time. Suppose that R(t) ≥ 0 processing requirements can be processed per unit of time at time t. First, we treat the general “machine capacity” R(t) and then consider the machine breakdown models where R(t) = 0 or 1. Jobs may arrive according to an arbitrary process. We show that simple priority rules are optimal under some assumptions. Specifically, the cμ rule minimizes the expected weighted total number of jobs if the processing requirements are exponentially distributed. The SEPT rule minimizes the expected total number of jobs if the processing requirements of jobs are stochastically ordered. The SERPT rule also minimizes it if the processing requirements form an ICR family.
Forces, Trends, and Opportunities in MS/OR
Authors: Geoffrion Arthur M.
Published: November 2008

The purposes of this paper—a revised and extended version of the Omega Rho Lecture given at the November 1991 ORSA/TIMS Joint National Meeting—are to assess some important aspects of the current MS/OR situation and to draw some conclusions about desirable future emphases. To these ends, it identifies and discusses four forces of historic importance (the microcomputer and communications revolutions, the dispersion of MS/OR in industry, and academia's unbalanced reward structure), three major trends (rapidly disseminating MS/OR tools, declining enrollments of native-born students, and persisting management apathy toward MS/OR), and five outstanding opportunities (ride the computer and communications revolutions, support dispersed practitioners, focus on the service sector, stress embedded applications, and go into the quality business). An underlying theme is that the field will flourish in proportion to how astutely individuals, organizations, professional societies, and universities adapt to the changing realities within which MS/OR lives.
Valuation-Based Systems for Bayesian Decision Analysis
Authors: Shenoy Prakash P.
Published: November 2008

This paper proposes a new method for representing and solving Bayesian decision problems. The representation is called a valuation-based system and has some similarities to influence diagrams. However, unlike influence diagrams which emphasize conditional independence among random variables, valuation-based systems emphasize factorizations of joint probability distributions. Also, whereas influence diagram representation allows only conditional probabilities, valuation-based system representation allows all probabilities. The solution method is a hybrid of local computational methods for the computation of marginals of joint probability distributions and the local computational methods for discrete optimization problems. We briefly compare our representation and solution methods to those of influence diagrams.
The Asymptotic Efficiency of Simulation Estimators
Authors: Glynn Peter W. , Whitt Ward
Published: November 2008

A decision-theoretic framework is proposed for evaluating the efficiency of simulation estimators. The framework includes the cost of obtaining the estimate as well as the cost of acting based on the estimate. The cost of obtaining the estimate and the estimate itself are represented as realizations of jointly distributed stochastic processes. In this context, the efficiency of a simulation estimator based on a given computational budget is defined as the reciprocal of the risk (the overall expected cost). This framework is appealing philosophically, but it is often difficult to apply in practice (e.g., to compare the efficiency of two different estimators) because only rarely can the efficiency associated with a given computational budget be calculated. However, a useful practical framework emerges in a large sample context when we consider the limiting behavior as the computational budget increases. A limit theorem established for this model supports and extends a fairly well known efficiency principle, proposed by J. M. Hammersley and D. C. Handscomb: “The efficiency of a Monte Carlo process may be taken as inversely proportional to the product of the sampling variance and the amount of labour expended in obtaining this estimate.”
Push and Pull Production Systems: Issues and Comparisons
Authors: Spearman Mark L. , Zazanis Michael A.
Published: November 2008

Concerns about American manufacturing competitiveness compel new interest in alternative production control strategies. In this paper, we examine the behavior of push and pull production systems in an attempt to explain the apparent superior performance of pull systems. We consider three conjectures: that pull systems have less congestion; that pull systems are inherently easier to control; and that the benefits of a pull environment owe more to the fact that WIP is bounded than to the practice of “pulling” everywhere. We examine these conjectures for analytically tractable models. In doing so, we not only find supporting evidence for our surmises but also identify a control strategy that has push and pull characteristics and appears to outperform both pure push and pure pull systems. This hybrid system also appears to be more general in its applicability than traditional pull systems such as Kanban.
Random Yield, Rework and Scrap in a Multistage Batch Manufacturing Environment
Authors: Wein Anne Spence
Published: November 2008

This study is motivated by a make-to-order marketing environment where an order is met from a single production lot size. The objective of the study is to endogenize rework and scrap decisions in a multistage production process. A Markov decision process model is developed and solved using dynamic programming techniques. The model assumes that demand is given, and material, processing and rework costs are linear in the production lot size. Modeling random yield at each stage of the production process is of key interest. The solution to the problem is characterized and the sensitivity of the solution to the parameters of the model is examined.
Single Machine Scheduling to Minimize Total Late Work
Authors: Potts C. N. , Van Wassenhove L. N.
Published: November 2008

In the problem of scheduling a single machine to minimize total late work, there are n jobs to be processed for which each has an integer processing time and a due date. The objective is to minimize the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. For the preemptive total late work problem, an O(n log n) algorithm is derived. The nonpreemptive total late work problem is shown to be NP-hard, although efficient algorithms are derived for the special cases in which all processing times are equal and all due dates are equal. A pseudopolynomial dynamic programming algorithm is presented for the general nonpreemptive total late work problem; it requires O(nUB) time, where UB is any upper bound on the total late work. Computational results for problems with up to 10,000 jobs are given.
A Single Machine Model for Determination of Optimal Due Dates and Sequence
Authors: Chand Suresh , Chhajed Dilip
Published: November 2008

The problem of simultaneous determination of optimal due dates and optimal sequence for N-job single machine problem with multiple due dates is considered in this paper. The penalty for a job is assumed to be a linear function of the due date and the earliness/tardiness for the job. The objective is to minimize the total penalty for all jobs. An efficient optimal algorithm to solve the problem is developed and several results are provided.
Deducing Queueing from Transactional Data: The Queue Inference Engine, Revisited
Authors: Bertsimas Dimitris J. , Servi L. D.
Published: November 2008

R. Larson proposed a method to statistically infer the expected transient queue length during a busy period in O(n5) solely from the n starting and stopping times of each customer's service during the busy period and assuming the arrival distribution is Poisson. We develop a new O(n3) algorithm which uses these data to deduce transient queue lengths as well as the waiting times of each customer in the busy period. We also develop an O(n) on-line algorithm to dynamically update the current estimates for queue lengths after each departure. Moreover, we generalize our algorithms for the case of a time-varying Poisson process and also for the case of i.i.d. interarrival times with an arbitrary distribution. We report computational results that exhibit the speed and accuracy of our algorithms.
A Fluid Model for Systems with Random Disruptions
Authors: Chen Hong , Yao David D.
Published: November 2008

Motivated by modeling manufacturing systems in which job arrivals and processing times are essentially deterministic, but the environment is typically random, we develop a fluid model with random disruptions. The quality and relevance of such a model are supported by the following facts which we establish in this study. The fluid model is more susceptible to analysis: Its (dynamical) sample paths are continuous and piecewise linear, and its stationary behavior can be studied using standard approaches in random walk; the model is a limit of corresponding queueing systems with random disruptions that are usually difficult to analyze; there exist pathwise bounds between the fluid model and D/D/1 queues with random disruptions, and the bounds are simple and tight.
Optimal Scheduling of Exponential Tasks with In-Tree Precedence Constraints on Two Parallel Processors Subject to Failure and Repair
Authors: Kulkarni V. G. , Chimento P. F.
Published: November 2008

In this paper, we consider the problem of scheduling n tasks on two processors. The processing times of the n tasks are i.i.d. exponential random variables. The precedence constraints among the n tasks form an in-tree. The two processors are subject to failure and repair in a completely arbitrary manner, but are independent of the task processing times. We introduce the concept of stochastic partial ordering on random in-trees and show that among all policies, the highest level first (HLF) policy produces the smallest in-tree of unfinished tasks under the stochastic partial ordering. This implies that the HLF policy stochastically minimizes the makespan even when the two processors are subject to failures and repairs. As a special case, we also show that the HLF policy minimizes the dynamic failure probability when the processors are subject to failure, but no repairs can be done.
Chronological Influences of the Variance of Electric Power Production Costs
Authors: Ryan Sarah M. , Mazumdar Mainak
Published: November 2008

The cost of producing electric power at a given time depends on the demand and the set of generating units that are available. We present a Markovian model of the generation system together with a deterministic, time-varying demand function that yields a stochastic integral for the production cost over a time interval. The variance of this integral may be computed exactly by enumerating states. An expression for the integrand is developed in which the deterministic time variation is decoupled from the stochastic variation. This expression is amenable to an asymptotic approximation that reduces the computation. When system state transition rates are high, little accuracy is lost. The exact and approximate results are compared for several parameter values in a small example system.
Allocation of Waiting Time by Trading in Position on a G/M/S Queue
Authors: Rosenblum Daniel M.
Published: November 2008

Customers on an S-server queue with exponential service times face losses due to waiting that are proportional to waiting time, with different loss rates. Customers are otherwise identical. They have complete knowledge of each other's loss rates. Instead of bribing a queue manager for priority assignment, they buy and sell queue positions among themselves. It is shown that the resulting market in queue positions optimally allocates waiting time. The transactions that can occur are completely characterized, including balking and reneging rules.
A Simple Relationship Between Light and Heavy Traffic Limits
Authors: Simon Burton
Published: November 2008

Let ρ be the traffic intensity of an open queueing system, and let f(ρ), 0 ≤ ρ < 1 be a function, such as an average queue length or sojourn time. A relationship between the light and heavy traffic limits of f is found that is asymptotically exact for high-order light traffic limits (derivatives at ρ = 0). This simple but unexpected result provides a natural method for approximating f based on partial information. The approximation it provides turns out to be identical to the “canonical” interpolation approximation based on the same partial information. Relationships are then derived that correspond to noncanonical interpolation approximations. These relationships may he useful for gauging the accuracy of interpolation approximations.
On Wolff's Pasta Martingale
Authors: Yao David D.
Published: November 2008

In establishing the seminal result PASTA (Poisson Arrivals See Time Averages), R. Wolff (1982) constructed a martingale, and demonstrated that PASTA was a consequence of a strong law of large numbers of this martingale. Here we establish a central limit theorem for the PASTA martingale, and characterize its asymptotic normality. The result can be used to construct confidence intervals for estimators of the difference between the arrival (event) and time averages.
Measuring Performance of Integrated Air Defense Networks Using Stochastic Networks
Authors: Bailey Michael P.
Published: November 2008

A model reflecting the evolution of an engagement between an integrated air defense system (IADS) and a penetrating strike group is presented. The engagement is modeled as an optimization problem on a network with stochastic arc lengths. We produce the distribution of our measure of effectiveness, as well as calculating the importance of each IADS agent to the performance of the overall system. We demonstrate the effectiveness of several jamming plans against the network.
Tight Bounds for Stochastic Convex Programs
Authors: Edirisinghe N. C. P. , Ziemba W. T.
Published: November 2008

Variable and row aggregation as a technique of simplifying a mathematical program is utilized to develop bounds for two-stage stochastic convex programs with random right-hand sides. If one is able to utilize the problem structure along with only first moment information, a tighter bound than the usual mean model bound (based on Jensen's inequality) may be obtained. Moreover, it is possible to construct examples for which the mean model bound will be arbitrarily poor. Consequently, one can tighten Jensen's bound for stochastic programs when the distribution has a compact support. This bound may be improved further by partitioning the support using conditional first moments. With regard to first moment upper bounds, the Gassmann-Ziemba inequality is used for the stochastic convex program to seek a model which can be solved using standard convex programming techniques. Moreover, it allows one to easily construct upper bounds using the solution of the lower bounding problem. Finally, the results are extended to multistage stochastic convex programming problems.
A Lagrangian Relaxation Technique for Optimizing Interconnection of Local Area Networks
Authors: Fetterolf Peter C. , Anandalingam G.
Published: November 2008

This paper addresses the problem of interconnecting a group of Local Area Networks (LANs) with bridges. The network designer would like to minimize the cost of connecting the LANs while maintaining acceptable traffic intensity levels on each of the LANs and the bridges. This problem belongs to the class of fixed charge network flow problems. A Lagrangian relaxation algorithm is proposed that incorporates two sets of constraints into the objective function. The relaxed problem has a special structure and can be solved as a minimum spanning tree problem and a set of shortest path problems. The subgradient algorithm is then used to maximize the Lagrangian dual. A Lagrangian heuristic algorithm is also proposed to find good primal feasible solutions. For problems with five LANs, the heuristic solutions are normally within 1% of the optimum. For larger problems the heuristic solutions are close to the lower bounds generated by the Lagrangian relaxation algorithm. This suggests that the quality of the heuristic solutions does not deteriorate as the dimension of the problem grows.
A Multiperiod Capacity Planning Model for Backbone Computer Communication Networks
Authors: Dutta Amitava , Lim Jay-Ick
Published: November 2008

The cost of transmission capacity constitutes a significant portion of the total investment cost of a backbone computer communications network. In this paper, we address the problem of deciding where, when and how much transmission capacity should be installed, over a multiperiod horizon, to meet increasing traffic requirements at minimum total discounted cost, while maintaining acceptable performance levels. The model allows traffic among existing nodes to increase, new nodes to be added to the network, and its topology to change, over time. It is formulated as an integer programming problem, and a Lagrangian relaxation based solution method is proposed. Capacity and routing decisions are made jointly over time in our multiperiod model. Furthermore, our method automatically provides numerical verification of solution quality through the Lagrangian lower bound. Computational experiments with several networks show that the method yields verifiably good solutions to this combinatorially explosive problem.
Batching and Scheduling Jobs on Batch and Discrete Processors
Authors: Ahmadi Javad H. , Ahmadi Reza H. , Dasu Sriram , Tang Christopher S.
Published: November 2008

We consider a situation in which the manufacturing system is equipped with batch and discrete processors. Each batch processor can process a batch (limited number) of jobs simultaneously. Once the process begins, no job can be released from the batch processor until the entire batch is processed. In this paper, we analyze a class of two-machine batching and scheduling problems in which the batch processor plays an important role. Specifically, we consider two performance measures: the makespan and the sum of job completion times. We analyze the complexity of this class of problems, present polynomial procedures for some problems, propose a heuristic, and establish an upper bound on the worst case performance ratio of the heuristic for the NP-complete problem. In addition, we extend our analysis to the case of multiple families and to the case of three-machine batching.
Part Dispatch in Random Yield Multistage Flexible Test Systems for Printed Circuit Boards
Authors: Akella Ram , Rajagopalan S. , Singh Medini R.
Published: November 2008

This paper concerns dynamic part dispatch decisions in electronic test systems with random yield. A discrete time, multiproduct, miltistage production system is used as a model for the test system with the objective to minimize the sum of inventory holding, backlogging, and overtime costs over a finite horizon. Exact results for such systems have been limited to either single-stage, multiple time period, or multistage, single time period problems with a single product. Here we develop two approximate policies: the linear decision rule, and the myopic resource allocation. The effectiveness of the two policies is evaluated through simulation under different operating conditions representative of those encountered in IBM and Tandem Computer facilities. The extensive computational study clearly demonstrates the overall superiority of the linear decision rule.
On the Distance Constrained Vehicle Routing Problem
Authors: Li Chung-Lun , Simchi-Levi David , Desrochers Martin
Published: November 2008

We analyze the vehicle routing problem with constraints on the total distance traveled by each vehicle. Two objective functions are considered: minimize the total distance traveled by vehicles and minimize the number of vehicles used. We demonstrate a close relationship between the optimal solutions for the two objective functions and perform a worst case analysis for a class of heuristics. We present a heuristic that provides a good worst case result when the number of vehicles used is relatively small.
Optimality of Myopic Policies in Disposing Excess Inventory
Authors: Rosenfield Donald B.
Published: November 2008

In a recent article, the author presented results for the optimum levels of inventory to dispose and keep in an excess inventory situation. This note shows that these levels do not change when additional disposal opportunities are presented in the future. In this sense, the optimal policy is myopic in that the decision can be made without any examination of future decisions.
An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems
Authors: Federgruen Awi , Zheng Yu-Sheng
Published: November 2008

The reorder point/reorder quantity policies, also referred to as (r, Q) policies, are widely used in industry and extensively studied in the literature. However, for a period of almost 30 years there has been no efficient algorithm for computing optimal control parameters for such policies. In this paper, we present a surprisingly simple and efficient algorithm for the determination of an optimal (r*, Q*) policy. The computational complexity of the algorithm is linear in Q*. For the most prevalent case of linear holding, backlogging and stockout penalty costs (in addition to fixed order costs), the algorithm requires at most (6r* + 13Q*) elementary operations (additions, comparisons and multiplications), and hence, no more than 13 times the amount of work required to do a single evaluation of the long-run average cost function in the point (r*, Q*).
The Upper Risk of an Inspection Agreement
Authors: Ruckle William H.
Published: November 2008

An inspection agreement, contained within a treaty proposal, determines a two-person, zero sum game which we call the implicit game. The value of the implicit game, called the upper risk, is an important parameter of the agreement. The upper risk and other parameters in the solution of the implicit game are useful for evaluating the proposal and comparing it to other proposals. The purpose of this paper is to define the implicit game which arises from an inspection arrangement, define the upper risk and other parameters, and then to illustrate the theory with examples, several of which originated in the analysis of actual inspection proposals.
Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods
Authors: Bixby Robert E. , Gregory John W. , Lustig Irvin J. , Marsten Roy E. , Shanno David F.
Published: November 2008

Experience with solving a 12.753.313 variable linear program is described. This problem is the linear programming relaxation of a set partitioning problem arising from an airline crew scheduling application. A scheme is described that requires successive solutions of small subproblems, yielding a procedure that has little growth in solution time in terms of the number of variables. Experience using the simplex method as implemented in CPLEX, an interior point method as implemented in OBI, and a hybrid interior point/simplex approach is reported. The resulting procedure illustrates the power of an interior point/simplex combination for solving very large-scale linear programs.
An Investigation of Finite-Sample Behavior of Confidence Interval Estimators
Authors: Sargent Robert S. , Kang Keebom , Goldsman David
Published: November 2008

We investigate the small-sample behavior and convergence properties of confidence interval estimators (CIEs) for the mean of a stationary discrete process. We consider CIEs arising from nonoverlapping batch means, overlapping batch means, and standardized time series, all of which are commonly used in discrete-event simulation. The performance measures of interest are the coverage probability, and the expected value and variance of the half-length. We use empirical and analytical methods to make detailed comparisons regarding the behavior of the CIEs for a variety of stochastic processes. All the CIEs under study are asymptotically valid; however, they are usually invalid for small sample sizes. We find that for small samples, the bias of the variance parameter estimator figures significantly in CIE coverage performance—the less bias the better. A secondary role is played by the marginal distribution of the stationary process. We also point out that some CIEs require fewer observations before manifesting the properties for CIE validity.
An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
Authors: Hochbaum Dorit S.
Published: November 2008

This paper describes a randomized algorithm for solving the maximum-flow maximum-cut problem on connected random graphs. The algorithm is very fast—it does not look up most vertices in the graph. Another feature of this algorithm is that it almost surely provides, along with an optimal solution, a proof of optimality of the solution. In addition, the algorithm's solution is, by construction, a collection of vertex-disjoint paths which is maximum. Under a restriction on the graph's density, an optimal solution to the NP-hard communication problem is provided as well, that is, finding a maximum collection of vertex-disjoint paths between sender-receiver pairs of terminals. The algorithm lends itself to a sublogarithmic parallel and distributed implementation. Its effectiveness is demonstrated via extensive empirical study.
Customer Service in Pull Production Systems
Authors: Spearman Mark L.
Published: November 2008

In this paper, we consider the issue of customer service in pull production systems. We first discuss the meaning of customer service in a pull system and contrast it to push systems. We also discuss both pure and hybrid pull systems that are found in the literature. We then investigate the effects of changing inventory levels and processing time characteristics on customer service in a pure kanban system. Finally, we show that a hybrid system known as CONWIP not only has better service than a pure kanban system, but also solves certain implementation problems.
Production Batching with Machine Breakdowns and Safety Stocks
Authors: Groenevelt Harry , Pintelon Liliane , Seidmann Abraham
Published: November 2008

We study the problem of selecting the economic lot size for an unreliable manufacturing facility with a constant failure rate and general randomly distributed repair times. Safety stocks must be used to meet the managerially prescribed service level (the fraction of lost sales) because these stochastic interventions reduce the effective production capacity. We develop bounds on the range of feasible service levels and investigate the impact of several system parameters on this range. We introduce an easily implementable production control policy (but do not establish the optimality of its structure) and prove that under this policy the safety stock dynamics can be characterized fully by a renewal process analogous to the workload process of a special single server queueing system. This analogy is exploited in deriving exact and approximate expressions for the safety stock holding costs. Several operational insights are revealed by experimenting with the models developed here. We show how the results can be incorporated in a broader management framework for evaluating resource allocation decisions aimed at reducing the failure rate of the machines. A clear tradeoff is shown to exist between the overall investment in increasing the maintenance level and the resulting savings in safety stocks and repair costs.
Minimizing Job Idleness in Deadline Constrained Environments
Authors: Ahmadi Reza H. , Bagchi Uttarayan
Published: November 2008

The paper presents a formulation of an n-job, m-machine flowshop problem whose objective is to determine a processing sequence of jobs that minimizes total job idleness subject to meeting job deadlines. A mirror image problem is defined with the property that there is a one-to-one correspondence between the feasible schedules of the original problem and the feasible schedules of the mirror image problem. The mirror image problem is a traditional scheduling problem with a regular performance measure, whereas the performance measure in the original problem is not regular. The equivalence of the original problem and its mirror image problem enables us to solve one by solving the other. One special case of the original problem is investigated. It concerns minimization of total job idleness in a 2-machine flowshop. For this NP-hard problem we study permutation schedules under sufficient conditions of feasibility. We present complexity results, dominance properties, bounding criteria, and computational experience with a branch-and-bound procedure.
A Product Design Problem in Semiconductor Manufacturing
Authors: Avram Florin , Wein Lawrence M.
Published: November 2008

We consider the product design problem of allocating the chip sites on a semiconductor wafer to various types of chips. The manufacturing facility sells chips to its customers in sets (a specified number of several different types of chips), and the objective of the facility is to maximize the average production rate of sets. Variability in the wafer fabrication process, in particular random yield, poses a major obstacle in producing sets in a reliable fashion. A stochastic analysis is employed to develop an effective wafer design, to measure the improvement in performance of the multitype wafer over the traditional single-type wafer, and to determine the cumulative production of sets of nondefective chips as a function of the rate at which lots of wafers are released into the facility. The analysis reveals that multitype wafers regularize the production flow of nondefective chips of each type and cause these flows to be correlated positively, both of which help to improve performance. A numerical example is provided that illustrates the analysis and demonstrates the design's effectiveness.
Ordering Policies in an environment of Stochastic Yields and Substitutable Demands
Authors: Bitran G. R. , Dasu S.
Published: November 2008

In this paper, we model production problems where yields are stochastic, demands are substitutable, and several items are jointly produced. We formulate this problem as a profit maximizing convex program, and study two approximation procedures. The first method solves finite horizon stochastic programs on a rolling horizon basis. We develop a decomposition algorithm for solving the finite horizon problems. The finite horizon problems are linear programs. Our algorithm utilizes the network-like structure of the coefficient matrix of the linear programs. The second method is a heuristic procedure that is based on the structure of the optimal policy for two-period problems. The heuristic parallels the decision rules used by managers in practice. The computational results suggest that the performance of this heuristic is comparable to that of the rolling horizon approach.
Computers and Operations Research: A Marriage for Growth
Authors: Harris Carl M.
Published: November 2008

Rapid changes in both hardware and software computer technology pose many challenges to quantitative applications, and especially to operations research. Much of the future success of OR will depend on its ability to meet these challenges by marrying its approaches to computer technology and then using this enhanced capability to reach out to important new problem areas. To support the contention that OR is moving in these directions, as it must, this paper begins by reviewing computing progress to date as it relates to OR. Then it views three facets of the expansion of OR: university enrollments (and those on nonresident aliens in particular), application opportunities, and the dispersion of OR people in large organizations. The paper is an outgrowth of a plenary lecture at the May 1991 TIMS/ORSA meeting in Nashville.
Nonparametric Age Replacement: Bootstrap Confidence Intervals for the Optimal Cost
Authors: Léger Christian , Cléroux Robert
Published: November 2008

Bootstrap confidence intervals for the actual cost of using a given nonparametric estimate of the optimal age replacement strategy are shown to have the claimed coverage probability. A numerical algorithm is given to obtain these confidence intervals in practice. The small sample behavior of these confidence intervals is illustrated by simulations. Finally, comparisons are made with the confidence interval obtained from asymptotic normal theory. We show that the bootstrap confidence interval is the one to use in age replacement problems.
Probabilistic Analysis of the Capacitated Vehicle Routing Problem with Unsplit Demands
Authors: Bramel Julien , Coffman Edward G. , Shor Peter W. , Simchi-Levi David
Published: November 2008

In the capacitated vehicle routing problem with unsplit demands, the demand of a customer may not be divided over more than one vehicle. The objective is to find tours for the vehicles such that the amount delivered by a vehicle does not exceed its capacity, each customer receives its demand, and the total distance traveled is as small as possible. We find the asymptotic optimal solution value of the capacitated vehicle routing problem with unsplit demands for any distribution of the demands when customers are independently and identically distributed in a given region. We also develop polynomial-time heuristics for the problem and show that, under certain assumptions on the distribution of customer locations and demands, the heuristics produce solutions that are asymptotically optimal. In addition, we give a tight bound on the rate of convergence for the case when customers are uniformly distributed in a rectangular region.
Optimal Dynamic Assignment of Customers to Heterogeneous Servers in Parallel
Authors: Xu Susan H. , Righter Rhonda , Shanthikumar J. George
Published: November 2008

The system under consideration comprises two classes of customers to be served by two stations, with parallel servers in each station. While class-1 customers can only receive service from station 1, class-2 customers can be served by either station. Arrival processes of customers form two mutually independent Poisson processes. The service time of a customer at either station is exponentially distributed with a common rate. A class-i customer, while present in the system, will incur a holding cost hi with h1 ≥ h2. The objective is to dynamically assign customers to idle servers so that the expected discounted (or the long-run average) holding cost is minimized. We show that a class-j customer should be assigned to an idle server in station j, j = 1, 2, whenever possible, and a class-2 customer should be assigned to an idle server in station 1 only if (no class-1 customers are waiting, and) the length of queue 2 exceeds a critical number. Moreover, the critical number is monotonically increasing in the number of busy servers in station 1. The numerical results for some test cases are reported.
The Output Processes of Serial Production Lines of Exponential Machines with Finite Buffers
Authors: Hendricks Kevin B.
Published: November 2008

Little is known about the interaction among the various manufacturing subsystems in a factory. The output of one manufacturing subsystem is usually the input to one or more downstream subsystems in the plant. Examples include the output of one production line being the input to another manufacturing stage, to a shipping system, or to an automated part conveyor. In all these examples, the output process of the production line forms the arrival process to the next subsystem. This paper develops a technique to analytically describe the output process of a serial production line of N machines with exponential processing time distributions and finite buffer capacities. Extensive exact results are used to examine the effects of line length, buffer capacity, and buffer placement on the interdeparture distribution, correlation structure, and variability of the output process of the production line. These results are used to determine the extent to which buffer allocation can be used to control the variability of the output process (and thereby the amount of work-in-process required to downstream subsystems). In addition, insights are provided to help explain why small buffers in production lines are normally adequate.
On the Minimization of Completion Time Variance with a Bicriteria Extension
Authors: De Prabuddha , Ghosh Jay B. , Wells Charles E.
Published: November 2008

We discuss a single-machine scheduling problem where the objective is to minimize the variance of job completion times. To date, the problem has not been solved in polynomial time. This paper presents a dynamic programming algorithm that is pseudopolynomial in complexity. We also propose a fully polynomial approximation scheme and derive a lower bound that is useful in its implementation. Furthermore, we show that the dynamic programming solution is easy to extend to a bicriteria version of the problem in which it is desired to simultaneously minimize the mean completion time.
A Weighted Markov Decision Process
Authors: Krass Dmitry , Filar Jerzy A. , Sinha Sagnik S.
Published: November 2008

The two most commonly considered reward criteria for Markov decision processes are the discounted reward and the long-term average reward. The first tends to “neglect” the future, concentrating on the short-term rewards, while the second one tends to do the opposite. We consider a new reward criterion consisting of the weighted combination of these two criteria, thereby allowing the decision maker to place more or less emphasis on the short-term versus the long-term rewards by varying their weights. The mathematical implications of the new criterion include: the deterministic stationary policies can be outperformed by the randomized stationary policies, which in turn can be outperformed by the nonstationary policies; an optimal policy might not exist. We present an iterative algorithm for computing an ε-optimal nonstationary policy with a very simple structure.
A Stopping Rule for Forecasting Horizons in Nonhomogeneous Markov Decision Processes
Authors: Bean James C. , Hopp Wallace J. , Duenyas Izak
Published: November 2008

We formulate a mixed integer program to determine whether a finite time horizon is a forecast horizon in a nonhomogeneous Markov decision process. We give a Bender's decomposition approach to solving this problem that evaluates the stopping rule, eliminates some suboptimal combinations of actions, and yields bounds on the maximum error that could result from the selection of a candidate action in the initial stage. The integer program arising from the decomposition has special properties that allow efficient solution. We illustrate the approach with numerical examples.
Dynamic and Stochastic Models for the Allocation of Empty Containers
Authors: Crainic Teodor Gabriel , Gendreau Michel , Dejax Pierre
Published: November 2008

The empty container allocation problem occurs in the context of the management of the land distribution and transportation operations of international maritime shipping companies. It involves dispatching empty containers of various types in response to requests by export customers and repositioning other containers to storage depots or ports in anticipation of future demands. We describe the problem and identify its basic structure and main characteristics. We then introduce two dynamic deterministic formulations for the single and multicommodity cases, which offer a general modeling framework for this class of problems, and which account for its specific characteristics: the space and time dependency of events, substitutions among container types, relationships with partner companies, imports and exports, massive equilibration flows, etc. Finally, we provide a mathematical formulation for handling, in the single commodity case, the uncertainty of demand and supply data that is characteristic of container allocation and distribution problems. Various modeling choices, data requirements, and algorithmic considerations related to the implementation of the models are also discussed.
Airline Seat Allocation with Multiple Nested Fare Classes
Authors: Brumelle S. L. , McGill J. I.
Published: November 2008

This paper addresses the problem of determining optimal booking policies for multiple fare classes that share the same seating pool on one leg of an airline flight when seats are booked in a nested fashion and when lower fare classes book before higher ones. We show that a fixed-limit booking policy that maximizes expected revenue can be characterized by a simple set of conditions on the subdifferential of the expected revenue function. These conditions are appropriate for either the discrete or continuous demand cases. These conditions are further simplified to a set of conditions that relate the probability distributions of demand for the various fare classes to their respective fares. The latter conditions are guaranteed to have a solution when the joint probability distribution of demand is continuous. Characterization of the problem as a series of monotone optimal stopping problems proves optimality of the fixed-limit policy over all admissible policies. A comparison is made of the optimal solutions with the approximate solutions obtained by P. Belobaba using the expected marginal seat revenue (EMSR) method.