bluuebunny/crossref_metadata_2025 huggingface dataset:
Allocation of Chips to Wafers in a Production Problem of Semiconductor Kits
Authors: Seshadri Sridhar , Shanthikumar J. G.
Published: November 2008

The problem of maximizing the production of good sets of semiconductor chips under random yield is reexamined in this paper. (A set of semiconductor chips is called a semiconductor kit.) This problem has been considered by Avram and Wein (Avram, F., L. Wein. 1992. A product design problem in semiconductor manufacturing. Opns. Res. 40(5) 986–998.) and Singh et al. (Singh, M. R., C. T. Abraham, R. Akella. 1988. Planning for production of a set of components when yield is random. Fifth IEEE CHMT Internat. Electronic Manufacturing Technology Proc.). To solve this problem we show that under certain combinations of assumptions the production process can be replaced by a black box. The use of the black box model considerably simplifies the analysis and reduces the simulation effort required for carrying out parametric analysis of the proposed solution procedure. The model includes that of Avram and Wein, and we extend their results to more general settings and strengthen their conclusions. Using the black box model, it is shown that the strategy of placing different types of chips on a single wafer gives larger yield of kits in a stochastic sense than the traditional method of placing single types of chips on a wafer. We compare the production of kits under different chip design and lot release policies and also carry out a parametric analysis with respect to factors such as set proportions and yield.
Understanding Linear Programming Modeling Through an Examination of the Early Papers on Model Formulation
Authors: Murphy Frederic H. , Panchanadam Venkat
Published: November 2008

We use the models of cognitive psychology and the early literature on linear programming models to understand how experts organize their thinking about models. We show that several different patterns appear in the way models are related to each other. This paper also is a kind of cognitive history of the formulation of linear programming models in the first decade after the invention of the field.
Numerical Solution of Piecewise-Stationary Mt/Gt/1 Queues
Authors: Choudhury Gagan L. , Lucantoni David M. , Whitt Ward
Published: November 2008

We develop an algorithm for computing the (exact) cumulative distribution function of the time-dependent workload in a piecewise-stationary Mt/Gt/1 queue with a work-conserving service discipline and general service-time distributions, where service times are determined at arrival instants. The t subscripts indicate that the arrival rate and the general service-time distribution may change with time, but we allow changes only at finitely many time points. The algorithm is based on numerical transform inversion, using the classical Takács double-transform of the transient workload in an M/G/1 queue recursively over the successive stationary intervals. In particular, we apply our recently developed Fourier-series-based inversion algorithms for two-dimensional transforms and nested one-dimensional transforms. We also do additional work to greatly speed up the computation while tightly controlling the error. As a consequence, the computation time grows only quadratically with the number of intervals. The algorithm is effective for ten or fewer intervals, where the intervals may have unlimited and possibly unequal lengths, typically running in at most a few minutes and maintaining high accuracy. We have also demonstrated that the algorithm can solve a 21-interval example with 7-to-10-digit accuracy in about half an hour. Models with only a few intervals are useful to study overload control strategies.
Asymptotically Optimal Routing and Servive Rate Allocation in a Multiserver Queueing System
Authors: Shanthikumar J. George , Xu Susan H.
Published: November 2008

We consider a single stage queueing system with c heterogeneous servers. Customers arrive at this system according to a renewal process with mean 1/λ and squared coefficient of variation (scv) Ca2. An incoming customer is routed to server i with probability θi, ∑i=1cθi = 1. The service times at server i are i.i.d random variables with mean 1/μi, and scv Csi2. The holding cost rate of queue i is hi per customer, i = 1, 2, …, c. The problems of interest are twofold: (a) for a fixed service rate allocation μi, ∑i=1c μi = μ, find the routing probabilities, θi*, ∑i=1c θi* = 1, that minimize the average total holding cost; and (b) for fixed routing probabilities θi, ∑i=1c θi, and total service rate μ, find the service rate allocation μi* = μδi*, ∑i=1c δi* = 1, that minimizes the average total holding cost of the system. For each problem, we characterize the optimal policy under heavy traffic conditions. We also derive the routing probabilities, θ̂i (proportions δ̂i), i = 1, …, c, that are strongly asymptotically optimal. That is, the difference between the average total holding costs under θ̂i, i = 1, …, c, and θi*, i = 1, …, c (δ̂i, i = 1, …, c, and δi*, i = 1, …, c) is bounded by a fixed constant independent of the routing probabilities (proportions) and the arrival rate. In addition, we discuss the necessity and sufficiency of the accurate knowledge of the means and scvs of the interarrival and service times m obtaining asymptotically optimal policies.
Cellular Manufacturing: A Statistical Review of the Literature (1965–1995)
Authors: Reisman Arnold , Kumar Ashok , Motwani Jaideep , Cheng Chun Hung
Published: November 2008

This paper is both an extension and an expansion of two earlier studies concerned with the direction of OR/MS research as reported in its archival literature (Reisman and Kirschnick [Reisman, A., F. Kirshnick. 1994. The devolution of OR/MS: Implications from a statistical content analysis of papers in flagship journals. Opns. Res. 42(4) 577–588], [Reisman, A., F. Kirshnick. 1995. Research strategies used by OR/MS workers as shown by an analysis of papers in flagship journals. Opns. Res. 43(5) 731–739.]). All of these papers provide a content analysis of the OR/MS archival journals. However, this paper focuses on the entire life-cycle literature of Cellular Manufacturing as a module of OR/MS. It addresses the research strategy employed by, and the theory-vs-applied orientation exhibited by, the authors. In all, 235 articles, starting in 1969, were reviewed and classified on a five-point scale, ranging from pure theory to bonafide applications. Secondly, the articles were classified in terms of seven types of research processes used by authors. Next, statistical correlations were performed relating data from the above classifications. The findings show that the literature is dominated (94 papers, or 40%) by articles classified as pure theory using synthetic “data” and the ripple or incremental process as a basic research strategy.

During the first decade of cellular manufacturing research (1969 through 1978) this subset accounted for but 4 out of 42 (or 9.5%) of the papers published, whereas during the most recent decade it accounted for 81 papers (or 47.4%) of the literature. Lastly, the article raises questions about the future of cellular manufacturing research vis-à-vis other related subject matter.
Lot Streaming in Job-Shop Scheduling
Authors: Dauzère-Pérès Stéphane , Lasserre Jean-Bernard
Published: November 2008

The issue in Lot Streaming is how to split lots into sublots in order to improve the makespan (or some other criterion). We present a model and an iterative procedure for a general job-shop environment. The procedure alternates between solving a lot-sizing problem with a given sequence of sublots on the machines, and a standard job-shop scheduling problem with fixed sublot sizes. We report the computational results on a significant sample of 120 job-shop and flow-shop scheduling problems (including the famous 10–10). In case of no setup, in a few iterations, the makespan approaches a lower bound using very few sublots, suggesting that the procedure yields a global optimum. As a by-product, this result somehow validates the capacitated lot-sizing models in which the detailed capacity constraints, induced by the sequencing of operations, are ignored.
Optimal Control of a Multiclass, Flexible Queueing System
Authors: Gans Noah , van Ryzin Garrett
Published: November 2008

We consider a general class of queueing systems with multiple job types and a flexible service facility. The arrival times and sizes of incoming jobs are random, and correlations among the sizes of arriving job types are allowed. By choosing among a finite set of configurations, the facility can dynamically control the rates at which it serves the various job types. We define system work at any given time as the minimum time required to process all jobs currently in the backlog. This quantity is determined by solving a linear program defined by the set of processing configurations.

The problem we study is how to dynamically choose configurations to minimize the time average system work. Using bounds and heuristics, we analyze a class of service policies that is provably asymptotically optimal as system utilization approaches one, as well as a policy that in numerical studies performs near-optimally in moderate traffic. Our analysis also yields a closed-form expression for the optimal, average work in heavy traffic.

This general problem has a number of applications in job shop and flexible manufacturing, in service organizations, and in the management of parallel processing and distributed database systems.
An Information Based Multiechelon Inventory System with Emergency Orders
Authors: Moinzadeh Kamran , Aggarwal Prabhu K.
Published: November 2008

In this paper we study a (S-1, S) type multiechelon inventory system where all the stocking locations have the option to replenish their inventory through either a normal or a more expensive emergency resupply channel. When ordering a unit, each stocking location decides which channel to use based on its inventory level and the remaining leadtimes of the its outstanding orders. We consider the implications of this policy by developing expressions for the operating characteristics of the system and describing a procedure for finding the optimal policy parameters. A numerical study presented in the paper indicates that when alternative resupply modes are available our policy, which incorporates the information on the remaining leadtimes of the outstanding orders in selecting the resupply mode, can result in considerable cost savings when compared to policies which allow a single resupply mode.
The Optimal Review Period in a Dynamic Inventory Model
Authors: Flynn James , Garstka Stanley
Published: November 2008

Consider a single-item, periodic review, infinite-horizon, undiscounted, inventory model with stochastic demands, proportional holding and shortage costs, and full backlogging. Orders can arrive in every period, and the cost of receiving them is negligible (as in a JIT setting). Every T periods, one observes the current stock level and orders deliveries for the next T periods, thus incurring a fixed setup cost. The goal is to find a review period T and an ordering policy that minimize the long run expected average cost per period. Flynn and Garstka (Flynn, J., S. Garstka. 1990. A dynamic inventory model with periodic auditing. Opns. Res. 38 1089–1103.) characterize an optimal ordering policy when T is fixed and study a myopic policy whose cost is often close to the optimal cost. This paper covers the problem of selecting T. We prove an optimal review period T* exists, characterize its properties, and present methods for its computation. We also study an approximation to T* based on the myopic policy of our earlier paper and a crude but simple approximation expressing T* in terms of the two-thirds power of the model parameters. Analytic results (where the coefficient of variation of demand is small) and computational experiments suggest both approximations perform well when demands are normal.
A New and Fast Approach to Very Large Scale Integrated Sequential Circuit Test Generation
Authors: Adams J. B. , Hochbaum D. S.
Published: November 2008

We present a new approach to automatic test pattern generation for very large scale integrated sequential circuit testing. This approach is more efficient than past test generation methods, since it exploits knowledge of potential circuit defects. Our method motivates a new combinatorial optimization problem, the Tour Covering Problem. We develop heuristics to solve this optimization problem, then apply these heuristics as new test generation procedures. An empirical study comparing our heuristics to existing methods demonstrates the superiority of our approach, since our approach decreases the number of input vectors required for the test, translating into a reduction in the time and money required for testing sequential circuits.
Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime
Authors: Hochbaum Dorit S. , Landy Dan
Published: November 2008

This paper addresses a problem of batch scheduling which arises in the burn-in stage of semiconductor manufacturing. Burn-in ovens are modeled as batch-processing machines which can handle up to B jobs simultaneously. The processing time of a batch is equal to the longest processing time among the jobs in the batch. The scheduling problem involves assigning jobs to batches and determining the batch sequence so as to minimize the total flowtime. In practice, there is a small number m of distinct job types. Previously, the only solution techniques known for the single-machine version of this problem were an O(m23Bm+1) pseudopolynomial algorithm, and a branch-and-bound procedure. We present an algorithm with a running time of O(m23m), which is independent of B, the maximum batch size. We also present a polynomial heuristic for the general problem (when m is not fixed), which is a two-approximation algorithm. For any problem instance, this heuristic provides a solution at least as good as that given by previously known heuristics. Finally, we address the m-type problem on parallel machines, providing an exact pseudopolynomial algorithm and a polynomial approximation algorithm with a performance guarantee of (1 + √2)/2.
Cyclic Scheduling in a Stochastic Environment
Authors: Zhang Hongtao , Graves Stephen C.
Published: November 2008

Cyclic or periodic schedules can be implemented in a job shop where demands for various products have a stable rate and mix. Numerous results on cyclic scheduling in deterministic settings are available, but studies considering uncertainties such as machine failure are rare. This paper examines the behavior of cyclic schedules in a stochastic environment characterized by random machine failures that may delay execution of tasks and thus may cause the actual production to deviate from a specified cyclic schedule. The authors intend to understand the behavior of cyclic schedules under uncertainty and to find those cyclic schedules that are the least disturbed by occurrences of machine failure. The cyclic scheduling problem of one or multiple machines can be formulated into a convex program for which the objective is to minimize a weighted sum of expected ergodic delays experienced by tasks. For one-machine schedules, the ergodic distributions of delays, as well as their expected values, are displayed. For multiple-machine schedules, a necessary condition for ergodicity is presented and stochastic lower bounds on task delays are derived.
98%-Effective Lot-Sizing for Assembly Inventory Systems with Backlogging
Authors: Sun Daning , Atkins Derek
Published: November 2008

In the previous work, we have shown that for a production/inventory system arranged in series with backlogging at its final product, the total cost of the best power-of-two frequency lot-size heuristic is within 6% of the optimal (or 2% if the base period is allowed to vary). In this paper, we extend our results to an assembly production/inventory system with constant external demand at its final product with backlogging allowed. By using a submodular property, we show that the total cost of any feasible policy is bounded below by finding the minimum of a set of series systems. In this way, we can get a best power-of-two frequency policy that is within 2% of the optimal: However, the number of series systems to be considered can be proportional to, in the worst case, the factorial of n (the number of nodes in the assembly system). As a consequence, this reduction cannot give us a polynomial algorithm and we have to use a different approach. By using a series of transformations, we reduce our problem to a special case of a polymatroidal network flow problem. The lower bound and the optimal power-of-two frequency policy for assembly systems with backlogging can then be found in O(n6) time.
Lot Sizing with Randomly Graded Yields
Authors: Nahmias Steven , Moinzadeh Kamran
Published: November 2008

We consider a single inventory item that is graded into one of two quality levels after production. The proportion of grade one units produced in a lot is a random variable assumed to follow the lognormal distribution. Demands for grade 2 may be filled with grade 1 product, but not vice versa. Assuming that demands for the two grades are known and constant, we develop a continuous review model in which cycles are defined as times when total inventory equals zero. Since grade 1 inventory may be depleted before total stock and shortages are not permitted, cycles may consist of multiple set-ups. We show that the optimal order-to-point, S, has a form similar to the EOQ. Tables of the CDF of an appropriately defined unit normal multivariate distribution are incorporated into a spreadsheet to facilitate calculations for any parameter setting.
A Note on the Optimal Positioning of Service Units
Authors: Carrizosa E. , Muñoz-Márquez M. , Puerto J.
Published: November 2008

In this paper we address the problem of locating p mobile service units in an n-dimensional space minimizing the expected response time. It is shown that an optimal solution to the problem is a degenerate distribution for the service, concluding that it is optimal to park the p units. This extends previous results in the literature for location on a segment.
Comments on the Paper: ‘Heuristic and Special Case Algorithms for Dispersion Problems’ by S. S. Ravi, D. J. Rosenkrantz, and G. K. Tayi
Authors: Tamir Arie
Published: November 2008

The paper discusses Max-Min Facility Dispersion (MMFD) and Max-Avg Facility Dispersion (MAFD) problems. These problems are the subject of a paper by Ravi et al. (1994). The results presented in that paper include a simple heuristic for MMFD which provides a performance guarantee of 1/2, and a similar heuristic for MAFD with a performance guarantee of 1/4. It is also proved there that obtaining a performance guarantee of more than 1/2 for MMFD is NP-hard. For the two-dimensional version of MAFD, Ravi et al.'s paper presents a heuristic with an asymptotic performance guarantee of 2/p. Further additional comments in this direction are given.
Multiairport Ground Holding Problem: A Computational Evaluation of Exact Algorithms
Authors: Andreatta Giovanni , Brunetta Lorenzo
Published: November 2008

Congestion in the air traffic network is becoming an increasingly serious problem that causes inconvenience to passengers, losses to airlines and, last but not least, threats to airspace safety. One way of reducing the amount of congestion is to use Ground Holding policies, i.e., to impose on selected aircraft a ground holding prior to their departure so that congestion during peak periods of time may be smoothed away. In this paper we restrict our attention to the Multiairport Ground Holding problem, where congestion may arise only at the airports due to limited arrival capacity. There are a few algorithms that, under suitable hypotheses, find an “optimal” policy for the Multiairport Ground Holding problem. In this paper we evaluate and compare computationally three of them, namely, the one recently proposed by Vranas, Bertsimas and Odoni, the one suggested by Andreatta and Tidona and that due to Bertsimas and Stock. The computational evaluation is based on two sets of test problems. The first set consists of seven problems taken from the literature. The second set consists of 32 “realistic” test problems. The results indicate the superiority of the Bertsimas and Stock approach among the three models considered.
Reflections and Projections on Creativity in Operations Research and Management Science: A Pressing Need for a Shift in Paradigm
Authors: Saaty Thomas L.
Published: November 2008

This paper is an outgrowth of a talk given at a plenary session of the national meeting of ORSA/TIMS (now INFORMS) in May of 1996. Rather than speculate on what might be the possible domain of OR/MS within a systems framework, the paper gives a sketch of what basic ideas there are today that can help us get to a unified mathematical theory of the subject. The concept of influence occurs in all fields of knowledge—from physics, with its gravitational and electromagnetic influences, to sociology with its societal, political, economic, and technological influences. We argue that influence, a sensed, perceived or inferred stimulus, is the single most central concept for analyzing causal relations in OR/MS problems. Problem solving is contextual and focuses on the distribution of influence in allocation, queuing, inventory, and similar problems by manipulating measurable quantities. Because most influences are abstract and intangible, emphasis on creating structures to represent and measure the flow of influence of intangibles and their propagation is critical for the development of a general scientific theory for OR/MS, more critical than in any other field because our problem domain is very general and interdisciplinary. The paper advocates the need for a systemic integration of the diverse approaches used in OR/MS within a single framework for all areas, including dependencies and feedback among influences to maintain the full integrity of the problems we solve. Examples and illustrations are given together with observations about the use of creativity and intelligence to move the process of creating a theory beyond the traditional process of problem solving.
Probabilistic Analyses and Practical Algorithms for Inventory-Routing Models
Authors: Chan Lap Mui Ann , Federgruen Awi , Simchi-Levi David
Published: November 2008

We consider a distribution system consisting of a single warehouse and many geographically dispersed retailers. Each retailer faces demands for a single item which arise at a deterministic, retailer specific rate. The retailers' stock is replenished by a fleet of vehicles of limited capacity, departing and returning to the warehouse and combining deliveries into efficient routes. The cost of any given route consists of a fixed component and a component which is proportional with the total distance driven. Inventory costs are proportional with the stock levels. The objective is to identify a combined inventory policy and a routing strategy minimizing system-wide infinite horizon costs. We characterize the asymptotic effectiveness of the class of so-called Fixed Partition policies and those employing Zero Inventory Ordering. We provide worst case as well as probabilistic bounds under a variety of probabilistic assumptions. This insight is used to construct a very effective algorithm resulting in a Fixed Partition policy which is asymptotically optimal within its class. Computational results show that the algorithm is very effective on a set of randomly generated problems.
A Scaling Algorithm for Multicommodity Flow Problems
Authors: Schneur Rina R. , Orlin James B.
Published: November 2008

We present a penalty-based algorithm that solves the multicommodity flow problem as a sequence of a finite number of scaling phases. The basis of the algorithm is simple and consists of iteratively detecting and sending flow around negative cost cycles. Two parameters control the algorithm's behavior: the penalty parameter and the scaling parameter. In the ε-scaling phase, where ε is a function of the penalty and scaling parameters, the algorithm determines an ε-optimal solution; a solution in which complementary slackness conditions are satisfied to within ε. We analyze the performance of the algorithm from both the theoretical and practical perspectives. The computational results support the theoretical behavior of the algorithm. They also demonstrate the efficiency of the algorithm for solving problem instances of different structure and size.
On Derivative Estimation of the Mean Time to Failure in Simulations of Highly Reliable Markovian Systems
Authors: Nakayama Marvin K.
Published: November 2008

The mean time to failure (MTTF) of a Markovian system can be expressed as a ratio of two expectations. For highly reliable Markovian systems, the resulting ratio formula consists of one expectation that cannot be estimated with bounded relative error when using standard simulation, while the other, which we call a nonrare expectation, can be estimated with bounded relative error. We show that some derivatives of the nonrare expectation cannot be estimated with bounded relative error when using standard simulation, which in turn may lead to an estimator of the derivative of the MTTF that has unbounded relative error. However, if particular importance-sampling methods (e.g., balanced failure biasing) are used, then the estimator of the derivative of the nonrare expectation will have bounded relative error, which (under certain conditions) will yield an estimator of the derivative of the MTTF with bounded relative error.
Managing Redundancy in Distributed Computer Networks: A State Transition Graph Approach for the Stashing Problem
Authors: Walker Brian , Sansó Brunilde
Published: November 2008

Managing redundant information is becoming an important issue in today's increasingly large distributed computer networks. As total redundancy is extremely costly to achieve, it has been proposed to keep perfectly updated information only at the servers, while keeping old copies of that information on local computers. For such copies to be useful, a maximum lifetime length is assigned to them. Before the lifetime has elapsed, the local devices must be stashed with a new updated copy. The problem of optimizing the updates so that the maximum lifetime length constraints are respected has been previously formulated as a binary problem and proved to be NP-hard through a reduction to the Steiner tree problem in graphs. In this paper we explore the properties of another formulation, based on a state transition graph approach. We prove that only a subset of states and transitions will be in the optimal solution and that, thanks to those properties, it is possible to greatly reduce the size of the graph. A solution algorithm that is based on an efficient evaluation of similar Steiner tree problems with similar properties is presented. We discuss extensions of this problem to future applications of broadband multicast services.
Branch-and-Price: Column Generation for Solving Huge Integer Programs
Authors: Barnhart Cynthia , Johnson Ellis L. , Nemhauser George L. , Savelsbergh Martin W. P. , Vance Pamela H.
Published: November 2008

We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of nonbasic variables to generate new columns or to prove LP optimality at a node of the branch-and-bound tree. We present classes of models for which this approach decomposes the problem, provides tighter LP relaxations, and eliminates symmetry. We then discuss computational issues and implementation of column generation, branch-and-bound algorithms, including special branching rules and efficient ways to solve the LP relaxation. We also discuss the relationship with Lagrangian duality.
Solving a Truck Dispatching Scheduling Problem Using Branch-and-Cut
Authors: Bixby Robert E. , Lee Eva K.
Published: November 2008

A branch-and-cut IP solver is developed for a class of structured 0/1 integer programs arising from a truck dispatching scheduling problem. This problem involves a special class of knapsack equality constraints. Families of facets for the polytopes associated with individual knapsack constraints are identified. In addition, a notion of “conflict graph” is utilized to obtain an approximating node-packing polytope for the convex hull of all 0/1 solutions. The branch-and-cut solver generates cuts based on both the knapsack equality constraints and the approximating node-packing polytope, and incorporates these cuts into a tree-search algorithm that uses problem reformulation and linear programming-based heuristics at each node in the search tree to assist in the solution process. Numerical experiments are performed on large-scale real instances supplied by Texaco Trading & Transportation, Inc. The optimal schedules correspond to cost savings for the company and greater job satisfaction for drivers due to more balanced work schedules and income distribution.
Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems
Authors: Sherali Hanif D. , Adams Warren P. , Driscoll Patrick J.
Published: November 2008

A new hierarchy of relaxations is presented that provides a unifying framework for constructing a spectrum of continuous relaxations spanning from the linear programming relaxation to the convex hull representation for linear mixed integer 0-1 problems. This hierarchy is an extension of the Reformulation-Linearization Technique (RLT) of Sherali and Adams (1990, 1994a), and is particularly designed to exploit special structures. Specifically, inherent special structures are exploited by identifying particular classes of multiplicative factors that are applied to the original problem to reformulate it as an equivalent polynomial programming problem, and subsequently, this resulting problem is linearized to produce a tighter relaxation in a higher dimensional space. This general framework permits us to generate an explicit hierarchical sequence of tighter relaxations leading up to the convex hull representation. (A similar hierarchy can be constructed for polynomial mixed integer 0-1 problems.) Additional ideas for further strengthening RLT-based constraints by using conditional logical implications, as well as relationships with sequential lifting, are also explored. Several examples are presented to demonstrate how underlying special structures, including generalized and variable upper bounding, covering, partitioning, and packing constraints, as well as sparsity, can be exploited within this framework. For some types of structures, low level relaxations are exhibited to recover the convex hull of integer feasible solutions.
Note on “Parallel Machine Scheduling with Batch Setup Times”
Authors: Webster Scott
Published: November 2008

Cheng and Chen (1994) use a high-multiplicity encoding scheme to prove binary NP-hardness of a scheduling problem. From this they infer a similar result for a well-known, more general problem. We explain that, although their initial proof is correct, their inference about the more general problem is not.
Tandem Queues with Blocking: A Comparison Between Dependent and Independent Service
Authors: Browning Sharon Guy
Published: November 2008

This paper considers tandem queues with finite buffers. Throughput values for the cases of independent and dependent service are compared, where in the dependent case a given customer has the same service time at each station. It is shown that for sufficiently large buffer sizes, dependent throughput is greater than independent. Simulation results that demonstrate this phenomenon are given.
The Stock Size Problem
Authors: Kellerer Hans , Kotov Vladimir , Rendl Franz , Woeginger Gerhard J.
Published: November 2008

Consider a number of jobs that have to be completed within some fixed period of time. Each job consumes or supplies a certain, job-dependent quantity of a resource thus changing the contents of a stock. Natural examples for this scenario arise in the case of trucks delivering goods to a trade house and taking other goods away from it, or in the case where processes change their environment. The goal is to find an ordering of the jobs such that all jobs can be completed and such that the maximum stock size needed over the time period becomes minimum. Since this problem can be shown to be NP-hard, we present three polynomial time approximation algorithms which yield job sequences with maximum stock size at most 2, respectively 8/5 times and 3/2 times the optimum stock size. These approximation algorithms are also compared by a numerical simulation. Moreover, we consider a variation of the problem where consecutive processes are allowed to directly exchange resources without using the stock.
An Inventory Model with Order Crossover
Authors: He Xin X. , Xu Susan H. , Ord J. Keith , Hayya Jack C.
Published: November 2008

In inventory systems with stochastic lead times, it is possible that more than a single order will be outstanding. In that case, orders may cross; that is, they may not be received in the same sequence in which they are placed. In this paper we develop a multicycle analysis for the case when lead times are independently and identically distributed. When contrasted with the conventional single cycle analysis, the multicycle approach provides a more accurate assessment of the overall inventory cost and leads to a superior inventory policy.
Evaluation of Installation Stock Based (R, Q)-Policies for Two-Level Inventory Systems with Poisson Demand
Authors: Axsäter Sven
Published: November 2008

We consider a two-level inventory system with one warehouse and N retailers. Leadtimes (transportation times) are constant, and the retailers face different Poisson demand processes. All facilities apply continuous review installation stock (R, Q)-policies with different reorder points and batch quantities. We show how to evaluate holding and shortage costs exactly in case of two retailers. In case of more than two retailers we use the same methodology as an approximation. When evaluating costs at a certain retailer, the other retailers are then aggregated into a single retailer.
Multiclass Production Systems with Setup Times
Authors: Righter Rhonda , Shanthikumar J. George
Published: November 2008

We consider polling systems with random setup times, and show that if setup times are reduced in the convex ordering sense, then waiting times, work loads, and queue sizes will be reduced in the usual stochastic sense. We also show that the joint distributions of various performance measures across time are invariant under shifts in setup times as long as the net shift is zero.
Scheduling with Finite Capacity Input Buffers
Authors: Hall Nicholas G. , Posner Marc E. , Potts Chris N.
Published: November 2008

In many scheduling problems, a newly released job must be stored in an input buffer while it waits to begin processing. The lack of attention given to these buffers in the classical scheduling literature results from the implicit assumption that they have infinite capacity. In modern manufacturing environments, however, there are several important reasons for limiting buffer capacity. We study nonpreemptive single machine dynamic scheduling problems under the assumption that some jobs may be lost, either because of insufficient input buffer capacity, or because due dates cannot be met. The objective is to minimize the weighted or unweighted number of lost jobs. We study problems with zero, fixed or arbitrary buffer capacity, with unit or arbitrary processing times, and with unit or arbitrary buffer storage requirements. We present a complexity classification in which, for each problem, either an efficient algorithm is derived, or a proof is given that such an algorithm is unlikely to exist.
A Subassembly Manufacturing Yield Problem with Multiple Production Runs
Authors: Nandakumar Purushottaman , Rummel Jeffrey L.
Published: November 2008

We consider the assembly of a product that needs to exceed a certain length. The subassemblies are manufactured with a planned length setting. The resulting lengths of the subassemblies are not known with certainty, and vary about the planned setting. After the subassemblies are manufactured, those that fall short are rerun. This process is repeated until all subassemblies exceed the required length. We build and solve a model, to specify the planned length at each run, that minimizes the expected cost of production.
AN (S − 1, S) Inventory System with Fixed Shelf Life and Constant Lead Times
Authors: Perry David , Posner M. J. M.
Published: November 2008

We consider an (S − 1, S) type perishable inventory system in which the maximum shelf life of each item is fixed. An order for an item is placed at each demand time as well as at each time that the maximum shelf life of an item is reached. The order lead times are constant, and the demand process for items is Poisson. Although the resulting process is ostensibly nonregenerative, we adapt level-crossing theory for the case of an S-dimensional Markov process to obtain its stationary law. Within this framework a number of model variants are solved.
Drive: Dynamic Routing of Independent Vehicles
Authors: Savelsbergh Martin , Sol Marc
Published: November 2008

We present DRIVE (Dynamic Routing of Independent VEhicles), a planning module to be incorporated in a decision support system for the direct transportation at Van Gend and Loos BV. Van Gend and Loos BV is the largest company providing road transportation in the Benelux, with about 1400 vehicles transporting 160,000 packages from thousands of senders to tens of thousands of addressees per day. The heart of DRIVE is a branch-and-price algorithm. Approximation and incomplete optimization techniques as well as a sophisticated column management scheme have been employed to create the right balance between solution speed and solution quality. DRIVE has been tested by simulating a dynamic planning environment with real-life data and has produced very encouraging results.
Models for Design and Control of Single Server Polling Computer and Communication Systems
Authors: Lee Thomas (Yew Sing)
Published: November 2008

The evolution of communication technology and the competitive software design environment dictates that performance characterization involves iterations between real-world design and its representation for modeling purposes. In this paper, models and analytical techniques are developed to evaluate the performance of single-server polling computer and communication systems, e.g., multiplexers or local area networks with a single token passing medium access protocol. We present a novel methodology for the design and control of such communication systems and computer systems. Our approach allows the handling of smooth, correlated, and bursty traffic, whereas traditional analytical approaches have depended on a Poisson traffic model. The methodology also provides a unified treatment of several existing methodologies for controlling single-server polling computer and communication systems.
Near-Optimal Echelon-Stock (R, nQ) Policies in Multistage Serial Systems
Authors: Chen Fangruo , Zheng Yu-Sheng
Published: November 2008

We study echelon-stock (R, nQ) policies in a multistage, serial inventory system with compound Poisson demand. We provide a simple method for determining near-optimal control parameters. This is achieved in two steps. First, we establish lower and upper bounds on the cost function by over- and under-charging a penalty cost to each upstream stage for holding inadequate stock. Second, we minimize the bounds, which are simple, separable functions of the control parameters, to obtain heuristic solutions. We also provide an algorithm that guarantees an optimal solution at the expense of additional computational effort. A numerical study suggests that the heuristic solutions are easy to compute (even for systems with many stages) and are close to optimal. It also suggests that a traditional approach for determining the order quantities can be seriously suboptimal. All the results can be easily extended to the discrete-time case with independent, identically distributed demands.
Modeling of Transport Risk for Hazardous Materials
Authors: Erkut Erhan , Verter Vedat
Published: November 2008

The transport of hazardous materials is an important strategic and tactical decision problem. Risks associated with this activity make transport planning difficult. Although most existing analytical approaches for hazardous materials transport account for risk, there is no agreement among researchers on how to model the associated risks. This paper provides an overview of the prevailing models, and addresses the question “Does it matter how we quantify transport risk?” Our empirical analysis on the U.S. road network suggests that different risk models usually select different “optimal” paths for a hazmat shipment between a given origin-destination pair. Furthermore, the optimal path for one model could perform very poorly under another model. This suggests that researchers and practitioners must pay considerable attention to the modeling of risks in hazardous materials transport.
Stopping Rules for a Class of Sampling-Based Stochastic Programming Algorithms
Authors: Morton David P.
Published: November 2008

Monte Carlo sampling-based algorithms hold much promise for solving stochastic programs with many scenarios. A critical component of such algorithms is a stopping criterion to ensure the quality of the solution. In this paper, we develop a stopping rule theory for a class of algorithms that estimate bounds on the optimal objective function value by sampling. We provide rules for selecting sample sizes and terminating the algorithm under which asymptotic validity of confidence intervals for the quality of the proposed solution can be verified. Empirical coverage results are given for a simple example.
Optimal Placement of Add/Drop Multiplexers: Heuristic and Exact Algorithms
Authors: Sutter Alain S. , Vanderbeck François , Wolsey Laurence
Published: November 2008

We study a problem that has arisen recently in the design of telecommunications transmission networks at France Telecom. Given a set of centers in a city or conglomeration linked together on a ring architecture, given the expected demands between the centers and an essentially unlimited availability of rings of fixed capacity on the network, assign demand pairs and corresponding add/drop multiplexers to the rings so as to satisfy the demands and minimize the number of “costly” multiplexers installed.

Heuristics based on simulated annealing have been developed for the basic problem and several variants. France Telecom is particularly interested in validating the effectiveness of the heuristics. An exact algorithm based on integer column generation is shown to provide tight performance guarantees, and in most cases to give provable minimum cost solutions. Column generation is used even though the subproblems are strongly NP-hard and are solved by standard mixed integer programming software. In addition, the Master Problems involve both integer columns and integer variables, whereas these are 0–1 in most reported applications.
Resource Constrained Chain Scheduling of UET Jobs on Two Machines
Authors: Kubiak W. , Błażewicz J. , Dror M. , Katoh N. , Rock H.
Published: November 2008

A well-known technique for solving scheduling problems with two identical parallel processors and unit execution time jobs under a makespan minimization criteria involves finding maximum cardinality matchings in the graph associated with the problem, and then using these matchings to create optimal schedules. For some problem instances, however, this method will not work, since the problems are NP-hard. In this note, a previously open problem involving additional resource constraints is shown to have a polynomial algorithm using cardinality matching method.
Airline Network Design
Authors: Lederer Phillip J. , Nambimadom Ramakrishnan S.
Published: November 2008

The goal of this paper is to understand choices of networks and schedules by a profit maximizing airline. By “network” we mean the routing pattern for planes and by “schedule” we mean the frequency of service between cities and the amount of time put into the schedule to assure on-time arrival. This paper analyzes network and schedule choice using an “idealized” model that permits derivation of analytic, closed form expressions for airline and passenger costs. Many important conclusions are obtained. It is optimal for a profit maximizing airline to design its network and schedule to minimize the sum of airline and passenger costs. Profit maximizing choice of schedule frequency depends on the network. Direct service has lower schedule frequency than other networks.

Parametric studies are performed on the effect of distance between cities, demand rate, and the number of cities served on the choice of the network. Some conclusions are: (1) If the distance between cities is very small, then direct service is optimal; otherwise, other networks, such as hub and spoke are optimal. (2) Similarly, for very high demand rates, direct service is optimal; and for intermediate values, hub and spoke is optimal. (3) If the number of cities is small, direct service dominates; and if it is large, hub and spoke is optimal.

We note that any airline's schedule includes safety time as a buffer against delays, and we demonstrate that schedule reliability is highest for direct routing. Surprisingly, the amount of time that is added to the schedule to buffer delays is relatively less in direct networks than in other networks. This can explain the superior on-time performance and high equipment utilization of direct carriers such as Southwest Airlines.
On the Order Fill Rate in a Multi-Item, Base-Stock Inventory System
Authors: Song Jing-Sheng
Published: November 2008

A customer order to a multi-item inventory system typically consists of several different items in different amounts. The probability of satisfying an arbitrary demand within a prespecified time window, termed the order fill rate, is an important measure of customer satisfaction in industry. This measure, however, has received little attention in the inventory literature, partly because its evaluation is considered a hard problem. In this paper, we study this performance measure for a base-stock system in which the demand process forms a multivariate compound Poisson process and the replenishment leadtimes are constant. We show that the order fill rate can be computed through a series of convolutions of one-dimensional compound Poisson distributions and the batch-size distributions. This procedure makes the exact calculation faster and much more tractable. We also develop simpler bounds to estimate the order fill rate. These bounds require only partial order-based information or merely the item-based information. Finally, we investigate the impact of the standard independent demand assumption when the demand is actually correlated across items.