bluuebunny/crossref_metadata_2025 huggingface dataset:
A Method to Calculate Steady-State Distributions of Large Markov Chains by Aggregating States
Authors: Feinberg Brion N. , Chiu Samuel S.
Published: November 2008

This paper develops an efficient iterative algorithm to calculate the steady-state distribution of nearly all irreducible discrete-time Markov chains. Computational experiences suggest that, for large Markovian systems (more than 130 states), the proposed algorithm can be ten times faster than standard Gaussian elimination in finding solutions to an accuracy of 0.1%. The proposed algorithm is developed in three stages. First, we develop a very efficient algorithm for determining steady-state distributions of a restricted class of Markovian systems. A second result establishes a relationship between a general irreducible Markovian system and a system in the restricted class of Markovian systems. Finally, we combine the two results to produce an efficient, iterative algorithm to solve Markov systems. The paper concludes with a discussion of the observed performance of the algorithm.
A Nonlinear Programming Heuristic for Computing Optimal Link Capacities in a Multi-Hour Alternate Routing Communications Network
Authors: Rosenberg Eric
Published: November 2008

We consider the problem of determining the optimal number of communications channels in a telecommunications network. Traffic between pairs of nodes is assumed to vary with the time of day. Traffic between two nodes can flow over a one-link direct path or, if no direct channels are available, over a two-link alternate route. The problem is to compute the optimal number of channels on each link to minimize cost, subject to a constraint that enough trunks are present so that the probability of no idle channel does not exceed a specified amount. The mathematical formulation of this problem, known as the multi-hour engineering problem, yields an integer nonlinear programming problem (NLP). We apply recursive quadratic programming, with exact penalty function (EPF) line searches, to solve the continuous NLP, and use the special problem structure to provide a starting point and EPF parameter. A simple heuristic is used to obtain integral number of channels satisfying desired blocking objectives. The method successfully solved a set of randomly generated test problems with up to 35 variables and 432 nonlinear constraints.
The Dynamic Lot-Sizing Problem with Startup and Reservation Costs
Authors: Karmarkar Uday S. , Kekre Sham , Kekre Sunder
Published: November 2008

Dynamic lot-sizing models often assume that a production system incurs a fixed cost in each period that production is positive. In this paper, we consider a model with a startup cost incurred for switching on the production facility and a separate reservation cost charged for keeping the facility on whether or not it is used for production. Computationally, this problem is as hard as the usual model; the general capacitated case is NP-hard. We present a dynamic programming algorithm for the uncapacitated case, and a branch-and-bound approach using Lagrangian relaxation for the capacitated problem. We report computational experience on both the quality of the bounds employed and the effectiveness of the algorithm.
Strong Convexity Results for Queueing Systems
Authors: Harel Arie , Zipkin Paul H.
Published: November 2008

We prove a strong (and seemingly odd) result about the M/M/c queue: the reciprocal of the average sojourn time is a concave function of the traffic intensity. We use this result to show that the average itself is jointly convex in arrival and service rates. The standard deviation has the same properties. Also, we determine conditions under which these properties are exhibited by a standard approximation for the M/G/c queue. These results are useful in design studies for telecommunications and production systems.
Approximating the Mean Time in System in a Multiple-Server Queue that Uses Threshold Scheduling
Authors: Nelson Randolph , Towsley Don
Published: November 2008

In this paper we consider a queueing system consisting of a single queue with multiple exponential servers with different servicing rates. We assume that arrivals to the queue come from a Poisson source and are scheduled according to a threshold policy. Since determining the exact mean time in system appears to be difficult, we present an approximation that yields results very close to those obtained from simulation.
Using Standardized Time Series to Estimate Confidence Intervals for the Difference Between Two Stationary Stochastic Processes
Authors: Chen Bor-Chung , Sargent Robert G.
Published: November 2008

This paper discusses confidence interval estimation for the difference between the means of two independent, strictly stationary phi-mixing stochastic processes. The confidence intervals are based on “batched” subseries of the two time series and are obtained by using Schruben's standardized time series method. We compare these intervals with the classical result applied to the batch means, and consider different assumptions on the variances and the number of observations. The comparison results show that the four new estimators for each case have asymptotic properties that clearly dominate the classical estimator. Two applications of these intervals are (1) validating stationary discrete event simulation models, and (2) comparing two alternative policies or system designs via simulation.
Technical Note—An Algorithm for Computing the Convolution of Poisson Negative Binomial and Geometric Distributions
Authors: O'Cinneide Colm Art , Schneider Helmut
Published: November 2008

We present a simple algorithm that computes the convolution of Poisson, negative binomial, and geometric distributions. We show that a certain infinite-server queue in a random facility repair environment has a steady-state distribution that involves such convolutions. The algorithm arises from the steady-state equations of this process.
Technical Note—A Note on the Weighted Tardiness Problem
Authors: Rachamadugu Ram Mohan V.
Published: November 2008

We identify a condition characterizing adjacent jobs in an optimal sequence for the weighted tardiness problem. This condition can be used as an effective pruning device in enumerative methods. Further, we show that the Modified Due Date Rule is a special case of this condition. Lastly, we identify a set of circumstances under which the first job in an optimal sequence can be determined without fully solving the problem.
OR Forum—British Operational Research in World War II
Authors: McCloskey Joseph F.
Published: November 2008

This article offers an overview of British operational research activities during World War II, and is the second in a series on the early history of operations research. The first (Operations Research 35, 143–152) traced the scattered beginnings from World War I up to the activities in Britain before and during the early months of World War II.
Presidents' Symposium: OR, A Post Mortem
Authors: Ackoff Russell L.
Published: November 2008

This note traces the devolution of operations research from its original state as a market-oriented profession through the stage of output orientation to its current status as largely input-oriented, and points out that this descent has taken the profession away from the most important needs of the organizations it could serve.
Estimation of Percentile Residual Life
Authors: Csörgő Miklós , Csörgő Sándor
Published: November 2008

We initiate a nonparametric, large sample estimation theory for the percentile residual lifetime. We introduce the empirical percentile residual life process and determine its asymptotic distribution, resulting in asymptotically distribution-free confidence intervals and confidence bands for the percentile residual lifetime. We illustrate the methods using strike duration data from the work of D. C. Schmittlein and D. G. Morrison.
OR Forum—Presidents' Symposium: George E. Kimball, A Pioneering Giant in Operations Research
Authors: Magee John F.
Published: November 2008

These remarks, adapted from a talk given at the April 1985 TIMS/ORSA meeting in Boston, are aimed at sustaining the memory of George Elbert Kimball, one of operations research's influential pioneers, who himself was president of the Society from 1964 to 1965.
Feature Article—Mathematical Models in Farm Planning: A Survey
Authors: Glen John J.
Published: November 2008

Farm planning has increased in complexity and importance as agriculture in the developed world has become concentrated in larger, more specialized farm units. These changes have stimulated the development of formal planning techniques based on mathematical models. Although this approach is characteristic of operations research, the profession's direct involvement in agricultural planning has been limited: much of the published work is associated with agricultural economics. In this paper, we provide an OR-oriented introduction to the problems involved in agricultural planning, particularly at the farm level. We describe the planning problems of both the crop and livestock sectors and outline the models that have been proposed for solving these problems. Researchers, and agricultural extension and advisory services, have been the main users of these models, but the widespread availability of microcomputers gives considerable scope for developing models for use by farmers.
OR Practice—Policy Decision Modeling of the Costs and Outputs of Education in Medical Schools
Authors: Lee Hau L. , Pierskalla William P. , Kissick William L. , Levy Joanne H. , Glick Henry A. , Bloom Bernard S.
Published: November 2008

This paper presents the results of a project designed to develop a methodology to aid policy decision making in statewide medical education systems. The methodology requires the development of quantitative models that project the state's future investment in medical education, as well as the effects of potential policy proposals on the costs of medical education, on state costs, and on physician manpower supply. To build these models, we collected and analyzed extensive data from one statewide medical education system. We discuss the development of our methodology, its application in the strategic planning by the state’s educational leaders, its significance in the policy formulation process, and we offer guidelines for future research.
The Optimal Timing of New Plants for Oil from the Alberta Tar Sands
Authors: Fuller J. D. , Vickson R. G.
Published: November 2008

In this paper we use an optimal control model to examine whether early exploitation of the vast Alberta tar sands resource may be justified due to constraints on the availability of construction resources for tar sands plants. We model conventional oil as an exhaustible resource whose unit production cost increases with cumulative production, and tar sands oil as a virtually inexhaustible resource (a backstop) having constant unit production cost initially much higher than that of conventional oil. There is a finite, time-dependent maximum rate of increase in tar sands production capacity. The problem involves a state-space constraint inasmuch as the tar sands production rate (a state variable) cannot exceed the exogeneous demand rate at any time. In a discounted cost formulation for sufficiently large finite, or infinite, planning periods, we show that the optimal policy is to use conventional oil alone until some critical time and then expand tar sands capacity at a maximum rate until it equals total demand, after which all demand is met through tar sands oil alone. We discuss an unexpected “cost overshoot”—the unit cost of conventional oil exceeds that of tar sands oil at the time of transition to total reliance on the tar sands backstop. Using plausible functional forms and parameter values, we conclude that construction of new tar sands plants should be deferred for several years, although other considerations not dealt with in our examination may have a significant effect on this conclusion.
Decision Analysis Under States-Additive SSB Preferences
Authors: Lavalle Irving H. , Fishburn Peter C.
Published: November 2008

We survey Fishburn's skew-symmetric bilinear (SSB) theory of risky choice under nonlinear and potentially nontransitive preferences and apply the states-additive special case in the context of decision analysis, showing that tractable characterizations of optimal choices are obtainable via linear programming once the decision has been expressed in normal (i.e., tabular) form. If preferences are transitive, they are also linear and representable by von Neumann-Morgenstern utility, in which case optimal choices may be obtained by the familiar recursion analysis of the extensive (i.e., tree) form.
Some Monotonicity Results for Partially Observed Markov Decision Processes
Authors: Lovejoy William S.
Published: November 2008

This paper provides sufficient conditions for the optimal value in a discrete-time, finite, partially observed Markov decision process to be monotone on the space of state probability vectors ordered by likelihood ratios. The paper also presents sufficient conditions for the optimal policy to be monotone in a simple machine replacement problem, and, in the general case, for the optimal policy to be bounded from below by an easily calculated monotone function.
The Arrangement of Servers in an Ordered-Entry System
Authors: Yao David D.
Published: November 2008

We consider a service system whose servers may work at different rates (systems with “heterogeneous servers”). Jobs arriving at the system access the servers in accordance with an “entry order” that relates to the arrangement of the servers. When all servers are occupied, arriving jobs are blocked and lost. This model has applications in the study of conveyors and other circulation systems. In this paper we wish to compare various server arrangements in such systems. We represent the arrangement of servers by a permutation vector of their service rates, and develop a partial order on these vectors. By moving in the direction pointed out by this partial order, one can reduce blocked traffic, thereby improving system performance. Our results may help system designers compare directly the performance of different server arrangements.
Technical Note—Successive Approximations in Value Determination for a Markov Decision Process
Authors: Sheskin Theodore J.
Published: November 2008

We present a new procedure for solving the value-determination equations for an undiscounted Markov decision process by the successive approximations of a Gauss-Seidel or Jacobi iteration method. The key step is to use the Markov chain partitioning algorithm to compute the steady-state probabilities corresponding to a given policy. The gain, computed in terms of the steady-state probabilities, is substituted into the value-determination equations. After deleting one relative value and one value-determination equation, we show that the remaining system of equations satisfies the sufficient conditions for the convergence of a Gauss-Seidel or Jacobi iteration.
Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition
Authors: Eppen Gary D. , Martin R. Kipp
Published: November 2008

Mixed-integer programming models are typically not used to solve realistic-sized production scheduling problems because they require exorbitant solution times. We impose a useful taxonomy on production scheduling problems and develop alternative formulations for a wide variety of problems within the taxonomy. The linear programming relaxation of the new models is very effective in generating bounds. We show that these bounds are equal to those that could be generated using Lagrangian relaxation or column generation. The linear programming bounds increase in effectiveness as the problems become larger. Perhaps of greatest significance is that practitioners can obtain our results using only standard “off-the-shelf” codes such as LINDO or MPSX/370. We report computational experience in several computing environments (hardware and software) on problems with up to 200 products and 10 time periods (2000 0-1 variables).
U.S. Operations Research in World War II
Authors: McCloskey Joseph F.
Published: November 2008

This article, the third in a series on the early history of operations research, offers an overview of American military operations research during World War II. The first and second articles (Operations Research 35, pp. 143–152 and 453–470) traced the scattered beginnings of operations research from World War I through the British experience of World War II.
Letter to the Editor—Comments on “On Optimal Inventory Policies When Ordering Prices are Random” by Kamal Golabi
Authors: Magirou Vangelis F.
Published: November 2008

Comments on “On Optimal Inventory Policies When Ordering Prices are Random” by Kamal Golabi (Golabi, K. 1985. Optimal inventory policies when ordering prices are random. Opns. Res. 33 575–588).
Sensitivity Analysis of Additive Multiattribute Value Models
Authors: Barron Hutton , Schmidt Charles P.
Published: November 2008

We present two simple computational procedures for sensitivity analysis of additive multiattribute value models that yield variations in attribute weights (scaling constants). For the first, or entropy-based, procedure, the point of departure is the concept of equal weights for all attributes. For the second, or least squares procedure, the point of departure is a set of arbitrary weights for attributes. In each procedure we either (a) calculate the “closest” set of weights that equates the multiattribute value for a pair of alternatives—that alternative whose overall value is optimal for the original attribute weights and any other specific nondominated alternative—or (b) calculate the “closest” set of weights required for the specific alternative to exceed the “optimal” alternative by a specified amount.
Planning and Scheduling for Epitaxial Wafer Production Facilities
Authors: Bitran Gabriel R. , Tirupati Devanath
Published: November 2008

In this paper we describe production planning and scheduling models for a semiconductor company manufacturing specialty wafers. The production of specialty wafers involves processing a large number of low volume, customer-specific orders which can be classified into a number of product groups. Typically, the literature on scheduling deals with one product and a single objective. In contrast, we propose and test several heuristics for scheduling jobs in a multiproduct parallel reactor (machine) shop with different criteria. We introduce a set of indices to measure the degree of homogeneity in the product set. Based on the results of the computational experiments, we recommend that the choice of the heuristic should be guided by the homogeneity of the product set and the chosen objective criterion. The planning problem relates to the assignment of reactors to the product groups to obtain homogeneous product sets, and can be viewed as an effort to define smaller, independent shops. The significance of the planning exercise is due to the fact that a homogeneous product set enables the use of a simpler heuristic and reduces the complexity of the scheduling system. We examine two variants of the planning model and briefly comment on their application to the design and layout of the facility. Since one of the variants of the problem is difficult to solve, we present a method to obtain an approximate solution. We provide bounds on the performance of this approximate solution and demonstrate that it is asymptotically optimal.
A Dynamic Programming Solution to the Dynamic, Multi-Item, Single-Machine Scheduling Problem
Authors: Gascon André , Leachman Robert C.
Published: November 2008

This article presents a dynamic programming algorithm for scheduling, on a single machine, production of multiple items with time-varying deterministic demands. We formulate the scheduling problem with the objective of minimizing the sum of changeover and inventory holding costs. The formulation is appealing in that it represents changeover costs directly instead of by the familiar approximate technique of including setup costs in the objective. Our algorithm, which we developed using an approach similar to C. R. Glassey's that minimizes the total number of changeovers, casts the optimal schedule as a shortest path through a network embedded in a state space. It generates optimal schedules under two assumptions. First, we assume that in each time period within the planning horizon, the machine must either be shut down or be producing some one item for the entire time period. Second, we assume that inventory holding costs are representable as a nondecreasing function of aggregate inventory. We provide a number of numerical examples that we solved using the algorithm.
Component Allocation and Partitioning for a Dual Delivery Placement Machine
Authors: Ahmadi Javad , Grotzinger Stephen , Johnson Dennis
Published: November 2008

Consider a computer numerically controlled placement machine for populating printed circuit cards with surface mounted components, which features two carriers for the delivery of components to the placement heads. This parallel type of delivery system requires a systems analysis to determine: the number of tape reels of each component to be allocated; and to which of the two carriers each should be assigned along with the assignment of corresponding sets of tools. Factors that impinge on the development are: the flexibility of the machine's controller, and the fixturing for component feed (vibratory and/or tape reel). The allocation models maximize the number of board completions attainable by a single allocation of components to the two carriers. This reduces the demand on the automated material handling system and the machine's operators for component replenishment. We consider the case where all components allocated are accessible and the case of a “static pick sequence.” The partioning model minimizes the “dead time” with respect to operation balance, excess rotation and the number of required nozzle changes, so as to support a high throughput rate. The utilization of vibratory, ski slope type fixtures for the delivery of components is also addressed in an Appendix.
Strategic Analysis of Integrated Production-Distribution Systems: Models and Methods
Authors: Cohen Morris A. , Lee Hau L.
Published: November 2008

This paper presents a comprehensive model framework for linking decisions and performance throughout the material-production-distribution supply chain. The purpose of the model is to support analysis of alternative manufacturing material/service strategies. A series of linked, approximate submodels and an heuristic optimization procedure are introduced. A prototype software implementation is also discussed.
A Discrete Time Average Cost Flexible Manufacturing and Operator Scheduling Model Solved by Deconvexification Over Time
Authors: Eaves B. Curtis , Rothblum Uriel G.
Published: November 2008

A flexible manufacturing and operator scheduling problem is introduced and solved. The principal concern is to schedule operators over time to various activities of a manufacturing system for the purpose of optimizing some steady-state criteria. In mathematical terms, the problem is modeled as a deterministic, infinite horizon, discrete dynamic program. Our solution procedure is to convexify the problem to obtain a linear program, and then to deconvexify the solution of the linear program over time to arrive at an optimal solution. Apparent loss in objective value due to the deconvexifications is circumvented with buffer inventories. The procedure is reduced to solving a sequence of linear programs and the complexity is stated in these terms.
Machine Layout Problem in Flexible Manufacturing Systems
Authors: Heragu Sunderesh S. , Kusiak Andrew
Published: November 2008

This paper analyzes the machine layout problem in flexible manufacturing systems (FMS's). We show that the quadratic assignment formulation cannot be used to model the machine layout problem. Four basic types of machine layouts that are frequently encountered in FMS's are presented. A measure to determine the relationship between machines is introduced. Since automated guided vehicles are commonly used to transport material between machines, their motion characteristic is discussed. Two new construction algorithms are presented to solve the machine layout problem in FMS's. They generate solutions with acceptable quality in low computational time. The triangle assignment algorithm (TAA) is compared to existing methods for 8 test problems and is found to give solutions of better quality than any other construction method published. When compared to existing methods, the computation time performance is attractive.
Production Control in Multistage Systems with Variable Yield Losses
Authors: Lee Hau L. , Yano Candace Arai
Published: November 2008

Many manufacturing processes involved in the fabrication and assembly of “high-tech” components have highly variable yields that complicate the planning and control of production. We develop a procedure to determine optimal input quantities at each stage of a serial production system in which process yields at each stage of production may be stochastic. The procedure is applied to an example in the manufacture of a light-emitting diode (LED) display using actual yield data. We also provide a brief analysis of the quantifiable savings obtained by reducing the variability of the yield at one production stage.
The Discrete Two-Dimensional Assortment Problem
Authors: Pentico David W.
Published: November 2008

In the two-dimensional assortment problem, a unit of product that is larger or better on two measurements or qualities may be used to substitute, at some cost, for a unit of demand that is smaller or inferior on both measurements or qualities. The problem is to determine which dimensional combinations to stock in order to minimize the combined stocking and substitution costs. Characteristics of the optimal stocking pattern are presented, and three heuristic solution procedures are compared with an optimization technique under a variety of conditions for demand and cost characteristics.
An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
Authors: Barahona Francisco , Grötschel Martin , Jünger Michael , Reinelt Gerhard
Published: November 2008

We study the problem of finding ground states of spin glasses with exterior magnetic field, and the problem of minimizing the number of vias (holes on a printed circuit board, or contacts on a chip) subject to pin preassignments and layer preferences. The former problem comes up in solid-state physics, and the latter in very-large-scale-integrated (VLSI) circuit design and in printed circuit board design. Both problems can be reduced to the max-cut problem in graphs. Based on a partial characterization of the cut polytope, we design a cutting plane algorithm and report on computational experience with it. Our method has been used to solve max-cut problems on graphs with up to 1,600 nodes.
OR Practice—Intelligent Data Compression in a Coal Model
Authors: Bullard Clark , Engelbrecht-Wiggans Richard
Published: November 2008

When the U.S. Congress began considering acid rain legislation in the early 1980s, the federal Environmental Protection Administration (EPA) relied on two major models for analyzing the impact of emission reduction policies on the coal and electric utility industries. Debate over the merit of these two models was hampered because they were proprietary, and both had achieved computational tractability through a priori exclusion of the nation's largest and most detailed data bases describing either: (1) the characteristics of individual electric generating units, or (2) coal reserves and washability. Because of general dissatisfaction with the limitations of both models, the EPA contracted with three universities to develop an Advanced Utility Simulation Model (AUSM) that would combine the best features of each of the existing models. This paper describes the approach taken to develop the AUSM, currently used by the EPA, in a manner that achieved computational tractability while making maximum use of the information contained in the available data.
Optimality of Zero-Inventory Policies for Unreliable Manufacturing Systems
Authors: Bielecki T. , Kumar P. R.
Published: November 2008

We show that there are ranges of parameter values describing an unreliable manufacturing system for which zero-inventory policies are exactly optimal even when there is uncertainty in manufacturing capacity. This result may be initially surprising since it runs counter to the argument that inventories are buffers against uncertainty and therefore one must strive to maintain a strictly positive inventory as long as there is any uncertainty. However, there is a deeper reason why this argument does not hold, and why a zero-inventory policy can be optimal even in the presence of uncertainty. This provable optimality reinforces the case for zero-inventory policies, which is currently made on the separate grounds that it enforces a healthy discipline on the entire manufacturing process.
Optimal Periodic Replacement of Multicomponent Reliability Systems
Authors: Özekici Süleyman
Published: November 2008

A complex device, like a jet engine or an electronic computer, is composed of hundreds of major components that require maintenance. The determination of the reliability and the optimal maintenance policy for such systems is further complicated by the dependence among interacting components. Component lifetimes are generally stochastically dependent due to the fact that they all function under the same environmental conditions like temperature, humidity, and vibrations. Moreover, they are also economically dependent since it is possible to do preventive maintenance to functioning components at marginal, additional cost, while failed components are being maintained. We discuss the effects of these dependencies on periodic replacement policies, and provide useful characterizations of the optimal replacement policy. The formulation involves a sample path analysis of the reliability system which leads to the utilization of Markov decision theory. Interesting intuitive and counterintuitive results are presented.
Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates
Authors: Liu C. Y. , Bulfin R. L.
Published: November 2008

We examine the problem of scheduling n jobs, each of which must be processed by m machines. If the order in which a given job is processed on the machines is not fixed, the system is called an open shop. This situation might occur in testing components of an electronic system or doing repair work on an automobile. The computational difficulty of solving most open shop problems is known, with the majority being NP-hard. The computational difficulty of a few special cases is unknown, most notably when the jobs have identical processing time and the measure of performance is a function of job due dates. We reduce this uncertainty by developing polynomial algorithms to minimize the total tardiness and the number of tardy jobs in an open shop with identical processing time jobs.
State Dependence in M/G/1 Server-Vacation Models
Authors: Harris Carl M. , Marchal William G.
Published: November 2008

This paper examines a generalization of the exhaustive and one-at-a-time-discipline M/G/1 server vacation models. This alternative model is viewed as a state-dependent (nonvacation) M/G/1 queue in which the original service times are extended to include a (possibly zero length) state-dependent vacation after each service. Such a vacation policy permits greater flexibility in modeling real problems, and does, in fact, subsume most prior M/G/1 approaches. This device reveals a fundamental decomposition somewhat like that previously established for the classical vacation disciplines. In addition, necessary and sufficient conditions for system ergodicity are established for the state-dependent vacation policy, and some comments are offered on computations.
Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning
Authors: Jain Anjani , Mamer John W.
Published: November 2008

This paper considers the problem of determining the mean and distribution of the length of a minimal spanning tree (MST) on an undirected graph whose arc lengths are independently distributed random variables. We obtain bounds and approximations for the MST length and show that our upper bound is much tighter than the naive bound obtained by computing the MST length of the deterministic graph with the respective means as arc lengths. We analyze the asymptotic properties of our approximations and establish conditions under which our bounds are asymptotically optimal. We apply these results to a network provisioning problem and show that the relative error induced by using our approximations tends to zero as the graph grows large.
Decision Processes with Monotone Hysteretic Policies
Authors: Hipp Sabine K. , Holzbaur Ulrich D.
Published: November 2008

Queueing models play an important role in the optimization of dynamic processes, especially in serving problems. For example, dynamic processor or storage allocation for computers, working intensity in a shop or in a service industry, and staff policy in the order-dependent industry may be modeled by optimizing the service levels of a queue. The goal is to minimize the cost that occurs from serving and from customers waiting in the queue. Changing the service levels creates switching costs, e.g., for resource reallocation, personnel increase or reduction. When switching costs are considered, the optimal service level depends on the current service level as well as on the number of customers in the queue. Of special interest are the structural properties of the optimal policies because structured policies are easier to determine and to implement. We give conditions for two properties of optimal policies: (1) monotone policies where the service level increases with the number of customers, and (2) hysteretic policies that change the service level only under some switching condition.
A Mathematical Programming Approach to a Nash-Cournot Equilibrium Analysis for a Two-Stage Network of Oligopolies
Authors: Sherali Hanif D. , Leleno Joanna M.
Published: November 2008

This paper deals with the existence, characterization and computation of equilibrium solutions arising from related mathematical programming problems associated with a particular market structure. The generic structure analyzed herein represents a two-stage production process in which a set of some firms produces a semifinished product that serves as an input to another set of firms which converts this to a final good. In addition, there exists a third set of vertically integrated firms. These firms perform the operations jointly performed by the other two sets of firms in producing the final product. On the demand side, an econometrically derived demand curve is specified for the final product. The aim of this paper is to characterize the nature of the equilibrium solutions for such problems under various market behavioral structures, derive sufficient conditions under which one can claim the existence of these equilibrium solutions, and prescribe methods for computing equilibrium solutions. The analysis provides a machinery for considering the effects of mergers and integrations on a firms' profits and on industry outputs and prices, thereby suggesting incentives, or otherwise, to merge or integrate.
Characterization and Optimization of Achievable Performance in General Queueing Systems
Authors: Federgruen A. , Groenevelt H.
Published: November 2008

This paper considers general (single facility) queueing systems with exponential service times, dealing with a finite number J of distinct customer classes. Performance of the system, as measured by the vector of steady state expected sojourn times of the customer classes (the performance vector) may be controlled by adopting an appropriate preemptive priority discipline. We show that the performance space, the set of performance vectors which are achievable under some preemptive work conserving rule, is a polyhedron described by 2J − 1 (in)equalities. The special structure of this polyhedron nevertheless allows for efficient procedures to minimize any separable convex function of the performance vector. Linear objectives are shown to be minimized by absolute priority rules, thus generalizing a well known result for M/M/1 systems. We also show that each point in the performance space may be achieved by a specific randomization of at most J + 1 absolute priority rules.
Short-Term Scheduling of Thermal-Electric Generators Using Lagrangian Relaxation
Authors: Bard Jonathan F.
Published: November 2008

This paper presents an expanded formulation of the unit commitment problem in which hundreds of thermal-electric generators must be scheduled on an hourly basis, for up to 7 days at a time. The underlying model incorporates the full set of costs and constraints including setup, production, ramping, and operational status, and takes the form of a mixed integer nonlinear control problem. Lagrangian relaxation is used to disaggregate the model by generator into separate subproblems which are then solved with a nested dynamic program. The strength of the methodology lies partially in its ability to construct good feasible solutions from information provided by the dual. Thus, the need for branch-and-bound is eliminated. In addition, the inclusion of the ramping constraint provides new insight into the limitations of current techniques. Computational experience with the proposed algorithm indicates that problems containing up to 100 units and 48 time periods can be readily solved in reasonable times. Duality gaps of less than 1% were achieved in all cases.
Efficiency Frontier Determination by Constrained Facet Analysis
Authors: Bessent A. , Bessent W. , Elam J. , Clark T.
Published: November 2008

Assessing the efficiency of organizational units has long been recognized as an important management problem but an extremely difficult one to solve, especially when one considers the multiplicity of resources and services or products associated with these units operating in a variety of industries. Data Envelopment Analysis (DEA), a promising approach for addressing this problem, is extended in this paper. The proposed extension, called Constrained Facet Analysis (CFA), provides a lower bound efficiency measure for organizational units that have a mix of resources and/or outputs that is different from any frontier point. In addition, CFA yields marginal rates of productivity and substitution associated with the lower bound efficiency measure. This lower bound analysis, combined with the upper bound efficiency analysis provided by the DEA, broadens the applicability of the DEA theory and methodology.
Development of a Knowledge-Based Model Management System
Authors: Liang Ting-Peng
Published: November 2008

This paper presents a software architecture and a graph-based framework for developing knowledge-based model management systems. The architecture consists of three major components: a model utilization subsystem, a modeling subsystem, and an inference engine. The core of the system is the inference engine that applies the graph-based framework to drive the processes of model integration and selection. The graph-based framework includes a model representation scheme and reasoning mechanisms. The representation scheme depicts a set of data as a node, a set of functions as an edge, and a basic model as a combination of two nodes and one connecting edge. Based on this scheme, mechanisms for model integration and selection are discussed. These mechanisms enable a model management system to create composite models automatically. A prototype implemented in PROLOG is also presented to demonstrate the graph-based framework.
A Decision Support System for Funds Management in a Public University
Authors: Tyagi Rajesh , Moore Laurence J. , Taylor Bernard W.
Published: November 2008

Senior administrators at public universities spend a great deal of time attempting to manage university funds. As the portion of total operations supported by state allocations has decreased, the number of sources of funding has been expanded by universities. This has led to a vastly more complex funds management problem for officials of public universities. The president and senior financial officer require up-to-date information on the status of university funds in terms of availability from numerous sources and applications to various uses over time. This need is more critical than ever due to legal, contractual, and legislated restrictions related to the uses of funds from the various sources. Assistance is also needed for the process of planning the allocation of funds from the various sources to potential uses over time. This paper reports on a computer based decision support system developed and implemented at a large public university to provide senior university administrators with up-to-date information on the status of funds, by source and use over time, and an interactive multicriteria model embedded within the overall computer package to assist university administrators in decision making regarding the allocation of funds from sources to uses over several time periods.
A Decision Support System for Purchasing Management of Large Projects
Authors: Ronen Boaz , Trietsch Dan
Published: November 2008

This paper describes a model based Decision Support System (DSS) for purchasing materials and components for large projects. The DSS may be used under two scenarios. Under the first scenario, we have a project to execute, and we are looking for a good way to manage the purchasing to minimize the expected costs. The decisions under our control are when and from whom to order each item. Under the other scenario, we are bidding for the project, and wish to assess the costs associated with the purchasing decisions which we should consider before making our bid. In both cases, we take into account expected out of pocket costs as well as lateness and/or expediting penalties. The DSS is designed to help choose the best supplier for each item and schedule the placement of the orders—decisions which are very difficult to make well without such a model based DSS.
Mass Screening Models for Contagious Diseases with No Latent Period
Authors: Lee Hau L. , Pierskalla William P.
Published: November 2008

In this paper, a simplified model describing the stochastic process underlying the etiology of contagious and noncontagious diseases with mass screening is developed. Typical examples might include screening of tuberculosis in urban ghetto areas, venereal diseases in the sexually active, or AIDS in high risk population groups. The model is addressed to diseases which have zero or negligible latent periods. In the model, it is assumed that the reliabilities of the screening tests are constant, and independent of how long the population unit has the disease. Both tests with perfect and imperfect reliabilities are considered. It is shown that most of the results of a 1978 study by W. P. Pierskalla and J. A. Voelker for noncontagious diseases can be generalized for contagious diseases. A mathematical program for computing the optimal test choice and screening periods is presented. It is shown that the optimal screening schedule is equally spaced for tests with perfect reliability. Other properties relating to the managerial problems of screening frequencies, test selection, and resource allocation are also presented.
A Stochastic Scheduling Problem with Intree Precedence Constraints
Authors: Frostig Esther
Published: November 2008

We consider n jobs to be scheduled on two parallel machines. The jobs are subject to intree precedence constraints, that is, each job, except one which is the root of the tree, has one successor. The job of the root is at level 0 and a job is at level l if its predecessor is at level l − 1. A job can start to be processed only after all its predecessors have finished. Job processing times are independent random variables with those at the same level being identically distributed. The objective is to minimize the expected completion time of the last job. Such a model can be applied to assembly line and computational problems. This paper generalizes a result of Pinedo and Weiss.
Near-Optimal Service Constrained Stocking Policies for Spare Parts
Authors: Cohen Morris A. , Kleindorfer Paul R. , Lee Hau L.
Published: November 2008

Consider a facility that stocks various parts in support of repairs for a set of products in some customer region. The problem considered is to determine base stock policies for each part to minimize expected inventory costs across all parts while satisfying some service constraint on total customer repair services completed. A heuristic procedure is developed for several variants of this problem. The heuristic is based on duality theory and is shown to have a close connection to the well known Greedy Heuristic. Encouraging experimental results on the performance of the proposed heuristic are reported. The basic problem structure considered is similar to the tool-kit problem, but it is formulated to allow applications in much broader spare part logistics contexts.
OR Practice—Design and Implementation of an Interactive Optimization System for Network Design in the Motor Carrier Industry
Authors: Powell Warren B. , Sheffi Yosef
Published: November 2008

We describe the design and implementation of an interactive optimization system for routing freight over a less-than-truckload motor carrier network. We formulate a very large, mixed integer programming problem, and develop a decomposition strategy based partly on the mathematical structure of the problem as well as a range of important, real-world issues and constraints. Then we develop and implement a local improvement heuristic in such a way as to keep the “man-in-the-loop,” using the analyst to make judgments regarding certain complex constraints and tradeoffs. Important aspects of the system include a range of modeling approximations to keep the problem tractable and the way the analyst evaluates the quality of the different numbers. The package was implemented and is currently being used on an ongoing basis by a major motor carrier. An overview of the major elements of the package is given as well as a summary of important implementation issues that arose during the three year project.
Optimal Scheduling of Jobs with Exponential Service Times on Identical Parallel Processors
Authors: Kämpke Thomas
Published: November 2008

The scheduling of jobs with stochastically independent, exponentially distributed service times on identical parallel processors is considered. General sufficient conditions for optimality in expectation of priority policies for certain cost functions are given, including cases of the weighted flow time. The priority policies under consideration may be more general than the longest expected processing time (LEPT) or the shortest expected processing time (SEPT) policy. We deal with a fixed number of processors as well as certain more general resource constraints. Finally, precedence relations between jobs given by strict interval orders are admitted and an optimality result for LEPT is stated for this situation.
Sensitivity Analysis and Performance Extrapolation for Computer Simulation Models
Authors: Rubinstein Reuven Y.
Published: November 2008

We present a method for deriving sensitivities of performance measures for computer simulation models. We show that both the sensitivities (derivatives, gradients, Hessians, etc.) and the performance measure can be estimated simultaneously from the same simulation. Our method is based on probability measure transformations derived from the efficient score. We also present a rather general procedure from which perturbation analysis and our method can be viewed as particular cases. Applications to reliability models and stochastic shortest path networks are given.