bluuebunny/crossref_metadata_2025 huggingface dataset:
Strategic Flow Management for Air Traffic Control
Authors: Terrab Mostafa , Odoni Amedeo R.
Published: November 2008

One of the most important functions of air traffic management systems is the assignment of ground-holding times to flights, i.e., the determination of whether and by how much the take-off of a particular aircraft headed for a congested part of the ATC system should be postponed to reduce the likelihood and extent of airborne delays. In this paper, we will present an analysis of the fundamental case in which flights from many origins must be scheduled for arrival at a single, congested airport. We will describe a set of approaches for addressing a deterministic and a stochastic version of the problem. A minimum cost flow algorithm can be used for the deterministic problem. Under a particular natural assumption regarding the functional form of delay costs, a very efficient, simple algorithm is also available. For the stochastic version, an exact dynamic programming formulation turns out to be impractical for typical instances of the problem and we present a number of heuristic approaches to it. The models and numerical results suggest the potential usefulness of formal decision support tools in developing effective ground-holding strategies. Many methodological and implementation issues, however, still require resolution.
Externalities, Average and Marginal Costs, and Tolls on Congested Networks with Time-Varying Flows
Authors: Carey Malachy , Srinivasan Ashok
Published: November 2008

For congested networks on which flows vary over time, we derive system marginal costs, user perceived costs and user externality costs, for each arc and path. We also obtain a set of optimal congestion tolls and flow controls which may be used to shift the user determined flows toward a socially preferred pattern. An important way in which our results differ from the usual static analysis is that the social cost externality depends not only on the level of congestion, but also on the rate of increase or decrease of congestion. This is intuitively explicable as follows. Consider users delayed on an arc. Their delays will be further compounded or multiplied if congestion has increased during the time they are delayed. On the other hand, their delays will be reduced if congestion has declined during the time they are delayed. This multiplier effect is such that the resultant dynamic externalities can easily be a few times larger, or smaller, than the externalities derived in the usual static analysis. As a result, the congestion tolls or tariffs which are usually proposed or advocated, based on static analysis, may be inappropriate. The results are illustrated with a numerical application to a small network example.
Dynamic Lot Sizing for Multi-Echelon Distribution Systems with Purchasing and Transportation Price Discounts
Authors: Diaby Moustapha , Martel Alain
Published: November 2008

We consider the problem of determining optimal purchasing and shipping quantities over a finite planning horizon for arborescent, multi-echelon physical distribution systems with deterministic, time-varying demands. We assume that the inventory holding cost at a given warehouse of the distribution network is a linear function of the inventory level, and that the total procurement cost (i.e., ordering, plus purchasing, plus transportation and reception costs) is a general piecewise-linear function of the quantities shipped to and from the warehouse. We formulate a mixed integer linear programming model of the problem and develop a Lagrangian relaxation-based procedure to solve it. We show computational results for problems with 12 periods, up to 15 warehouses, and 3 transportation price ranges.
Dynamic Shortest Paths in Acyclic Networks with Markovian Arc Costs
Authors: Psaraftis Harilaos N. , Tsitsiklis John N.
Published: November 2008

We examine shortest path problems in acyclic networks in which arc costs are known functions of certain environment variables at network nodes. Each of these variables evolves according to an independent Markov process. The vehicle can wait at a node (at a cost) in anticipation of more favorable arc costs. We first develop two recursive procedures for the individual arc case, one based on successive approximations, and the other on policy iteration. We also solve the same problem via parametric linear programming. We show that the optimal policy essentially classifies the state of the environment variable at a node into two categories: green states for which the optimal action is to immediately traverse the arc, and red states for which the optimal action is to wait. We then extend these concepts for the entire network by developing a dynamic programming procedure that solves the corresponding problem. The complexity of this method is shown to be O(n2K + nK3), where n is the number of network nodes and K is the number of Markov states at each node. We present examples and discuss possible research extensions.
Making Large-Scale Models Manageable: Modeling from an Operations Management Perspective
Authors: Murphy Frederic H.
Published: November 2008

While building complex models is an important part of operations research practice, OR workers have focused too often on modeling's technical aspects instead of making the models manageable, that is, designing them around the ways people will operate them. The issues raised for complex models are different from those most widely discussed for decision support systems because the focus is on models that require a staff to maintain and operate them and on how the staff functions. Operations management provides the tools for thinking about the operations of large complex models; this paper examines some of these tools and shows how they relate to the design and operation of large complex models.
A Faster Strongly Polynomial Minimum Cost Flow Algorithm
Authors: Orlin James B.
Published: November 2008

In this paper, we present a new strongly polynomial time algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of O(n log n) shortest path problems on networks with n nodes and m arcs and runs in O(n log n(m + n log n)) time. Using a standard transformation, this approach yields an O(m log n(m + n log n)) algorithm for the capacitated minimum cost flow problem. This algorithm improves the best previous strongly polynomial time algorithm, due to Z. Galil and E. Tardos, by a factor of n2/m. Our algorithm for the capacitated minimum cost flow problem is even more efficient if the number of arcs with finite upper bounds, say m′, is much less than m. In this case, the running time of the algorithm is O((m′ + n) log n(m + n log n)).
On Decomposition Methods for Tandem Queueing Networks with Blocking
Authors: Dallery Yves , Frein Yannick
Published: November 2008

Queueing networks with blocking are useful for modeling and analyzing discrete event systems, especially manufacturing systems. Most analysis methods for queueing networks with blocking are approximation methods that involve a decomposition of the network into a set of subsystems. This paper presents some insight into these decomposition methods as well as new results. Attention is mainly restricted to the case of tandem queueing networks with exponential service times and blocking-after-service. This type of blocking is especially encountered in manufacturing systems. The first aim of this paper is to improve the understanding and present a unified view of the decomposition methods. We show that decomposition methods can be classified according to three main approaches. One of these approaches is of special interest because it offers a symmetrical view of the decomposition. The second aim of the paper is to provide properties pertaining to these decomposition methods in the case of exponential characterizations of subsystems. We prove the existence and uniqueness of the solution. Moreover, we prove the convergence of the computational algorithm associated with the symmetrical approach.
Numerical Solution of Continuous-State Dynamic Programs Using Linear and Spline Interpolation
Authors: Johnson Sharon A. , Stedinger Jery R. , Shoemaker Christine A. , Li Ying , Tejada-Guibert José Alberto
Published: November 2008

This paper demonstrates that the computational effort required to develop numerical solutions to continuous-state dynamic programs can be reduced significantly when cubic piecewise polynomial functions, rather than tensor product linear interpolants, are used to approximate the value function. Tensor product cubic splines, represented in either piecewise polynomial or B-spline form, and multivariate Hermite polynomials are considered. Computational savings are possible because of the improved accuracy of higher-order functions and because the smoothness of higher-order functions allows efficient quasi-Newton methods to be used to compute optimal decisions. The use of the more efficient piecewise polynomial form of the spline was slightly superior to the use of Hermite polynomials for the test problem and easier to program. In comparison to linear interpolation, use of splines in piecewise polynomial form reduced the CPU time to obtain results of equivalent accuracy by a factor of 250–330 for a stochastic 4-dimensional water supply reservoir problem with a smooth objective function, and factors ranging from 25–400 for a sequence of 2-, 3-, 4-, and 5-dimensional problems. As a result, a problem that required two hours to solve with linear interpolation was solved in a less than a minute with spline interpolation with no loss of accuracy.
Variance of the Sample Mean: Properties and Graphs of Quadratic-Form Estimators
Authors: Song Wheyming Tina , Schmeiser Bruce W.
Published: November 2008

Many commonly used estimators of the variance of the sample mean from a covariance-stationary process can be written as quadratic forms. We study the class of quadratic-form estimators algebraically and graphically, including five specific types of estimators, some from the literature and some that are new. Finite and asymptotic bias, variance, and covariance are derived and examined, with emphasis on developing intuition and insight by interpreting these properties graphically. The graphs depict the nonoptimal statistical behavior of some of the simulation literature estimators such as nonoverlapping batch means, as well as the better behavior of estimators obtained by overlapping batches.
Shadow Prices for Measures of Effectiveness, I: Linear Model
Authors: Robinson Stephen M.
Published: November 2008

This is the first of two papers dealing with the establishment of shadow prices for measures of effectiveness in an optimization-based combat model. In this paper we explain how the requirement for the analysis arose, and we show how to build a simple linear model that produces shadow, prices for kill requirements. When the model is further specialized, these shadow prices become the classical eigenvalue weights familiar from Lanchester theory.
Improved Algorithms for Economic Lot Size Problems
Authors: Aggarwal Alok , Park James K.
Published: November 2008

Many problems in inventory control, production planning, and capacity planning can be formulated in terms of a simple economic lot size model proposed independently by A. S. Manne (1958) and by H. M. Wagner and T. M. Whitin (1958). The Manne-Wagner-Whitin model and its variants have been studied widely in the operations research and management science communities, and a large number of algorithms have been proposed for solving various problems expressed in terms of this model, most of which assume concave costs and rely on dynamic programming. In this paper, we show that for many of these concave cost economic lot size problems, the dynamic programming formulation of the problem gives rise to a special kind of array, called a Monge array. We then show how the structure of Monge arrays can be exploited to obtain significantly faster algorithms for these economic lot size problems. We focus on uncapacitated problems, i.e., problems without bounds on production, inventory, or backlogging; capacitated problems are considered in a separate paper.
Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
Authors: Feo Thomas A. , Provan J. Scott
Published: November 2008

A simple, O(|V|2) time algorithm is presented that reduces a connected two-terminal, undirected, planar graph to a single edge, by way of series and parallel reductions and delta-wye transformations. The method is applied to a class of optimization/equilibnum problems which includes max flow, shortest path, and electrical resistance problems.
The Natural Drift: What Happened to Operations Research?
Authors: Corbett Charles J. , Van Wassenhove Luk N.
Published: November 2008

“Crisis? What crisis?” could also have been an appropriate title for this paper. The OR/MS literature contains more than enough papers addressing the crisis in OR/MS to take the matter seriously, but it is not always clear exactly what is meant by crisis. The complaints usually concern the perceived gap between theory and practice, pointing out that there are too many theoretical and too few practice-oriented papers. This may well be true, but we suggest a slightly different view of the crisis, by hypothesizing that a ‘natural drift’ has occurred, i.e., that old-style OR has remained underdeveloped relative to its more purely theoretical and practical counterparts. To explain how this hypothesis arose, we provide an overview of the debate on professional concerns in OR/MS, and contrast it with Harvard Business Review papers providing a managerial perspective. We also explore the extent to which such a natural drift would be truly natural, by comparing the development of OR/MS to that of other professions. We arrive at a mixed conclusion. All is not well, but all is not lost either.
A Primal Partitioning Solution for the Arc-Chain Formulation of a Multicommodity Network Flow Problem
Authors: Farvolden Judith M. , Powell Warren B. , Lustig Irvin J.
Published: November 2008

We present a new solution approach for the multicommodity network flow problem (MCNF) based upon both primal partitioning and decomposition techniques, which simplifies the computations required by the simplex method. The partitioning is performed on an arc-chain incidence matrix of the MCNF, similar within a change of variables to the constraint matrix of the master problem generated in a Dantzig-Wolfe decomposition, to isolate a very sparse, near-triangular working basis of greatly reduced dimension. The majority of the simplex operations performed on the partitioned basis are simply additive and network operations specialized for the nine possible pivot types identified. The columns of the arc-chain incidence matrix are generated by a dual network simplex method for updating shortest paths when link costs change.
Convergence Rates of Finite-Difference Sensitivity Estimates for Stochastic Systems
Authors: Zazanis Michael A. , Suri Rajan
Published: November 2008

A mean square error analysis of finite-difference sensitivity estimators for stochastic systems is presented and an expression for the optimal size of the increment is derived. The asymptotic behavior of the optimal increments, and the behavior of the corresponding optimal finite-difference (FD) estimators are investigated for finite-horizon experiments. Steady-state estimation is also considered for regenerative systems and in this context a convergence analysis of ratio estimators is presented. The use of variance reduction techniques for these FD estimates, such as common random numbers in simulation experiments, is not considered here. In the case here, direct gradient estimation techniques (such as perturbation analysis and likelihood ratio methods) whenever applicable, are shown to converge asymptotically faster than the optimal FD estimators.
A Stochastic, Multiclass Airline Network Equilibrium Model
Authors: Soumis François , Nagurney Anna
Published: November 2008

In this paper, we develop a stochastic, multiclass network equilibrium model of airline passenger transportation. The model explicitly incorporates the behavior of the passengers in regard to the decision whether or not to travel, and route selection, and formalizes the passenger's decision as an abstract network. The equilibrium between the realized demand for the routes of travel and the supply of the seats is shown to satisfy a system of nonlinear equations. A Gauss-Seidel algorithm is then proposed for the computation of the equilibrium and conditions for convergence are established. Finally, the algorithm is applied to compute the solution to the national Air Canada airline passenger network, and the output is compared to the actual observed flows.
Scheduling Networks of Queues: Heavy Traffic Analysis of a Multistation Closed Network
Authors: Chevalier Philippe B. , Wein Lawrence M.
Published: November 2008

We consider the problem of finding an optimal dynamic priority sequencing policy to maximize the mean throughput rate in a multistation, multiclass closed queueing network with general service time distributions and a general routing structure. Under balanced heavy loading conditions, this scheduling problem can be approximated by a control problem involving Brownian motion. Although a unique, closed-form solution to the Brownian control problem is not derived, an analysis of the problem leads to an effective static sequencing policy, and to an approximate means of comparing the relative performance of arbitrary static policies. Several examples are provided that illustrate the effectiveness of our procedure.
Stochastic Single Machine Scheduling with Quadratic Early-Tardy Penalties
Authors: Mittenthal John , Raghavachari M.
Published: November 2008

We address the problem of scheduling n jobs on a single machine, which is subject to random breakdowns, to minimize an expected sum of nonregular penalty functions. A simple recourse model is considered when the penalty function is the squared deviation of job completion times from a common due date, and a deterministic equivalent objective function is developed. Characterizations of optimal schedules for this quadratic objective function are established both when the common due date is a decision variable and when it is given and fixed. Most importantly, the V-shaped nature of optimal schedules is investigated for a class of Poisson processes, {N(t), t > 0}, describing the number of breakdowns in the interval (0, t). In addition, relationships to a class of bicriteria models are demonstrated.
Further Developments and Tests of a Progressive Algorithm for Multiple Criteria Decision Making
Authors: Korhonen Pekka , Moskowitz Herbert , Salminen Pekka , Wallenius Jyrki
Published: November 2008

P. Korhonen, H. Moskowitz, and J. Wallenius (1986) developed a progressive algorithm and the supporting theory for modeling and solving multiple criteria decision problems with discrete alternatives. A special feature of the algorithm is that it relaxes the usual assumption of a fixed set of available decision alternatives and complete knowledge of a decision maker's (DM's) preference structure or value function. The algorithm is based on progressively sampling the decision space, obtaining preference information from the DM, determining the likelihood of finding possibly/surely better alternatives, and based on this information, continuing the search or terminating it by making the final choice. We describe a computerized implementation and extensive computational tests of the algorithm, as well as some of our experiences in applying and field testing it in practice. We also consider several improvements and developments of the algorithm to further facilitate its use in practice.
The Delivery Man Problem and Cumulative Matroids
Authors: Fischetti Matteo , Laporte Gilbert , Martello Silvano
Published: November 2008

Given a complete directed graph G = (V, A), the delivery man problem (DMP) consists of determining a Hamiltonian circuit minimizing the sum of distances (along the circuit) from a given vertex v1, to every vertex of V, including v1 itself. There exists a number of applications of the DMP in the fields of distribution and machine scheduling. The DMP is NP-hard. The objective of this paper is to develop new theoretical results and an exact algorithm for the problem. A new, integer linear programming formulation is provided, and results on the matroidal structure of a class of combinatorial problems are developed. These are used to derive lower bounds for the DMP. These bounds are embedded into an enumerative algorithm. The largest problems solved to optimality with the proposed algorithm involve 60 vertices. This compares favorably with previously published methods.
Developing Conflict-Free Routes for Automated Guided Vehicles
Authors: Krishnamurthy Nirup N. , Batta Rajan , Karwan Mark H.
Published: November 2008

Automated guided vehicles (AGVs) are a highly sophisticated and increasingly popular type of material handling device in flexible manufacturing systems. This paper details solution methodologies for the static routing problem in which demand assignment of the AGVs are known; the focus is to obtain an implementable solution within a reasonable amount of computer time. The objective is to minimize the makespan, while routing AGVs on a bidirectional network in a conflict-free manner. This problem is solved via column generation. The master problem in this column generation procedure has the makespan and vehicle interference constraints. Columns in the master problem are routes iteratively generated for each AGV. The subproblem is a constrained shortest path problem with time-dependent costs on the edges. An improvement procedure is developed to better the solution obtained at the end of the master-subproblem interactions. Several methods of iterating between the master and subproblem are experimented with in-depth computational experiments. Our empirical results indicate that the procedure as a whole usually generates solutions that are within a few percent of a proposed bound, within reasonable computer time.
Dynamic Scheduling of a Multiclass Fluid Network
Authors: Chen Hong , Yao David D.
Published: November 2008

A fluid network is a deterministic network model in which dynamic continuous flows are circulated and processed among a set of stations. A fluid network often describes the asymptotic behavior of a stochastic queueing network via functional strong law of large numbers. We study the dynamic scheduling of multiple classes of fluid traffic in such a network. An algorithm is developed that systematically solves the dynamic scheduling problem by solving a sequence of linear programs. It generates a policy, in the form of dynamic capacity allocation at each station (among all fluid classes), that consists of a finite set of linear “pieces” over the entire time horizon. In a single-station, or equivalently, single-server, network, this solution procedure recovers the priority index set that is optimal for the corresponding discrete queueing model, generally known as Klimov's problem.
Global Convergence of a Generalized Iterative Procedure for the Minisum Location Problem with lp Distances
Authors: Brimberg Jack , Love Robert F.
Published: November 2008

This paper considers a general form of the single facility minisum location problem (also referred to as the Fermat-Weber problem), where distances are measured by an lp norm. An iterative solution algorithm is given which generalizes the well-known Weiszfeld procedure for Euclidean distances. Global convergence of the algorithm is proven for any value of the parameter p in the closed interval [1, 2], provided an iterate does not coincide with a singular point of the iteration functions. However, for p > 2, the descent property of the algorithm and as a result, global convergence, are no longer guaranteed. These results generalize the work of Kuhn for Euclidean (p = 2) distances.
Mean-Variance Tradeoffs in an Undiscounted MDP
Authors: Sobel Matthew J.
Published: November 2008

A stationary policy and an initial state in an MDP (Markov decision process) induce a stationary probability distribution of the reward. The problem analyzed here is generating the Pareto optima in the sense of high mean and low variance of the stationary distribution. In the unichain case, Pareto optima can be computed either with policy improvement or with a linear program having the same number of variables and one more constraint than the formulation for gain-rate optimization. The same linear program suffices in the multichain case if the ergodic class is an element of choice.
Mean-Variance Tradeoffs in an Undiscounted MDP: The Unichain Case
Authors: Chung Kun-Jen
Published: November 2008

The problem analyzed here is the computation of Pareto optima in the sense of high mean and low variance of the stationary distribution in the unichain, undiscounted Markov decision process (MDP, for short).
A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem
Authors: Ribeiro Celso C. , Soumis François
Published: November 2008

We give a new formulation to the multiple-depot vehicle scheduling problem as a set partitioning problem with side constraints, whose continuous relaxation is amenable to be solved by column generation. We show that the continuous relaxation of the set partitioning formulation provides a much tighter lower bound than the additive bound procedure previously applied to this problem. We also establish that the additive bound technique cannot provide tighter bounds than those obtained by Lagrangian decomposition, in the framework in which it has been used so far. Computational results that illustrate the robustness of the combined set partitioning-column generation approach are reported for problems four to five times larger than the largest problems that have been exactly solved in the literature. Finally, we show that the gap associated with the additive bound based on the assignment and shortest path relaxations can be arbitrarily bad in the general case, and as bad as 50% in the symmetric case.
Fenchel Cutting Planes for Integer Programs
Authors: Boyd E. Andrew
Published: November 2008

A technique for generating cutting planes for integer programs is introduced that is based on the ability to optimize a linear function on a polyhedron rather than explicit knowledge of the underlying polyhedral structure of the integer program. The theoretical properties of the cuts and their relationship to Lagrangian relaxation are discussed, the cut generation procedure is described, and computational results are presented.
Parallel Simplex for Large Pure Network Problems: Computational Testing and Sources of Speedup
Authors: Barr Richard S. , Hickman Betty L.
Published: November 2008

This paper reports on a new parallel implementation of the primal simplex method for minimum cost network flow problems that decomposes both the pivoting and pricing operations. The self-scheduling approach is flexible and efficient; its implementation is close in speed to the best serial code when using one processor, and is capable of substantial speedups as parallel computing units are added. An in-depth computational study of randomly generated transportation and transshipment problems verified the effectiveness of this approach, with results on a 20-processor 80386-based system that are competitive with, and occasionally superior to, massively parallel implementations using tens of thousands of processors. A microanalysis of the code's behavior identified unexpected sources of (the occasionally superlinear) speedup, including the evolutionary topology of the network basis.
Insights on Modeling from a Dozen Experts
Authors: Willemain Thomas R.
Published: November 2008

Twelve selected expert modelers described themselves as modelers, the models they make, the problems they model, and the way they model. They also expressed opinions about the qualities of effective models, modelers, modeling processes, and desirable modeling clients. Finally, they provided stories about their modeling experiences. Their responses provide benchmarks for developing a modeling science and validate the importance of the craft aspects of OR/MS practice. The paper suggests changes in instructors' approaches to OR/MS content and describes a new course that responds to the experts' insights.
Sample Path Derivatives for (s, S) Inventory Systems
Authors: Fu Michael C.
Published: November 2008

for (s, S) inventory systems, we derive sample path derivatives of performance measures with respect to the two parameters s and S. These derivatives yield derivative estimators which can be estimated from a single sample path or simulation of the inventory system, in some cases not even requiring actual knowledge of the underlying demand distribution. Such derivative estimates would be useful in sensitivity analysis or in gradient-based optimization techniques. We consider the nondiscounted periodic review system with general independent and identically distributed (i.i.d.) continuous demands, full backlogging, and general holding and shortage costs. For the infinite horizon model, consistency proofs are given for some special cases, although we argue why the estimators should be correct for the more general case.
Unifying Expert Systems and the Decision Sciences
Authors: Silverman Barry G.
Published: November 2008

There are many tools and much literature that combine the expert systems and mathematical modeling paradigms. This survey focuses on a subset consisting of: decision making and unification, and not mere co-existence, of the two approaches. The unification effort is new and presents many research challenges at the theoretical, methodological, and tool levels. At the theoretical level, accepted prescriptions now exist that stipulate in which situations it is valid to use various forms of mathematical and qualitative reasoning. This is leading to a unified theory of the decision sciences for problems spanning choice, forecasting, risk assessment, design, operations, and many others. At the tool level three forms of synthesis of expert systems and mathematical models are particularly noteworthy: knowledge-based decision aids, intelligent decision modeling systems, and decision analytic expert systems. This survey gives definitions, surveys, and examples of each of these ways of unifying expert systems and modeling. Following this are lessons learned and further research needs. A great deal of synthesis work remains to be done, and a goal of this survey is to highlight some of the issues and invite discussion.
Dynamic Production Scheduling for a Process Industry
Authors: de Matta Renato , Guignard Monique
Published: November 2008

Capacity-oriented production scheduling can be described as the assignment of competing products to several single level, capacitated production lines over a given planning horizon. This study was initially motivated by the production planning of various types of tiles by a tile manufacturing company. We considered different integer programming formulations and found that a disaggregated model, while increasing the size of the model, lends itself best to Lagrangian techniques and produces the strongest bounds. Additionally, from every Lagrangian solution, we can generate a feasible production schedule by systematically reassigning lines from products whose production exceeded demand to products with unsatisfied demands. The technique is not specific to tile companies, but can be used by any firm where product setups on production lines can be scheduled between consecutive periods with changeover cost, but without production loss. Our computational experience with real data from the tile company and randomly generated problem instances gave excellent lower and upper bounds.
A Priori Optimization of the Probabilistic Traveling Salesman Problem
Authors: Laporte Gilbert , Louveaux François V. , Mercure Hélène
Published: November 2008

The probabilistic traveling salesman problem (PTSP) is defined on a graph G = (V, E), where V is the vertex set and E is the edge set. Each vertex vi has a probability pi of being present. With each edge (vi, vj) is associated a distance or cost cij. In a first stage, an a priori Hamiltonian tour on G is designed. The list of present vertices is then revealed. In a second stage, the a priori tour is followed by skipping the absent vertices. The PTSP consists of determining a first-stage solution that minimizes the expected cost of the second-stage tour. The problem is formulated as an integer linear stochastic program, and solved by means of a branch-and-cut approach which relaxes some of the constraints and uses lower bounding functionals on the objective function. Problems involving up to 50 vertices are solved to optimality.
Sequencing and Cooperation
Authors: Curiel Imma , Potters Jos , Prasad Rajendra , Tijs Stef , Veltman Bart
Published: November 2008

In machine scheduling the first problem is to find a timetable that is optimal with respect to some efficiency criterion. If the jobs come from different clients the solution of the optimization problem is not the end of the story. In addition, we have to decide how the minimal total cost must be distributed among the parties involved. In this note, cost allocation problems will be considered to arise from one-machine scheduling problems with an additive and weakly increasing cost function. We will show that the cooperative games related to these cost allocation problems have a nonempty core. Furthermore, we give a rule that assigns a core element of the associated cost saving game to each scheduling problem of this kind and an initial order of the jobs.
The Devolution of OR/MS: Implications from a Statistical Content Analysis of Papers in Flagship Journals
Authors: Reisman Arnold , Kirschnick Frank
Published: November 2008

Ackoff has decried the “devolution” of OR/MS, Corbett and Van Wassenhove have spoken of its “natural drift,” and a sociologist has described its “regression” as typifying that of other learned professions. To shed light on these views, we undertook a detailed survey of a segment of the OR/MS literature, with particular focus on the space in flagship journals devoted to theory on the one hand and applications on the other. While the literature of OR/MS contains many articles and texts with the word application in the title and the word data in the text, the definitions and uses of these terms are not precise. The claimed applications differ in degree and the actual data differ in kind. To encompass these different meanings we used a five-point scale to classify articles in the 1962 and 1992 volumes of Operations Research and Management Science and the 1972 and 1992 volumes of Interfaces. The resulting statistical analyses shed considerable light on the direction that OR/MS is taking and raise questions about its appropriateness. Finally, the paper raises fundamental questions about the direction that OR/MS should take and the roles that its journals should play in pursuing this direction.
Devising a Cost Effective Schedule for a Baseball League
Authors: Russell Robert A. , Leung Janny M. Y.
Published: November 2008

In this paper, we discuss the problem of devising a cost effective schedule for a baseball league. Sports scheduling is a notoriously difficult problem. A schedule must satisfy constraints on timing such as the number of games to be played between every pair of teams, the bounds on the number of consecutive home (or away) games for each team, that every pair of teams must have played each other in the first half of the season, and so on. Often, there are additional factors to be considered for a particular league, for example, the availability of venues on specific dates, home-game preferences of teams on specific dates, and balancing of schedules so that games between two teams are evenly-spaced throughout the season. In addition to finding a feasible schedule that meets all the timing restrictions, the problem addressed in this paper has the additional complexity of having the objective of minimizing travel costs. We discuss some structural properties of a schedule that meets the timing constraints and present two heuristics for finding a low-cost schedule. The methodology is used to develop an improved schedule for the Texas Baseball League.
Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees
Authors: Fisher Marshall L.
Published: November 2008

We consider the problem of optimally scheduling a fleet of K vehicles to make deliveries to n customers subject to vehicle capacity constraints. Given a graph with n + 1 nodes, a K-tree is defined to be a set of n + K edges that span the graph. We show that the vehicle routing problem can be modeled as the problem of finding a minimum cost K-tree with two K edges incident on the depot and subject to some side constraints that impose vehicle capacity and the requirement that each customer be visited exactly once. The side constraints are dualized to obtain a Lagrangian problem that provides lower bounds in a branch-and-bound algorithm. This algorithm has produced proven optimal solutions for a number of difficult problems, including a well-known problem with 100 customers and several real problems with 25–71 customers.
On the Convergence Rates of IPA and FDC Derivative Estimators
Authors: L'Ecuyer Pierre , Perron Gaétan
Published: November 2008

We show that under the (sufficient) conditions usually given for infinitesimal perturbation analysis (IPA) to apply for derivative estimation, a finite-difference scheme with common random numbers (FDC) has the same order of convergence, namely O(n−1/2), provided that the size of the finite-difference interval converges to zero fast enough. This holds for both one- and two-sided FDC. This also holds for different variants of IPA, such as some versions of smoothed perturbation analysis (SPA), which is based on conditional expectation. Finally, this also holds for the estimation of steady-state performance measures by truncated-horizon estimators, under some ergodicity assumptions. Our developments do not involve monotonicity, but are based on continuity and smoothness. We give examples and numerical illustrations which show that the actual difference in mean square error (MSE) between IPA and FDC is typically negligible. We also obtain the order of convergence of that difference, which is faster than the convergence of the MSE to zero.
Cross Decomposition Applied to Integer Programming Problems: Duality Gaps and Convexification in Parts
Authors: Holmberg Kaj
Published: November 2008

We study the lower bounds on the optimal objective function value of linear pure integer programming problems obtainable by the convexification in parts that results from using Benders' or cross decomposition, and the best lower bounds obtainable by the convexification resulting from Lagrangian relaxation together with subgradient optimization or Dantzig-Wolfe decomposition. A comparison shows that generalized Benders' and generalized cross decomposition yield the best of these bounds, while ordinary Benders' decomposition yields bounds that are sometimes better and sometimes worse than those of Lagrangian relaxation. However, cross decomposition can be used to automatically get the best of the two bounds. The conclusion of this paper is that cross decomposition can be useful for getting good lower bounds for pure integer programming problems, bounds that can be made better than those of the frequently used Lagrangian relaxation.
A Greedy Randomized Adaptive Search Procedure for the Two-Partition Problem
Authors: Laguna Manuel , Feo Thomas A. , Elrod Hal C.
Published: November 2008

We present a greedy randomized adaptive search procedure (GRASP) for the network 2-partition problem. The heuristic is empirically compared with the Kernighan-Lin (K&L) method on a wide range of instances. The GRASP approach dominates K&L with respect to solution value on a large percentage of the instances tested. The ability of GRASP to find optimal solutions is assessed by comparing its performance with a general purpose mixed integer programming package.
Optimal Prices of an M/G/1 Jobshop
Authors: Johansen Søren Glud
Published: November 2008

This paper concerns the optimal control of input to a FIFO jobshop with a single workstation. The input is jobs for which the processing and delivery times are observable upon arrival. The control is exercised by charging a price for each completed job. The objective is either profit maximization or welfare maximization. The semi-Markov decision processes that maximize the two objectives are studied simultaneously. Optimal prices are specified in terms of opportunity costs. The opportunity cost of a job is the expected future loss of earnings caused by having the job submitted to the shop. Results for the cases with and without discounting are established simultaneously by a new approach. It is based on the idea of studying the infinite-horizon model directly and it allows the state space and the decision set to be denumerable. Mild assumptions ensure that the opportunity cost is increasing as a function of the work backlog, and increasing and convex as a function of the processing time.
A Polynomial Algorithm for the Degree-Constrained Minimum K-Tree Problem
Authors: Fisher Marshall L.
Published: November 2008

Given a graph with n + 1 nodes, a K-tree is defined to be a set of n + K edges that span the graph. This paper presents an algorithm for finding a minimum cost K-tree with a specified degree at a designated node. The algorithm runs in O(n3) time and is useful in the optimal solution of certain Lagrangian relaxations arising in vehicle routing.
Using Values in Operations Research
Authors: Keeney Ralph L.
Published: November 2008

Values pervade the field of operations research. Expressed as objectives, goals, criteria, performance measures, and/or objective functions, they are necessary in theoretical operations research models and in applications. Because of their critical role, it is useful to develop these expressions of values from basic principles. This paper outlines how to identify values for a specific decision problem, how to structure these values to facilitate thinking and analysis, and how to quantify values. Since values provide the basis for interest in a problem, these same values should guide all of our effort on that problem. Two important uses of values are to create better alternatives for decision problems and to define decision problems that are more appealing than those that confront us. On another level, the operations researcher's values are crucial in selecting the research and applications that he or she pursues. I illustrate this with a brief summary of a few projects concerning both life-threatening risks and the storage of nuclear waste. The presentation concludes with a challenge to operations researchers to consider devoting some effort and talent to what I think of as the mega-risks facing our country.
A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs
Authors: Fischetti Matteo , Toth Paolo , Vigo Daniele
Published: November 2008

We consider the asymmetric capacitated vehicle routing problem (CVRP), a particular case of the standard asymmetric vehicle routing problem in which only the vehicle capacity constraints are imposed. CVRP is known to be NP-hard and finds practical applications in distribution and scheduling. We describe two new bounding procedures for CVRP, based on the so-called additive approach. Each procedure computes a sequence of nondecreasing lower bounds, obtained by solving different relaxations of CVRP. Effective implementations of the procedures are also outlined which considerably reduce the computational effort. The two procedures are combined into an overall bounding algorithm. A branch-and-bound exact algorithm is then proposed, whose performance is enhanced by means of reduction procedures, dominance criteria, and feasibility checks. Extensive computational results on both real-world and random test problems are presented, showing that the proposed approach favorably compares with previous algorithms from the literature.
Minimizing Transportation and Inventory Costs for Several Products on a Single Link
Authors: Speranza Maria Grazia , Ukovich Walter
Published: November 2008

This paper deals with the problem of determining the frequencies at which several products have to be shipped on a common link to minimize the sum of transportation and inventory costs. A set of feasible shipping frequencies is given. Transportation costs are supposed to be proportional to the number of journeys performed by vehicles of a given capacity. Vehicles may or may not be supposed to carry out completely all materials available, and products assigned to different frequencies may or may not share the same truck. Integer and mixed integer linear programming models are formulated for each of the resulting four situations, and their properties are investigated. In particular, we show that allowing products to be split among several shipping frequencies makes trucks traveling at high frequencies to be filled up completely. In this situation, trucks may always be loaded with products shipped at the same frequency.
The Stability of a Capacitated, Multi-Echelon Production-Inventory System Under a Base-Stock Policy
Authors: Glasserman Paul , Tayur Sridhar
Published: November 2008

Most models of multilevel production and distribution systems assume unlimited production capacity at each site. When capacity limits are introduced, an ineffective policy may lead to increasingly large order backlogs: The stability of the system becomes an issue. In this paper, we examine the stability of a multi-echelon system in which each node has limited production capacity and operates under a base-stock policy. We show that if the mean demand per period is smaller than the capacity at every node, then inventories and backlogs are stable, having a unique stationary distribution to which they converge from all initial states. Under i.i.d. demands we show that the system is a Harris ergodic Markov chain and is thus wide-sense regenerative. Under a slightly stronger condition, inventories return to their target levels infinitely often, with probability one. We discuss cost implications of these results, and give extensions to systems with random lead times and periodic demands.
M/G/1//N Queues with Server Vacations and Exhaustive Service
Authors: Takagi Hideaki
Published: November 2008

Queues with a finite population of customers and occasional periods (called vacations) when the server is unavailable appear in many engineering systems, but have not been studied. In this paper, we specifically consider an M/G/1//N queueing system in which the server takes repeated vacations each time it has emptied the queue, until it finds a customer waiting. For the steady state, we show that performance measures such as the system throughput and mean response time can be obtained from the known analysis of a regenerative cycle of busy and vacation periods. We then study the joint distribution of the server state, the queue size, and the remaining service or vacation time at an arbitrary point in time for certain initial conditions. In the steady state, we explicitly obtain the distributions of the unfinished work, the virtual waiting time, and the real waiting time. The mean response times in several other vacation models are also provided.
Accelerating Procedures of the Value Iteration Algorithm for Discounted Markov Decision Processes, Based on a One-Step Lookahead Analysis
Authors: Herzberg Meir , Yechiali Uri
Published: November 2008

Accelerating procedures for solving discounted Markov decision processes problems are developed based on a one-step lookahead analysis of the value iteration algorithm. We apply the criteria of minimum difference and minimum variance to obtain good adaptive relaxation factors that speed up the convergence of the algorithm. Several problems (including Howard's automobile replacement) are tested and a preliminary numerical evaluation reveals considerable reductions in computation time when compared to existing value iteration schemes.