bluuebunny/crossref_metadata_2025 huggingface dataset:
Decomposition Algorithms for Analyzing Transient Phenomena in Multiclass Queueing Networks in Air Transportation
Authors: Peterson Michael D. , Bertsimas Dimitris J. , Odoni Amedeo R.
Published: November 2008

A previous paper (1992) by the same authors studied the phenomenon of transient congestion in landings at an airport and developed a recursive approach for computing moments of queue lengths and waiting times. This paper extends our approach to a network, developing two approximations based on the prior method. Both approaches work by using delay information estimated at one location to update arrival schedules at other points in the network. We present computational results for a simple 2-node network, comparing the performance of the approximations with an alternative simulation approach. The methods give similar results in light to moderate traffic but show a growing disparity under heavier traffic, where the algorithms underestimate the true magnitude of delay propagation relative to simulation. Finally, to illustrate the usefulness of the modeling, we show how the results may be used to explore the issue of interaction between airports. Although this particular application motivated development of the model, the method is, in principle, applicable to other multiclass queueing networks where service capacity at a station may be modeled as a Markov or semi-Markov process. The model represents a new approach for analyzing transient congestion phenomena in such networks.
Exploratory Evidence on the Behavior of Quality Costs
Authors: Ittner Christopher D.
Published: November 2008

This study examines the time series behavior of quality costs reported by 49 manufacturing units of 21 companies. Analyses using both pooled annual data and plant-specific quarterly data indicate that the majority of units in the sample achieved ongoing reductions in nonconformance costs while maintaining or reducing reported prevention and appraisal costs. These findings are consistent with recent quality-based learning and continuous improvement models which suggest that, once an effective quality program is established, companies can reduce nonconformance costs over time with little or no subsequent increase in conformance expenditures.
Forecasting and Inventory Management of Short Life-Cycle Products
Authors: Kurawarwala Abbas A. , Matsuo Hirofumi
Published: November 2008

In this paper, we provide an integrated framework for forecasting and inventory management of short life-cycle products. The literature on forecasting and inventory management does not adequately address issues relating to short life-cycle products. We first propose a growth model that can be used to obtain accurate monthly forecasts for the entire life cycle of the product. The model avoids limiting data requirements of traditional methods. Instead, it extracts relevant information from past product histories and utilizes the information on total life-cycle sales and the peak sales timing. Using disguised demand data from a personal computer (PC) manufacturer, we validate the model. Next, we model the inventory management problem for the short life-cycle environment. The uncertainty in demand is modeled through the uncertainty in the realized values of the parameters of the forecasting model. The high cost of terminal inventory, shortages, and rapidly changing procurement costs are all included in the model. Extensions to the basic model are also developed. Using optimal control theory, we derive a solution that provides valuable information on procurement cutoff time and terminal service levels. A detailed example explains the characteristics of the policy and its relevance in decision making. Many of the issues covered in the models were brought to our attention while implementing a forecasting model at a PC manufacturer. The benchmark monthly forecasts and the associated inventory levels provide information that can be very helpful in planning and controlling marketing, sales, and production.
Sequential Screening in Semiconductor Manufacturing, I: Exploiting Spatial Dependence
Authors: Longtin Mark D. , Wein Lawrence M. , Welsch Roy E.
Published: November 2008

This paper addresses a problem of simultaneous quality and quantity control motivated by semiconductor manufacturing. After wafers are fabricated, the individual chips on the wafers are probed, or electrically tested, and, in some cases, the probing facility is the bottleneck for the entire IC manufacturing process. Under this assumption, we consider the problem of choosing the optimal start rate of lots of wafers into the fabrication facility and the optimal chip screening policy in front of the probing facility to maximize the expected profit, which is the revenue from good chips minus the variable fabrication and probing costs. These decisions are subject to capacity constraints at both the wafer fabrication and probing facilities. Over 300 wafers from two industrial facilities are analyzed in this paper, and a Markov random field model is employed to capture the spatial clustering of bad chips. Chip screening strategies are proposed that exploit the various types of yield nonuniformities that are detected in the data, such as radial effects, spatial clustering of bad chips, and yield variation by chip location. The numerical results suggest that screening at the chip level can be highly profitable in a semiconductor manufacturing process constrained by its probe capacity.
Managing Hotel Reservations with Uncertain Arrivals
Authors: Bitran Gabriel R. , Gilbert Stephen M.
Published: November 2008

Based on our interactions with managers at two large hotels, we present a realistic model of the hotel reservation problem. Unlike traditional models, ours does not assume that all customers arrive simultaneously on the targeted booking date. We explain why this assumption may not be appropriate for the hotel industry and develop a model of reservation booking which explicitly includes the room allocation decisions which are made on the targeted booking date. Based on observations of how the problem is solved in practice as well as the insights gained from this analysis, we develop simple heuristic procedures for accepting reservations. Computational results demonstrate that these heuristics perform well relative to an upper bound that is based on perfect information about reservations requests and customer arrivals.
On the Simultaneous Optimization of Server and Work Allocations in Production Line Systems with Variable Processing Times
Authors: Hillier Frederick S. , So Kut C.
Published: November 2008

The allocation of servers and the allocation of work are two important decision variables in designing production line systems. Previous studies of each variable in isolation have found that throughput is maximized by using an allocation that gives preferential treatment to interior stations (especially center stations) over the two end stations. In this paper we study the simultaneous optimization of server and work allocations and obtain some surprising results of a different nature. One key finding is the L-phenomenon, whereby the throughput is maximized by assigning all extra servers over one per station to just one of the end stations and then adjusting the work allocation so that this station has by far the greatest amount of work per server. Another key finding is the multiple-server phenomenon, whereby extra servers add far more throughput per server than the initial one-per-station servers. Both findings have important implications for the design of some production line systems in ways that will greatly improve their efficiency. Similar conclusions are drawn when lower and/or upper bounds are imposed on the number of servers per station and the number of stations is included as a decision variable.
Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows
Authors: Bramel Julien , Simchi-Levi David
Published: November 2008

In the Vehicle Routing Problem with Time Windows, a set of customers are served by a fleet of vehicles of limited capacity, initially located at a central depot. Each customer provides a period of time in which they require service, which may consist of repair work or loading/unloading the vehicle. The objective is to find tours for the vehicles, such that each customer is served in its time window, the total load on any vehicle is no more than the vehicle capacity, and the total distance traveled is as small as possible. In this paper, we present a characterization of the asymptotic optimal solution value for general distributions of service times, time windows, customer loads and locations. This characterization leads to the development of a new algorithm based on formulating the problem as a stylized location problem. Computational results show that the algorithm is very effective on a set of standard test problems.
Optimal Dimensioning of Pipe Networks with Application to Gas Transmission Networks
Authors: de Wolf Daniel , Smeers Yves
Published: November 2008

We develop an algorithm to solve the problem of the optimal dimensioning of a fluid (gas or water) transmission network when the topology of the network is known. The pipe diameters must be chosen to minimize the sum of the investment and operating costs. This two stage problem is solved by application of the bundle method for nonsmooth optimization. The validity of the approach is tested on a problem corresponding to a real situation: the optimal design of a reinforcement of the Belgian gas network.
Basing Airtankers for Forest Fire Control in Ontario
Authors: MacLellan James I. , Martell David L.
Published: November 2008

The Ontario Ministry of Natural Resources (OMNR) operates a fleet of nine CL-215 airtankers for forest fire control. The aircraft are based at a small number of airports that serve as home bases, from which they are deployed to a larger set of airports that serve as initial attack bases for fire fighting operations each day. We helped regional fire managers derive subjective airtanker deployment rules that specified how many airtankers were to be deployed at each initial attack base each day. We then developed a mathematical programming model that was used to help identify a home-basing strategy that would minimize the average annual cost of satisfying daily airtanker deployment demands. Our analysis provided OMNR decision makers with valuable insight into airtanker management and was used to help decide where to base the OMNR airtankers for the 1993 and subsequent fire seasons.
The Delta-Wye Approximation Procedure for Two-Terminal Reliability
Authors: Chari Manoj K. , Feo Thomas A. , Provan J. Scott
Published: November 2008

The Delta-Wye Approximation Procedure (DWAP) is a procedure for estimating the two-terminal reliability of an undirected planar network G = (V, E) by reducing the network to a single edge via a sequence of local graph transformations. It combines the probability equations of Lehman—whose solutions provide bounds and approximations of two-terminal reliability for the individual transformations—with the Delta-Wye Reduction Algorithm of the second two authors—which performs the corresponding graph reduction in O(|V|2) time. A computational study is made comparing the DWAP to one of the best currently known methods for approximating two-terminal reliability, and it is shown that the DWAP produces approximations that are between 10 and 80 times as accurate.
A New Heuristic for Three-Machine Flow Shop Scheduling
Authors: Chen Bo , Glass Celia A. , Potts Chris N. , Strusevich Vitaly A.
Published: November 2008

This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An O(n log n) time heuristic that is based on Johnson's algorithm is presented. It is shown to generate a schedule with length at most 5/3 times that of an optimal schedule, thereby reducing the previous best available worst-case performance ratio of 2. An application to the general flow shop is also discussed.
Optimal Dynamic Scheduling Policy for a Make-To-Stock Production System
Authors: Ha Albert Y.
Published: November 2008

This paper considers the dynamic scheduling problem of a single-server, make-to-stock queue with two products. For the case of Poisson demands and exponential production times, we show that it is optimal to produce the product with the larger bμ index when it is backordered. If the production times are identically distributed, the optimal policy can further be characterized by monotone switching curves. We also prove that a base stock policy coupled with a switching curve is optimal for some initial inventory levels. A simple linear switching rule for determining production priority is proposed and compared with other heuristic policies in a computational experiment.
Instability of the Join-the-Shortest-Queue and FCFS Policies in Queueing Systems and Their Stabilization
Authors: Sharifnia Ali
Published: November 2008

We demonstrate the instability of the “join-the-shortest-queue” routing policy and the “first-come-first-served” dispatching policy for a multiclass single-station queuing system with multiple nonidentical servers. Although instability is demonstrated in a deterministic setting, we have found strong evidence that it is not limited to this setting. The phenomenon that leads to instability is different from the one reported recently in the literature for nonacyclic systems, namely, servers starvation. The systems considered here are acyclic, and instability is caused by the failure of the policies to assign jobs to servers in an efficient manner. A modification to the investigated policies is proposed to make them stable. The modified policies (called guided policies) provide an oversight control that ensure efficient utilization of the servers and hence stability.
The Stochastic Learning Curve: Optimal Production in the Presence of Learning-Curve Uncertainty
Authors: Mazzola Joseph B. , McCardle Kevin F.
Published: November 2008

Theoretical analyses incorporating production learning are typically deterministic: costs are posited to decrease in a known, deterministic fashion as cumulative production increases. This paper introduces a stochastic 1earning:curve model that incorporates random variation in the decreasing cost function. We first consider a discrete-time, infinite-horizon, dynamic programming formulation of monopolistic production planning when costs follow a learning curve. This basic formulation is then extended to allow for random variation in the learning process. We also explore properties of the resulting optimal policies. For example, in some of the stochastic models we analyze optimal production is shown to exceed myopic production, echoing a key result from the deterministic learning-curve literature. In other of the stochastic models, however, this result does not hold, underscoring the need for extended analysis in the stochastic setting. We also provide new insights in the deterministic setting: for example, while an increase in the learning rate leads to an increase in the firm's expected profits in the deterministic case, there is not necessarily an increase in the optimal policy—faster learners do not necessarily produce more.
Spatial Optimization of Prairie Dog Colonies for Black-Footed Ferret Recovery
Authors: Bevers Michael , Hof John , Uresk Daniel W. , Schenbeck Gregory L.
Published: November 2008

A discrete-time reaction-diffusion model for black-footed ferret release, population growth, and dispersal is combined with ferret carrying capacity constraints based on prairie dog population management decisions to form a spatial optimization model. Spatial arrangement of active prairie dog colonies within a ferret reintroduction area is optimized over time for maximum expected adult ferret population, This modeling approach is applied in an exploratory case study to a black-footed ferret reintroduction program in Badlands National Park and Buffalo Gap National Grassland, South Dakota. The model is currently being used to evaluate prairie dog population management alternatives and captive-bred ferret release locations for the Buffalo Gap National Grassland. This approach is also being adapted for use on other grasslands and with other species in the northern Great Plains.
Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem
Authors: Kroon Leo G. , Salomon Marc , Van Wassenhove Luk N.
Published: November 2008

The Tactical Fixed Interval Scheduling Problem (TFISP) is the problem of determining the minimum number of parallel nonidentical machines, such that a feasible schedule exists for a given set of jobs. In TFISP, each job must belong to a specific job class and must be carried out in a prespecified time interval. The problem is complicated by the restrictions that (1) each machine can handle only one job at a time, (2) each machine can handle only jobs from a subset of the job classes, and (3) preemption is not allowed. In this paper we discuss the occurrence of TFISP in practice, we analyze the computational complexity of TFISP, and we present exact and approximation algorithms for solving TFISP. The paper concludes with a computational study.
An Air Mission Planning Algorithm Using Decision Analysis and Mixed Integer Programming
Authors: Griggs Brian J. , Parnell Gregory S. , Lehmkuhl Lee J.
Published: November 2008

This paper describes the development of an air mission planning algorithm for the Joint Stochastic Warfare Analysis Research (JSTOCHWAR). The overall problem scope was to develop an algorithm to handle major factors bearing on the combat mission planning problem while providing hook-ups for the JSTOCHWAR architecture. Other aspects of the problem included finding the appropriate level of detail, developing a fast solving technique, and attempting to use existing data. The problem was handled by using some ideas from existing aircraft allocation algorithms and by adding some new techniques.

The proposed air mission planning algorithm supplies the optimum degree of force for campaign objectives by using a mixed integer program (MIP) to allocate the optimum number and type of aircraft and munitions against each target. The MIP takes advantage of the force multiplying effects of mass and mutual support through its use of strike packages with air defense suppression and air-to-air escort aircraft. Additionally, a decision tree algorithm determines the best plan in light of the uncertainties of weather and weather forecasts.

This air mission planning algorithm omits many of the details in the actual aircraft tasking process, but in its continuous variable version, provides fast, nearly optimal solutions that should approximate real-world tasking results.
A Heuristic for Estimating Nadir Criterion Values in Multiple Objective Linear Programming
Authors: Korhonen Pekka , Salo Seppo , Steuer Ralph E.
Published: November 2008

In this paper we further investigate the problem of finding nadir criterion values (minimum criterion values over the nondominated set) in multiple objective linear programming. Although easy to obtain, the minimum values present in a payoff table are unreliable and should only be used with caution, especially in problems that have more than a small number of extreme points. To obtain better estimates of the nadir criterion values without adding great complexity to the task, we present an approach based upon the use of reference directions. At each iteration of this approach, a reference direction is chosen that maximally minimizes the objective under consideration. We proceed with reference directions that accomplish this until the objective under consideration reaches a local minimum over the nondominated set. Then a cutting plane is inserted into the problem and another direction, if one can be found, that maximally minimizes the objective under consideration is employed. Although the method is heuristic, computational experience shows that much better estimates of the nadir criterion values can be obtained than from payoff tables.
Designing a Zoned Automated Guided Vehicle System with Multiple Vehicles and Multiple Load Capacity
Authors: Thonemann Ulrich W. , Brandeau Margaret L.
Published: November 2008

We introduce an analytical model for the design of a multiple-vehicle automated guided vehicle system (AGVS) with multiple-load capacity operating under a “go-when-filled” dispatching rule. The AGVS delivers containers of material from a central depot to workcenters throughout the factory floor. The workcenters are partitioned into delivery zones. They are served by a common pool of automated guided vehicles (AGVs), each of which can carry multiple orders per delivery. The demand of the workcenters and the time until delivery are stochastic. We develop a nonlinear binary integer program to determine the optimal partition of workcenters into zones, the optimal number of AGVs to purchase, and the set of workcenters that warrant AGV delivery, subject to constraints on maximum allowable mean waiting time for material delivery. We develop an analytical expression for the mean waiting time until material delivery and present an efficient branch-and-bound algorithm that solves the AGVS design model optimally. Without the analytical solution method, one would have to simulate the system for all zoning options, all combinations of open and closed workcenters, and all possible numbers of AGVs, in order to determine the optimal AGVS design—an approach likely to be infeasible for most problems.
Designing Hierarchical Survivable Networks
Authors: Balakrishnan Anantaram , Magnanti Thomas L. , Mirchandani Prakash
Published: November 2008

As the computer, communication, and entertainment industries begin to integrate phone, cable, and video services and to invest in new technologies such as fiber-optic cables, interruptions in service can cause considerable customer dissatisfaction and even be catastrophic. In this environment, network providers want to offer high levels of service—in both serviceability (e.g., high bandwidth) and survivability (failure protection)—and to segment their markets, providing better technology and more robust configurations to certain key customers. We study core models with three types of customers (primary, primary but critical, and secondary) and two types of services/technologies (primary and secondary). The network must connect all primary customers using primary (high bandwidth) services and, additionally, contain a back-up path connecting the critical primary customers. Secondary customers require only single connectivity to other customers and can use either primary or secondary facilities. We propose a general multi-tier survivable network design model to configure cost effective networks for this type of market segmentation. When costs are triangular, we show how to optimally solve single-tier subproblems, with two critical customers, as a matroid intersection problem. We also propose and analyze the worst-case performance of tailored heuristics for several special cases of the two-tier model. Depending upon the particular problem setting, the heuristics have worst-case performance ratios ranging between 1.25 and 2.6. We also provide examples to show that the performance ratios for these heuristics are the best possible.
The Aircraft Maintenance Routing Problem
Authors: Gopalan Ram , Talluri Kalyan T.
Published: November 2008

Federal aviation regulations require that all aircraft undergo maintenance after flying a certain number of hours. To ensure high aircraft utilization, maintenance is done at night, and these regulations translate into requiring aircraft to overnight at a maintenance station every three to four days (depending on the fleet type), and to visit a balance-check station periodically. After the schedule is fleeted, the aircraft are routed to satisfy these maintenance requirements. We give fast and simple polynomial-time algorithms for finding a routing of aircraft in a graph whose routings during the day are fixed, that satisfies both the three-day maintenance as well as the balance-check visit requirements under two different models: a static infinite-horizon model and a dynamic finite-horizon model. We discuss an implementation where we embed the static infinite-horizon model into a three-stage procedure for finding a maintenance routing of aircraft.
An Axiomatic Characterization of a Class of Locations in Tree Networks
Authors: Foster Dean P. , Vohra Rakesh V.
Published: November 2008

In this paper we describe four axioms that uniquely characterize the class of locations in tree networks that are obtained by minimizing an additively separable, nonnegative, nondecreasing, differentiable, and strictly convex function of distances. This result is analogous to results that have been obtained in the theory of bargaining, social choice, and fair resource allocation.
On Optimal Allocation of Indivisibles Under Uncertainty
Authors: Norkin Vladimir I. , Ermoliev Yuri M. , Ruszczyński Andrzej
Published: November 2008

The optimal allocation of indivisible resources is formalized as a stochastic optimization problem involving discrete decision variables. A general stochastic search procedure is proposed, which develops the concept of the branch-and-bound method. The main idea is to process large collections of possible solutions and to devote more attention to the most promising groups. By gathering more information to reduce the uncertainty and by narrowing the search area, the optimal solution can be found with probability one. Special techniques for calculating stochastic lower and upper bounds are discussed. The results are illustrated by a computational experiment.
On the Meaningfulness of Optimal Solutions to Scheduling Problems: Can an Optimal Solution be Nonoptimal?
Authors: Mahadev N. V. R. , Pekeč Aleksandar , Roberts Fred S.
Published: November 2008

We consider the problem of finding an optimal schedule for jobs on a single machine when there are penalties for both tardy and early arrivals. We point out that if attention is paid to how these penalties are measured, then a change of scale of measurement might lead to the anomalous situation where a schedule is optimal if these parameters are measured in one way, but not if they are measured in a different way that seems equally acceptable. In particular, we note that if the penalties measure utilities or disutilities, or loss of goodwill or customer satisfaction, then these kinds of anomalies can occur, for instance if we change both unit and zero point in scales measuring these penalties. We investigate situations where problems of these sorts arise for four specific penalty functions under a variety of different assumptions. The results of the paper have implications far beyond the specific scheduling problems we consider, and suggest that considerations of scale of measurement should enter into analysis of conclusions of optimality both in scheduling problems and throughout combinatorial optimization.
Stationary Policies in Multiechelon Inventory Systems with Deterministic Demand and Backlogging
Authors: Chen Fangruo
Published: November 2008

A stationary policy conducts replenishment activities—the placement and fulfillment of orders—in a stationary fashion. That is, each facility receives a constant batch (facility specific) in equal time intervals (facility specific) under a stationary policy. Although the advantages of stationary policies are clear (i.e., smooth operations), they represent a restriction in policy selection. This paper investigates how costly this restriction can be. For two multiechelon systems (serial and distribution) with deterministic demand and backlogging, we show that stationary policies are 70%-effective. This bound is tight in the sense that an example exists where the bound is reached. On the other hand, the average effectiveness of stationary policies is very high. In a set of 1,000 randomly generated numerical examples, we observed that the average effectiveness was 99%, and the standard deviation was 1.5%. The numerical examples also suggest that the performance of stationary policies deteriorates in systems where the setup cost decreases dramatically from an upstream stage to a downstream stage. Finally, a key building block of the above results is the existing lower bounds on the average costs of all feasible policies in the above systems. We provide a simpler derivation of these bounds.
A Primal Method for the Solution of the Groundwater Quality Management Problem
Authors: Tucciarelli Tullio , Karatzas George P. , Pinder George F.
Published: November 2008

A new algorithm for the solution of the groundwater quality management problem is presented. The method assumes that most of the computational effort in such problems involves evaluation of the concentrations and their derivatives with respect to the pumping rates at the control points. The methodology proposed herein is a combination of the cutting plane method and the primal method. In this approach each line search moves from a feasible point towards the solution of a subproblem with linear constraints and the same objective function as the original problem. Sensitivity analysis is used to compute the derivative of a single concentration with respect to all the pumping rates by solving only one linear system at each time step. The method has been tested with analytical convex problems and a model example. A comparison of the algorithm's performance was conducted using MINOS 5.1. For the case of a linear cost function the method shows a computational growth rate almost linearly proportional to the number of decision variables.
Solution of the Multisource Weber and Conditional Weber Problems by D.-C. Programming
Authors: Chen Pey-Chun , Hansen Pierre , Jaumard Brigitte , Tuy Hoang
Published: November 2008

D.-c. programming is a recent technique of global optimization that allows the solution of problems whose objective function and constraints can be expressed as differences of convex (i.e., d.-c.) functions. Many such problems arise in continuous location theory. The problem first considered is to locate a known number of source facilities to minimize the sum of weighted Euclidean distances between a user's fixed location and the source facility closest to the location of each user. We also apply d.-c. programming to the solution of the conditional Weber problem, an extension of the multisource Weber Problem, in which some facilities are assumed to be already established. In addition, we consider a generalization of Weber's problem, the facility location problem with limited distances, where the effective service distance becomes a constant when the actual distance attains a given value. Computational results are reported for problems with up to 10,000 users and two new facilities, 50 users and three new facilities, 1,000 users, 20 existing facilities and one new facility or 200 users, 10 existing and two new facilities.
Strong Stochastic Bounds for the Stationary Distribution of a Class of Multicomponent Performability Models
Authors: Taylor P. G. , Van Dijk N. M.
Published: November 2008

We consider a class of models for multicomponent systems in which components can break down and be repaired in a dependent manner and where breakdown and repair times can be arbitrarily distributed. The problem of calculating the equilibrium distribution and, from this, the expected performability for these models is intractable unless certain assumptions are made about breakdowns and repairs. In this paper we show that the performability of multicomponent systems that do not satisfy these rules can be bounded by tractable modifications. Our results are proved by stochastic comparability arguments and a Markov reward technique, which is of interest in itself as it enables one to prove that the equilibrium distribution of one process can be bounded by that of another even when the sample paths of the process are not. This is illustrated by an example.
Leadtime-Inventory Trade-Offs in Assemble-to-Order Systems
Authors: Glasserman Paul , Wang Yashan
Published: November 2008

This paper studies the trade-off between inventory levels and the delivery leadtime offered to customers in achieving a target level of service. It addresses the question of how much a delivery leadtime can be reduced, per unit increase in inventory, at a fixed fill rate. We show that for a class of assemble-to-order models with stochastic demands and production intervals there is a simple linear trade-off between inventory and delivery leadtime, in a limiting sense, at high fill rates. The limiting slope is easy to calculate and can be interpreted as the approximate marginal rate for trading off inventory against leadtime at a constant level of service. We also investigate how various model features affect the trade-off—in particular, the impact of orders for multiple units of a single item and of orders for multiple units of different items.
A Capacitated Production-Inventory Model with Periodic Demand
Authors: Kapuściński Roman , Tayur Sridhar
Published: November 2008

For a single product, single-stage capacitated production-inventory model with stochastic, periodic (cyclic) demand, we find the optimal policy and characterize some of its properties. We study the finite-horizon, the discounted infinite-horizon and the infinite-horizon average cases. A simulation based optimization method is provided to compute the optimal parameters. Based on a numerical study, several insights into the model are also provided.
A Graph-Theoretic Decomposition of the Job Shop Scheduling Problem to Achieve Scheduling Robustness
Authors: Wu S. David , Byeon Eui-Seok , Storer Robert H.
Published: November 2008

In this paper we study the weighted tardiness job-shop scheduling problem, taking into consideration the presence of random shop disturbances. A basic thesis of the paper is that global scheduling performance is determined primarily by a subset of the scheduling decisions to be made. By making these decisions in an a priori static fashion, which maintains a global perspective, overall performance efficiency can be achieved. Further, by allowing the remaining decisions to be made dynamically, flexibility can be retained in the schedule to compensate for unforeseen system disturbances. We develop a decomposition method that partitions job operations into an ordered sequence of subsets. This decomposition identifies and resolves a “crucial subset” of scheduling decisions through the use of a branch-and-bound algorithm. We conduct computational experiments that demonstrate the performance of the approach under deterministic cases, and the robustness of the approach under a wide range of processing time perturbations. We show that the performance of the method is superior, particularly for low to medium levels of disturbances.
Partition-Reversible Markov Processes
Authors: Alexopoulos Christos , El-Tannir Akram A. , Serfozo Richard F.
Published: November 2008

This study introduces a generalization of reversibility called partition-reversibility. A Markov jump process is partition-reversible if the average numbers of its transitions between sets that partition the state space are equal. In this case, its stationary distribution is obtainable by solving the balance equations separately on the sets. We present several characterizations of partition-reversibility and identify subclasses of treelike, starlike, and circular partition-reversible processes. A new circular birth-death process is used in the analysis. The results are illustrated by a queueing model with controlled service rate, a multitype service system with blocking, and a parallel-processing model. A few comments address partition-reversibility for non-Markovian processes.
Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators
Authors: L'Ecuyer Pierre
Published: November 2008

Combining parallel multiple recursive sequences provides an efficient way of implementing random number generators with long periods and good structural properties. Such generators are statistically more robust than simple linear congruential generators that fit into a computer word. We made extensive computer searches for good parameter sets, with respect to the spectral test, for combined multiple recursive generators of different sizes. We also compare different implementations and give a specific code in C that is faster than previous implementations of similar generators.
A Product and Process Selection Model with Multidisciplinary Environmental Considerations
Authors: Stuart Julie Ann , Ammons Jane C. , Turbini Laura J.
Published: November 2008

Introduction of product designs and process innovation requires a company to evaluate complex cost and environmental tradeoffs. In the past, these have not included environmental costs. This paper describes the first known analytical approach to capture comprehensively measurable corporate environmental impact considerations for the product life cycle. A mixed integer programming model is developed to select product and process alternatives while considering tradeoffs of yield, reliability, and business-focused environmental impacts. Explicit constraints for environmental impacts such as material consumption, energy consumption, and process waste generation are modeled for specified assembly and disassembly periods. The constraint sets demonstrate a new way to define the relationship between disassembly configurations and assembly activities through take-back rates. Use of the model as an industry decision tool is demonstrated with an electronics assembly case study.
On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach
Authors: Luss Hanan
Published: November 2008

In this expository paper, we review a variety of resource allocation problems in which it is desirable to allocate limited resources equitably among competing activities. Applications for such problems are found in diverse areas, including distribution planning, production planning and scheduling, and emergency services location. Each activity is associated with a performance function, representing, for example, the weighted shortfall of the selected activity level from a specified target. A resource allocation solution is called equitable if no performance function value can be improved without either violating a constraint or degrading an already equal or worse-off (i.e., larger) performance function value that is associated with a different activity. A lexicographic minimax solution determines this equitable solution; that is, it determines the lexicographically smallest vector whose elements, the performance function values, are sorted in nonincreasing order. The problems reviewed include large-scale allocation problems with multiple knapsack resource constraints, multiperiod allocation problems for storable resources, and problems with substitutable resources. The solution of large-scale problems necessitates the design of efficient algorithms that take advantage of special mathematical structures. Indeed, efficient algorithms for many models will be described. We expect that this paper will help practitioners to formulate and solve diverse resource allocation problems, and motivate researchers to explore new models and algorithmic approaches.
Sequential Inspection Under Capacity Constraints
Authors: Yao David D. , Zheng Shaohui
Published: November 2008

We study the inspection process in the context of multistage batch manufacturing, focusing on interstage coordination under capacity limits. The problem is formulated as a constrained Markov decision program. We establish the optimality of a sequential policy that is characterized by a sequence of thresholds, with certain randomization at the thresholds. We further show that such an optimal policy can be completely derived through solving a linear program, and that randomization is needed at no more than two threshold values. We discuss an application in semiconductor wafer fabrication, which motivates our study.
Optimal Routing of Customers to Two Parallel Heterogeneous Servers: The Case of IHR Service Times
Authors: Frostig Esther , Levikson Benny
Published: November 2008

We consider here the optimal routing of customers, arriving to a system consisting of two heterogeneous parallel servers. The service times of the two servers have an increasing hazard rate. The arrival process is a general renewal process. The cost of holding x customers in the system per time unit is a nondecreasing and convex function. The objective is to minimize the expected discounted holding cost. We show some monotonicity properties of the optimal policy. Then we show that the optimal policy routes an arriving customer to the fastest server whenever this server has the lowest workload.
The Assignment Problem with Seniority and Job Priority Constraints
Authors: Caron Gaétan , Hansen Pierri , Jaumard Brigitte
Published: November 2008

Consider an assignment problem in which persons are qualified for some but usually not all of the jobs. Moreover, assume persons belong to given seniority classes and jobs have given priority levels. Seniority constraints impose that the solution be such that no unassigned person can be given a job unless an assigned person with the same or higher seniority becomes unassigned. Priority constraints specify that the solution must be such that no unassigned job can become assigned without a job with the same or higher priority becoming unassigned. It is shown that: (i) adding such constraints does not reduce and may even increase the number of assigned persons in the optimal solution; (ii) using a greedy heuristic for constrained assignment (as often done in practice) may reduce the number of assigned persons by half, and (iii) an optimal solution to the assignment problem with both types of constraints can be obtained by solving a classical assignment problem with adequately modified coefficients.
On the Complexity of Verifying Structural Properties of Discrete Event Simulation Models
Authors: Jacobson Sheldon H. , Yücesan Enver
Published: November 2008

This paper uses computational complexity theory to assess the difficulty of various discrete event simulation problems. More specifically, accessibility of states, ordering of events, noninterchangeability of model implementations, and execution stalling for discrete event simulations are formally stated as search problems and proven to be NP-hard. The consequences of these results cover a wide range of modeling and analysis problems in simulation. For example, problems associated with certain variance reduction techniques, model verification, model validation, and the applicability of infinitesimal perturbation analysis, among others, are deemed intractable.
Heavy Traffic Analysis of Polling Systems in Tandem
Authors: Reiman Martin I. , Wein Lawrence M.
Published: November 2008

We analyze the performance of a tandem queueing network populated by two customer types. The interarrival times of each type and the service times of each type at each station are independent random variables with general distributions, but the load on each station is assumed to be identical. A setup time is incurred when a server switches from one customer type to the other, and each server employs an exhaustive polling scheme. We conjecture that a time scale decomposition, which is known to occur at the first station under heavy traffic conditions, holds for the entire tandem system, and we employ heavy traffic approximations to compute the sojourn time distribution for a customer that arrives to find the network in a particular state. When setup times are zero (except perhaps at the first station) and additional “product-form” type assumptions are imposed, we find the steady-state sojourn time distribution for each customer type.
Approximating an Optimal Production Policy in a Continuous Flow Line: Recurrence and Asymptotic Properties
Authors: Yan Houmin , Zhou Xun Yu , Yin G.
Published: November 2008

This work is concerned with manufacturing systems with two failure-prone tandem machines. The production is regulated by a continuous version of buffer control. Our goal is to obtain an optimal buffer-control policy to minimize a long-run average cost function. Concentrating on threshold type of control policies, our effort is devoted to parameter optimization problems for the continuous material produce-to-stock models. We estimate the gradients of the cost function with respect to the parameter using perturbation analysis techniques, and approximate the optimal value of the parameter via a constant step-size stochastic approximation algorithm. An analysis for error accumulation in perturbation propagation is undertaken, and a sufficient condition for breaking the propagation chain is derived. In addition, we show that the event of breaking the perturbation propagation chain is recurrent if the system has sufficient capacity, derive the consistency of the gradient estimators, and establish the convergence of the iterative algorithm. We also treat non-Markovian models with the machine repair time following an Erlang distribution, and provide numerical examples to illustrate the proposed algorithm.
The Changeover Scheduling Problem with Time and Cost Considerations: Analytical Results and a Forward Algorithm
Authors: Blocher James D. , Chand Suresh , Sengupta Kaushik
Published: November 2008

In a multiproduct, discrete-item manufacturing environment, it is often more economical to have one “flexible” machine to produce several products rather than to have a dedicated machine for the production of each product. We consider the problem of scheduling multiple products on a single-finite-capacity resource when faced with product-dependent, but sequence-independent, changeover costs and times. The problem horizon is assumed finite and the demand time-varying and known over this horizon. The objective is to find a feasible schedule that meets all demand on time and minimizes the total changeover cost.

With the “delivery-on-time-or-else” mentality and the trend toward shorter order-to-delivery lead times, scheduling and managing changeovers has become just that much more important. We first present analytical results to reduce the feasible solution space and then develop a branch-and-bound algorithm to solve this NP-complete problem. Computational results are presented that show that the algorithm can solve realistic size problems in a reasonable amount of time.
Core Problems in Knapsack Algorithms
Authors: Pisinger David
Published: November 2008

Since Balas and Zemel in the 1980s introduced the so-called core problem as an efficient tool for solving the Knapsack Problem, all the most successful algorithms have applied this concept. Balas and Zemel proved that if the weights in the core are uniformly distributed then there is a high probability for finding an optimal solution in the core. Items outside the core may be fathomed because of reduction rules.

This paper demonstrates that generally it is not reasonable to assume a uniform distribution of the weights in the core, and it is experimentally shown that the heuristic proposed by Balas and Zemel does not find as good solutions as expected. Also, other algorithms that solve some kind of core problem may be stuck by difficult cores. This behavior has apparently not been noticed before because of unsufficient testing.

Capacities leading to difficult problems are identified for several categories of instance types, and it is demonstrated that the hitherto applied test instances are easier than the average. As a consequence we propose a series of new randomly generated test instances and show how recent algorithms behave when applied to these problems.