bluuebunny/crossref_metadata_2025 huggingface dataset:
Two-Dimensional Failure-Free Warranty Policies: Two-Dimensional Point Process Models
Authors: Murthy D. N. P. , Iskandar B. P. , Wilson R. J.
Published: November 2008

A two-dimensional warranty policy is characterized by a region in a two-dimensional plane with the horizontal axis representing time and the vertical axis the usage. In this paper, we study two-dimensional failure-free warranty policies for nonrepairable items that require the manufacturer to replace all items which fail under warranty by new ones at no cost to the buyer. We derive expressions for the expected warranty cost per item sold and for the expected life cycle cost for four different warranty regions. We illustrate these by numerical examples and discuss some resulting implications for the consumer and the manufacturer.
An Application of Yield Management to the Hotel Industry Considering Multiple Day Stays
Authors: Bitran Gabriel R. , Mondschein Susana V.
Published: November 2008

In this paper we study optimal strategies for renting hotel rooms when there is a stochastic and dynamic arrival of customers from different market segments. We formulate the problem as a stochastic and dynamic programming model and characterize the optimal policies as functions of the capacity and the time left until the end of the planning horizon. We consider three features that enrich the problem: we make no assumptions concerning the particular order between the arrivals of different classes of customers; we allow for multiple types of rooms and downgrading; and we consider requests for multiple nights. We also consider implementations of the optimal policy. The properties we derive for the optimal solution significantly reduce the computational effort needed to solve the problem, yet in the multiple product and/or multiple night case this is often not enough. Therefore, heuristics, based on the properties of the optimal solutions, are developed to find “good” solutions for the general problem. We also derive upper bounds which are useful when evaluating the performance of the heuristics. Computational experiments show a satisfactory performance of the heuristics in a variety of scenarios using real data from a medium size hotel.
Exploiting Partial Information in Queueing Systems
Authors: Masuda Yasushi
Published: November 2008

We often try to draw inferences from partial observations of queueing systems in real-life situations. For example, if we observe many customer arrivals, we may presume that the system is crowded and many customers are served. Unfortunately, such an intuitive statement is not necessarily valid. We provide sufficient conditions under which the intuition can be justified, and investigate related properties of queueing systems. We also study a way to exploit the partial information in a quantitative manner for simple queueing systems. One numerical result is rather counterintuitive. Specifically, the number of customers in the system at time t given that the cumulative number of departures is a certain constant is not necessarily stochastically increasing in t for a simple M/M/1 system with finite capacity.
Networks of Queues with Customers, Signals and Arbitrary Service Time Distributions
Authors: Chao Xiuli
Published: November 2008

We consider a network of queues with multiple classes of customers, signals, and arbitrary service time distributions. The signals bring commands to the service nodes and may trigger customers to move instantly within the network. We consider symmetric service disciplines (e.g., processor sharing, LIFO preemptive, infinite server) similar to those in F. Kelly (Kelly, F. 1979. Reversibility and Stochastic Networks. John Wiley, New York.), and show that when each node has a single server operating under a symmetric service discipline, the stationary distribution has a product-form solution. The product form, however, depends on the service time distributions of customers at each node beyond their means. This is in contrast to the insensitivity result of the conventional Jackson networks and can be attributed to the effect of signals. When the nodes have multiple servers in parallel, the usual definition of signals does not lead to a product-form solution. We propose a new definition of signals that depends on the service effort and provides a product-form solution.
Mathematical Programming Models for Environmental Quality Control
Authors: Greenberg Harvey J.
Published: November 2008

This paper surveys the use of mathematical programming models for controlling environmental quality. The scope includes air, water, and land quality, stemming from the first works in the 1960s. It also includes integrated models, generally that are economic equilibrium models which have an equivalent mathematical program or use mathematical programming to compute a fixed point. A primary goal of this survey is to identify interesting research avenues for people in mathematical programming with an interest in applying it to help control our environment with as little economic sacrifice as possible.
The Parameter Space Investigation Method of Multiple Objective Nonlinear Programming: A Computational Investigation
Authors: Steuer Ralph E. , Sun Minghe
Published: November 2008

In this paper we study the parameter space investigation method of I. M. Sobol and R. B. Statnikov. The method is a “random hitting” procedure for solving the kinds of small, but difficult, multiple objective nonlinear programming problems often encountered in engineering design and optimal control. Sobol and Statnikov have argued the effectiveness of their approach and its application possibilities. In this paper, we computationally test the parameter space investigation method to examine the extent to which claims about their method can be substantiated.
On Normalizing Constants in Multiclass Queueing Networks
Authors: Gerasimov Alexander I.
Published: November 2008

Analytical expressions (formulas) for normalizing constants in closed queueing networks with different classes of customers are presented and discussed in this article.
The Throughput of Multistation Production Lines with No Intermediate Buffers
Authors: Papadopoulos Hrissoleon T.
Published: November 2008

This paper concerns the throughput rate of multistation reliable production lines with no intermediate buffers. Processing times at the service stations are independent, exponential random variables, possibly with different means. We extend the work started in E. J. Muth (Muth, E. J. 1984. Stochastic processes and their network representations associated with production line queueing model. Eur. J. Opnl. Res. 15 63–83.) to provide an algorithm that allows for the efficient computation of longer lines and to provide results for the nonidentical server case. A result is presented which provides the distribution function of the holding time at the stations.
On the Finite Horizon EOQ Model with Cost Changes
Authors: Gascon André
Published: November 2008

In this note, an algorithm previously introduced by B. Lev and H. Weiss to optimally solve the finite horizon EOQ model with price changes is modified to avoid infeasible solutions. An example is provided.
Application of Linear Programming in a Gauze Splitting Operation
Authors: Schultz Todd A.
Published: November 2008

“Real-world” adaptation of a linear programming model for cutting stock problems has led to significant financial and operational improvements at Kendall Corporation. Originally developed for controlling waste when slitting rolls of cloth, the project also reduced work-in-process inventory, which helped the firm reach just-in-time production goals. Another dramatic, but largely unplanned, benefit from the project was the company’s ability to investigate operations redesign. Direct and indirect benefits derived from making scheduling decisions more visible, systematic, and tractable have been estimated by Kendall to be more than $2 million per year.
Optimal Algorithms and a Remarkably Efficient Heuristic for the Ground-Holding Problem in Air Traffic Control
Authors: Richetta Octavio
Published: November 2008

Since it is safer and less expensive to absorb delays on the ground, air traffic control management tries to limit the duration of airborne delays by holding aircraft previous to departure when congestion at the airport of destination is anticipated. The problem of assigning appropriate ground-holds to aircraft is known as the ground-holding problem. Ground-holding decisions must be implemented in real time and for multiple airports; therefore, the speed of solution for algorithms is critical. This paper tests static and dynamic optimal solutions, and a very fast heuristic for the assignment of ground-holds in air traffic control. The optimal solutions are based on stochastic linear programming. The heurtstic incorporates elements of stochastic modeling by utilizing information conveyed by a probabilistic forecast of airport landing capacity, while taking into consideration the dynamic nature of the problem. In extensive computational experiments based on data for Logan airport, the heuristic performed significantly better than the optimal static solution, a deterministic solution, and the passive strategy of no-ground-holds; and within 5% of the optimal dynamic solution at a fraction of the computational time. Due to its remarkable efficiency, the stochastic-dynamic heuristic appears to be a promising building block in the development of fast ground-holding algorithms for the complete network of airports.
A Weighted Least Squares Approach to Computer Simulation Factor Screening
Authors: Morrice Douglas J. , Bardhan Indranil R.
Published: November 2008

In this paper, we develop a weighted least squares (WLS) approach to computer simulation factor screening. Like frequency domain methodology (FDM), the regression analysis is performed in the frequency domain. However, unlike FDM, where unknown nuisance parameters are eliminated by cancellation in a ratio statistic, the WLS procedure is designed to estimate these parameters (the WLS weights) and incorporate this information into the regression analysis. We propose and compare one- and two-run approaches for estimating the weights in the WLS approach.
Response Time Design in Integrated Order Processing/Production Systems
Authors: Lovejoy William S. , Whang Seungjin
Published: November 2008

We consider a single-product firm in which arriving orders are processed by an information processing system before being downloaded to the production system. The design problem is to choose the appropriate processing and control technologies for the information (production) systems, the decision variables being the speed with which these systems can process orders (products). Rapid systems are assumed to be more costly to operate than slower systems, and it is assumed that products can be inventoried, but information processing cannot. Longer information processing times incur greater delay costs, but provide benefits in the form of more advanced warning of upcoming demand to the production function. This paper is a first attempt to model this tradeoff. We describe a plausible set of conditions under which the information processing time will never exceed the production lead time in an optimal design. Conditions are also described that guarantee that the greatest marginal benefit, starting from a suboptimal system design, will be to invest in time reductions in the information processing, rather than the production, system. Performance measures are suggested that provide the appropriate incentives to integrate the information processing and production functions.
Preparing for the Future: The Opportunities and Limitations for INFORMS on the Pacific Rim
Authors: Coates Joseph F.
Published: November 2008

Based on an address given at the April 1995 INFORMS meeting in Los Angeles, this paper's purpose is to suggest the opportunities that the Pacific Rim will bring to OR/MS and INFORMS. It first looks at the two important needs in the profession: to improve the scope of its communications with the public and to expand the context in which OR/MS work is done. After describing some of the radically unfamiliar and different conditions affecting enterprises on the Pacific Rim and suggesting their important challenges, the paper describes some influences acting to inhibit the free growth of the profession and its contributions to society. It closes by suggesting how meeting the challenges of the Pacific Rim cannot only help solve the problems this new context poses, but also help prepare the profession for its larger international future.
Model Formulation: What Experts Think About and When
Authors: Willemain Thomas R.
Published: November 2008

Model formulation is a critical craft skill that deserves more attention from OR practitioners and educators. As a step toward understanding how experts formulate OR models, I conducted an experiment in which twelve skilled analysts generated think-aloud protocols while working model formulation exercises 60 minutes long. The coded transcripts tracked the modelers' attention to five topics corresponding to stages in the usual OR paradigm: problem context and model structure, realization, assessment, and implementation. Analysis of the transcripts yielded these conclusions: topics other than structure attracted a significant proportion of modelers' attention; modelers frequently switched their attention among the topics; the switching was usually an alternation between structure and the other topics, especially assessment; on average, the modelers progressed through the topics in the given order; there was limited support for the notion of modeler-specific and problem-specific effects influencing the attention given to each topic; and there was support for the idea of individual modeling styles.
Global Sensitivity Analysis
Authors: Wagner Harvey M.
Published: November 2008

In applications of operations research models, decision makers must assess the sensitivity of outputs to imprecise values for some of the model's parameters. Existing analytic approaches for classic optimization models rely heavily on duality properties for assessing the impact of local parameter variations, parametric programming for examining systematic variations in model coefficients, or stochastic programming for ascertaining a robust solution. This paper accommodates extensive simultaneous variations in any of an operations research model's parameters. For constrained optimization models, the paper demonstrates practical approaches for determining relative parameter sensitivity with respect to a model's optimal objective function value, decision variables, and other analytic functions of a solution. Relative sensitivity is assessed by assigning a portion of variation in an output value to each parameter that is imprecisely specified. The computing steps encompass optimization, Monte Carlo sampling, and statistical analyses, in addition to model specification. The required computations can be achieved with commercially available off-the-shelf software available for microcomputers and other platforms. The paper uses a broad set of test models to demonstrate the merit of the approaches. The results are easily put to use by a practitioner. The paper also outlines further research developments to extend the applicability of the approaches.
Withdrawable Bids as Winner's Curse Insurance
Authors: Harstad Ronald M. , Rothkopf Michael H.
Published: November 2008

When bidders have a common value or strongly affiliated values for an object or contract being auctioned by sealed bids, it is possible that the maker of a rational and apparently winning bid would, upon learning the competing bids, prefer losing the auction to honoring his bid. The ability to withdraw a bid, perhaps at a cost, in such circumstances provides a form of “winner's curse insurance.” Bidding with such insurance is analyzed, obtaining the general condition for rational bid withdrawal and sufficient conditions for the existence of an equilibrium with more aggressive bidding. Next, we define a “compensation penalties” bid withdrawal penalty scheme and show that with it the bid-taker is better off on the average than if bid withdrawal is impossible. Finally, we find equilibrium bidding and withdrawal strategies in a multiplicative model as a function of the magnitude of the bid withdrawal penalty and of the bid-taker's likelihood, after a withdrawal, of honoring the second-best bid. This model has cases in which allowing withdrawal at a cost is in the bid-taker's interest and ones in which it is not.
Sequential Screening in Semiconductor Manufacturing, II: Exploiting Lot-to-Lot Variability
Authors: Ou Jihong , Wein Lawrence M.
Published: November 2008

This paper addresses the same quality management problem as Longtin, Wein and Welsch (Longtin, M., L. M. Wein, R. E. Welsch. 1996. Sequential screening in semiconductor manufacturing, I: Exploiting spatial dependence. Opns. Res. 44 173–195.), except that here screening is performed at the wafer level, rather than at the chip level. An empirical Bayes approach is employed: The number of bad chips on a wafer is assumed to be a gamma random variable, where the scale parameter is unknown and varies from lot to lot according to another gamma distribution. We fit the yield model to industrial data and test the optimal policy on these data. The numerical results suggest that screening at the chip level, as in Longtin, Wein and Welsch, is significantly more profitable than screening at the wafer level.
Circuit Partitioning Via Set Partitioning and Column Generation
Authors: Eben-Chaime Moshe , Tovey Craig A. , Ammons Jane C.
Published: November 2008

In this paper, a new application of the methodology of set partitioning formulation augmented with heuristic column generation is presented. An efficient method for the partitioning of large-scale electronic circuits is developed based on this methodology. Circuit partitioning constitutes a major step of the physical design phase of electronic circuits, the fundamental components of electronic products. The major advantage of the scheme presented here is to provide a framework for an effective integration of most existing circuit partitioning methods. Another attractive feature of the current approach is the incorporation of interactive optimization: The circuit designer controls the operation of the procedure and enhances its performance by suggesting and/or requiring specific partitions. Following the development of the model, the solution approach is presented and computational results are reported for several benchmark circuits.
Process Planning for Aluminum Tubes: An Engineering-Operations Perspective
Authors: Balakrishnan Anantaram , Brown Stuart
Published: November 2008

Metal-forming operations such as extrusion, drawing, and rolling offer many opportunities for operations improvement through better process understanding and improved planning practices. This paper addresses medium-term planning issues in aluminum tube manufacturing operations. First, we identify certain distinctive characteristics—the inherent process flexibility, close inter-dependence between successive stages, and economies of scale—of metal-forming operations, and identify performance trade-offs across stages. To exploit the strategic potential of process planning, it must be closely coupled with process engineering efforts, and must simultaneously consider the facility's entire product mix. In contrast, current process engineering efforts are mainly reactive, focusing on fixing problems at individual operations and with less emphasis on the interactions between successive stages. Similarly, planning activities are incremental, considering only individual products or orders one at a time rather than the entire range of product sizes to be manufactured. By working together, planners and engineers can develop effective process plans that exploit process capability, and adopt proactive process improvement strategies that focus on critical constraints. We describe a medium-term planning model to select standard extrusion sizes, illustrate the close linkages between planning and engineering activities, and identify research opportunities spanning management science, materials science, and mechanical engineering.
Optimizing Flight Operations for an Aircraft Carrier in Transit
Authors: Rosenthal Richard E. , Walsh William J.
Published: November 2008

Suppose that an aircraft carrier is in transit to an assigned position within strike range of a designated target, and is required to be there at a specified time. The carrier may use aircraft assets for defense against threats that may be encountered en route, but doing so will encumber the carrier's progress toward the required objective. We present a highly detailed integer programming model for scheduling aircraft launches and recoveries, to achieve an optimal balance between the conflicting needs of self-protection and on-time arrival.
Multiattribute Utility Theory Without Expected Utility Foundations
Authors: Miyamoto John M. , Wakker Peter
Published: November 2008

Methods for determining the form of utilities are needed for the implementation of utility theory in specific decisions. An important step forward was achieved when utility theorists characterized useful parametric families of utilities and simplifying decompositions of multiattribute utilities. The standard development of these results is based on expected utility theory which is now known to be descriptively invalid. The empirical violations of expected utility impair the credibility of utility assessments. This paper shows, however, that parametric and multiattribute utility results are robust against the major violations of expected utility. They retain their validity under nonexpected utility theories that have been developed to account for actual choice behavior. To be precise, characterizations of parametric and multiattribute representations are extended to rank-dependent utility, state-dependent utility, Choquet-expected utility, and prospect theory.
An Object-Oriented Methodology for Solving Assignment-Type Problems with Neighborhood Search Techniques
Authors: Ferland Jacques A. , Hertz Alain , Lavoie Alain
Published: November 2008

Because of its specificity, it is usually difficult to reuse computer code developed for a given combinatorial problem to deal with another one. We use the Object Oriented Programming methodology to derive general purpose software including four different neighborhood search techniques (descent method, tabu search, exchange procedure, simulated annealing) to deal with any assignment-type problem with a bare minimum of coding effort. The structure of the software even allows a more advanced user to play around with several parameters of these techniques and to modify the techniques to create specific variants.
Managing Uncertainty in a Serial Production Line
Authors: Denardo Eric V. , Lee Thomas Y. S.
Published: November 2008

This paper studies a serial production line that is uncertain. We introduce a linear model of the uncertainty that can exist in the demand for the product and in each stage's processing time, yield, rework probability, and reliability. We construct a linear discrete-time rule for controlling production, and we show that repeated application of this rule leads the system to steady-state conditions, which include closed-form formulas for the mean and variance of each buffer's stock and the mean and variance of the workload in each stage. We optimize these operating characteristics by a convex nonlinear program. For the case of identical stages with no scrap, we show that this optimal solution tends to place larger buffer stocks toward the end of the line. We adapt these discrete-time results to the short-period surrogate of the analogous continuous-time control problem.
Scheduling a Make-To-Stock Queue: Index Policies and Hedging Points
Authors: Veatch Michael H. , Wein Lawrence M.
Published: November 2008

A single machine produces several different classes of items in a make-to-stock mode. We consider the problem of scheduling the machine to regulate finished goods inventory, minimizing holding and backorder, or holding and lost sales costs. Demands are Poisson, service times are exponentially distributed, and there are no delays or costs associated with switching products. A scheduling policy dictates whether the machine is idle or busy and specifies the job class to serve in the latter case. Since the optimal solution can be numerically computed only for problems with several products, our goal is to develop effective policies that are computationally tractable for a large number of products. We develop index policies to decide which class to produce, including Whittle's “restless bandit” index, which possesses a certain asymptotic optimality. Several idleness policies are derived, and the best policy is obtained from a heavy traffic diffusion approximation. Nine sample problems are considered in a numerical study, and the average suboptimality of the best policy is less than 3%.
A Note on Heuristics of Flow-Shop Scheduling
Authors: Lai Tsung-Chyan
Published: November 2008

We present an O(mn) two-group (TG) heuristic for the m-machine, n-job permutation flow-shop scheduling problem. We show that heuristic TG has a worst-case performance ratio of (m + 1)/2. We also establish worst-case bounds for several heuristics proposed in the past.
Allocating Production Capacity Among Multiple Products
Authors: Glasserman Paul
Published: November 2008

We consider the problem of allocating production capacity among multiple items, assuming that a fixed proportion of overall capacity can be dedicated exclusively to the production of each item. Given a capacity allocation, production of each item follows a base-stock policy, i.e., each demand triggers a replenishment order to restore safety stocks to target levels. We present procedures for choosing base-stock levels and capacity allocations that are asymptotically optimal. Our objective is to minimize holding and backorder costs, or to minimize holding costs subject to a service-level constraint. Asymptotic optimality refers to large backorder penalties or stringent service-level constraints. Numerical results indicate that our rules perform very well even far from the asymptotic regime. A further approximation step results in allocation rules based on heavy-traffic limits; these, too, perform well.
Mean Flow Time Minimization in Reentrant Job Shops with a Hub
Authors: Kubiak Wieslaw , Lou Sheldon X. C. , Wang Yingmeng
Published: November 2008

This paper considers a reentrant job shop with one hub machine which a job enters K times. Between any two consecutive entries into the hub, the job is processed on other machines. The objective is to minimize the total flow time. Under two key assumptions, the bottleneck assumption and the hereditary order (HO) assumption on the processing times of the entries, it is proved that there is an optimal schedule with the shortest processing time (SPT) job order and a dynamic programming algorithm is derived to find such a schedule. An approximation algorithm based on the shortest path algorithm and the SPT job order is also proposed to solve the problem. The approximation algorithm finds an optimal clustered schedule. In clustered schedules, jobs are scheduled in disjoint clusters; they resemble batch processing and seem to be of practical importance. Worst-case bounds for clustered schedules are proved with the HO assumption relaxed. Two special cases with the restriction that there are only two entries to the hub machine are further analyzed to offer more insight into the structure of optimal solutions.
Implementing Setup Optimization on the Shop Floor
Authors: Jain Shailendra , Johnson M. Eric , Safai Fereydoon
Published: November 2008

We develop a model and solution algorithm for sequencing production on a flexible assembly line. The model incorporates the practical considerations of printed circuit board (PCB) assembly where the goal is to reduce the time spent in setup. We discuss the practical implementation problems of integrating optimization software on the shop floor—both from an operations research and systems perspective. We describe Hewlett-Packard's successful use of the software and the limitations of production sequencing in PCB assembly.
The Plant Location Problem: New Models and Research Prospects
Authors: Revelle Charles S. , Laporte Gilbert
Published: November 2008

The plant location problem has been studied for many years. Yet, a number of important real world issues and variants have not been investigated or resolved and merit further attention and research. This paper describes new statements of the problem (1) with new and different objectives, (2) with multiple products and multiple machines in which new models of production are considered, and (3) with spatial interactions.
Hub Location and the p-Hub Median Problem
Authors: Campbell James F.
Published: November 2008

Hub facilities serve as switching and transshipment points in transportation and communication networks. Hub networks concentrate flows on the hub-to-hub links and benefit from economies of scale in interhub transportation. Most hub location research has focused on problems where each origin/destination is allocated to a single hub. However, multiple allocation to more than one hub is necessary to minimize total transportation costs. This paper defines a p-hub median, analogous to a p-median, and presents integer programming formulations for the multiple and single allocation p-hub median problems. Two new heuristics for the single allocation p-hub median problem are evaluated. These heuristics derive a solution to the single allocation p-hub median problem from the solution to the multiple allocation p-hub median problem. Computational results are presented for problems with 10–40 origins/destinations and up to eight hubs. The new heuristics generally perform well in comparison with other heuristics.
Two-Moment Analysis of Open Queueing Networks with General Workstation Capabilities
Authors: Harrison J. Michael , Pich Michael T.
Published: November 2008

The QNET method for two-moment analysis of multiclass open networks is extended to allow complex workstations of various types. For example, the extension described here allows one to treat stations where several unreliable machines are tended by a small number of repair technicians, or stations where several machines that require setups are tended by a small number of operators. To illustrate the general concepts, a four-station manufacturing example is discussed in detail. In the QNET method, one first replaces the original queueing network by an approximating Brownian system model. The Brownian approximation is motivated by heavy traffic theory, and to achieve a unified treatment of complex workstations within the QNET framework we apply the following principle: For purposes of heavy traffic analysis, a workstation can be characterized by just two parameters, the asymptotic mean and asymptotic variance of its cumulative potential output process. This heavy traffic principle has long been known to researchers in the field, but we show that it has power and utility even in circumstances where the mean and variance parameters cannot be determined analytically. We explain how the heavy traffic principle can be applied successfully under certain conditions, and show by example that those conditions are not always met.
Capacity Allocation for Dynamic Process Improvement with Quality and Demand Considerations
Authors: Chand Suresh , Moskowitz Herbert , Novak Andreas , Rekhi Ishpal , Sorger Gerhard
Published: November 2008

Management of process improvement activities is an essential part of the manufacturing strategy of a firm to remain globally competitive in the long run. This paper considers a manufacturing environment where process improvement activities require use of the productive capacity of the firm in addition to other investments. Thus the firm must allocate its productive capacity between production activities and improvement activities. The output of production activities is used to meet customer demand. Process improvement activities improve the quality of the output, which in turn leads to lower quality related costs (both internal and external) and possibly lower per-unit production cost. It is assumed that the demand function is downward sloping and that revenue is a concave function of output. A continuous-time, finite-horizon, profit maximization, resource allocation model is developed to find an optimal time path for process improvement activities and production activities. Computational results are provided to study the effect of various problem parameters on the optimal decisions.
The Impact of Setup Times on the Performance of Multiclass Service and Production Systems
Authors: Federgruen Awi , Katalan Ziv
Published: November 2008

We characterize the impact of the means and distributions of setup times in polling systems. Starting with cyclic systems with exhaustive service, we show that the vector of average setup times affects the complete distribution of waiting times and queue sizes only via its sum. In addition, all moments of all waiting times and queue sizes are reduced if the higher order moments of one or more of the setup times is reduced while maintaining their means. We also obtain a fundamental decomposition result of the queue sizes at polling instants which is reminiscent of those obtained in vacation models. We show that the above results continue to apply under more general and more efficient protocols, e.g., general polling tables, systems with gated service, and systems with mixed service.
Heuristics for a One-Warehouse Multiretailer Distribution Problem with Performance Bounds
Authors: Herer Yale , Roundy Robin
Published: November 2008

We investigate the one warehouse multiretailer distribution problem with traveling salesman tour vehicle routing costs. We model the system in the framework of the more general production/distribution system with arbitrary non-negative monotone joint order costs. We develop polynomial time heuristics whose policy costs are provably close to the cost of an optimal policy. In particular, we show that given a submodular function which is close to the true order cost then we can find a power-of-two policy whose cost is only moderately greater than the cost of an optimal policy. Since such submodular approximations exist for traveling salesman tour vehicle routing costs we present a detailed description of heuristics for the one warehouse multiretailer distribution problem.

We formulate a nonpolynomial dynamic program that computes optimal power-of-two policies for the one warehouse multiretailer system assuming only that the order costs are non-negative monotone.

Finally, we perform computational tests which compare our heuristics to optimal power of two policies for problems of up to sixteen retailers. We also perform computational tests on larger problems; these tests give us insight into what policies one should employ.
A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
Authors: Mireault Paul , Orlin James B. , Vohra Rakesh V.
Published: November 2008

We consider the problem of minimizing the makespan when scheduling tasks on two uniform parallel machines, where one machine is q times as efficient on each task as is the other. We compute the maximum relative error of the LPT (largest processing time first) heuristic as an explicit function of q. In the special case that the two machines are identical (q = 1), our problem and heuristic reduce to the problem and heuristic analyzed by Graham (Graham, R. 1969. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17 416–429.).
A Markov Chain Approach to Baseball
Authors: Bukiet Bruce , Harold Elliotte Rusty , Palacios José Luis
Published: November 2008

Most earlier mathematical studies of baseball required particular models for advancing runners based on a small set of offensive possibilities. Other efforts considered only teams with players of identical ability. We introduce a Markov chain method that considers teams made up of players with different abilities and which is not restricted to a given model for runner advancement. Our method is limited only by the available data and can use any reasonable deterministic model for runner advancement when sufficiently detailed data are not available. Furthermore, our approach may be adapted to include the effects of pitching and defensive ability in a straightforward way. We apply our method to find optimal batting orders, run distributions per half inning and per game, and the expected number of games a team should win. We also describe the application of our method to test whether a particular trade would benefit a team.
An Approximation Method for the Analysis of GI/G/1 Queues
Authors: Li Jingwen
Published: November 2008

We study in this paper an approximation method for the calculation of various performance measures of a GI/G/1 queue. Instead of solving the waiting time directly, we analyze the idle-period distribution as the starting point. The result is then taken as input to many known results to get other performance measures. We show that the distribution of the GI/G/1 idle period satisfies a nonlinear integral equation. This equation directly leads to an accurate approximate solution of the idle-period distribution of the GI/G/1 queue where the interarrival times have a generalized hyperexponential distribution (GH). Since all distribution functions can be approximated by a GH distribution at any given accuracy (Botta and Harris [Botta, R. F., C. M. Harris. 1986. Approximation with generalized hyperexponential distributions: Weak convergence results. Queueing Systems 2 169–190.]), the solution method developed in this paper serves as a unified basis for the analysis of GI/G/1 queues.
A Heuristic for a Scheduling Problem with Communication Delays
Authors: Munier Alix , König Jean-Claude
Published: November 2008

This paper addresses a scheduling problem with interprocessor communication delays: the jobs and the communication delays are of unit length. The number of processors is unbounded. The aim is to minimize the makespan.

We develop a new list scheduling heuristic and we prove that its worst-case relative performance is 4/3.
A Multiproduct Dynamic Pricing Problem and Its Applications to Network Yield Management
Authors: Gallego Guillermo , van Ryzin Garrett
Published: November 2008

A firm has inventories of a set of components that are used to produce a set of products. There is a finite horizon over which the firm can sell its products. Demand for each product is a stochastic point process with an intensity that is a function of the vector of prices for the products and the time at which these prices are offered. The problem is to price the finished products so as to maximize total expected revenue over the finite sales horizon. An upper bound on the optimal expected revenue is established by analyzing a deterministic version of the problem. The solution to the deterministic problem suggests two heuristics for the stochastic problem that are shown to be asymptotically optimal as the expected sales volume tends to infinity. Several applications of the model to network yield management are given. Numerical examples illustrate both the range of problems that can be modeled under this framework and the effectiveness of the proposed heuristics. The results provide several fundamental insights into the performance of yield management systems.
Performance Measures and Schedules in Periodic Job Shops
Authors: Lee Tae-Eog , Posner Marc E.
Published: November 2008

This paper discusses the periodic job shop scheduling problem, a problem where an identical mixture of items, called a minimal part set (MPS), is repetitively produced. The performance and behavior of schedules are discussed. Two basic performance measures, cycle time and makespan, are shown to be closely related. The minimum cycle time is identified as a circuit measure in a directed graph. We establish that there exists a class of schedules that minimizes cycle time and repeats an identical timing pattern every MPS. An algorithm is developed to construct such schedules. We show that minimizing the makespan as a secondary criterion, minimizes several other performance measures.

For makespan minimization, we examine earliest starting schedules where each operation starts as soon as possible. We characterize the cases where after a finite number of MPSs, the earliest starting schedule repeats an identical timing pattern every fixed number of MPSs. We also develop a modification to an earliest starting schedule that repeats an identical timing pattern every MPS when the beginning operations on the machines are delayed.
OR/MS Publications: Extension of the Analysis of U.S. Flagship Journals to the United Kingdom
Authors: Ormerod Richard , Kiossis Ioannis
Published: November 2008

Reisman and Kirschnick (Reisman, A., F. Kirschnick. 1994. The devolution of OR/MS: Implications from a statistical content analysis of papers in flagship journals. Opns. Res. 42 577–588.) have analysed United States Flagship OR/MS Journals over a thirty-year period using statistical content analysis. We have applied their method of analysis, which seeks to distinguish between the space devoted to theory on the one hand and that devoted to applications on the other, to journals based in the United Kingdom. Using their definitions we have classified articles published in the Journal of the Operational Research Society (previously OR Quarterly), OMEGA, and OR Insight over the period from 1962 to 1994 to parallel their study. As well as shedding some light on the direction that OR/MS is taking in the United Kingdom, comparison is made with trends in the United States. Further, the European Journal of Operational Research has also been included in the analysis, adding a European dimension. The country of affiliation of the authors has been analysed, providing data on the publishing habits of U.S. authors in the United Kingdom and European-based journals. This casts new light on the findings of Reisman and Kirschnick (Reisman, A., F. Kirschnick. 1994. The devolution of OR/MS: Implications from a statistical content analysis of papers in flagship journals. Opns. Res. 42 577–588.). Finally, the paper contributes to the debate about the current state and future direction of OR/MS.
A Branch-and-Bound Procedure for the Generalized Resource-Constrained Project Scheduling Problem
Authors: Demeulemeester Erik L. , Herroelen Willy S.
Published: November 2008

In this paper a branch-and-bound procedure is described for scheduling project activities subject to precedence diagramming type of precedence relations, ready times, due dates, and variable multiple resource availability constraints, where the objective is to minimize project duration. The procedure is based on a depth-first solution strategy in which nodes in the solution tree represent resource and precedence feasible partial schedules. Branches emanating from a parent node correspond to exhaustive and minimal combinations of activities, the delay of which resolves resource conflicts at each parent node. A precedence based lower bound and several dominance rules are introduced in order to restrict the growth of the solutions tree. The procedure has been programmed in the C language. Extensive computational experience is reported.
Optimized Crossover for the Independent Set Problem
Authors: Aggarwal Charu C. , Orlin James B. , Tai Ray P.
Published: November 2008

We propose a knowledge-based crossover mechanism for genetic algorithms that exploits the structure of the solution rather than its coding. More generally, we suggest broad guidelines for constructing the knowledge-based crossover mechanisms. This technique uses an optimized crossover mechanism, in which the one of the two children is constructed in such a way as to have the best objective function value from the feasible set of children, while the other is constructed so as to maintain the diversity of the search space. We implement our approach on a classical combinatorial problem, called the independent set problem. The resulting genetic algorithm dominates all other genetic algorithms for the problem and yields one of the best heuristics for the independent set problem in terms of robustness and time performance. The primary purpose of this paper is to demonstrate the power of knowledge based mechanisms in genetic algorithms.
Bounds and Asymptotics for Planning Critical Safety Stocks
Authors: Glasserman Paul
Published: November 2008

We develop bounds and approximations for setting base-stock levels in production-inventory systems with limited production capacity. Our approximations become exact as inventories become critical, meaning either that the target service level is very high or the backorder penalty is very large. Our bounds apply even without this requirement. We consider both single-stage and multi-stage systems. For single-stage systems, we find tight bounds and asymptotically exact approximations for optimal base-stock levels; for multistage systems, our results give partial characterizations of the optimal levels. Part of our analysis is a precise connection, in the critical regime, between a multistage system and an associated single-stage system consisting solely of the bottleneck facility.
Short Shop Schedules
Authors: Williamson D. P. , Hall L. A. , Hoogeveen J. A. , Hurkens C. A. J. , Lenstra J. K. , Sevast'janov S. V. , Shmoys D. B.
Published: November 2008

We consider the open shop, job shop, and flow shop scheduling problems with integral processing times. We give polynomial-time algorithms to determine if an instance has a schedule of length at most 3, and show that deciding if there is a schedule of length at most 4 is 𝒩𝒫-complete. The latter result implies that, unless 𝒫 = 𝒩𝒫, there does not exist a polynomial-time approximation algorithm for any of these problems that constructs a schedule with length guaranteed to be strictly less than 5/4 times the optimal length. This work constitutes the first nontrivial theoretical evidence that shop scheduling problems are hard to solve even approximately.
On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows
Authors: Bramel Julien , Simchi-Levi David
Published: November 2008

The Vehicle Routing Problem with Time Windows (VRPTW) is one of the most important problems in distribution and transportation. A classical and recently popular technique that has proven effective for solving these problems is based on formulating them as a set covering problem. The method starts by solving its linear programming relaxation, via column generation, and then uses a branch and bound strategy to find an integer solution to the set covering problem: a solution to the VRPTW. An empirically observed property is that the optimal solution value of the set covering problem is very close to its linear programming relaxation which makes the branch and bound step extremely efficient. In this paper we explain this behavior by demonstrating that for any distribution of service times, time windows, customer loads, and locations, the relative gap between fractional and integer solutions of the set covering problem becomes arbitrarily small as the number of customers increases.
Complexity of the Discrete Time-Cost Tradeoff Problem for Project Networks
Authors: De Prabuddha , Dunne E. James , Ghosh Jay B. , Wells Charles E.
Published: November 2008

This note addresses the discrete version of the well-known time-cost tradeoff problem for project networks, which has been studied previously in the standard project management literature as well as in the related literature on Decision-CPM. All the algorithms proposed thus far for the solution of the general problem exhibit exponential worst-case complexity, with the notable exception of the pseudo-polynomial dynamic program due to Hindelang and Muth. We first demonstrate that this algorithm is flawed, and that when we correct it, it no longer remains pseudo-polynomial. Continuing on in the main result of the note, we show that this is not at all surprising, since the problem is strongly NP-hard. Finally, we discuss the complexities of various network structures and validate an old conjecture that certain structures are necessarily more difficult to solve.