bluuebunny/crossref_metadata_2025 huggingface dataset:
OR Practice—Large-Scale Nonlinear Network Models and Their Application
Authors: Dembo Ron S. , Mulvey John M. , Zenios Stavros A.
Published: November 2008

Nonlinear network applications arise in a variety of contexts: hydroelectric power system scheduling, financial planning, matrix estimation, air traffic control, and so on. This paper reviews applications of network optimization models with nonlinear objectives and, possibly, generalized arcs. Particular emphasis is placed on large-scale implementations. Specialized nonlinear network programming software is typically an order of magnitude faster than general purpose codes.
The Transition to Nondepletable Energy: Social Planning and Market Models of Capacity Expansion
Authors: Powell Stephen G. , Oren Shmuel S.
Published: November 2008

As depletable energy becomes increasingly scarce and expensive, energy markets will turn to a multitude of nondepletable sources of energy. The rate at which this transition occurs will depend on the quantities of fuels available, production costs, government policies, and the choices of major producers. In this paper, we analyze the transition to nondepletable fuels, first in the context of a social planning model, then using a Stackelberg model to represent the dynamic game between owners of depletable and nondepletable fuels. We show that the pace of capacity expansion in the nondepletable sector has a strong influence on socially optimal energy prices and production rates. With the Stackelberg model, we characterize the strategy a market-dominating producer of depletable energy will use against the nondepletable sector. Numerical implementations of this model allow us to compare the socially optimal and market-determined outcomes. Our results show how a dominant depletable-energy producer can manipulate the nondepletable sector by pricing at the marginal cost of backstop output during an early phase of resource depletion.
Disposal of Excess Inventory
Authors: Rosenfield Donald B.
Published: November 2008

This paper deals with the problem of disposal of slow-moving or obsolete inventory. For many reasons, companies will find themselves in an overstock situation where the potential sales value of excess stock, less the expected storage costs, does not match the salvage value. We present relationships for the optimum number of items to keep under conditions of stochastic demand and perishing.
Dynamic Game Results of the Acquisition of New Technology
Authors: Gaimon Cheryl
Published: November 2008

Open and closed-loop Nash strategies are derived and analyzed for a differential game in which two competing firms choose prices and productive capacity where new technology reduces a firm's unit operating cost. Using an open-loop strategy, a firm makes an irreversible commitment to a future course of action. For example, a contract with a labor union may force a firm to commit to maintaining its entire workforce regardless of its competitor's future realized behavior. In contrast, using a closed-loop strategy, a firm's decisions evolve over time, continuously responding to the competitor's behavior. The dynamic Nash strategies obtained for the closed-loop model exhibit a more restricted acquisition of new technology and a greater reduction of existing capacity relative to the open-loop solutions. In addition, the dynamic Nash price to be charged for output is higher in the closed as opposed to open-loop competitive environment. Numerical solutions are presented to demonstrate that if both firms apply the closed-loop approach, each will earn higher profits than if one or both firms choose an open-loop strategy.
Estimating the s − t Reliability Function Using Importance and Stratified Sampling
Authors: Fishman George S.
Published: November 2008

This paper considers an undirected network G with a node set V and an arc set E = {1, …, n}. The nodes are perfect, but the arcs fail randomly and independently with known probabilities 1 − p1, …, 1 − pn. The system reliability g(p) is defined as the probability that two nodes, s and t ∈ V, are connected where p = (p1, p2), p1 = (p1, …, pn′) and p2 = (pn′+1, …, pn). This paper describes a highly efficient Monte Carlo sampling plan for estimating the sensitivity of g(p) as the component reliabilities in p1 vary over a set of values P in the n′-dimensional unit hypercube. Sensitivity analysis becomes an important consideration when contemplating component replacement and alternative system designs, and when accounting for the effect of using sample estimates, based on historical failure data, for the true component reliabilities. The sampling plan is a major advance over most other Monte Carlo proposals which only estimate g(p) at a single point p. The method combines importance and stratified sampling techniques to gain its advantage. In addition to unbiased point estimates, the paper derives individual confidence intervals as well as simultaneous confidence intervals for all the points. It also describes the steps for implementation and illustrates how the plan works in practice.
OR Forum—What's Happened in Search Theory Since the 1975 Lanchester Prize?
Authors: Stone Lawrence D.
Published: November 2008

This article is based on a talk that I gave at the 1988 TIMS/ORSA meeting in Washington, D.C. about developments in search theory since the Lanchester Prize for 1975 was awarded to me for Theory of Optimal Search. The answer to the question in the title is that a lot has happened, particularly in the area of the search for moving targets and in the use of computers in search theory and applications.
Tradeoff Curves, Targeting and Balancing in Manufacturing Queueing Networks
Authors: Bitran Gabriel R. , Tirupati Devanath
Published: November 2008

In this paper, we introduce the notions of tradeoff curves, targeting and balancing in manufacturing systems to describe the relationship between variables such as work-in-process, lead-time and capacity. We consider multiproduct manufacturing systems modeled by open networks of queues and formulate the targeting (TP) and balancing (BP) problems as nonlinear programs. These formulations are based primarily on parametric decomposition methods for estimating performance measures in open queueing networks. Since TP and BP typically are hard to solve, we show that under fairly realistic conditions they can be approximated by easily solvable convex programs. We present heuristics to obtain approximate solutions to these problems and to derive tradeoff curves. We also provide bounds on the performance of the heuristics, relative to the approximation problems, and show that they are asymptotically optimal under mild conditions.
Optimal Inventory Policies for Assembly Systems Under Random Demands
Authors: Rosling Kaj
Published: November 2008

This paper considers an inventory model of an assembly system with random demands and proportional costs of production and stock holding activities. The model is a generalization of the facilities in series model of Clark and Scarf. Under an assumption on the initial stock levels that in any case should appear in the long run (Long-Run Balance), it is demonstrated that the assembly system can be remodeled as a series system. Hence, simple reorder policies are optimal and the computational requirements are drastically reduced. Simple approximate policies are suggested for the generally short period of time when systems might be out of long-run balance. There is some discussion of extensions.
Dynamic Process Improvement
Authors: Fine Charles H. , Porteus Evan L.
Published: November 2008

This paper explores the economics of investing in gradual process improvement, a key component, with empirically supported importance, of the well known Just-in-Time and Total Quality Control philosophies. We formulate a Markov decision process, analyze it, and apply it to the problem of setup reduction and process quality improvement. Instead of a one-time investment opportunity for a large predictable technological advance, we allow many smaller investments over time, with potential process improvements of random magnitude. We use a somewhat nonstandard formulation of the immediate return, which facilitates the derivation of results. The policy that simply maximizes the immediate return, called the last chance policy, provides an upper bound on the optimal investment amount. Furthermore, if the last chance policy invests in process improvement, then so does the optimal policy. Each continues investing until a shared target state is attained. We derive fairly restrictive conditions that must be met for the policy of investing forever in process improvements to be optimal. Decreasing the uncertainty of the process (making the potential improvements more predictable) has a desirable effect: the total return is increased and the target state increases, so the ultimate system is more productive. Numerical examples are presented and analyzed.
Approximate Analysis of Queues in Series with Phase-Type Service Times and Blocking
Authors: Altiok Tayfur
Published: November 2008

Queues in series with phase-type service times and finite queue capacities are considered. Servers may get blocked due to the limited space in queues. An approximation method is developed to compute the steady state probability distributions of the number of units in each queue. Three cases are considered: the first queue has an infinite capacity; the first queue has a finite capacity; and the first server is always busy. The method decomposes the system of tandem queues into individual queues with revised arrival and service processes and with queue capacities. Then, each queue is analyzed in isolation within an iterative scheme which relates these queues to each other. The approximation method is computationally efficient and it appears to have an acceptable error level.
Monotonic and Insensitive Optimal Policies for Control of Queues with Undiscounted Costs
Authors: Stidham Shaler , Weber Richard R.
Published: November 2008

We consider the problem of controlling the service and/or arrival rates in queues, with the objective of minimizing the total expected cost to reach state zero. We present a unified, simple method for proving that an optimal policy is monotonic in the number of customers in the system. Applications to average-cost minimization over an infinite horizon are given. Both exponential and nonexponential models are considered; the essential characteristic is a left-skip-free transition structure and a nondecreasing (not necessarily convex) holding-cost function. Some of our results are insensitive to service-time distributions.
Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem
Authors: Guignard Monique , Rosenwein Moshe B.
Published: November 2008

The generalized assignment problem (GAP) determines the minimum cost assignment of n jobs to m agents such that each job is assigned to exactly one agent, subject to an agent's capacity. Existing solution algorithms have not solved problems with more than 100 decision variables. This paper designs an optimization algorithm for the GAP that effectively solves problems with up to 500 variables. Compared with existing procedures, this algorithm requires fewer enumeration nodes and shorter running times. Improved performance stems from: an enhanced Lagrangian dual ascent procedure that solves a Lagrangian dual at each enumeration node; adding a surrogate constraint to the Lagrangian relaxed model: and an elaborate branch-and-bound scheme. An empirical investigation of various problem structures, not considered in existing literature, is also presented.
OR Practice—Selecting a Portfolio of Environmental Programs for a Synthetic Fuels Facility
Authors: Peerenboom James P. , Buehring William A. , Joseph Timothy W.
Published: November 2008

This article describes how a U.S. Department of Energy steering committee used a decision analysis procedure to develop a portfolio of environmental and health research programs for a commercial-scale synthetic fuels facility. The procedure used information and insights from decision analyses conducted in five technical areas to support decision analysis at the portfolio level. The problem was complex because it included many combinations of studies that could be funded; multiple objectives in the five technical areas, as well as at the portfolio level; and uncertainties about research needs, the availability of technical data, and research costs. The article discusses: the rationale for using formal decision analysis, the main features of the procedure, and how the procedure provided the steering committee with a logical basis for evaluating a large number of diverse technical projects and, with the help of health and environmental experts, established research priorities and budget allocations in a logical and defensible manner.
OR Practice—An Efficient Decision Support System for Academic Course Scheduling
Authors: Dinkel John J. , Mote John , Venkataramanan M. A.
Published: November 2008

This paper describes a network-based decision support system approach to the most general form of the academic course scheduling problem. The dimensions of faculty, subject, time, and room are considered by incorporating a penalty function into a network optimization approach. The approach, based on a network algorithm, is capable of solving very large problems. This methodology can be applied to other scheduling situations where there are competing objectives and multiple resources. Such situations include: scheduling of exams, times, and rooms in an academic setting, and scheduling of clients, times, and facilities for physicians, hospitals, dentists, counselors, and clinics. Common problems in such settings include the utilization of available space, and dissatisfaction with assigned times and locations. The proposed system results in more effective room utilization patterns, improved instructor satisfaction levels, and streamlines the tedious scheduling process. We describe the use of the model to schedule all graduate and undergraduate courses in the College of Business Administration at Texas A&M University. This involves 175 faculty, over 300 sections, 20 rooms, and 16 time slots for each semester's scheduling problem.
APROS: Algorithmic Development Methodology for Discrete-Continuous Optimization Problems
Authors: Paules Granville E. , Floudas Christodoulos A.
Published: November 2008

APROS represents an algorithmic development procedure for classes of mathematical programming problems that involve some form of decomposition technique and require extensive communication of data between a set of subproblems whose sizes and structures may vary during the solution procedure. Examples include most classes of mixed-integer nonlinear programming problems and large-scale mixed-integer linear programming problems as well as a wide variety of algorithms for large-scale nonlinear and linear programming problems exhibiting special structure. APROS works through the General Algebraic Modeling System (GAMS) to provide exact syntactic statement of algorithmic solution procedures. APROS procedures are implemented through GAMS which is interfaced with nonlinear, linear and mixed-integer linear programming solvers to provide completely general automated implementations of many well known algorithms including the Generalized Benders Decomposition, the Outer Approximation/Equality Relaxation and Dantzig-Wolfe Decomposition. The flexibility of APROS and the highly procedural modeling language GAMS provide a means of obtaining quick solutions to difficult classes of problems by implementing a selected algorithm, and also provide a unique tool for developing, prototyping and experimenting with new algorithms. A description of the procedural components, features and setups is presented with emphasis on the generality of the techniques.
Fast, Effective Algorithms for Simple Assembly Line Balancing Problems
Authors: Hackman Steven T. , Magazine Michael J. , Wee T. S.
Published: November 2008

A simple, fast and effective heuristic for the Simple Assembly Line Balancing Type I problem (minimizing the number of workstations) is proposed. A fast and effective branch-and-bound algorithm, which incorporates this heuristic for use in bounding, is developed. The algorithm introduces heuristic fathoming as a technique for reducing the size of the branch-and-bound tree. Methods to solve the Simple Assembly Line Balancing Type II problem (maximizing the production rate) are also described. Upper bounds on all heuristics for both problems are provided.
Sequencing in an Assembly Line with Blocking to Minimize Cycle Time
Authors: McCormick S. Thomas , Pinedo Michael L. , Shenker Scott , Wolf Barry
Published: November 2008

We consider an assembly line with m stations in series having finite capacity buffers. Blocking occurs when buffers are full. There are M different types of products to be assembled, each with its own processing requirements. There is a production target set for each type. The problem is to operate the line to maximize throughput. We propose heuristic approaches to this problem based on an equivalent maximum flow problem and on critical path techniques.
A Dynamic Nash Game Model of Oil Market Disruption and Strategic Stockpiling
Authors: Murphy Frederic H. , Toman Michael A. , Weiss Howard J.
Published: November 2008

In this paper we present and analyze a Nash dynamic game model for investigating public and private sector oil inventory policies in unstable world oil markets. Conceptual results about the model include simple, verifiable conditions for uniqueness and stability of solutions, along with characterizations of optimal policies. We also present results and discuss computational issues that arise in determining subgame perfect infinite-horizon equilibria, using a steady-state policy iteration approach.
OR Forum—Perspectives on Parallel Computing
Authors: Kindervater G. A. P. , Lenstra J. K. , Rinnooy Kan A. H. G.
Published: November 2008

Operations research is one problem domain that is likely to benefit from advances in parallel computing. We briefly review what has been achieved in recent years and try to sketch what may be expected in the near future. We argue that the lack of uniformity in available architectures is the main obstacle for the breakthrough of parallel computing. Also, formal techniques will have to be developed for the design and implementation of efficient parallel algorithms, and more realism will be required in theoretical models of parallel computation.
An Optimal Branch-and-Bound Procedure for the Constrained Path, Moving Target Search Problem
Authors: Eagle James N. , Yee James R.
Published: November 2008

A searcher and target move among a finite set of cells C = 1, 2, …,N in discrete time. At the beginning of each time period, one cell is searched. If the target is in the selected cell j, it is detected with probability qj. If the target is not in the cell searched, it cannot be detected during the current time period. After each search, a target in cell j moves to cell k with probability pjk. The target transition matrix, P = [pjk] is known to the searcher. The searcher's path is constrained in that if the searcher is currently in cell j, the next search cell must be selected from a set of neighboring cells Cj. The object of the search is to minimize the probability of not detecting the target in T searches.
Polyhedral Characterization of Discrete Dynamic Programming
Authors: Martin R. Kipp , Rardin Ronald L. , Campbell Brian A.
Published: November 2008

Many interesting combinatorial problems can be optimized efficiently using recursive computations often termed discrete dynamic programming. In this paper, we develop a paradigm for a general class of such optimizations that yields a polyhedral description for each model in the class. The elementary concept of dynamic programs as shortest path problems in acyclic graphs is generalized to one seeking a least cost solution in a directed hypergraph. Sufficient conditions are then provided for binary integrality of the associated hyperflow problem. Given a polynomially solvable dynamic program, the result is a linear program, in polynomially many variables and constraints, having the solution vectors of the dynamic program as its extreme-point optima. That is, the linear program provides a succinct characterization of the solutions to the underlying optimization problem expressed through an appropriate change of variables. We also discuss projecting this formulation to recover constraints on the original variables and illustrate how some important dynamic programming solvable models fit easily into our paradigm. A classic multiechelon lot sizing problem in production and a host of optimization problems on recursively defined classes of graphs are included.
An Analytic Approach to a General Class of G/G/s Queueing Systems
Authors: Bertsimas Dimitris
Published: November 2008

We solve the queueing system Ck/Cm/s, where Ck is the class of Coxian probability density functions (pdfs) of order k, which is a subset of the pdfs that have a rational Laplace transform. We formulate the model as a continuous-time, infinite-space Markov chain by generalizing the method of stages. By using a generating function technique, we solve an infinite system of partial difference equations and find closed-form expressions for the system-size, general-time, prearrival, post-departure probability distributions and the usual performance measures. In particular, we prove that the probability of n customers being in the system, when it is saturated is a linear combination of geometric terms. The closed-form expressions involve a solution of a system of nonlinear equations that involves only the Laplace transforms of the interarrival and service time distributions. We conjecture that this result holds for a more general model. Following these theoretical results we propose an exact algorithm for finding the system-size distribution and the system's performance measures. We examine special cases and apply this method for numerically solving the C2/C2/s and Ek/C2/s queueing systems.
Decision Support System for the School Districting Problem
Authors: Ferland Jacques A. , Guénette Gilles
Published: November 2008

For a school board with several schools in its territory, the School Districting Problem is to specify the groups of children attending each school. A decision support system used to help administrators is described in this paper. It includes several heuristic procedures to assign edges of the network to the schools. The color graphics display is extensively used to assess the quality of the solution and to provide interactive functions for modifying the solution.
An Anti-PASTA Result for Markovian Systems
Authors: Green Linda , Melamed Benjamin
Published: November 2008

PASTA (Poisson Arrivals See Time Averages) is a term coined by R. Wolff in his well known 1982 paper. In keeping with Wolff's terminology, we use the term anti-PASTA to refer to the following converse of PASTA. Given that arrivals do indeed see time averages, when must the arrival process necessarily be Poisson? We show that anti-PASTA is satisfied in a pure-jump Markov process, provided that the arrival process corresponds to a subset of the Markov process jumps.
A Note on PASTA and Anti-PASTA for Continuous-Time Markov Chains
Authors: Wolff Ronald W.
Published: November 2008

The result Poisson Arrivals See Time Averages (PASTA) is well established in the queueing literature. Although there are some well known examples where non-Poisson arrivals see time averages, arrival and time averages usually are different when arrivals are not Poisson. There are also situations where it has been shown that arrivals see time averages only if arrivals are Poisson, a property called Anti-PASTA. We present a simple and direct proof of Anti-PASTA for continuous-time Markov chains.
Sequencing with Earliness and Tardiness Penalties: A Review
Authors: Baker Kenneth R. , Scudder Gary D.
Published: November 2008

We consider the problem of scheduling n jobs to minimize the total earliness and tardiness penalty. We review the literature on this topic, providing a framework to show how results have been generalized starting with a basic model that contains symmetric penalties, one machine and a common due date. To this base we add such features as parallel machines, complex penalty functions and distinct due dates. We also consolidate many of the existing results by proving general forms of two key properties of earliness/tardiness models.
Simple Solution Procedures for a Class of Two-Echelon Inventory Problems
Authors: Axsäter Sven
Published: November 2008

We consider an inventory system with one warehouse and N retailers. Lead times are constant and the retailers face independent Poisson demand. Replenishments are one-for-one. We provide simple recursive procedures for determining the holding and shortage costs of different control policies.
Prediction and Prescription in Systems Modeling
Authors: Simon Herbert A.
Published: November 2008

Modeling is a principal tool for studying complex systems. Since models may be used for predictions, for analysis, or for prescription, we must ask what our goals are before we build our models. Historically, predictive numerical models have dominated our practice. Since the world we are modeling is orders of magnitude more complex than even the largest models our computers can handle, we must conserve computational power, first, by asking how much temporal detail we need and how much can be supported by available data and theories, second, by asking whether knowledge of steady states may not be more important than knowledge of temporal paths, third, by using the hierarchical properties of systems to aggregate and thereby simplify them, and, fourth, by substituting symbolic modeling, where appropriate, for numerical modeling.
Heuristic Methods for Selection and Ordering of Part-Orienting Devices
Authors: Sethi S. P. , Sriskandarajah C. , Tayi Giri Kumar , Rao M. R.
Published: November 2008

Part-orienting systems are employed in many manufacturing environments to feed work parts in correct orientation for proper operations. A part-orienting system is a serial arrangement of orienting devices; the selection and ordering of these devices is an important design aspect that is addressed in this paper. In addition, a parallel configuration that consists of individual orienting subsystems is briefly investigated. Numerical examples and extensive computational results are reported.
Sharp Bounds on Probabilities Using Linear Programming
Authors: Prékopa András
Published: November 2008

In a previous paper (1988), the author proposed methods to obtain sharp lower and upper bounds for probabilities that at least one out of n events occurs, based on the knowledge of some of the binomial moments of the number of events which occur and linear programming formulations. This paper presents further results concerning other and more general logical functions of events: We give sharp lower and upper bounds for the probabilities that: a) exactly r events, b) at least r events occur, using linear programming. The basic facts are expressed by the dual feasible basis characterization theorems which are interpreted in terms of the vertices of the dual problems. We mention some linear inequalities, among the binomial moments, generalize the theory for the case of nonconsecutive binomial moments and present numerical examples.
An Empirical Evaluation of the KORBX® Algorithms for Military Airlift Applications
Authors: Carolan William J. , Hill James E. , Kennington Jeffery L. , Niemi Sandra , Wichmann Stephen J.
Published: November 2008

KORBX® (a registered trademark of AT&T) is AT&T's new system for solving large-scale linear programs. The system consists of both hardware, which uses parallel processing technology configured with 256 MB of memory, and software which exploits the design and resources of this modern hardware. The KORBX linear programming software system contains four algorithms which are variations of the interior point method of Narendra Karmarkar. The primal, dual, primal-dual, and power series algorithms were empirically evaluated on a set of linear programming application models being used by the staff of the Military Airlift Command at Scott Air Force Base. For calibration purposes, a set of smaller test problems were also run using MPSX and XMP; and some pure network problems were solved using NETFLO, MPSX, and XMP.
Optimal and Approximate Policies in Multiperiod, Multilocation Inventory Models with Transshipments
Authors: Robinson Lawrence W.
Published: November 2008

This paper examines the effects on the optimal ordering policy (and its cost) of allowing for interactions among retail outlets. Specifically, transshipments are allowed as recourse actions occurring after demands are realized but before they must be satisfied. The resultant savings in holding and shortage costs are balanced against the costs of transshipment. A base stock ordering policy is optimal for this model. If the final period base stock order-up-to point is nonnegative, then it will be the base stock order-up-to point for all periods; unfortunately, it can be found analytically only for two special cases, where either the cost parameters are equal at every outlet or there are only two outlets. These two special cases are used to validate a heuristic solution technique employing Monte Carlo integration, which is then compared to an easily calculated base policy in order to gauge the contribution of this model. The additional savings from using this heuristic policy are significant, particularly for problems with many retail outlets and low transshipment costs.
A Queueing Model to Analyze the Value of Centralized Inventory Information
Authors: Zheng Yu-Sheng , Zipkin Paul
Published: November 2008

Competitive pressures and technological improvements are leading many firms to consider centralized information systems to manage inventories and schedule production. We propose a simple model to explore the potential benefits of such coordination. The model represents two products competing for a single production facility. Simple Markovian behavior is assumed throughout. The key step in the analysis is the explicit solution of a queueing model with a novel priority discipline: Serve a customer from the class having the largest number of customers in the system.
Exchangeable Items in Repair Systems: Delay Times
Authors: Daduna Hans
Published: November 2008

We compute the delay time distribution for a customer who delivers a failed item to a repair system, when the items are exchangeable and the customer accepts any repaired item that is offered when he is at the head of the customer queue.
Generalized Entropy-Based Weights for Multiattribute Value Models
Authors: Soofi Ehsan S.
Published: November 2008

The minimum discrimination information weights generalizes the entropy-based “nearly-equal” weights for additive multiattribute value models.
Mathematical Programming and Economic Theory
Authors: Scarf Herbert E.
Published: November 2008

This paper, which is based on the remarks offered during a plenary address at the May 1989 CORS/TIMS/ORSA meeting in Vancouver, discusses the analogy between economic institutions and algorithms for solving mathematical programming problems. The simplex method for solving linear programs can be interpreted as a search for market prices that equilibrate the demand for factors of production with their supply. A possible interpretation in terms of the internal organization of a large firm is offered for Lenstra's integer programming algorithm.
Asymptotically Attainable Structures in Nonhomogeneous Markov Systems
Authors: Vassiliou P.-C. G. , Georgiou A. C.
Published: November 2008

In this paper, we provide and study a new aspect in the classical problem of the asymptotic behavior of a nonhomogeneous Markov system (NHMS). The set of asymptotically attainable structures is determined as the convex hull of k vertices, which are given. Also, the rate of convergence to asymptotically attainable structures is studied and conditions are provided for the convergence to be geometrically fast. Finally, an illustration of the results with data from manpower systems is provided.
A Note on: An Efficient Point Algorithm for a Linear Two-Stage Optimization Problem
Authors: Haurie A. , Savard G. , White D. J.
Published: November 2008

The efficient point algorithm proposed by J. F. Bard for the computation of the solution of the Linear Two-Stage Optimization Problem does not always converge to the desired solution. A counterexample is provided and the reasons for this lack of convergence are discussed.
Computational Difficulties of Bilevel Linear Programming
Authors: Ben-Ayed Omar , Blair Charles E.
Published: November 2008

We show, using small examples, that two algorithms previously published for the Bilevel Linear Programming problem (BLP) may fail to find the optimal solution and thus must be considered to be heuristics. A proof is given that solving BLP problems is NP-hard, which makes it unlikely that there is a good, exact algorithm.
Heavy Traffic Response Times for a Priority Queue with Linear Priorities
Authors: Nelson Randolph D.
Published: November 2008

This paper analyzes a queueing system consisting of a single server which dispenses service to jobs of K ≥ 1 priority classes. Jobs are assumed to arrive to the queue according to a Poisson point process with a class dependent rate and to have class dependent service demands that are generally distributed. A linear priority function of the time spent in the system is specified for each job class and is used to schedule jobs. Specifically, the server, when available for service, nonpreemptively selects the job having the highest priority value to be the next job scheduled. Previous work in analyzing a system of this type has concentrated on providing bounds on the expected class response time. We extend these results by providing a closed form expression for the mean class response time and an expression for the ratio of expected response times in the limiting case of heavy traffic. We also provide a closed form expression for the mean class response time under certain light load conditions.
Aggregation and Disaggregation in Integer Programming Problems
Authors: Hallefjord Åsa , Storøy Sverre
Published: November 2008

Column aggregation of 0/1 programming problems is considered. By relaxing the integer requirements in the aggregated problem, an easy problem results, the solution of which can be used to compute bounds on the loss of accuracy in the objective function value. It is shown how these bounds can be improved by identification of valid inequalities and by exploiting primal degeneracy. A small example is given to illustrate the procedure.
The Structure of Periodic Review Policies in the Presence of Random Yield
Authors: Henig Mordechai , Gerchak Yigal
Published: November 2008

This work provides a comprehensive analysis of a general periodic review production/inventory model with random (variable) yield. Existence of an order point whose value does not depend on yield being random is proved in the single period case without specifying the yield model and using a very general cost structure. When yield is a random multiple of lot size, the nonorder-up-to optimal policy is characterized for a finite-horizon model. The finite-horizon value functions are shown to converge to the solution of an infinite-horizon functional equation, and the infinite-horizon order point is shown to be no smaller than when yield is certain.
Priority Queues with Setup Times
Authors: Takagi Hideaki
Published: November 2008

Queueing analysis is conducted for M/G/1-type systems with multiple classes of service requests that need a setup time prior to each busy period. We consider a variety of service disciplines: FCFS (first-come, first-served), LCFS (last-come, first-served), nonpreemptive priority, preemptive resume priority, and gated batch priority. This study has been motivated by the performance evaluation of multiprocessor bus arbitration protocols. The Laplace–Stieltjes transform of the distribution function, the mean, and the second moment of the waiting time for each class are derived explicitly. As a limit of continuous priorities, the shortest-job-first discipline with setup times is also considered.
On the Optimal Allocation of Servers and Workloads in Closed Queueing Networks
Authors: Dallery Yves , Stecke Kathryn E.
Published: November 2008

In this paper, properties are derived that are useful for characterizing optimal allocations of servers and workloads in single-class, multiserver closed queueing networks (CQNs). The problem is as follows: Suppose a particular workload is allocated to a set of servers within a subnetwork of a CQN. This set of servers is to be partitioned into several multiserver stations. The number of stations, the number of servers, and the workload allocation to each station define a configuration of this subnetwork. Thus, the problem is to determine the best configuration of each subnetwork to maximize the throughput in the original CQN. Decomposition is used to address this problem. Results are obtained for subnetworks in isolation. These results are used to solve the optimal-configuration problem. Applications of the results to design and planning problems of flexible manufacturing are also described.
Risk Criteria in a Stochastic Knapsack Problem
Authors: Henig Mordechai I.
Published: November 2008

We consider an investor who wants to allocate funds among several projects. Each project is expected to yield a certain reward, and the objective is that a total reward will achieve a certain given amount, called the target. This problem is relatively easy to solve when rewards are deterministic, but may be hard in a more realistic setting when the rewards are stochastic and the investor wants to maximize the probability of attaining the target. We show that, by combining dynamic programming with a search procedure, the stochastic version of the problem can be solved relatively fast when rewards are normally distributed. The procedure is also useful for other risk criteria, which involve both the mean and the variance of the total reward.
Myopic Solutions of Affine Dynamic Models
Authors: Sobel Matthew J.
Published: November 2008

New sufficient conditions are presented for a dynamic process to have a myopic optimum and for a sequential game to possess a myopic equilibrium point. An optimum (or an equilibrium point) is said to be myopic if it can be specified by solving a static optimization problem (or a static Nash game). The results are applied to an aquaculture harvesting model and a dynamic oligopoly model with advertising decisions.
The Mixed Integer Linear Bilevel Programming Problem
Authors: Moore James T. , Bard Jonathan F.
Published: November 2008

A two-person, noncooperative game in which the players move in sequence can be modeled as a bilevel optimization problem. In this paper, we examine the case where each player tries to maximize the individual objective function over a jointly constrained polyhedron. The decision variables are variously partitioned into continuous and discrete sets. The leader goes first, and through his choice may influence but not control the responses available to the follower. For two reasons the resultant problem is extremely difficult to solve, even by complete enumeration. First, it is not possible to obtain tight upper bounds from the natural relaxation; and second, two of the three standard fathoming rules common to branch and bound cannot be applied fully. In light of these limitations, we develop a basic implicit enumeration scheme that finds good feasible solutions within relatively few iterations. A series of heuristics are then proposed in an effort to strike a balance between accuracy and speed. The computational results suggest that some compromise is needed when the problem contains more than a modest number of integer variables.
A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm
Authors: Todd Michael J.
Published: November 2008

We show that a variant of Karmarkar's projective algorithm for linear programming can be viewed as following the approach of Dantzig-Wolfe decomposition. At each iteration, the current primal feasible solution generates prices which are used to form a simple subproblem. The solution to the subproblem is then incorporated into the current feasible solution. With a suitable choice of stepsize a constant reduction in potential function is achieved at each iteration. We also use our analysis to motivate a new primal simplex pivot rule that is closely related to rules used by E. Klotz and L. Schrage.
A Unified Family of Single-Server Queueing Location Models
Authors: Brandeau Margaret L. , Chiu Samuel S.
Published: November 2008

In this paper, we introduce a general class of single-server network location models which includes the median, center, stochastic queue median, stochastic queue center, Lp norm, and other location problems in a single parametric framework. The model incorporates both queueing effects and a cost function (similar to a disutility function), which is nonlinear in response time. We develop a number of properties of this class of models, and present a method for evaluating a range of different objective functions for any given problem. The robustness of the median and center objectives as solution concepts is highlighted.
Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Network with Controllable Inputs
Authors: Wein Lawrence M.
Published: November 2008

Motivated by a factory scheduling problem, we consider the problem of input control, subject to a specified product mix, and priority sequencing in a two-station multiclass queueing network with general service time distributions and a general routing structure. The objective is to minimize the long-run expected average number of customers in the system subject to a constraint on the long-run expected average output rate. Under balanced heavy loading conditions, this scheduling problem is approximated by a control problem involving Brownian motion. A reformulation of this Brownian control problem was solved exactly in 1990 by L. M. Wein. In the present paper, this solution is interpreted in terms of the queueing network model in order to obtain an effective scheduling rule. The resulting sequencing policy dynamically prioritizes customers according to reduced costs calculated from a linear program. The input rule is a workload regulating input policy, where a customer is injected into the system whenever the expected total amount of work in the system for the two stations falls within a prescribed region. An example is presented that illustrates the procedure and demonstrates its effectiveness.
Testing Feasibility in a Lot Scheduling Problem
Authors: Anderson Edward J.
Published: November 2008

In this paper, we consider a version of the Economic Lot Scheduling Problem in which there are no costs specified. The usual form of this problem seeks a pattern of production that minimizes the sum of holding the setup costs. We investigate the problem of finding a feasible schedule which avoids a stockout given the initial stocks of the products being manufactured. It is shown that this problem is NP-hard, and an effective heuristic method for its solution is proposed. This heuristic method is compared with a more naive approach to the problem and some computational results are given.
Approximation Analysis of Open Acyclic Exponential Queueing Networks with Blocking
Authors: Lee Hyo-Seong , Pollock Stephen M.
Published: November 2008

An arbitrary configuration of an open queueing network with exponential service times and finite buffers is analyzed. We offer an iterative procedure for approximating the marginal occupancy probabilities for each queue of the system. The method decomposes the queueing network into individual queues and analyzes each in isolation using information from only its nearest neighbors. Based upon the SIMP approximation previously used for tandem queues, it replaces each server's service time with a clearance time, which includes blocking, and each server's arrival rate by an equivalent acceptance rate. The procedure is easy to implement and requires modest memory and computer time. Extensive numerical experiments, performed for various topologies, yield accurate results compared with those obtained by exact or simulation methods.
Ford Whitman Harris and the Economic Order Quantity Model
Authors: Erlenkotter Donald
Published: November 2008

Ford Whitman Harris first presented the familiar economic order quantity (EOQ) model in a paper published in 1913. Even though Harris's original paper was disseminated widely, it apparently was unnoticed for many years before its rediscovery in 1988. During this period much confusion developed over the origin of the EOQ model. This paper explores the early literature on this model and traces the evolution of the confusion. It also sketches the remarkable life of Harris, who made contributions as an engineer, inventor, author and patent attorney, even though he received no formal education beyond high school. Harris's original 1913 essay is reprinted following this paper.
On the Existence of a Feasible Flow in a Stochastic Transportation Network
Authors: Prékopa András , Boros Endre
Published: November 2008

Many transportation networks, e.g., networks of cooperating power systems, and hydrological networks involve a real-valued demand function, defined on the set of nodes, and it is said to be feasible if there exists a flow such that at each node the sum of the incoming flow values is greater than or equal to the demand assigned to this node. By the theorem of D. Gale and A. Hoffman, a system of linear inequalities involving the demand and the arc capacity functions, gives necessary and sufficient condition for the feasibility of the demand. If the demands and/or the arc capacities are random, then an important problem is to find the probability that all these inequalities are satisfied. This paper proposes a new method to eliminate all redundant inequalities for given lower and upper bounds of the demand function, and finds sharp lower and upper bounds for the probability that a feasible flow exists. The results can be used to support transportation network analysis and design.
An Algorithm for the Three-Index Assignment Problem
Authors: Balas Egon , Saltzman Matthew J.
Published: November 2008

We describe a branch-and-bound algorithm for solving the axial three-index assignment problem. The main features of the algorithm include a Lagrangian relaxation that incorporates a class of facet inequalities and is solved by a modified subgradient procedure to find good lower bounds, a primal heuristic based on the principle of minimizing maximum regret plus a variable depth interchange phase for finding good upper bounds, and a novel branching strategy that exploits problem structure to fix several variables at each node and reduce the size of the total enumeration tree. Computational experience is reported on problems with up to 78 equations and 17,576 variables. The primal heuristics were tested on problems with up to 210 equations and 343,000 variables.
Computationally Feasible Bounds for Partially Observed Markov Decision Processes
Authors: Lovejoy William S.
Published: November 2008

A partially observed Markov decision process (POMDP) is a sequential decision problem where information concerning parameters of interest is incomplete, and possible actions include sampling, surveying, or otherwise collecting additional information. Such problems can theoretically be solved as dynamic programs, but the relevant state space is infinite, which inhibits algorithmic solution. This paper explains how to approximate the state space by a finite grid of points, and use that grid to construct upper and lower value function bounds, generate approximate nonstationary and stationary policies, and bound the value loss relative to optimal for using these policies in the decision problem. A numerical example illustrates the methodology.