bluuebunny/crossref_metadata_2025 huggingface dataset:
Basic Techniques for Lot Streaming
Authors: Trietsch Dan , Baker Kenneth R.
Published: November 2008

We present an overview of basic models and solution algorithms for the lot streaming problem. We include models with continuous and discrete sublot sizes, models with and without intermittent idling of machines, and models with consistent and variable sublots. We also introduce a model with limited transporter capacity. First we present solutions for two machines, then generalize to three machines and, where possible, to several machines. We synthesize previous research and introduce several new results.
Batching and Scheduling in FMS Hubs: Flow Time Considerations
Authors: Lane Daniel E. , Sidney Jeffrey B.
Published: November 2008

Many flexible manufacturing systems (FMS) involve complex queueing networks in the processing of lots (jobs) in a production facility. In particular, the feedback of lots to a common, multipurpose workstation, or hub, processing different tasks for the same lot at various points in the production process, can create serious scheduling problems. This paper models the hub structure and presents some results for dual measures of flow time in the facility, namely, total flow time required for a fixed number of lots (or makespan), and average flow time for all lots (or average completion time). The flow time performance is a function of different batch sizes and priority scheduling rules for lots arriving at the hub. The results can be used to establish strategies for batching and scheduling lots according to adjustments in the importance of the cycle time versus the work-in-process (WIP) tradeoff. Extensions of the results to more general production facilities are also discussed.
Time-Sharing Policies for Controlled Markov Chains
Authors: Altman Eitan , Shwartz Adam
Published: November 2008

We propose a class of nonstationary policies called policy time sharing (PTS), which possesses several desirable properties for problems where the criteria are of the average-cost type; an optimal policy exists within this class, the computation of optimal policies is straightforward, and the implementation of this policy is easy. While in the finite state case stationary policies are also known to share these properties, the new policies are much more flexible, in the sense that they can be applied to solve adaptive problems, and they suggest new ways to incorporate the particular structure of the problem at-hand into the derivation of optimal policies. In addition, they provide insight into the pathwise-structure of controlled Markov chains. To use PTS policies one alternates between the use of several stationary deterministic policies, switching when reaching some predetermined state. In some (countable state) cases optimal solutions of the PTS type are available and easy to compute, whereas optimal stationary policies are not available. Examples that illustrate the last point and the usefulness of the new approach are discussed, involving constrained optimization problems with countable state space or compact action space.
On the Convergence of a Hyperboloid Approximation Procedure for the Perturbed Euclidean Multifacility Location Problem
Authors: Rosen J. B. , Xue G. L.
Published: November 2008

For the Euclidean single facility location problem, E. Weiszfeld proposed a simple closed-form iterative algorithm in 1937. Later, numerous authors proved that it is a convergent descent algorithm. In 1973, J. Eyster, J. White and W. Wierwille extended Weiszfeld's idea and proposed a Hyperboloid Approximation Procedure (HAP) for solving the Euclidean multifacility location problem. They believed, based on considerable computational experience, that the HAP always converges. In 1977, Ostresh proved that the HAP is a descent algorithm under certain conditions. In 1981, Morris proved that a variant of the HAP always converges. However, no convergence proof for the original HAP has ever been given. In this paper, we prove that the HAP is a descent algorithm and that it always converges to the minimizer of the objective function from any initial point.
Likelihood Ratio Sensitivity Analysis for Markovian Models of Highly Dependable Systems
Authors: Nakayama Marvin K. , Goyal Ambuj , Glynn Peter W.
Published: November 2008

This paper discusses the application of the likelihood ratio gradient estimator to simulations of large Markovian models of highly dependable systems. Extensive empirical work, as well as some mathematical analysis of small dependability models, suggests that (in this model setting) the gradient estimators are not significantly more noisy than the estimates of the performance measures themselves. The paper also discusses implementation issues associated with likelihood ratio gradient estimation, as well as some theoretical complements associated with application of the technique to continuous-time Markov chains.
Analysis of the ΣPhi/Ph/1 Queue
Authors: Bitran Gabriel R. , Dasu Sriram
Published: November 2008

In this paper, we analyze a queue to which the arrival process is the superposition of separate arrival streams, each of whose interarrival time distributions is of phase type, and the service time distribution is also of phase type. The performance measures derived for this queue include: the distribution of the number in the system as seen by each customer class upon arrival, Laplace-Stieltjes transform (LST) of the waiting-time distribution for each customer class, stationary interdeparture time distribution and the lag correlation coefficients of the departure process, and characteristics of the tails of the waiting time and queue length distributions.
Scheduling Unit-Time Open Shops with Deadlines
Authors: Tautenhahn Thomas
Published: November 2008

We consider open shop problems with unit processing times and due dates, where n jobs have to be processed on m machines. The order in which a given job is processed on the machines is not fixed. Such problems occur in testing components of an electronic system or doing repair work on automobiles. In an earlier paper, C. Y. Liu and R. L. Bulfin gave an O(n2m) algorithm to minimize total tardiness and the number of tardy jobs. We will give a polynomial algorithm to minimize the completion time of all jobs where a deadline is imposed for each job. The complexity of this problem is still open. Then we apply this solution to give improved algorithms to minimize the number of tardy jobs and the maximum lateness.
Optimal Real-Time Data Acquisition and Processing by a Multiserver Stand-by System
Authors: Kreimer Joseph , Mehrez Abraham
Published: November 2008

We obtain an optimal operation policy for a general n-server (channel, machine) stand-by system involving preventive maintenance and operating in real time. We show that such a policy is achieved by successive total use of each server capacity, and does not depend on the arrival pattern of processed data and task duration. We show also that this policy is optimal for any finite, initial period of time, and not only in the sense of long-run availability. The analysis is performed in two stages: a worst-case analysis is performed, and then, a general case is treated. Such a consecutive approach also seems to be useful in the analysis of more complicated systems. Rigorous mathematical proofs are provided. Actual and possible applications of results to military and production control systems are discussed.
Ten Years of the OR Practice Section
Authors: Rothkopf Michael H.
Published: November 2008

The OR Practice Section of Operations Research is approaching its tenth anniversary. This note examines and interprets the nature of the papers that it has attracted and argues that they suggest vigor in the practice of operations research.
Operations Research in Libraries: A Review of 25 Years of Activity
Authors: Reisman Arnold , Xu Xiaomei
Published: November 2008

This paper reviews the record of OR/MS applications to library management. Although libraries constitute a major factor in both the public and the private (not-for-profit) sectors, OR/MS has not fulfilled its potential in enhancing the cost effectiveness of library systems.
The Age of Optimization: Solving Large-Scale Real-World Problems
Authors: Nemhauser George L.
Published: November 2008

In the last decade, new advances in algorithms have been as important as the impressive advances in computer technology. Using the new interior-point algorithms and advanced implementations of simplex methods, we can now solve linear programs with more than one million variables and thousands of constraints. Preprocessing and polyhedral theory have yielded at least an order of magnitude improvement in branch-and-bound algorithms for solving mixed integer programs. Moreover, these algorithmic advances have been incorporated in commercially inexpensive software that is readily available, easily portable, and supported by a variety of systems that make it possible for unsophisticated users to input and check their models and obtain understandable outputs. This paper, based on the Morse Lecture given in May 1993 at the TIMS/ORSA meeting in Chicago, begins with some of the modem history of optimization, then surveys some recent developments (illustrating them with an application in the airline industry), and closes with some remarks about the future.
Needed: An Empirical Science of Algorithms
Authors: Hooker J. N.
Published: November 2008

Deductive algorithmic science has reached a high level of sophistication, but its worst-case and average-case results seldom tell us how well an algorithm is actually going to work in practice. I argue that an empirical science of algorithms is a viable alternative. I respond to misgivings about an empirical approach, including the prevalent notion that only a deductive treatment can be “theoretical” or sophisticated. NP-completeness theory, for instance, is interesting partly because it has significant, if unacknowledged, empirical content. An empirical approach requires not only rigorous experimental design and analysis, but also the invention of empirically-based explanatory theories. I give some examples of recent work that partially achieves this aim.
Scheduling Multiple Variable-Speed Machines
Authors: Trick Michael A.
Published: November 2008

We examine scheduling problems where we control not only the assignment of jobs to machines, but also the time used by the job on the machine. For instance, many tooling machines allow control of the speed at which a job is run. Increasing the speed incurs costs due to machine wear, but also increases throughput. We discuss some fundamental scheduling problems in this environment and give algorithms for some interesting cases. Some cases are inherently difficult so for these we give heuristics. Our approach illustrates the exploitation of underlying network structure in combinatorial optimization problems. We create heuristics that optimally schedule a large portion of the jobs and then attempt to fit in the remainder. This also gives a method for quickly finding valid inequalities violated by the linear relaxation solution. For the problem of minimizing the sum of makespan and production costs, a rounding heuristic is within a constant factor of optimal. Our heuristics are compared to other classical heuristics.
A Stochastic Analysis of State Transitions in an Air-Space Management System
Authors: Ringel Emanuel I. , Mode Charles J.
Published: November 2008

This paper explores the application of stochastic process ideas to answer some fundamental questions about a state system which arises in the Mode Select Beacon System (Mode-S), an air-space management system. A series of models is developed, based on semi-Markov processes, population models, and Monte Carlo simulation. Computer programs in the APL programming language to implement the models and to process the resulting data are developed. The output of the models illuminate the behavior of the state system by providing predictions with confidence bounds about the movements of aircraft among the states over time.
An Algorithm for the Multiattribute, Multicommodity Flow Problem with Freight Consolidation and Inventory Costs
Authors: Popken Douglas A.
Published: November 2008

To remain competitive, manufacturers must seek transportation strategies that both reduce costs and maintain high levels of service. One approach is to consolidate inbound freight at transshipment points. This provides economies of scale and promotes capacity efficient mixes of high and low density items. When service level considerations are included via inventory holding costs, the approach yields a nonlinear network model with multiattribute multicommodity flows. The model is difficult to solve for global optimality in that the objective function is neither convex nor concave; therefore, a composite algorithm is proposed. The algorithm alternates between a linearization technique to find local optima and a heuristic search based on “adjacent concave flows” to provide local improvements. Computational results demonstrate the ability of the multiattribute approach to identify savings in overall transportation and inventory costs when compared to a single attribute approach.
Worst-Case Analysis of Heuristics for the Bin Packing Problem with General Cost Structures
Authors: Anily Shoshana , Bramel Julien , Simchi-Levi David
Published: November 2008

We consider the famous bin packing problem where a set of items must be stored in bins of equal capacity. In the classical version, the objective is to minimize the number of bins used. Motivated by several optimization problems that occur in the context of the storage of items, we study a more general cost structure where the cost of a bin is a concave function of the number of items in the bin. The objective is to store the items in such a way that total cost is minimized. Such cost functions can greatly alter the way the items should be assigned to the bins. We show that some of the best heuristics developed for the classical bin packing problem can perform poorly under the general cost structure. On the other hand, the so-called next-fit increasing heuristic has an absolute worst-case bound of no more than 1.75 and an asymptotic worst-case bound of 1.691 for any concave and monotone cost function. Our analysis also provides a new worst-case bound for the well studied next-tit decreasing heuristic when the objective is to minimize the number of bins used.
Optimal Control of a Two-Station Tandem Production/Inventory System
Authors: Veatch Michael H. , Wein Lawrence M.
Published: November 2008

A manufacturing facility consisting of two stations in tandem operates in a make-to-stock mode: After production, items are placed in a finished goods inventory that services an exogenous Poisson demand. Demand that cannot be met from inventory is backordered. Each station is modeled as a queue with controllable production rate and exponential service times. The problem is to control these rates to minimize inventory holding and backordering costs. Optimal controls are computed using dynamic programming and compared with the kanban, basestock and buffer control mechanisms that have been proposed for manufacturing facilities. Conditions are found under which certain simple controls are optimal using stochastic coupling arguments. Insights are gained into when to hold work-in-process and finished goods inventory, comparable to previous studies of production lines in make-to-order and unlimited demand environments.
Observing Queues Before Joining
Authors: Hlynka M. , Stanford D. A. , Poon W. H. , Wang T.
Published: November 2008

We consider a queueing system with two servers, each with its own queue. The interarrival times are generally distributed. The service time for each server is exponentially distributed but the rates may be different. No jockeying between the two queues is allowed. We consider situations in which a smart customer can delay joining a queue until some arrivals or service departures have been observed. All other customers join the shortest queue. We find conditions under which the smart customer can lower its expected sojourn time in the system by waiting and observing rather than immediately joining the shortest queue.
The Relationship Between Bernoulli and Fixed Feedback Policies for the M/G/1 Queue
Authors: Adve Vikram S. , Nelson Randolph
Published: November 2008

We consider an M/G/1 queue with feedback, in which customers, after receiving service, either return to the tail of the queue or depart the system, according to some feedback policy. We derive simple expressions for the expected response time for feedback policies that include Bernoulli feedback and feeding back a fixed number of times. Our results reveal some interesting and nonintuitive properties of the behavior of such feedback policies when the coefficient of variation of service time is varied. One result shows that for the Bernoulli feedback and fixed feedback policies with an equal mean number of visits to the queue, the expected response time for the Bernoulli policy is smaller than for the fixed policy if the coefficient of variation of service time is greater than 1. The relationship reverses if the coefficient of variation is less than 1.
Application of State-Dependent Queues to Pedestrian/Vehicular Network Design
Authors: Smith J. MacGregor
Published: November 2008

State-dependent queues and finite capacity queueing network models of facilities are important tools for the topological design of facilities, the routing of customers, and the allocation of resources to accommodate customer traffic. Key properties of these M/G/C/C queueing models and their applications in facility planning are described in detail. The incorporation of these concepts, tools, and techniques is important to the OR profession because they provide a unifying, system-wide planning methodology for tackling the many complex issues of designing, analyzing, and synthesizing pedestrian traffic flows in large-scale facilities and their environments. The scope and limitations of the methodology are demonstrated in the design of a pedestrian/vehicular circulation system of a large regional hospital campus.
Solving a Class of Stochastic Minimization Problems
Authors: Bailey Michael P.
Published: November 2008

This work gives a methodology for analyzing a class of discrete minimization problems with random element weights. The minimum weight solution is shown to be an absorbing state in a Markov chain, while the distribution of weight of the minimum weight element is shown to be of phase type. We then present two-sided bounds for matroids with NBUE distributed weights, as well as for weights with bounded positive hazard rates. We illustrate our method using a realistic military communications problem.
Minimal Forecast Horizons and a New Planning Procedure for the General Dynamic Lot Sizing Model: Nervousness Revisited
Authors: Federgruen Awi , Tzur Michal
Published: November 2008

We show for the general dynamic lot sizing model how minimal forecast horizons may be detected by a slight adaptation of an earlier O(n log n) or O(n) forward solution method for the model. A detailed numerical study indicates that minimal forecast horizons tend to be small, that is, include a small number of orders. We describe a new planning approach to ensure stability of the lot sizing decisions over an initial interval of time or stability horizon in those (relatively rare) cases where no planning horizon is detected or where the stability horizon extends beyond the planning horizon. To this end, we develop a heuristic, but full horizon-based adaptation of the optimal lot sizing schedule, designed to minimize an upper bound for the worst-case optimality gap under the desired stability conditions. We also show how the basic horizon length n may be chosen to guarantee any prespecified positive optimality gap.
On Optimal Replacement Policies—Random Horizon
Authors: Banerjee P. K. , Kabadi S. N.
Published: November 2008

A system with a functional life of T units of time requires a certain functional part for its operation. If this part fails before the failure of the system, it has to be replaced immediately to keep the system in operation. Two brands are available for replacements. These two brands differ in unit costs and life distributions. The objective is to determine a time-dependent replacement policy that minimizes the expected operational cost. We show that if certain conditions are satisfied, then the optimal policy exists and has a simple intuitive structure.
Improved Algorithms for Machine Allocation in Manufacturing Systems
Authors: Frenk Hans , Labbé Martine , van Vliet Mario , Zhang Shuzhong
Published: November 2008

In this paper we present two algorithms for a machine allocation problem occurring in manufacturing systems. For the two algorithms presented we prove worst-case performance ratios of 2 and 3/2, respectively. The machine allocation problem we consider is a general convex resource allocation problem, which makes the algorithms applicable to a variety of resource allocation problems. Numerical results are presented for two real-life manufacturing systems.
An Improved Algorithm for Finding Optimal Lot Sizing Policies for Finite Production Rate Assembly Systems
Authors: Roundy Robin O. , Sun Daning
Published: November 2008

We show that an O(n3 log n) algorithm can find optimal power-of-two lot size policies for finite production rate assembly systems. This Improves an O(n5) algorithm proposed in D. Atkins, M. Queyranne and D. Sun's 1992 paper.
Quantitative Methods in Credit Management: A Survey
Authors: Rosenberg Eric , Gleit Alan
Published: November 2008

Many static and dynamic models have been used to assist decision making in the area of consumer and commercial credit. The decisions of interest include whether to extend credit, how much credit to extend, when collections on delinquent accounts should be initiated, and what action should be taken. We survey the use of discriminant analysis, decision trees, and expert systems for static decisions, and dynamic programming, linear programming, and Markov chains for dynamic decision models. Since these models do not operate in a vacuum, we discuss some important aspects of credit management in practice, e.g., legal considerations, sources of data, and statistical validation of the methodology. We provide our perspective on the state-of-the-art in theory and in practice.
Optimal Production Sequence for a Product with Matching Components
Authors: So Kut C. , Scott Carlton H.
Published: November 2008

In the manufacture of mechanical heart valves, very high precision manufacturing and quality control is an absolute necessity. Since a mechanical heart valve consists of a number of components, it is imperative that the components match precisely. Motivated by this need in heart valve manufacturing, we study a new production control model for a product comprised of matching components. The model is also applicable to other production systems for manufacturing high precision products requiring careful matching of components. For a two-component case, we prove that a “greedy” production sequencing rule is optimal. Based on this result, we then develop an effective greedy heuristic sequencing rule for more general cases. An extensive empirical study is used to evaluate the performance of this and one other heuristic rule.
Optimal Control Policy for Stochastic Inventory Systems with Markovian Discount Opportunities
Authors: Zheng Yu-Shen
Published: November 2008

In this paper, we study a single-item continuous-review inventory system with Poisson demand. In addition to the standard cost structure of a fixed setup cost and a quasiconvex expected inventory holding and shortage cost, special opportunities for placing orders at a discounted setup cost occur according to a Poisson process that is independent of the demand process. This model has been studied as a subproblem of multi-item/location inventory systems where there are economies-of-scale in joint replenishment. For the single-item model, the literature proposes the (s, c, S) policy, under which an order is placed to increase the inventory position to S either when the inventory position drops to s, or when the inventory position is at or below c and a discount opportunity occurs. We prove that the (s, c, S) policy is optimal for the model, develop an efficient algorithm for computing optimal control parameters s*, c*, S*, and carry out a parametric analysis showing the effects of changes in problem parameters on the optimal control parameters and the minimum cost.
Markov Decision Processes with Imprecise Transition Probabilities
Authors: White Chelsea C. , Eldeib Hany K.
Published: November 2008

We present new numerical algorithms and bounds for the infinite horizon, discrete stage, finite state and action Markov decision process with imprecise transition probabilities. We assume that the transition probability mass vector for each state and action is described by a finite number of linear inequalities. This model of imprecision appears to be well suited for describing statistically determined confidence limits and/or natural language statements of likelihood. The numerical procedures for calculating an optimal max-min strategy are based on successive approximations, reward revision, and modified policy iteration. The bounds that are determined are at least as tight as currently available bounds for the case where the transition probabilities are precise.
Transient Behavior of the M/G/1 Workload Process
Authors: Abate Joseph , Whitt Ward
Published: November 2008

In this paper we describe the time-dependent moments of the workload process in the M/G/1 queue. The kth moment as a function of time can be characterized in terms of a differential equation involving lower moment functions and the time-dependent server-occupation probability. For general initial conditions, we show that the first two moment functions can be represented as the difference of two nondecreasing functions, one of which is the moment function starting at zero. The two nondecreasing components can be regarded as probability cumulative distribution function (cdf's) after appropriate normalization. The normalized moment functions starting empty are called moment cdf's; the other normalized components are called moment-difference cdf's. We establish relations among these cdf's using stationary-excess relations. We apply these relations to calculate moments and derivatives at the origin of these cdf's. We also obtain results for the covariance function of the stationary workload process. It is interesting that these various time-dependent characteristics can be described directly in terms of the steady-state workload distribution.
A Sea Story: Implementing the Navy's Personnel Assignment System
Authors: Blanco Thomas A. , Hillery Robert C.
Published: November 2008

During its operational test and evaluation, despite top management support and significant technical achievements, a personnel assignment model implemented for the United States Navy to support assignment decisions experienced overwhelming resistance from the users, the 200 or so enlisted detailers, located at the Bureau of Naval Personnel in Washington, D.C. Our MS/OR research team had neglected to assess the negative impact of the personnel assignment model on an important detailing function: assignment negotiations or bargaining between the detailers and their customers, the service members. By involving the detailers in revising the model and making the failings of the old model the strengths of the new model, we turned certain failure into a successful program. By managing the behavioral aspects of the implementation with special emphasis on problem identification and requirements structuring, we overcame the difficulties of introducing change to a largely manual and highly decentralized decision process and we compare lessons learned with the experiences of other implementers.
A Policy Analysis of Dutch River Dike Improvements: Trading Off Safety, Cost, and Environmental Impacts
Authors: Walker Warren E. , Abrahamse Allan , Bolten Joseph , Kahan James P. , van de Riet Odette , Kok Matthijs , Braber Marjan Den
Published: November 2008

This paper describes a four-month study performed for the Dutch Minister of Transport, Public Works, and Water Management that examined the consequences of alternative policies for providing flood protection to the nontidal branches of the Rijn and Maas Rivers in The Netherlands. The paper focuses on estimating the flood damage that would occur under alternative safety standards, estimating the financial costs of alternative dike improvement strategies, and estimating the damage that would be inflicted on the landscape, natural, and cultural values along the rivers under each of these strategies. The primary objective of the study was to identify policies that would provide a high level of safety, would not cost too much, and would preserve as much as possible of the existing landscape, natural, and cultural values along the rivers. Less than six months after the completion of the study, the Dutch Parliament approved a new river dike policy that was based on the study's results.
Stability of Flexible Manufacturing Systems
Authors: Courcoubetis Costas , Weber Richard
Published: November 2008

We consider a flexible manufacturing facility that can be operated in any of m different modes. While running in mode k certain intermediate products are consumed and other intermediate or finished products are created. There may be variability in the manufacturing process, as well as random arrivals of raw materials and orders for finished products. We establish conditions that ensure demands can be satisfied while maintaining bounded levels of inventories. These results that may be viewed as generalizing to the flexible manufacturing context the notion of stability for a queueing system.
Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
Authors: Dror Moshe
Published: November 2008

In this note we prove that the relaxation approach in designing the subproblem of pricing out only the feasible routes for the set partition formulation of the VRPTW is justified on complexity grounds. That is, the first dynamic programming model presented in M. Desrochers, J. Desrosiers and M. Solomon (1992), that is able to price out all feasible routes, is NP-hard in the strong sense.
A Heuristic System to Solve Mixed Integér Forest Planning Models
Authors: Weintraub Andrés , Jones Greg , Magendzo Adrian , Meacham Mary , Kirby Malcolm
Published: November 2008

Implementing forest plans involves decisions regarding the geographic arrangement and timing of management activities, and the design of efficient transportation networks to provide access for these activities. These planning problems have been modeled successfully as mixed integer linear programs. However, these models are difficult to solve with commercial software due to their relatively large number of binary variables. We present a heuristic approach that has solved these problems well. The heuristic rules and a linear programming package interact within a closed system requiring no special user intervention. We describe several applications of this system for decision making in the USDA Forest Service.
The Total Tardiness Problem: Review and Extensions
Authors: Koulamas Christos
Published: November 2008

We provide a unified framework for the total tardiness problem by surveying the related literature in the single-machine, parallel machine, flowshop and jobshop settings. We focus on critically evaluating the heuristic algorithms; we also propose new heuristics for both the single-machine and the parallel-machine tardiness problems. Finally, we identify the areas where further research is needed and we give directions for future research.
Direction-Specific Gradient Scaling for Interactive Multicriterion Optimization Using an Abstract Mass Concept
Authors: Troutt Marvin D.
Published: November 2008

In the Method of Abstract Forces for the direction finding (or tradeoff cut) subproblems of interactive multicriterion optimization, it is necessary to scale criterion gradients. Previously, an ad hoc, analyst assisted, but nevertheless effective scaling method was used. This paper introduces a concept of abstract mass. It is shown that the previous ad hoc scaling method may be considered an approximation to the present direction-specific approach. Also, the abstract mass approach provides a strengthening of the original Newton's Second Law of Motion analogy motivation for the Method of Abstract Forces. A method for automatic and direction-specific scaling is proposed which depends on the solution of a continuous piecewise polynomial system of equations. The method is illustrated on an example with three criterion functions. In this example, Newton's method for solving simultaneous nonlinear systems converges to a solution. More generally, restart homotopy methods may be required.
Sojourn Time and Waiting Time Distributions for M/GI/1 Queues with Preemption-Distance Priorities
Authors: Paterok Martin , Ettl Markus
Published: November 2008

Scheduling strategies for real-time systems often employ semipreemptive priorities, allowing for a deadline enforcement by preemptive priorities while avoiding the overhead of unnecessary interrupts. A variety of these strategies can be described by preemption-distance priorities in a straightforward and flexible fashion. A preemption-distance is a globally assigned positive integer number. An arriving task must exceed the priority of the task being served by at least the preemption-distance to cause a preemption. We derive the Laplace-Stieltjes transforms of the marginal waiting and sojourn time distributions for each task class in M/GI/1 single-server queues with preemption-distance priorities. The solutions generalize results for the classical M/GI/1 preemptive and nonpreemptive priority queues and cover a variety of priority systems working under different service policies. The basic derivations are straightforward and lead to solutions which are easy to interpret with respect to the influence of the different system properties. Since the basic equations are modular, solutions for different service policies can be obtained by rederiving auxiliary measures using different mathematical techniques. The modeling power of preemption-distance priorities is illustrated by an example taken from the scheduling of real-time process control systems. This example also validates the derived solutions.
Parallel Machine Scheduling with Batch Setup Times
Authors: Cheng T. C. E. , Chen Z.-L.
Published: November 2008

We consider a problem of scheduling several batches of jobs on two identical parallel machines to minimize the total completion time of jobs. A setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. When the number of jobs is arbitrary, the computational complexity of the problem is posed as an open problem in the literature. We show in this note that the problem is binary NP-hard even when the setup times are sequence independent and all processing times are equal.
Operations Research in Agriculture: Thornthwaite's Classic Revisited
Authors: Kreiner Howard W.
Published: November 2008

In 1953 Operations Research (then called the Journal of the Operations Research Society of America) published a paper that represented a model of practical operations research in the civilian field of agriculture. A recent reexamination, however, showed it to have gaps in exposition and discrepancies in reported times. Research to resolve these difficulties revealed that the original paper omitted some earlier steps in the work, and concentrated on the end-product of the research. This involved developing a climatic calendar based on rates of growth in pea plants, and applying it to scheduling sowing and harvesting vegetable crops for a firm producing frozen food. Behind this development, but unmentioned in the original paper, lay an analysis of water use by plants and the translation of growth measurements into temperature-related growth units applicable to many types of vegetable and fruit crops. This translation allowed plant maturing to be tracked easily and conveniently with a view toward harvest scheduling, and made the development of the climatic calendar possible. With it a farmer gains great economy in the costs and orderliness of planting and harvesting. This paper completes the picture of the work described in Thornthwaite's original paper. The management methods derived originally have remained in use unchanged for over forty years. Thornthwaite's approach and original attitude toward field research may still serve as guides for analysts working on practical problems today.
The Bureau of Mines Electric Utility Model
Authors: Hillsman Edward L. , Alvic Donald R. , Bennett John B.
Published: November 2008

Discussion of alternative proposals to control emission precursors of acid precipitation focused on their effects on the electric power and coal industries. The Bureau of Mines was concerned about possible indirect effects on electricity-intensive mineral processing facilities, and sponsored research to help it estimate these effects. The research developed a modeling system to estimate compliance strategies and associated changes in electricity costs under different legislation, and dissemination of these results helped inform and broaden discussion of alternative proposals. Early recognition that design of the modeling system would have to allow for flexibility and change enabled development of a system that the Bureau of Mines can use to analyze a broad range of issues involving the electric utility industry, and that utilities or states can use for developing and screening plans to comply with the 1990 Clean Air Act Amendments.
Smoothing Point Processes as a Means to Increase Throughput
Authors: Chang Cheng-Shang
Published: November 2008

Unlike the leaky-bucket scheme which regulates the input rate, the filters we study in this paper reduce the variability of interarrival times (subject to a maximum delay constraint for each customer). These filters are called smoothing filters for point processes. By considering the output processes of various queueing systems, we show that an infinite-server queue acts as a smoothing filter for a doubly stochastic Poisson process, and a single-server queue with deterministic service times acts as a smoothing filter for a stationary and ergodic point process. Based on the second point, we provide a smoothing algorithm that satisfies a maximum delay constraint. The algorithm is shown to be robust and consistent. We then consider two examples where these filters can be applied to increase throughput: One is the single-server loss system with exponential service times, the other is the leaky-bucket scheme with token buffer size 1. Numerical examples and simulations are also given for comparing the tradeoff between delay and throughput. Our approach is based on the variability ordering and a cut criterion for the majorization ordering. The criterion appears to be new and of independent interest.
Speech Compression in Attendant Services: Analysis of a Queueing System with Delay-Dependent Service Times
Authors: Smith Donald E.
Published: November 2008

We study a multiserver queueing system in which delays influence service times. The system arises in a proposed application of speech compression technology to telephone directory assistance. Customers who must wait for service record their service requests and these are compressed and played to a server as soon as one becomes available (even if the customer is still talking). The longer the delay, the larger the portion of the request that may be compressed, and hence the larger the service time reduction. We develop a model that predicts various performance measures of the system relative to the corresponding system without speech compression.
An Assessment of the Risk of Chronic Lung Injury Attributable to Long-Term Ozone Exposure
Authors: Winkler Robert L. , Wallsten Thomas S. , Whitfield Ronald G. , Richmond Harvey M. , Hayes Stanley R. , Rosenbaum Arlene S.
Published: November 2008

This paper presents an application of a formal process for encoding experts’ probabilistic judgments. The objective is to characterize scientific judgment regarding the risk of chronic lung injury to children aged 8 through 16 and to adult outdoor workers due to long-term ozone exposure in areas with patterns of exposure similar to those found in Southern California and the Northeast. Our measure of injury is the incidence of mild or moderate lesions in the centriacinar region of the lung. Probabilities over population response rates were elicited from six health experts actively researching ozone-induced lung injury. We describe our approach, present some judgmental probability distributions over the population response rates for formation of lesions induced by exposure to ozone, summarize some qualitative results, and offer some concluding comments.
Lower Bounding Procedures for Multiperiod Telecommunications Network Expansion Problems
Authors: Chang Suk-Gwon , Gavish Bezalel
Published: November 2008

This paper suggests an improved formulation for the multiperiod network topology and capacity expansion problem and proposes new lower bounding schemes based on it. It differs from earlier formulations and solution methods in that entirely new and different subproblems are solved and a number of lower bound tightening schemes are added within the framework of a Lagrangian relaxation. Dual ascent and multiplier adjustment procedures are suggested for the Lagrange multiplier updating procedure. Computational results are reported to demonstrate the tightness of the bounds generated by the suggested procedures. Heuristics based on converting the dual information obtained from the Lagrangian procedure into primal feasible solutions are tested. The tests show that the Lagrangian-based heuristics generate solutions superior to solutions generated by other heuristics proposed in the literature.
Second-Order Fluid Flow Models: Reflected Brownian Motion in a Random Environment
Authors: Karandikar Rajeeva L. , Kulkarni Vidyadhar G.
Published: November 2008

This paper considers a stochastic fluid model of a buffer content process {X(t), t ≥ 0} that depends on a finite-state, continuous-time Markov process {Z(t), t ≥ 0} as follows: During the time-intervals when Z(t) is in state i, X(t) is a Brownian motion with drift μi, variance parameter σi2and a reflecting boundary at zero. This paper studies the steady-state analysis of the bivariate process {(X(t), Z(t)), t ≥ 0} in terms of the eigenvalues and eigenvectors of a nonlinear matrix system. Algorithms are developed to compute the steady-state distributions as well as moments. Numerical work is reported to show that the variance parameter has a dramatic effect on the buffer content process.
Two-Person Zero-Sum Games for Network Interdiction
Authors: Washburn Alan , Wood Kevin
Published: November 2008

A single evader attempts to traverse a path between two nodes in a network while a single interdictor attempts to detect the evader by setting up an inspection point along one of the network arcs. For each arc there is a known probability of detection if the evader traverses the arc that the interdictor is inspecting. The evader must determine a probabilistic “path-selection” strategy which minimizes the probability of detection while the interdictor must determine a probabilistic “arc-inspection” strategy which maximizes the probability of detection. The interdictor represents, in a simplified form, U.S. and allied forces attempting to interdict drugs and precursor chemicals as they are moved through river, road, and air routes in Latin America and the Caribbean. We show that the basic scenario is a two-person zero-sum game that might require the enumeration of an exponential number of paths, but then show that optimal strategies can be found using network flow techniques of polynomial complexity. To enhance realism, we also solve problems with unknown origins and destinations, multiple interdictors or evaders, and other generalizations.
Robust Optimization of Large-Scale Systems
Authors: Mulvey John M. , Vanderbei Robert J. , Zenios Stavros A.
Published: November 2008

Mathematical programming models with noisy, erroneous, or incomplete data are common in operations research applications. Difficulties with such data are typically dealt with reactively—through sensitivity analysis—or proactively—through stochastic programming formulations. In this paper, we characterize the desirable properties of a solution to models, when the problem data are described by a set of scenarios for their value, instead of using point estimates. A solution to an optimization model is defined as: solution robust if it remains “close” to optimal for all scenarios of the input data, and model robust if it remains “almost” feasible for all data scenarios. We then develop a general model formulation, called robust optimization (RO), that explicitly incorporates the conflicting objectives of solution and model robustness. Robust optimization is compared with the traditional approaches of sensitivity analysis and stochastic linear programming. The classical diet problem illustrates the issues. Robust optimization models are then developed for several real-world applications: power capacity expansion; matrix balancing and image reconstruction; air-force airline scheduling; scenario immunization for financial planning; and minimum weight structural design. We also comment on the suitability of parallel and distributed computer architectures for the solution of robust optimization models.
The Distributional Little's Law and Its Applications
Authors: Bertsimas Dimitris , Nakazato Daisuke
Published: November 2008

This paper discusses the distributional Little's law and examines its applications in a variety of queueing systems. The distributional law relates the steady-state distributions of the number in the system (or in the queue) and the time spent in the system (or in the queue) in a queueing system under FIFO. We provide a new proof of the distributional law and in the process we generalize a well known theorem of Burke on the equality of pre-arrival and postdeparture probabilities. More importantly, we demonstrate that the distributional law has important algorithmic and structural applications and can be used to derive various performance characteristics of several queueing systems which admit distributional laws. As a result, we believe that the distributional law is a powerful tool for the derivation of performance measures in queueing systems and can lead to a certain unification of queueing theory.
The Two-Stage Assembly Scheduling Problem: Complexity and Approximation
Authors: Potts C. N. , Sevast'janov S. V. , Strusevich V. A. , Van Wassenhove L. N. , Zwaneveld C. M.
Published: November 2008

This paper introduces a new two-stage assembly scheduling problem. There are m machines at the first stage, each of which produces a component of a job. When all m components are available, a single assembly machine at the second stage completes the job. The objective is to schedule jobs on the machines so that the makespan is minimized. We show that the search for an optimal solution may be restricted to permutation schedules. The problem is proved to be NP-hard in the strong sense even when m = 2. A schedule associated with an arbitrary permutation of jobs is shown to provide a worst-case ratio bound of two, and a heuristic with a worst-case ratio bound of 2 − 1/m is presented. The compact vector summation technique is applied for finding approximation solutions with worst-case absolute performance guarantees.