bluuebunny/crossref_metadata_2025 huggingface dataset:
Using Block Norms for Location Modeling
Authors: Ward James E. , Wendell Richard E.
Published: November 2008

In formulating a continuous location model with facilities represented as points in Rn (e.g., typically in the plane), one must characterize the distance between two points as a function of their coordinates. Two criteria in selecting a distance function are (1) to obtain good approximations of actual distances, and (2) to obtain a mathematical model of the location problem that is easy to solve. In this paper, we show how a class of norms with polygonal contours, called block norms, can yield attractive choices as distance functions with respect to these criteria. In particular, we consider the following relevant properties of block norms: they generalize the concepts of rectilinear or city-block travel; they are dense in the set of all norms; they have interesting travel interpretations; in the plane, they can be expressed as a sum of the absolute values of linear functions; they often give better approximations to actual highway distances than the most frequently used family of norms, the lp norms; and, finally, they yield linear programming formulations of certain facility location problems (i.e., the Weber problem and the Rawls problem).
On Pinedo's Conjecture for Scheduling in a Stochastic Flow Shop
Authors: Suresh S. , Foley R. D. , Dickey S. Elizabeth
Published: November 2008

Pinedo has conjectured that, in a stochastic flow shop with m machines, n − 2 deterministic jobs with unit processing time, and two stochastic jobs each with mean one, the sequence minimizing the expected makespan would schedule one of the stochastic jobs first and the other last. We prove that Pinedo's conjecture is almost true: either Pinedo's sequence or a sequence with the stochastic jobs adjacent at one end of the sequence minimizes the expected makespan. Our result does not require the stochastic jobs to have an expected value of 1, nor even to be independent and identically distributed. We show that our result cannot be improved in the sense that, in some cases, one sequence is strictly optimal, and in some other cases, the other sequence is strictly optimal.
OR Practice—Analysis of the Economic Effect of the Alaskan Oil Export Ban
Authors: Higgins Terrence , Jenkins-Smith Hank C.
Published: November 2008

Analysts in the federal government have repeatedly been drawn into the analytical debate over the merits of the existing ban on crude oil exports. This paper describes the most recent and sophisticated attempt to assess the economic effects of the export ban, employing a large nonlinear programming model of the world oil market. It describes the model, analysis, and analytical results, as well as the authors' perspectives on why the analysis failed to achieve its anticipated objectives. The paper concludes by discussing the implications of the analysis for federal oil export policy, and by considering how the study results could have been made more accessible to federal policy makers.
The Caterer Problem
Authors: Szwarc Wlodzimierz , Posner Marc E.
Published: November 2008

This paper develops a one-pass transportation solution that solves the Caterer Problem with a fixed number of new napkins. It provides conditions for determining when this solution can be improved by changing the number of purchased napkins. This approach leads to a simple method of solving the Caterer Problem by treating the fixed case as a parametric programming problem. The procedure is 0(n2).
Scheduling Jobs with Exponentially Distributed Processing Times and Intree Precedence Constraints on Two Parallel Machines
Authors: Pinedo Michael , Weiss Gideon
Published: November 2008

We consider n jobs with independent exponentially distributed processing times that are to be processed on two machines operating in parallel. The jobs are subject to precedence constraints that have the form of an intree, i.e., each job, except for the last one, has one direct successor. A job is at level l if its successor is at level l − 1 (the last job is at level 0). We assume that all jobs at level l have i.i.d. exponentially distributed processing times, with mean 1/μl. Under these assumptions, we show that the policy that schedules HLF (highest level first) minimizes the expected makespan in the class of preemptive as well as nonpreemptive schedules. This conclusion generalizes a previous result of Chandy and Reynolds.
Technical Note—An Improved Implementation of Conditional Monte Carlo Estimation of Path Lengths in Stochastic Networks
Authors: Kulkarni V. G. , Provan J. S.
Published: November 2008

This note suggests an improvement to the Monte Carlo simulation technique of Sigal, Pritsker and Solberg for estimating the distribution of the shortest/longest path length in a stochastic network. This improvement also applies in network reliability estimation and PERT analysis.
Technical Note—A Note on “Myopic Solutions of Markovian Decision Processes and Stochastic Games”
Authors: Köchel Peter
Published: November 2008

The aim of this note is to correct some oversights in a 1981 paper by M. J. Sobel on myopic policies. We show by example that somewhat stronger assumptions than Sobel's must be imposed on a Markovian decision model to ensure the optimality of myopic policies. We offer alternatives for augmenting or altenng Sobel's assumptions so that they will be sufficient for myopic policies to be optimal from every initial state.
An Asymptotic Analysis of a Queueing System with Markov-Modulated Arrivals
Authors: Burman David Y. , Smith Donald R.
Published: November 2008

We study the mean delay and the mean number in queue in a single-server system whose arrivals are given by a nonhomogeneous Poisson process with rate equal to a function of the state of an independent Markov process. Models of this sort arise naturally in the study of packet arrivals to a local switch. There are, in general, no closed form expressions for these quantities. We consider the normalized delay and the normalized number in queue with respect to the equivalent quantity for an M/M/1 queue with the same arrival and service rates. We show that in light and heavy traffic these quotients converge to finite, nonzero quantities that can be calculated in terms of the original model parameters. When the arrival stream is the superposition of arrival processes, the overall limit is related to the individual limits for each of the separate arrival processes. These results lead to approximations for the mean delay and number in queue for intermediate traffic. We present several examples showing the accuracy of this approximation.
On Johnson's Two-Machine Flow Shop with Random Processing Times
Authors: Ku Peng-Sheng , Niu Shun-Chen
Published: November 2008

A set of n jobs is to be processed by two machines in series that are separated by an infinite waiting room; each job requires a (known) fixed amount of processing from each machine. In a classic paper, Johnson gave a simple rule for ordering of the set of jobs to minimize the time until the system becomes empty, i.e., the makespan. This paper studies a stochastic generalization of this problem in which job processing times are independent random variables. Our main result is a sufficient condition on the processing time distributions that implies that the makespan becomes stochastically smaller when two adjacent jobs in a given job sequence are interchanged. We also give an extension of the main result to job shops.
Short-Term Scheduling of Vessels for Shipping Bulk or Semi-Bulk Commodities Originating in a Single Area
Authors: Ronen David
Published: November 2008

We analyze a single-voyage ship-scheduling problem. A set of ships of different sizes and cost functions must be used to deliver a set of shipments to their destinations. The cost function that is minimized consists of the cost of ships' time and port charges, as this cost applies to the various terms of ships employment. We compare several algorithms for allocating shipments to ships, and achieve substantial cost savings as compared with industry practice. A biased random algorithm provides very good solutions that are close to the optimal ones.
A Debugging Model with Independent Flaws and Random Masking
Authors: Siegrist Kyle
Published: November 2008

A system with a Poisson-distributed number of flaws is undergoing a sequence of trials designed to detect and remove the flaws. On each trial, independently and with probability q, masking occurs that blocks the detection of flaws on that trial. If masking does not occur on a trial then each flaw in the system, independently, is detected with probability p on that trial. Each flaw detected on a trial, independently, is removed with probability r before the next trial. This note derives distributions and measures of quality for this problem.
OR Practice—An Analysis of Baltimore Gas and Electric Company's Technology Choice
Authors: Keeney Ralph L. , Lathrop John F. , Sicherman Alan
Published: November 2008

The Baltimore Gas and Electric Company (BGE) must select a strategy for adding 600 megawatts of electric generating capacity at the Perryman site near Baltimore to come on-line in the 1990s. This paper reports an analysis that evaluates strategies involving either a conventional coal facility or one of three technologies not currently available commercially. A key issue is whether the perceived advantages of the new technologies are worth the risks of not having, the generation capacity early enough to meet load growth. The analysis evaluates strategies using several BGE objectives, including customer cost, shareholder return, corporate image, health and safety, and feasibility. These objectives are combined by means of an evaluation function that uses corporate value tradeoffs, elicited first from analysts in the Generation Planning Unit and then refined in interviews with five BGE senior executives. Uncertainties addressed in the analysis include load growth, time when a new technology becomes available, and construction and licensing delay. The analysis is partially based on preliminary input information, but designed for iterative use incorporating better information. The computer software for the model has been transferred to BGE to be used to provide insights into technology choice problems.
Errata—Correction to “A Queueing System with General-Use and Limited-Use Servers”
Authors: Green Linda
Published: November 2008

Correction to Green, L. 1985. A queueing system with general-use and limited-use servers. Opns. Res. 33 168–182.
Editorial
Authors: Magnanti Thomas L.
Published: November 2008

Editorial.
Deciding Which Queue to Join: Some Counterexamples
Authors: Whitt Ward
Published: November 2008

Consider a queueing system with two or more servers, each with its own queue with infinite capacity. Customers arrive according to some stochastic process (e.g., a Poisson process) and immediately upon arrival must join one of the queues, thereafter to be served on a first-come first-served basis, with no jockeying or defections allowed. The service times are independent and identically distributed with a known distribution. Moreover, the service times are independent of the arrival process and the customer decisions. The only information about the history of the system available for deciding which queue to join is the number of customers currently waiting and being served at each server. Joining the shortest queue is known to minimize each customer's individual expected delay and the long-run average delay per customer when the service-time distribution is exponential or has nondecreasing failure rate. We show that there are service-time distributions for which it is not optimal to always join the shortest queue. We also show that if, in addition, the elapsed service times of customers in service are known, the long-run average delay is not always minimized by customers joining the queue that minimizes their individual expected delays.
Philip McCord Morse (1903–1985)—A Remembrance
Authors: Horvath William J. , Ernst Martin L.
Published: November 2008

Philip M. Morse, friend and mentor of two generations of operations researchers, and first president of the Operations Research Society, died in Concord, Massachusetts, on September 5, 1985. In many ways, Philip Morse was a symbol of operations research over the past four decades.
Optimal Response to Oil Spills: The Strategic Decision Case
Authors: Psaraftis Harilaos N. , Tharakan Geverghese G. , Ceder Avishai
Published: November 2008

In this paper we develop a model for the problem of (a) locating appropriate levels and types of cleanup capability to respond to oil spills and (b) allocating such capability among points of high oil spill potential. The model takes into account frequency of spill occurrence, variability of spill volumes, different cleanup technologies, equipment efficiency and operability, fixed costs to open a facility, equipment acquisition, transportation and operating costs, and costs of damage as functions of spill volume and level of response. The model can also accept policy stipulations on response times. We present an illustrative application of the model in the New England region and discuss its possible uses within existing and alternative policy environments.
Optimal Lot-Sizing Algorithms for Complex Product Structures
Authors: Afentakis Panayotis , Gavish Bezalel
Published: November 2008

Lot sizing of products that have complex bills of materials plays an important role in the efficient operations of modern manufacturing and assembly processes. In this paper we develop algorithms for optimal lot sizing of products with a complex product structure. We convert the classical formulation of the general structure problem into a simple but expanded assembly structure with additional constraints, and solve the transformed problem by a branch-and-bound based procedure. The algorithm uses a Lagrangean relaxation and subgradient optimization procedure to generate tight lower bounds on the optimal solutions. In computational experiments, a code based on this method was able to solve single end product problems with up to 40 stages in the product structure. The model is extended to handle problems with multi-end items in the product structure, but with less favorable computational results.
An N-Server Cutoff Priority Queue
Authors: Schaack Christian , Larson Richard C.
Published: November 2008

We consider a multi-priority, nonpreemptive, multi-server queueing system, with Poisson arrivals and negative exponential service times. In order to save available servers for higher priority customers, the system deliberately queues arriving lower priority customers whenever the number of busy servers equals or exceeds a given priority-dependent cutoff number. A queued, priority i customer enters service the instant there are fewer than the respective cutoff number of servers busy and all higher priority queues are empty. We derive several performance measures for the waiting time of the ith priority class: its mean, its second moment, and its distribution (in transforms). We also extend the analysis to systems in which any subset of priority levels may overflow to some other system rather than join infinite capacity queues.
The Bulk Service Queue with a General Control Strategy: Theoretical Analysis and a New Computational Procedure
Authors: Powell Warren B. , Humblet Pierre
Published: November 2008

This paper develops a general framework for analyzing a wide class of vehicle dispatching strategies for bulk arrival, bulk service queues. We provide a simple derivation of the queue length transform for the embedded Markov chain, and present a new computational procedure for finding the moments of the queue length distribution. Extensive computational tests demonstrate that the new procedure is significantly faster and more stable than the standard method, from the literature, that requires solving a set of simultaneous linear equations. We give formulas for the mean and variance of the length of the queue for the general case of compound Poisson arrivals, random batch capacities, general service times and a general control strategy.
Cycle Times in Two-Stage Closed Queueing Networks: Applications to Multiprogrammed Computer Systems with Virtual Memory
Authors: Daduna Hans
Published: November 2008

We compute the distribution of the time for a sequence of successive cycles in a two-stage exponential queue which represents a multiprogrammed computer system.
Comments on “On Normalizing Constants in Queueing Networks” by P. G. Harrison
Authors: Koenigsberg Ernest
Published: November 2008

Comments on Harrison, P. G. 1985. On normalizing constants in queueing networks. Opns. Res. 33 464–468.
A Bank Asset and Liability Management Model
Authors: Kusy M. I. , Ziemba W. T.
Published: November 2008

In managing its assets and liabilities in light of uncertainties in cash flows, cost of funds and return on investments, a bank must determine its optimal trade-off between risk, return and liquidity. In this paper we develop a multiperiod stochastic linear programming model (ALM) that includes the essential institutional, legal, financial, and bank-related policy considerations, and their uncertainties, yet is computationally tractable for realistically sized problems. A version of the model was developed for the Vancouver City Savings Credit Union for a 5-year planning period. The results indicate that ALM is theoretically and operationally superior to a corresponding deterministic linear programming model, and that the effort required for the implementation of ALM, and its computational requirements, are comparable to those of the deterministic model. Moreover, the qualitative and quantitative characteristics of the solutions are sensitive to the model's stochastic elements, such as the asymmetry of cash flow distributions. We also compare ALM with the stochastic decision tree (SDT) model developed by S. P. Bradley and D. B. Crane. ALM is computationally more tractable on realistically sized problems than SDT, and simulation results indicate that ALM generates superior policies.
An Algorithm to Compute the Equilibrium Distribution of a One-Dimensional Bounded Random Walk
Authors: Fryer M. J. , Winsten C. B.
Published: November 2008

We present an algorithm that is suitable for finding the equilibrium distribution of a one-dimensional random walk in the presence of one or more boundaries. The method involves the evaluation of a “reduced” difference equation whose coefficients are found to have the very useful property of being insensitive to small changes in the parameters of the random walk and to rounding errors in the computation.
Two-Stage Cyclic Queues with Nonexponential Servers: Steady-State and Cyclic Time
Authors: Daduna Hans
Published: November 2008

We consider a closed two-stage cyclic queueing model for a multiprogrammed computer system. Assuming one general server and one server whose service time distribution is a mixture of Erlang distributions, we compute both the steady-state distribution at departure points and the Laplace-Stieltjes transform of the cycle time, given the state of system at the beginning of the cycle. We also find delay time and cycle time distributions for systems both in and out of equilibrium.
Scheduling Cyclic Production on Several Identical Machines
Authors: Maxwell W. L. , Singh H.
Published: November 2008

This paper considers problems that arise in scheduling cyclic production of different parts on several identical machines where the cycle times are of the form kiw, with i varying only with each part. First we derive a simple necessary and sufficient condition for scheduling one machine when the production times of all jobs are identical. Then we describe three conditions, any one of which ensures that if a feasible schedule on M machines exists, then a schedule also exists in which each part always executes on the same machine. These conditions can be used to motivate heuristics to address the scheduling problem.
Consistency of the Disaggregation Process in Hierarchical Planning
Authors: Erschler J. , Fontan G. , Merce C.
Published: November 2008

This paper deals with the planning process of a manufacturing system in which the aggregation of products sharing similar characteristics leads to a hierarchical structure. It gives special attention to the consistency of decisions in a two-level structure, and presents necessary and sufficient conditions for consistency of a disaggregation procedure. Using a subset of these conditions improves upon the disaggregation procedure proposed by Bitran and Hax (Bitran, G. R., A. C. Hax. 1981. Disaggregation and resource allocation using convex knapsack problems with bounded variables. Mgmt. Sci. 27 431–441.).
An Optimal Selection Problem for a Sequence with a Random Number of Applicants Per Period
Authors: Nakai Tōru
Published: November 2008

In the classical secretary problem, an employer interviews and rates applicants one at a time, and wants to stop at an optimal applicant. Such optimal stopping problems also arise in the selection of projects, military targets, and resource alternatives. We consider a generalization of this optimal stopping problem in which the employer wishes to hire a certain number of applicants, the total number of applicants is known, and the number of applicants per day is random. We also treat a variation in which a random number of applicants arrive randomly over time. We derive several properties of the optimal policy and the total expected reward obtainable from this policy. For an optimal policy, in order for an applicant to be selected by the decision maker, the applicant's value must be large in absolute magnitude and be high from among all the applicants.
OR Practice—Computer-Based Models for Policy Making: Uses and Impacts in the U.S. Federal Government
Authors: Kraemer Kenneth L. , King John Leslie
Published: November 2008

This paper examines factors influencing implementation and use of computer models that have been successfully institutionalized as part of federal policy-making. It is based upon detailed case studies of two kinds of models that have been widely assimilated and used in federal agencies—microanalytic simulation models and macroeconomic models. It concludes that the most important influences on successful modeling are the means to do modeling (supply factors) and the desire of bureaucrats and politicians to use model-generated information (demand factors). Of these, demand factors are most important. The availability and promotion of computer models alone is insufficient to generate use, whereas their political saliency is critical. Thus, where the means to do modeling are weak, but the desire to use models is strong, government agencies invest heavily in the creation of new modeling efforts.
Efficiency Analysis for Exogenously Fixed Inputs and Outputs
Authors: Banker Rajiv D. , Morey Richard C.
Published: November 2008

We evaluate, by means of mathematical programming formulations, the relative technical and scale efficiencies of decision making units (DMUs) when some of the inputs or outputs are exogenously fixed and beyond the discretionary control of DMU managers. This approach further develops the work on efficiency evaluation and on estimation of efficient production frontiers known as data envelopment analysis (DEA). We also employ the model to provide efficient input and output targets for DMU managers in a way that specifically accounts for the fixed nature of some of the inputs or outputs. We illustrate the approach, using real data, for a network of fast food restaurants.
Optimal Design of Systems Subject to Two Types of Error
Authors: Assaf David , Ben-Dov Yosi , Krieger Abba M.
Published: November 2008

We consider systems such as relay circuits or juries that are composed of components, e.g., relays or jury votes. Each component is in one of two states, with probabilities that depend on the qualities of the components and the requests made of the system. The problem is to construct the system (i.e., determine the configurations of the components for which the system is in each of the two states) in a way that minimizes the probabilities of errors. We find conditions on the probabilities for which the optimal system is monotone or k out of n. We further study these conditions when the components behave independently.
Resource-Constrained Assignment Scheduling
Authors: Mazzola Joseph B. , Neebe Alan W.
Published: November 2008

Many resource-constrained assignment scheduling problems can be modeled as 0-1 assignment problems with side constraints (APSC). Unlike the well-known assignment problem of linear programming, APSC is NP-complete. In this paper we define a branch-and-bound algorithm for solving APSC to optimality. The algorithm employs a depth-first, polychotomous branching strategy in conjunction with a bounding procedure that utilizes subgradient optimization. We also define a heuristic procedure for obtaining approximate solutions to APSC. The heuristic uses subgradient optimization to guide the search for a good solution as well as to provide a bound on solution quality. We present computational experience with both procedures, applied to over 400 test problems. The algorithm is demonstrated to be effective across three different classes of resource-constrained assignment scheduling problems. The heuristic generates solutions for these problems that are, on average, within 0.8% of optimality.
Technical Note—On the Weighted Selection Algorithm for Certain Linear Programs with Nested Constraint Coefficients
Authors: Erenguc S. Selcuk , Benson Harold P.
Published: November 2008

Recently, B. Faaland has developed a weighted selection algorithm for certain linear programming problems with nested constraint coefficients. The purpose of this note is to present a direct, concise proof of validity of Faaland's weighted selection algorithm that does not use graph theory or duality theory.
Nonlinear Network Programming on Vector Supercomputers: A Study on the CRAY X-MP
Authors: Zenios Stavros A. , Mulvey John M.
Published: November 2008

The parallelism built into vector supercomputers raises several challenging issues for designers of optimization algorithms. We survey recent trends in parallel computer systems and study the impact of vector computing on nonlinear network programming. We propose a general framework for migrating fortran optimization software to a vector computer, and apply it in the context of two nonlinear network codes: NLPNETG, based on the primal truncated Newton algorithm, and GNSD, based on the simplicial decomposition method. We include computational experiments on a CRAY X-MP/24 system that tested the nonlinear network codes and compared the results with those of MINOS, a general purpose optimizer. Our experience indicates that vectorized codes can achieve significant improvements in performance (as much as 80% for primal truncated Newton), but achieve only modest improvements (15% for simplicial decomposition) for other algorithms.
Solving Nonlinear Single-Facility Network Location Problems
Authors: Hooker John
Published: November 2008

We present a general approach to solving nonlinear single-facility network location problems. We assume that cost is any convex function of distances, and solve this class of problem by solving convex subproblems on “treelike segments” into which the network is decomposed. We show that only a fraction of treelike segments generally need be examined, and that our method results in a reasonably efficient general-purpose algorithm. The algorithm is particularly effective on real-world (as opposed to random) networks, and when the cost function is nondecreasing and “semiseparable,” as are many popular cost functions. Finally, we describe theoretical complexity bounds and computational experience.
OR Forum—Perspectives on Vehicle Routing: Exciting New Developments
Authors: Golden Bruce L. , Assad Arjang A.
Published: November 2008

This article discusses the substantial recent progress made by researchers and practitioners in the field of computer-assisted vehicle routing. We focus on advances in routing methodology and the uses of this new technology in concrete practical environments. In particular, we discuss successful implementations, advances in model realism, and new algorithmic techniques, and we speculate on the future of this field.
OR Practice—Lagrangian Relaxation for Testing Infeasibility in VLSI Routing
Authors: Feo Thomas A. , Hochbaum Dorit S.
Published: November 2008

We present a technique for very large scale integrated (VLSI) circuit design that recognizes the infeasibility of connecting pairs of terminals on modules placed on a chip. The method is based on a novel application of Lagrangian relaxation. Positive empirical results obtained from difficult problems found both in the literature and in industry strongly support the usefulness of this method. It has been incorporated in the proprietary computer-aided integrated circuit design package used at Bell Communications Research Inc., that allows systems engineers to design integrated circuits independent of the manufacturing processes specified by the foundries making the chips. The method has resulted in a faster turnaround time in the Bell design process.
Socially Optimal Job Search and Its Inducement
Authors: Bernhardt Irwin , Gerchak Yigal
Published: November 2008

The level of effort in searching for a job has two dimensions: intensity and duration. We derive socially optimal intensities and reservation wages that determine the probability distribution of duration. The social optimum reflects the effect one person's productivity has on others' incomes. We show the need for subsidies that reduce the cost of search to the searcher, since financial support alone will not yield optimal effort. Governments now use certain search subsidies such as free counseling, but do not integrate them with financial support. Our results imply that integration is required for optimality. We also derive certain properties of optimal support and subsidies.
Evaluating Influence Diagrams
Authors: Shachter Ross D.
Published: November 2008

An influence diagram is a graphical structure for modeling uncertain variables and decisions and explicitly revealing probabilistic dependence and the flow of information. It is an intuitive framework in which to formulate problems as perceived by decision makers and to incorporate the knowledge of experts. At the same time, it is a precise description of information that can be stored and manipulated by a computer. We develop an algorithm that can evaluate any well-formed influence diagram and determine the optimal policy for its decisions. Since the diagram can be analyzed directly, there is no need to construct other representations such as a decision tree. As a result, the analysis can be performed using the decision maker's perspective on the problem. Questions of sensitivity and the value of information are natural and easily posed. Modifications to the model suggested by such analyses can be made directly to the problem formulation, and then evaluated directly.
Technical Note—A Dual Machine Replacement Model: A Note on Planning Horizon Procedures for Machine Replacements
Authors: Goldstein T. , Ladany S. P. , Mehrez A.
Published: November 2008

This note extends the work of S. Sethi and S. Chand, who considered a dual machine replacement model in an improving technological environment over time. The model covers cases in which the two machines are of different technology as measured by their investment and operating costs. Under fairly general conditions, we suggest a procedure to solve the infinite horizon problem and find the properties of the optimal solution. A numerical example illustrates the procedure.
Technical Note—A Dominance Theorem for the Stochastic Queue Median Problem
Authors: Chiu Samuel S.
Published: November 2008

In this note we prove a dominance property of the set of Hakimi medians for the Stochastic Queue Median (SQM) problem on a network. The SQM minimizes the average response time of a mobile server to a random request for service which occurs in accordance with independent Poisson processes from nodes of a network. We constructively find two strictly positive ranges of the Poisson arrival rate over which a subset of the Hakimi medians will dominate all other locations on the network. These ranges are at the extremes of the arrival rates in which the SQM problem is feasible. Specifically, these intervals are server utilization ranges covering zero and one, respectively.
A Modular Approach to Optimal Multiple-Shift Manpower Scheduling
Authors: Burns R. N. , Koop G. J.
Published: November 2008

This paper introduces a practical approach to multiple-shift manpower scheduling by presenting an algorithm that applies the approach to a large and common class of problems. The algorithm constructs schedules that utilize no more than the minimum number of workers necessary for a schedule satisfying constraints that include two offdays each week, a specified number of offweekends in any fixed number of consecutive weekends, a maximum of six consecutive work shifts and different staffing demands for each type of shift. We discuss the application of the approach to several other classes of manpower scheduling problems.
Deterministic and Random Single Machine Sequencing with Variance Minimization
Authors: Vani Vina , Raghavachari M.
Published: November 2008

We discuss the problem of scheduling several jobs on a single machine so as to minimize the variance of the jobs' completion times. By exploiting the well-known pooled variance formula, we obtain a general formula for the change in variance due to the interchange of two specified jobs whose positions have not been fixed in the sequence. This result permits us to obtain explicit optimal sequences for problems with 6 or 7 jobs, and to show that Schrage's conjecture on positioning the job with the third largest processing time is true for problems with up to 18 jobs. We then develop a heuristic procedure based on a variance interchange formula and compare it with other known heuristic methods. We also consider a problem never before examined, namely, the case when processing times are not known deterministically but are random variables. We obtain some general results, under certain assumptions on the parameters of the distributions of processing times, and extend to the random situation many results applicable to the deterministic case. Finally, we give some results for the exponential distribution of processing times.
Prison Populations: A Projection Model
Authors: Barnett Arnold
Published: November 2008

We propose a method for estimating prison populations under a variety of assumptions about sentencing policy and demographic structure. The approach builds on a familiar stochastic model of the individual criminal career. After a validation exercise involving Pennsylvania data, we use the model to make illustrative projections about Massachusetts, Utah and Florida. The results suggest that, while prison populations might stabilize everywhere during the early 1990s, only rarely will this situation signify an end to the growth in prison-capacity requirements.
OR Practice—Computerized Vehicle Routing in the Soft Drink Industry
Authors: Golden Bruce L. , Wasil Edward A.
Published: November 2008

This paper examines the use of microcomputer-based vehicle routing software in the soft drink industry. In general, the construction of vehicle routes is a complicated task due to the size of the fleet, the number of customers, difficult real-world constraints, and the fact that such routes must be constructed in a relatively short period of time. In the past several years, microcomputers have become more powerful and less expensive, thus enhancing their attractiveness to potential users. Not surprisingly, the marketplace has witnessed rapid growth in the number of vehicle routing packages that are commercially available. In this paper, we review some of the critical vehicle routing issues in the soft drink industry and present several case studies that highlight the ways in which software packages have been able to cope with these concerns and other industry-related problems. The case studies focus on the interfacility transfer of soft drink products, the delivery of products that have been ordered in advance by customers, and the delivery of soft drink products that are sold by drivers to customers.
An Efficient Geometric Solution to the Minimum Spanning Circle Problem
Authors: Oommen B. John
Published: November 2008

We consider the century-old problem of finding the minimum spanning circle (MSC) of N points in the plane. We propose a computational scheme that incorporates the ideas that motivate three of the best-known primal feasible algorithms. The technique converges in finite time and is extremely fast. In all our experiments that involved digitized and random data, without even a rare exception, the technique converged in exactly two iterations. We conjecture that the algorithm, which is purely geometric, has a linear time complexity.
Modeling a Class of Flexible Manufacturing Systems with Reversible Routing
Authors: Yao David D. , Buzacott J. A.
Published: November 2008

We model a flexible manufacturing system (FMS) as a closed queueing network with a set of stations, each with a local buffer of limited capacity. Based on the theory of reversibility as well as some known approaches in the studies of queueing networks with finite buffers, we derive product-form solutions to a class of such FMS networks that have reversible parts routing (a system with a centralized material handling station being one example). This class also includes a certain type of dynamic routing scheme. For systems with zero-buffer stations, we show that the solutions have product form even for nonexponential processing times.
The Role of External Search in Bilateral Bargaining
Authors: Chikte Shirish D. , Deshmukh Sudhakar D.
Published: November 2008

We consider the problem of bargaining between two individuals who can also search for possible alternatives to each other's offers. We explicitly incorporate the search activity into the process of bargaining: a disagreement in bargaining will lead each individual to search for an outside offer in the hope of improving his future bargaining position and attaining a more favorable outcome. We model the interlaced phases of bargaining and search over time as an extensive noncooperative game. We characterize the associated subgame-perfect equilibrium outcome and strategies. Finally, we show that superior search ability yields an individual a more favorable outcome and hence represents a greater bargaining strength.
OR Forum—Presidents' Symposium: Science and Professionalism in Operations Research
Authors: Miser Hugh J.
Published: November 2008

This note draws attention to some aspects of the early work of operations research and to some modern concepts of science and professionalism as a basis for suggesting some things the operations research community should do to strengthen its future.
OR Forum—President's Symposium: A Perspective on the Future of Operations Research
Authors: Gass Saul I.
Published: November 2008

Will operations research be “the same yesterday, and to day, and for ever?” (Hebrews 13:8). Taking the past success of OR as their point of departure, these comments view its future as hinging on aspects of professionalism: identification, standards of quality, outreach to new areas of social concern, and a critical study of its own work and approaches.
A Convergent Interactive Cutting-Plane Algorithm for Multiobjective Optimization
Authors: Loganathan G. V. , Sherali Hanif D.
Published: November 2008

This paper presents an interactive cutting-plane algorithm for determining a best-compromise solution to a multiobjective optimization problem in situations with an implicitly defined utility function. We derive cutting planes that are based on suitable pairwise trade-offs between the objective functions, as prescribed by the decision maker at each iterate generated by the algorithm. The proposed algorithm requires no line searches, and generates iterates that are all contained in the efficient frontier. This feature facilitates the preference judgment of the decision maker, and permits an analyst to terminate short of optimality with an efficient near-optimal solution. A convergence analysis establishes that any accumulation point generated by the algorithm is a best-compromise solution. We also conduct an error analysis to point out the effect of inconsistencies in trade-off information provided by the decision maker. The algorithm may be extended to situations involving nonconvex feasible regions, as well as nonconcave (for a max problem) objective functions. We offer remarks for such cases, and describe an application to an urban runoff control-design problem.
Scheduling Tasks with Due Dates in a Fabrication/Assembly Process
Authors: Faaland Bruce , Schmitt Tom
Published: November 2008

In fabrication and assembly processes, end-product due dates play a significant role in scheduling tasks to minimize earliness and lateness penalties. We develop a heuristic technique for this problem that solves a sequence of maximum flow problems to identify improved schedules. This method compares favorably with finite loading, another scheduling heuristic. Our computational results include the solution of a problem involving 26,100 tasks scheduled on 52 work centers.
An Algorithmic Aid for Intensity Measures of Consumer Preference
Authors: Pasumarty K. , Karney D. F. , Morley T. D.
Published: November 2008

Recently, J. R. Hauser and S. M. Shugan, and K. Pasumarty, have used constant-sum paired comparisons to estimate the intensity of consumer preferences for various products. Both studies use the consumer's responses to determine whether his/her preference function is ratio, interval or ordinal in nature. This determination involves performing a statistical analysis based upon the experimental design matrix, M, which identifies the various transitivity tests designed into the experiment, and upon a companion matrix, W. Unfortunately, both studies generated W by means of exhaustive enumeration, a costly computational technique. In this paper, we propose an algorithm that generates the matrix W cheaply and efficiently. The algorithm is based in part upon modular arithmetic and a technique developed by R. J. Duffin and T. D. Morley for meshing electrical networks. When implemented on a Zenith 150 personal computer, the proposed algorithm found W, for the examples given in both Hauser and Shugan and Pasumarty, in a fraction of the time (at most 0.032) required by exhaustive enumeration. We also show that even when W is not unique, the statistical measurements that utilize W are.
OR Practice—The Status of Nonlinear Programming Software: An Update
Authors: Waren Allan D. , Hung Ming S. , Lasdon Leon S.
Published: November 2008

This paper reports on progress in nonlinear programming software since 1979. Developments in the computer industry have had a significant impact on the design of mathematical software and the expectations of users. Microcomputers in particular are changing the software industry to an extent that was not anticipated in the last survey. Continuing refinements in NLP algorithms have enabled users to solve larger and more complicated problems, even some with integer variables. Modeling systems with nonlinear programming capabilities have now become available. Interest and improvements in computational experimentation have increased the rigor and objectivity of studies assessing software quality. This report surveys these important developments and speculates on the future.
The Break-Bulk Role of Terminals in Many-to-Many Logistic Networks
Authors: Daganzo Carlos F.
Published: November 2008

This paper examines the structure of many-to-many logistics networks. Using as little data as possible, it attempts to answer macroscopic questions such as: How many terminals should be used? Should they be used at all? What should be the frequency of service? Although such a problem could be formulated with a large number of parameters and data, we show that near-optimal network structures can be characterized by two dimensionless constants which can be determined from the data (e.g., from the value of the items carried, the number of origins, the size of the service region, etc …). The number of stops made by vehicles, for example, is proportional to powers of the dimensionless constants, the powers depending on the number of transhipments allowed. Similar expressions are given for other network descriptors and for the resulting cost. The simple formulas and principles embodied in the paper can lead to quick cost estimates and rough design plans, with a minimum of data, that can be fine-tuned with existing tools. We also highlight the difference between many-to-many and one-to-many (or many-to-one) networks: we describe the (break-bulk) role of terminals as swapping points, and quantify the benefits and disadvantages of routing vehicles through a terminal that lies in their desired general direction of travel.
Simple Inequalities for the D/G/1 Queue
Authors: Ott Teunis J.
Published: November 2008

During the last quarter century a large number of papers, starting in 1962 with J. F. C. Kingman, have been written about inequalities for queues. Their objective has been to eliminate the need for detailed distributional analysis by providing upper and lower bounds for such entities as the expected waiting time and the probability of no waiting. Notable results include Kingman's upper bound for the expected waiting time in a GI/G/1 queue and K. T. Marshall's lower bound for the expected waiting time in a D/G/1 queue. In this paper we present a new method for obtaining bounds for the stationary D/G/1 queue. The basic idea is to translate crude bounds on the probability that the system is empty at time t into sharp bounds for the expected waiting time. The crudest possible bounds on the probability that the system is empty at time t reproduce the Kingman upper bound and the Marshall lower bound, and show that the Marshall lower bound is tight for the D/G/1 queue and is attained if and only if the service times are integer (random) multiples of the interarrival time.
Correlated Simulation Experiments in First-Order Response Surface Design
Authors: Hussey James R. , Myers Raymond H. , Houck Ernest C.
Published: November 2008

The collection of mathematical models, experimental strategies, and statistical inference referred to as response surface methodology (RSM) has been used in the empirical exploration of a wide variety of systems, particularly industrial situations in which a large number of variables influence the system response of interest. This paper examines experimental strategies for implementing RSM procedures in a simulation environment. Of particular interest is the question of how to best assign the pseudorandom number streams that drive the simulation to the experimental points when the objective is to estimate a first-order response surface model. We present general results for factorial and fractional-factorial plans where each factor is present at two levels. For this class of response surface designs, we consider three strategies for the assignment of pseudorandom number streams to experimental points: (i) the use of a unique set of streams at each design point; (ii) the assignment of a common set of streams to all experiments; and (iii) the simultaneous use of common and antithetic stream sets by the use of design blocking. We base our analysis of these correlation induction strategies on variance criteria commonly employed in response surface design, including: generalized variance, prediction variance, integrated variance, and variance of slopes. Our findings show that the simultaneous use of common and antithetic stream sets is the preferred correlation induction strategy, but that no one assignment procedure is uniformly superior for all four criteria. Our results provide a basis for selecting among the three correlation induction strategies.