bluuebunny/crossref_metadata_2025 huggingface dataset:
Input Control for Serial Production Lines Consisting of Processing and Assembly Operations with Random Yields
Authors: Lee Hau L.
Published: November 2008

This paper deals with a serial production line where each of the stages can be either a processing or an assembly stage. A processing stage processes outputs from an upstream stage and transforms them into inputs for the downstream stage. Each processing stage is subject to yield losses. At an assembly stage, a batch of identical input components is processed and the nondefective components are then combined with the output from the upstream stage. The processing operation for the input component is imperfect. For such a system, we characterize the form of the optimal policy for input quantity at each stage in the production line, when stochastically proportional yield is assumed at each stage, i.e., the distribution of the yield fraction is assumed to be independent of the lot size. The optimal policy exhibits some form of a critical number policy. For production lines consisting of assembly stages only, the critical numbers can be computed easily. When yields are of the “exponential” type, the critical number policy is still optimal, although there are interesting differences in the policies for the different types of yield characterizations.
A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers
Authors: Gendreau Michel , Laporte Gilbert , Séguin René
Published: November 2008

This paper considers a version of the stochastic vehicle routing problem where customers are present at locations with some probabilities and have random demands. A tabu search heuristic is developed for this problem. Comparisons with known optimal solutions on problems whose sizes vary from 6 to 46 customers indicate that the heuristic produces an optimal solution in 89.45% of cases, with an average deviation of 0.38% from optimality.
Heuristics, LPs, and Trees on Trees: Network Design Analyses
Authors: Balakrishnan Anantaram , Magnanti Thomas L. , Mirchandani Prakash
Published: November 2008

We study a class of models, known as overlay optimization problems, composed of “base” and “overlay” subproblems, linked by the requirement that the overlay solution be contained in the base solution. In some telecommunication settings, a feasible base solution is a spanning tree, and the overlay solution is an embedded Steiner tree or path. For the general overlay optimization problem, we describe a composite heuristic solution procedure that selects the better of two feasible solutions obtained by independently solving the base and the overlay subproblems, and establish worst-case performance guarantees (as a function of the worst-case bounds for the subproblems) for the composite heuristic as well as an LP relaxation of the model. For certain special cases, both the heuristic and the LP relaxation have a worst-case bound of 4/3. We extend this analysis to multiple overlays on the same base solution, producing the first known worst-case bounds (approximately proportional to the square root of the number of commodities) for the uncapacitated multicommodity network design problem. In a companion paper, we develop heuristic performance guarantees for various new multi-tier, survivable network design models that incorporate both multiple facility types and differential node connectivity levels.
DEA/Assurance Region SBDC Efficiency and Unique Projections
Authors: Thompson R. G. , Dharmapala P. S. , Gatewood E. J. , Macy S. , Thrall R. M.
Published: November 2008

The University of Houston (UH) Small Business Development Centers (SBDCs) were analyzed by Data Envelopment Analysis (DEA) and Assurance Region (AR) methods. The DEA/AR analyses were made for 11 DMUs in 1990 and 1991 and for 13 DMUs in 1992. The DEA ratio (CCR) method was applied to Model I in all three years; unique optimal solutions to the DEA-inefficient DMUs were verified. Also, ARs were applied to eliminate some DEA-efficient DMUs requiring unreasonable multipliers to maximize efficiency. In addition, measures of returns-to-scale (RTS) intervals from application of the DEA convex (BCC) method in 1992 showed several additional DEA-efficient DMUs needed some additional funds to work toward the most productive scale size.
A Flow Algorithm for Network Synchronization
Authors: Hassin Refael
Published: November 2008

The problem we treat is defined on a graph where each node is associated with a variable and there are loss functions defined on the arcs, depending on the difference between the corresponding node variables. The objective is to compute values for the node variables so as to minimize the sum of losses. We exploit the relation between this problem and network flows optimization and use it in developing an approximation algorithm for the problem. A main application of the problem is the synchronization of fixed cycle traffic signals.
Decomposition of Utility Functions on Subsets of Product Sets
Authors: Sainfort François , Deichtmann Jean M.
Published: November 2008

The standard decomposition theorem for additive and multiplicative utility functions (Pollak [Pollak, R. O. 1967. Additive von Neumann-Morgenstern utility functions. Econometrica 35 485–494.], Keeney [Keeney, R. L. 1974. Multiplicative utility functions. Opns. Res. 22 22–34.]) assumes that the outcome set is a whole product set. In this paper this assumption is relaxed, and the question of whether or not a natural revision of this theorem necessarily holds is investigated. This paper proves that two additional conditions are needed for the decomposition theorem to hold in the context where the outcome set is a subset of a Cartesian product. It is argued that these two new conditions are satisfied by a large family of subsets corresponding to significant real-world problems. Further research avenues are suggested including a generalization of this new decomposition result to nonexpected utility theories.
The Departure Process of the GI/G/1 Queue and Its MacLaurin Series
Authors: Hu Jian-Qiang
Published: November 2008

In this paper, we study the departure process of the GI/G/1 queue. We develop a simple recursive procedure to calculate the MacLaurin series of its moments and covariances with respect to a parameter in the service time. Based on this recursive procedure the explicit formulas of the coefficients of these MacLaurin series can be obtained in terms of derivatives of the probability density function of the interarrival time evaluated at zero and the moments of the interarrival time and the service time. One important application of these MacLaurin series is that they can be used to obtain the entire response curves of the moments and variances of the departure process, for example, via interpolation by polynomials or rational functions.
An Algorithm for the Multiperiod Market Equilibrium Model with Geometric Distributed Lag Demand
Authors: Wu Y. June , Fuller J. David
Published: November 2008

This paper presents a new equilibrium-seeking algorithm, called the decoupling algorithm, for calculation of multiperiod equilibrium of supplies and demands when demand has a geometric distributed lag (GDL) structure and supply is represented by a linear process submodel. The new algorithm is required because it may be difficult to obtain the equilibrium by a diagonalization algorithm such as PIES. In each step of the decoupling algorithm, a modified GDL equilibrium model, the “decoupled submodel,” is solved by the PIES algorithm; successive approximations move closer to the true equilibrium. Two versions of a large-scale realistic model of North American energy supplies and demands are solved with the decoupling algorithm to aid in understanding the behavior of the decoupling algorithm.
X-Y Band and Modified (s, S) Policy
Authors: Shaoxiang Chen , Lambrecht M.
Published: November 2008

This paper considers the stochastic, single-item, periodic review inventory problem. Most importantly we assume a finite production capacity per period and a production cost function containing a fixed (as well as a variable) component. With stationary data, a convex expected holding and shortage cost function, we show that generally the modified (s, S) policy is not optimal to the finite horizon problems. The optimal policy does, however, show a systematic pattern which we call the X-Y band structure. This X-Y band policy is interpreted as follows: whenever the inventory level drops below X, order up to capacity; when the inventory level is above Y, do nothing; if the inventory level is between X and Y, however, the ordering pattern is different from problem to problem. Although the X and Y bounds may change from period to period, we prove the existence of a pair of finite X and Y values that can apply for all the periods (i.e., bounds on individual bounds). One calculation for such X and Y bounds that are tight in some cases is also provided. By exploring the X-Y band structure, we can drastically reduce the computation effort for finding the optimal policies.
A Probabilistic Analysis of Two-Machine Flowshops
Authors: Ramudhin Amar , Bartholdi John J. , Calvin James M. , Vande Vate John H. , Weiss Gideon
Published: November 2008

We study a two-machine flowshop in which all processing times are independently and identically distributed, with values known to the scheduler. We are able to describe in detail the expected behavior of the flowshop under optimal and heuristic schedules. Our results suggest that minimizing makespan might be a superfluous objective: random schedules are easier to construct and require significantly less intermediate storage between the machines; moreover, they are known to be asymptotically optimal.
Stationary-Process Approximations for the Nonstationary Erlang Loss Model
Authors: Massey William A. , Whitt Ward
Published: November 2008

In this paper we consider the Mt/G/s/0 model, which has s servers in parallel, no extra waiting space, and i.i.d. service times that are independent of a nonhomogeneous Poisson arrival process. Arrivals finding all servers busy are blocked (lost). We consider approximations for the average blocking probabilities over subintervals (e.g., an hour when the expected service time is five minutes) obtained by replacing the nonstationary arrival process over that subinterval by a stationary arrival process. The stationary-Poisson approximation, using a Poisson (M) process with the average rate, tends to significantly underestimate the blocking probability. We obtain much better approximations by using a non-Poisson stationary (G) arrival process with higher stochastic variability to capture the effect of the time-varying deterministic arrival rate. In particular, we propose a specific approximation based on the heavy-traffic peakedness formula, which is easy to apply with either known arrival-rate functions or data from system measurements. We compare these approximations to exact numerical results for the Mt/M/s/0 model with linear arrival rate.
Activity Delay in Stochastic Project Networks
Authors: Buss Arnold H. , Rosenblatt Meir J.
Published: November 2008

In this paper we deal with a stochastic project network and consider the impact of activity delay to maximize the expected present value of a project. It is shown that in certain situations, delaying the onset of an activity from its earliest start time can indeed increase the present value of a project due to the postponing of associated negative cash flows. Furthermore, a project that could otherwise be rejected (negative expected present value) may become profitable (positive expected present value) due to delay. We demonstrate that even activities on the critical path, as determined by each activity's expected duration, may be profitably delayed. Optimal and approximate procedures are developed to determine the amount of delay of the various activities.
Performance Assessment for the Waste Isolation Pilot Plant: From Regulation to Calculation for 40 CFR 191.13
Authors: Helton J. C. , Anderson D. R. , Marietta M. G. , Rechard R. P.
Published: November 2008

The Waste Isolation Pilot Plant (WIPP) is being developed by the U.S. Department of Energy as a disposal facility for transuranic waste and must comply with several environmental regulations, including the U.S. Environmental Protection Agency's standard for geologic disposal of radioactive waste (40 CFR 191). Procedures used in recent performance assessments for the WIPP to translate regulations into a structure that facilitates quantitative analysis are described. Topics considered include (1) development of a clear conceptual representation for problems that are initially ill-defined, (2) conversion of qualitative guidance into numerical calculations. (3) explicit incorporation of different types of uncertainty (i.e., aleatory and epistemic) into analysis outcomes, (4) requirements for efficient computation and models at different levels of complexity, (5) use of sensitivity analysis to guide additional data collection and future calculations, (6) requirements for results to be presented and explained to audiences with different interests and levels of sophistication, and (7) ambiguity with respect to final uses of the analysis and its outcomes. The need to address similar concepts and problems arises in many analyses.
Airline Crew Scheduling: A New Formulation and Decomposition Algorithm
Authors: Vance Pamela H. , Barnhart Cynthia , Johnson Ellis L. , Nemhauser George L.
Published: November 2008

Airline crew scheduling is concerned with finding a minimum cost assignment of flight crews to a given flight schedule while satisfying restrictions dictated by collective bargaining agreements and the Federal Aviation Administration. Traditionally, the problem has been modeled as a set partitioning problem. In this paper, we present a new model based on breaking the decision process into two stages. In the first stage we select a set of duty periods that cover the flights in the schedule. Then, in the second stage, we attempt to build pairings using those duty periods. We suggest a decomposition approach for solving the model and present computational results for test problems provided by a major carrier. Our formulation provides a tighter linear programming bound than that of the conventional set partitioning formulation but is more difficult to solve.
Multigroup Discriminant Analysis Using Linear Programming
Authors: Gochet Willy , Stam Antonie , Srinivasan V. , Chen Shaoxiang
Published: November 2008

In this paper we introduce a nonparametric linear programming formulation for the general multigroup classification problem. Previous research using linear programming formulations has either been limited to the two-group case, or required complicated constraints and many zero-one variables. We develop general properties of our multigroup formulation and illustrate its use with several small example problems and previously published real data sets. A comparative analysis on the real data sets shows that our formulation may offer an interesting robust alternative to parametric statistical formulations for the multigroup discriminant problem.
Performance Decay in a Single Server Exponential Queueing Model with Long Range Dependence
Authors: Resnick Sidney , Samorodnitsky Gennady
Published: November 2008

We discuss how long-range dependence can influence the characteristics of a single server queue. We take the analogue of the G/M/1 queue except that the input stream is altered to exhibit long-range dependence. The equilibrium queue size and equilibrium waiting time distributions have heavy tails. By suitably selecting the parameters of the inputs, the queue size or waiting time can be made to possess infinite variance and even infinite mean. Some simulations dramatically illustrate the potential for undetected long-range dependence to significantly alter the queueing behavior compared to what is anticipated with traditional inputs.
On the Difference Between the Cardinalities of Measurable Value Functions and Von Neumann-Morgenstern Utility Functions
Authors: Deichtmann Jean M. , Sainfort François
Published: November 2008

Dyer and Sarin (Dyer, J. S., R. K. Sarin. 1979. Measurable multiattribute value functions. Opns. Res. 27 810–822.) proposed an important generalization of the additive-multiplicative decomposition theorem for von Neumann-Morgenstern (vNM) utility functions to measurable value functions based on the cardinality property of measurable value functions. However, because of a difference between the cardinality of measurable value functions and the cardinality of vNM utility functions, an additional technical condition is needed, and presented here, for the decomposition theorem to hold.
A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
Authors: Fischetti Matteo , Salazar González Juan José , Toth Paolo
Published: November 2008

We consider a variant of the classical symmetric Traveling Salesman Problem in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. This NP-hard problem is known in the literature as the symmetric Generalized Traveling Salesman Problem (GTSP), and finds practical applications in routing, scheduling and location-routing. In a companion paper (Fischetti et al. [Fischetti, M., J. J. Salazar, P. Toth. 1995. The symmetric generalized traveling salesman polytope. Networks 26 113–123.]) we modeled GTSP as an integer linear program, and studied the facial structure of two polytopes associated with the problem. Here we propose exact and heuristic separation procedures for some classes of facet-defining inequalities, which are used within a branch-and-cut algorithm for the exact solution of GTSP. Heuristic procedures are also described. Extensive computational results for instances taken from the literature and involving up to 442 nodes are reported.
Vehicle Routing with Time Windows: Two Optimization Algorithms
Authors: Fisher Marshall L. , Jörnsten Kurt O. , Madsen Oli B. G.
Published: November 2008

We describe two optimization methods for vehicle routing problems with time windows. These are a K-Tree relaxation with time windows added as side constraints and a Lagrangian decomposition in which variable splitting is used to divide the problem into two subproblems—a semi-assignment problem and a series of shortest path problems with time windows and capacity constraints. We present optimal solutions to problems with up to 100 customers.
Polling Models With and Without Switchover Times
Authors: Borst S. C. , Boxma O. J.
Published: November 2008

We consider two different single-server cyclic polling models: (i) a model with zero switchover times, and (ii) a model with nonzero switchover times, in which the server keeps cycling when the system is empty. For both models we relate the steady-state queue length distribution at a queue to the queue length distributions at server visit beginning and visit completion instants at that queue; as a by-product we obtain a short proof of the Fuhrmann-Cooper decomposition. For the large class of polling systems that allow a multitype branching process interpretation, we expose a strong relation between the queue length, as well as waiting-time, distributions in the two models. The results enable a very efficient numerical computation of the waiting-time moments under different switchover time scenarios.
Two-Machine Open Shops with Renewable Resources
Authors: Jurisch Bernd , Kubiak Wieslaw
Published: November 2008

In open shops with renewable resources, an operation may require additional resources, besides a machine, for its execution. All resources required by the operation are allocated to it all the time during its execution. At no time may total resource requirements exceed resource capacities. We consider the problem of minimizing makespan in a two-machine open shop with a single renewable resource. We show that optimal nonpreemptive schedules are not longer than optimal preemptive schedules, which we then translate into a polynomial time algorithm for the makespan minimization problem. This is an important generalization of a well-known result obtained by Gonzalez and Sahni (Gonzalez, G., S. Sahni. 1976. Open shop scheduling to minimize finish time. J. ACM 23 665–679.) for the two-machine open shop without additional resources. We also study the problem of minimizing makespan in a two-machine open shop with at least two different resources. In this case, optimal nonpreemptive schedules may be longer than optimal preemptive ones. We show that this makes the makespan minimization problem NP-hard.
Workforce Planning in Mixed Model Assembly Systems
Authors: Lee Chung-Yee , Vairaktarakis George L.
Published: November 2008

Serial assembly systems are formed by arranging several production cells or stations in series. We study a popular class of serial assembly lines where all stations have the same production cycle. We address a workforce planning problem for such lines which finds applications in labor-intensive operations in automobile, fire engine, aircraft, and PC board assembly. The problem presented can be applied to lines that produce several variations of a basic stable design; i.e., mixed model transfer lines. Given a set of n jobs, we want to find a sequence that minimizes the maximum workforce requirements over all production cycles. An optimal polynomial algorithm for the two-station line is presented, and the three-station case is proved to be strongly 𝒩𝒫-complete. Several heuristic algorithms that produce upper and lower bounds are developed for the general problem. Worst case behavior of the upper bounds, as well as average performance of lower and upper bounds, are reported. Computational results show that some of the heuristics produce near optimal solutions. As an extension of the basic model we exploit the tradeoff between cycle time and workforce level.
The Covering Tour Problem
Authors: Gendreau Michel , Laporte Gilbert , Semet Frédéric
Published: November 2008

The Covering Tour Problem (CTP) is defined on a graph G = (V ∪ W, E), where W is a set of vertices that must be covered. The CTP consists of determining a minimum length Hamiltonian cycle on a subset of V such that every vertex of W is within a prespecified distance from the cycle. The problem is first formulated as an integer linear program, polyhedral properties of several classes of constraints are investigated, and an exact branch-and-cut algorithm is developed. A heuristic is also described. Extensive computational results are presented.
Probabilistic Analysis of a Generalized Bin Packing Problem and Applications
Authors: Federgruen Awi , van Ryzin Garrett
Published: November 2008

We give a unified probabilistic analysis for a general class of bin packing problems by directly analyzing corresponding mathematical programs. In this general class of packing problems, objects are described by a given number of attribute values. (Some attributes may be discrete; others may be continuous.) Bins are sets of objects, and the collection of feasible bins is merely required to satisfy some general consistency properties. We characterize the asymptotic optimal value as the value of an easily specified linear program whose size is independent of the number of objects to be packed, or as the limit of a sequence of such linear program values. We also provide bounds for the rate of convergence of the average cost to its asymptotic value. The analysis suggests an (a.s.) asymptotically ϵ-optimal heuristic that runs in linear time. The heuristics can be designed to be asymptotically optimal while still running in polynomial time. We also show that in several important cases, the algorithm has both polynomially fast convergence and polynomial running time. This heuristic consists of solving a linear program and rounding its solution up to the nearest integer vector. We show how our results can be used to analyze a general vehicle routing model with capacity and time window constraints.
The QNET Method for Re-Entrant Queueing Networks with Priority Disciplines
Authors: Dai J. G. , Yeh D. H. , Zhou C.
Published: November 2008

This paper is concerned with the estimation of performance measures of two priority disciplines in a d-station re-entrant queueing network. Such networks arise from complex manufacturing systems such as wafer fabrication facilities. The priority disciplines considered are First-Buffer-First-Served (FBFS) and Last-Buffer-First-Served (LBFS). An analytical method is developed to estimate the long-run average workload at each station and the mean sojourn time in the network. When the first-buffer-first-served discipline is used, a refined estimate of the mean sojourn time is also developed. The workload estimation has two steps. In the first step, following Harrison and Williams (Harrison, J. M., R. J. Williams. 1992. Brownian models of feedforward queueing networks: Quasireversibility and product form solutions. Anns. Appl. Prob. 2 263–293.), we use a d-dimensional reflecting Brownian motion (RBM) to model the workload process. We prove that the RBM exists and is unique in distribution and that it has a unique stationary distribution. We then use an algorithm of Dai and Harrison (Dai, J. G., J. M. Harrison. 1992. Reflected Brownian motion in an orthant: Numerical methods for steady-state analysis. Anns. Appl. Prob. 2 65–86.) to compute the stationary distribution of the RBM. Our method uses both the first and second moment information, and it is rooted in heavy traffic theory. It is closely related to the QNET method of Harrison and Nguyen (Harrison, J. M., V. Nguyen. 1993. Brownian models of multiclass queueing networks: Current status and open problems. Queueing Systems: Theory and Appl. 13 5–40.) for two-moment analysis of First-In-First-Out (FIFO) discipline. Our performance estimates of several example problems are compared to the simulation estimates to illustrate the effectiveness of our method.
Flight Attendant Rostering for Short-Haul Airline Operations
Authors: Day Paul R. , Ryan David M.
Published: November 2008

The construction of flight attendant (cabin crew) rosters for short-haul (domestic) airline flight services that satisfies rostering constraints and employment contract regulations is a combinatorially complex problem. In this paper the problem is described and an effective optimisation-based solution method is introduced. The rostering problem involves the allocation of days-off and various duties to each crew member over a roster period. The days-off and the duty allocation problems are separated into two distinct subproblems. The days-off allocation solution approach involves complete enumeration of all possible days-off lines for each crew member over the roster period, and then the solution of a set partitioning optimisation to determine a best quality feasible days-off roster. The duty allocation solution approach first involves the generation of many lines-of-work consistent with the days-off solution for each crew member over a subroster period and then the solution of a set partitioning optimisation to determine an optimal feasible subroster. These two steps of generation and optimisation are repeated for each subsequent subroster period until a full legal and feasible roster is constructed for the complete roster period. The use of subrosters reduces the combinatorial complexity resulting in problems that can be solved efficiently. After construction of the initial roster, the quality can often be improved using re-rostering techniques. The method leads to efficient construction of good quality legal rosters, and has been used to produce all short-haul flight attendant rosters at Air New Zealand since 1993.
Optimal Control of a Single Stage Production System Subject to Random Process Shifts
Authors: Nurani Raman K. , Seshadri Sridhar , Shanthikumar J. George
Published: November 2008

We consider a single stage production system with Poisson demand and exponential processing times. After producing a good item, the production process can shift to an “out-of-control” state with a given probability and start producing bad items. The state of the process is known only when the next stage (or customer) receives the item. Once an out-of-control process is detected, process correction is instantaneous. Customers arriving to an empty system get backlogged. In this framework, we examine FIFO (First In First Out) and LIFO (Last In First Out) issuing policies. The objective is to minimize the total expected discounted or average costs over an infinite time horizon. We characterize the structure of the optimal production policy for FIFO and LIFO, show that LIFO is better than FIFO and, in general, better than a large class of issuing policies. A numerical example illustrates that savings up to 20 percent can be obtained from using LIFO over FIFO. We also derive conditions under which maintaining zero inventory is optimal, and show that zero inventory is more likely to be optimal when either the backlogging cost or arrival rate of customers is small, and when the inventory carrying cost or the processing rate or the probability of getting a good item is large.
A Tire Production Scheduling System for Bridgestone/Firestone Off-The-Road
Authors: Degraeve Zeger , Schrage Linus
Published: November 2008

We describe a scheduling system for the curing operation at Bridgestone/Firestone Off-The-Road (BFOR), a manufacturer of large tires for heavy off-the-road machines such as trucks, tractors, and earthmoving equipment used in the construction, lumber, and mining industries. The huge tires, having different priorities, are built in molds and put into heaters for the curing process. The problem is to find a feasible assignment of tires to molds and molds to heaters to achieve a maximum total priority. Our system produces about 7% more tires per shift compared to the previous manual way of developing schedules and moves the company toward its goal of quick response manufacturing with low inventories. The core algorithm is a column generation procedure to produce a production schedule for one work shift. This approach is then used in a “rolling horizon” fashion. The size of the problem posed several computational challenges. Computational efficiencies come from (1) a dramatic effort to eliminate alternative solutions up front in an aggregation preprocessor, (2) considering the most “interesting” tires to be scheduled subsequently at each point of the algorithm, and (3) using cutting planes to provide for tight LP formulations for the subproblems.
An Inventory Problem with Two Randomly Available Suppliers
Authors: Gürler Ülkü , Parlar Mahmut
Published: November 2008

This paper considers a stochastic inventory model in which supply availability is subject to random fluctuations that may arise due to machine breakdowns, strikes, embargoes, etc. It is assumed that the inventory manager deals with two suppliers who may be either individually ON (available) or OFF (unavailable). Each supplier's availability is modeled as a semi-Markov (alternating renewal) process. We assume that the durations of the ON periods for the two suppliers are distributed as Erlang random variables. The OFF periods for each supplier have a general distribution. In analogy with queuing notation, we call this an Es1[Es2]/G1[G2] system. Since the resulting stochastic process is non-Markovian, we employ the “method of stages” to transform the process into a Markovian one, albeit at the cost of enlarging the state space. We identify the regenerative cycles of the inventory level process and use the renewal reward theorem to form the long-run average cost objective function. Finite time transition functions for the semi-Markov process are computed numerically using a direct method of solving a system of integral equations representing these functions. A detailed numerical example is presented for the E2[E2]/M[M] case. Analytic solutions are obtained for the particular case of “large” (asymptotic) order quantity, in which case the objective function assumes a very simple form that can be used to analyze the optimality conditions. The paper concludes with the discussion of an alternative inventory policy for modeling the random supply availability problem.
Cyclic Scheduling of Identical Parts in a Robotic Cell
Authors: Crama Yves , van de Klundert Joris
Published: November 2008

We consider a robotic flowshop in which one type of product is to be repeatedly produced, and where transportation of the parts between the machines is performed by a robot. The identical parts cyclic scheduling problem is then to find a shortest cyclic schedule for the robot; i.e., a sequence of robot moves that can be infinitely repeated and that has minimum cycle time. This problem has been solved by Sethi et al. (Sethi, S. P., C. Sriskandarajah, G. Sorger, J. Blazewicz, W. Kubiak. 1992. Sequencing of parts and robot moves in a robotic cell. Internat. J. Flexible Manufacturing Systems 4 331–358.) when m ≤ 3. In this paper, we generalize their results by proving that the identical parts cyclic scheduling problem can be solved in time polynomial in m, where m denotes the number of machines in the shop. In particular, we present a dynamic programming approach that allows us to solve the problem in O(m3) time. Our analysis relies heavily on the concept of pyramidal permutation, a concept previously investigated in connection with the traveling salesman problem.
Computing Loss Probabilities in Discrete-Time Queues
Authors: Gouweleeuw Frank N. , Tijms Henk C.
Published: November 2008

Discrete-time queueing systems are frequently encountered in telecommunication networks. These systems usually involve finite buffers. The purpose of this paper is to present a generally applicable method to compute the loss probability in discrete-time finite-buffer queues by using only the state probabilities in the corresponding infinite-buffer queue.
Partial Characterization of Optimal Hedging Point Policies in Unreliable Two-Part-Type Manufacturing Systems
Authors: Srivatsan N. , Dallery Yves
Published: November 2008

The production control problem in unreliable manufacturing systems has generated a great deal of interest recently. The goal is the real-time calculation of production rates to minimize total expected surplus and backlog costs in a production system. A class of feedback control policies, called hedging point policies, has been studied in literature and shown to be optimal for certain single-part-type systems. This paper focuses mainly on the performance of hedging point policies in two-part-type systems. We first generalize known stability results for hedging point policies in single-part-type systems and extend them to two-part-type systems. An average cost analysis of trajectories is then used to partially characterize an optimal policy belonging to this class. A complete characterization is obtained for special parameter values. The results in this paper provide insights for designing simple yet effective heuristics for controlling manufacturing systems producing many part-types.
The Multiprocessor Scheduling of Precedence-Constrained Task Systems in the Presence of Interprocessor Communication Delays
Authors: Baruah Sanjoy K.
Published: November 2008

The problem of scheduling precedence-constrained task systems characterized by interprocessor communication delays is addressed. It is assumed that task duplication is permitted. The target machine is a homogenous multiprocessor with an unbounded number of processors. The general problem is known to be NP-hard; however, when communication delays are small relative to task execution times, the C.P.M. based approach of Colin and Chrétienne (1991) yields an optimal schedule in polynomial time. Extensions to this method of Colin and Chrétienne are presented here, which allow for polynomial-time optimal schedule generation for certain categories of task systems with arbitrary precedence relations, processing times, and communication delays.
Some Quality Improvement Principles Useful in the OR/MS Research and Publication Process
Authors: Troutt Marvin D.
Published: November 2008

The OR/MS research and publication process provides a particularly effective setting in which to illustrate and emphasize the importance of several general quality improvement principles. From planning the scope and content to final manuscript production, numerous quality checks are beneficial. The academic writer never knows that the quality of an article is sufficient until it has actually been published. Even then, potential defects are possible and should be guarded against throughout the process. Beginning scholars may fail to publish successfully by disregarding some of these principles. This article discusses the connection of general quality principles to the scientific article writing process. Also, some specific techniques used by the author are described.
A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows
Authors: Gendreau Michel , Hertz Alain , Laporte Gilbert , Stan Mihnea
Published: November 2008

This article describes a generalized insertion heuristic for the Traveling Salesman Problem with Time Windows in which the objective is the minimization of travel times. The algorithm gradually builds a route by inserting at each step a vertex in its neighbourhood on the current route, and performing a local reoptimization. This is done while checking the feasibility of the remaining part of the route. Backtracking is sometimes necessary. Once a feasible route has been determined, an attempt is made to improve it by applying a post-optimization phase based on the successive removal and reinsertion of all vertices. Tests performed on 375 instances indicate that the proposed heuristic compares very well with alternative methods and very often produces optimal or near-optimal solutions.
A Decomposition Approach for a Class of Economic Equilibrium Models
Authors: Murphy Frederic H. , Mudrageda Murthy V.
Published: November 2008

In this paper we present the theoretical foundations for one of the methods used to achieve convergence in the National Energy Modeling System (NEMS). NEMS is a large model with several component models that are built and operated by different branches in the organization and is an example of a system without a hierarchical structure that cannot be solved by traditional equation solving methods. Some of the component models use linear programs to construct supply and demand curves. The discontinuities that result lead to oscillations in the standard relaxation algorithms. We explain where the convergence problems lie and how the convergence theory with step functions links to the convergence theory with continuous functions. To achieve convergence within the entire system, a set of ad hoc techniques were developed to implement a decomposition strategy that allows the individual models to be run separately. We present the theoretical justification for one of them here. The technique presented here has the potential to allow an organization to use operational models for planning without resorting to aggregation. It also facilitates decentralized computing over Internet.
Moments in Tandem Queues
Authors: Scheller-Wolf Alan , Sigman Karl
Published: November 2008

We settle a conjecture concerning necessary conditions for finite mean steady-state customer delay at the second node of a tandem queue, using as an example a stable tandem queue with mutually independent i.i.d. interarrival and service times. We assume that the service times have infinite variance at the first node, finite variance at the second node, and smaller mean at the first node than at the second node. We show that this causes infinite mean stationary delay at the second node. Thus, in general, when the mean service time is smaller at the first node than at the second, finite variance of service times at node 1 is necessary for finite mean delay at node 2. This confirms a conjecture made by Wolff. Our result complements sufficiency conditions previously published by Wolfson; together these necessary and sufficient conditions are presented as a theorem at the conclusion of the paper. Our proof uses a known duality between risk processes and queues.
From Valid Inequalities to Heuristics: A Unified View of Primal-Dual Approximation Algorithms in Covering Problems
Authors: Bertsimas Dimitris , Teo Chung-Piaw
Published: November 2008

In recent years approximation algorithms based on primal-dual methods have been successfully applied to a broad class of discrete optimization problems. In this paper, we propose a generic primal-dual framework to design and analyze approximation algorithms for integer programming problems of the covering type that uses valid inequalities in its design. The worst-case bound of the proposed algorithm is related to a fundamental relationship (called strength) between the set of valid inequalities and the set of minimal solutions to the covering problems. In this way, we can construct an approximation algorithm simply by constructing the required valid inequalities. We apply the proposed algorithm to several problems, such as covering problems related to totally balanced matrices, cyclic scheduling, vertex cover, general set covering, intersections of polymatroids, and several network design problems attaining (in most cases) the best worst-case bound known in the literature.
Optimal Load Balancing on Distributed Homogeneous Unreliable Processors
Authors: Liu Zhen , Righter Rhonda
Published: November 2008

We consider optimal load balancing in a distributed computing environment consisting of homogeneous unreliable processors. Each processor receives its own sequence of tasks from outside users, some of which can be redirected to the other processors. Processing times are independent and identically distributed with an arbitrary distribution. The arrival sequence of outside tasks to each processor may be arbitrary as long as it is independent of the state of the system. Processors may fail, with arbitrary failure and repair processes that are also independent of the state of the system. The only information available to a processor is the history of its decisions for routing work to other processors, and the arrival times of its own arrival sequence.

We prove the optimality of the round-robin policy, in which each processor sends all the tasks that can be redirected to each of the other processors in turn. We show that, among all policies that balance workload, round robin stochastically minimizes the nth task completion time for all n, and minimizes response times and queue lengths in a separable increasing convex sense for the entire system. We also show that if there is a single centralized controller, round-robin is the optimal policy, and a single controller using round-robin routing is better than the optimal distributed system in which each processor routes its own arrivals. Again “optimal” and “better” are in the sense of stochastically minimizing task completion times, and minimizing response time and queue lengths in the separable increasing convex sense.
Correlation-Induction Techniques for Estimating Quantiles in Simulation Experiments
Authors: Avramidis Athanassios N. , Wilson James R.
Published: November 2008

A simulation-based quantile estimator measures the level of system performance that can be delivered with a prespecified probability. To estimate selected quantiles of the response of a finite-horizon simulation, we develop procedures based on correlation induction techniques for variance reduction, with emphasis on antithetic variates and Latin hypercube sampling. These procedures achieve improved precision by controlling the simulation's random-number inputs as an integral part of the experimental design. The proposed multiple-sample quantile estimator is the average of negatively correlated quantile estimators computed from disjoint samples of the simulation response, where negative correlation is induced between corresponding responses in different samples while mutual independence of responses is maintained within each sample. The proposed single-sample quantile estimator is computed from negatively correlated simulation responses within one all-inclusive sample. The single-sample estimator based on Latin hypercube sampling is shown to be asymptotically normal and unbiased with smaller variance than the comparable direct-simulation estimator based on independent replications. Similar asymptotic comparisons of the multiple-sample and direct-simulation estimators focus on bias and mean square error. Monte Carlo results suggest that the proposed procedures can yield significant reductions in bias, variance, and mean square error when estimating quantiles of the completion time of a stochastic activity network.
Solving a Class of Two-Dimensional Uncapacitated Location-Allocation Problems by Dynamic Programming
Authors: Brimberg Jack , Love Robert F.
Published: November 2008

In this paper we define and analyze a class of two-dimensional location-allocation problems that can be solved with a one-dimensional dynamic programming algorithm. We define a criterion that must be satisfied in order that a problem can be classified as having a one-dimensional intrinsic property. An algorithm is developed to test any given problem to see if it possesses this property. We then show that any problem possessing the intrinsic property can be solved by means of an efficient dynamic programming algorithm developed earlier by one of the authors.
SUMT (Revisited)
Authors: Nash Stephen G.
Published: November 2008

Fiacco and McCormick's 1968 book is a classic. It arose out of the authors' activities at the Research Analysis Corporation, and as such it is the record of an ambitious and productive collaboration. But it is more than that. The topics they studied and the situations they encountered are representative of the experiences of other researchers in the 1960s. At a deeper level, Fiacco and McCormick's book illustrates the influence of two great traditions of research: one based on linear programming, and the other based on the calculus of variations. The work of Fiacco and McCormick remains influential, as do the influences of these two traditions. An understanding of these influences illuminates not only the history of nonlinear programming, but also its present and future.
Individual Equilibrium and Learning in Processor Sharing Systems
Authors: Altman Eitan , Shimkin Nahum
Published: November 2008

We consider a processor-sharing service system, where the service rate to individual customers decreases as the load increases. Each arriving customer may observe the current load and should then choose whether to join the shared system. The alternative is a constant-cost option, modeled here for concreteness as a private server (e.g., a personal computer that serves as an alternative to a central mainframe computer). The customers wish to minimize their individual service times (or an increasing function thereof). However, the optimal choice for each customer depends on the decisions of subsequent ones, through their effect on the future load in the shared server. This decision problem is analyzed as a noncooperative dynamic game among the customers. We first show that any Nash equilibrium point consists of threshold decision rules and establish the existence and uniqueness of a symmetric equilibrium point. Computation of the equilibrium threshold is demonstrated for the case of Poisson arrivals, and some of its properties are delineated. We next consider a reasonable dynamic learning scheme, which converges to the symmetric Nash equilibrium point. In this model customers simply choose the better option based on available performance history. Convergence of this scheme is illustrated here via a simulation example and is established analytically in subsequent work.