bluuebunny/crossref_metadata_2025 huggingface dataset:
Technical Note—An Efficient Approach to Some Cases of Coefficient Variations in Linear Programs
Authors: Weintraub Andrés , Ingram William
Published: November 2008

In some cases, a series of linear programs are run in sequence where a set of coefficients in the constraint matrix or in the right hand side is varied in such a way that inequality constraints are relaxed from one run to the next. For this type of variation we present an algorithm that determines in at most K pivots a new feasible solution, if K coefficients are varied. This algorithm relies on post optimality options of linear programming packages. In addition the algorithm proved to be advantageous in determining optimal solutions to the modified problems.
A Mixed-Integer Goal Programming Model for Nursing Service Budgeting
Authors: Trivedi Vandankumar M.
Published: November 2008

This paper presents a mixed-integer goal programming model for expense budgeting in a hospital nursing department. The model incorporates several different objectives based upon such considerations as cost containment and providing appropriate nursing hours for delivering quality nursing care. Also considered are possible trade-offs among full-time, part-time and overtime nurses on weekdays as well as weekends. The budget includes vacation, sick leave, holiday, and seniority policies of a hospital and various constraints on a hospital nursing service imposed by nursing unions. The results are based upon data from a study hospital and indicate that the model is practical for budgeting in a hospital nursing department.
Dynamic Equilibrium Energy Modeling: The Canadian BALANCE Model
Authors: Daniel Terrence E. , Goldberg Henry M.
Published: November 2008

We discuss the development and structure of the University of Alberta BALANCE model of Canadian energy supply and demand. The model is a multi-time-period linear programming formulation of Canadian energy supply integrated with a large econometric model of price-sensitive energy demands in the Canadian economy. The model finds an equilibrium set of prices, supplies and demands over all time periods using a new dynamic version of the equilibrium-seeking algorithm developed for the Project Independence Evaluation System. The special aspects of a dynamic model and equilibration are described. An example illustrating the convergence properties of the algorithm is given. Finally, the question of whether or not to increase Canadian natural gas exports to the United States is examined using the model.
Technical Note—A Note on the M/M/1 Queue with λ = μ
Authors: Roque Diego R.
Published: November 2008

The simplest Markovian queue where the arrival rate equals the service rate (λ = μ) has been successfully treated using a diffusion approximation that assumes a continuous state space in continuous time. Here it is shown that an intuitively appealing approach using a simple restricted random walk with a discrete state space in discrete time yields the same results.
Errata
Authors: Kao Edward P. C.
Published: November 2008

Erratum to Kao, E. P. C. 1978. A preference order dynamic program of a stochastic traveling salesman problem. Opns. Res. 26 1033–1045.
Letter to the Editor—Logical Translation of English
Authors: Gilmore John W.
Published: November 2008

No abstract available.

Operations Research, ISSN 0030-364X, was published as Journal of the Operations Research Society of America from 1952 to 1955 under ISSN 0096-3984.
The Influence of Vehicular Speed and Spacing on Tunnel Capacity
Authors: Olcott Edward S.
Published: November 2008

In the flow of traffic through vehicular tunnels, it is shown that an approximate linear relationship between speed and density of traffic exists, whereby, as the average speeds of vehicles increase, the density of the traffic stream decreases. The relationship is used to establish a series of theoretical equations that, in turn, permit the determination of optimum conditions of speed and spacing required to produce maximum volumes under given conditions of traffic composition. The significance of uniform speeds and spacings in moving large volumes of traffic, which is disclosed in this study, has been clearly recognized in practice. In the Lincoln Tunnel in New York City, the Port Authority has established minimum speed limits, banned slow under-powered trucks from the tunnel, and erected a number of signs to influence motorists to maintain a specified distance behind preceding vehicles. All of these traffic control devices are directed toward an optimizing of vehicular speeds and spacings, and have resulted in significant increases in maximum hourly traffic volumes accommodated by the tunnel.

Operations Research, ISSN 0030-364X, was published as Journal of the Operations Research Society of America from 1952 to 1955 under ISSN 0096-3984.
Terminal Ballistics
Authors: Steinhardt Jacinto
Published: November 2008

Address of the Retiring President of the Operations Research Society of America at the Third Annual Meeting, New York, June 3, 1955.

Operations Research, ISSN 0030-364X, was published as Journal of the Operations Research Society of America from 1952 to 1955 under ISSN 0096-3984.
Letter to the Editor—A Note on the Numerical Evaluation of Certain Probability Integrals
Authors: Kelso John M.
Published: November 2008

No abstract available.

Operations Research, ISSN 0030-364X, was published as Journal of the Operations Research Society of America from 1952 to 1955 under ISSN 0096-3984.
Cost-Effectiveness Analysis for Strategic Decisions
Authors: Foster Richard B. , Hoeber Francis P.
Published: November 2008

No abstract available.

Operations Research, ISSN 0030-364X, was published as Journal of the Operations Research Society of America from 1952 to 1955 under ISSN 0096-3984.
Letter to the Editor—Further Remarks on the Direct Use of Extremal Principles in Solving Certain Optimizing Problems Involving Inequalities
Authors: Klein B.
Published: November 2008

In reply to a recent commentary on the paper, “Direct Use of Extremal Principles in Solving Certain Optimizing Problems Involving Inequalities,” which appeared in the May, 1955 issue of this Journal (p. 168), the author wishes to make some remarks.

Operations Research, ISSN 0030-364X, was published as Journal of the Operations Research Society of America from 1952 to 1955 under ISSN 0096-3984.
Minimizing the Expected Makespan in Stochastic Flow Shops
Authors: Pinedo Michael
Published: November 2008

The optimization problem of minimizing the completion time in permutation flow shop scheduling is considered under the assumption that the processing times of a job on different machines are independent and identically distributed random variables. Models with and without intermediate storage are considered. Solutions for special cases are found and based on these results a more general rule of thumb is obtained.
A Single Server Queueing System Working under Mixed Priority Disciplines
Authors: Adiri I. , Domb I.
Published: November 2008

A single server dispenses service to m priority classes of customers. The arrival process of the ith class, i = 1, 2, …, m, is a homogeneous Poisson distribution. Service times of each class are independent identical arbitrarily distributed random variables with a finite second moment. The smaller the index of a class, the higher its priority degree. For i < j, class i has preemptive priority over j if and only if (iff) j − i > d, and nonpreemptive priority otherwise, where d is a predetermined non-negative integer. Within each priority class the FIFO service rule is obeyed. Setup activities take place before starting or resuming service. An interrupted service is resumed when the system contains no customers with preemptive priority. The preemptive regimes considered are resume and repeat with and without resampling. For each of the mixed disciplines the steady state Laplace-Stieltjes transforms and the expectations of the waiting time and the time in the system are calculated for a k customer (k = 1, 2, …, m). Guidelines for minimization of the system's expected operating cost per unit time with respect to d and to the priority assignment, are discussed. Results are illustrated by a numerical example.
Optimal Performance of Inverted Files
Authors: Hoffer Jeffrey A. , Kovacevic Antonio
Published: November 2008

Many managerial users of information systems require access to data based upon nonunique data record qualifications or classifications. A class of computer file organizations, called inverted files, has been devised to efficiently support such data retrieval. Fundamental to the use of such a file or database organization is the selection of data elements or keys for creation of nonunique key indexes. These indexes provide rapid access to data records which are qualified by logical key expressions. This paper formulates this selection problem as a zero-one, nonlinear programming problem with constraints and describes an optimization algorithm. The model recognizes both known and ad hoc uses of data; complex, Boolean key queries; and index storage capacity and query response time constraints. Computational experience is similar to previous algorithms, which consider more restricted problem formulations.
Bivariate Gamma Random Vectors
Authors: Schmeiser Bruce W. , Lal Ram
Published: November 2008

A seven-parameter family of bivariate probability distributions is developed which allows for any gamma marginal distributions, any associated correlation (positive or negative), and a range of regression curves. The form of the family, which relies on the reproducibility property of the gamma distribution, is motivated by the search for tractable parameter estimation, general dependency structure, and straightforward computer sampling for simulation modeling. A modification with closed-form parameter estimation, but less general dependency structure, is also given. Finally, the use of these distributions in the form of first order autoregressive time series is discussed.
On Dynamic Programming Methods for Assembly Line Balancing
Authors: Kao Edward P. C. , Queyranne Maurice
Published: November 2008

Two dynamic programming approaches for treating sequencing problems—one proposed by Schrage and Baker and the other by Lawler—are discussed in the context of an assembly line balancing problem. A variant of the Schrage-Baker method is proposed to extend its range of applicability. The three approaches are compared using randomly generated test problems. We find that Lawler's “reaching”-based approach is superior to the other two “pulling”-based alternatives in both time and storage requirements. Based on the empirical results, we present time and space estimates for solving problems of different sizes and order strengths, and discuss the relative merits of the three procedures.
Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem
Authors: Panwalkar S. S. , Smith M. L. , Seidmann A.
Published: November 2008

We consider an n job, one machine scheduling problem in which all jobs have a common due date. The objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. This penalty function is based on the due date value and on the earliness or the lateness of each job in the selected sequence. We present a polynomial bound scheduling algorithm for the solution of this problem along with the proof of optimality, a numerical example and discuss some extensions.
Coupled Successive Approximations for Markov Programs
Authors: Fox Bennett L.
Published: November 2008

Each Markov program corresponds to a pair of linear programs. Constructing successive approximations for the primal and dual variables that are respectively decreasing and increasing allows a mutual stopping criterion based on LP duality. This assumes that ordinary successive approximations have determined an optimal or ϵ-optimal policy but not its value function (exactly). The dual variables approximated are those corresponding to the policy used. In this sense, the dual-variable approximation scheme is piggybacked onto the primal-variable approximation scheme. In another sense, the two schemes are coupled by the reciprocal termination criterion that determines when to stop refining the estimates of both the primal and dual variables.
A Comparison Between Tandem Queues with Dependent and Independent Service Times
Authors: Pinedo Michael , Wolff Ronald W.
Published: November 2008

This paper considers tandem queues in which a given customer has equal service times at each station. The case M/M/1 → M/1 is considered in detail and the expected waiting time in the case where any given customer has independent service times at the two stations is compared with the expected waiting time in the case where any given customer has equal service times at the two stations. This comparison is based on theoretical results as well as on simulation. Tandem queues with blocking (zero queue capacity between the stations) are also considered and the waiting time and system capacity in the case where any given customer has independent service times are compared with the waiting time and system capacity in the case where any given customer has equal service times.
Batch Size Effects in the Analysis of Simulation Output
Authors: Schmeiser Bruce
Published: November 2008

Batching is a commonly used method for calculating confidence intervals on the mean of a sequence of correlated observations arising from a simulation experiment. Several recent papers have considered the effect of using batch sizes too small to satisfy assumptions of normality and/or independence, and the resulting incorrect probabilities of the confidence interval covering the mean. This paper quantifies the effects of using batch sizes larger than necessary to satisfy normality and independence assumptions. These effects include (1) correct probability of covering the mean, (2) an increase in expected half length, (3) an increase in the standard deviation and coefficient of variation of the half length, and (4) an increase in the probability of covering points not equal to the mean. For any sample size and independent and normal batch means, the results are (1) the effects of less than 10 batches are large and the effects of more than 30 batches small, and (2) additional batches have lesser effects on confidence intervals having lower confidence levels. The results also are useful in the context of using independent replications for establishing confidence intervals on the mean.
Perishable Inventory Theory: A Review
Authors: Nahmias Steven
Published: November 2008

This paper reviews the relevant literature on the problem of determining suitable ordering policies for both fixed life perishable inventory, and inventory subject to continuous exponential decay. We consider both deterministic and stochastic demand for single and multiple products. Both optimal and sub-optimal order policies are discussed. In addition, a brief review of the application of these models to blood bank management is included. The review concludes with a discussion of some of the interesting open research questions in the area.
On the Objective Function Behavior in (s, S) Inventory Models
Authors: Sahin Izzet
Published: November 2008

The most common measure of effectiveness used in determining the optimal (s, S) inventory policies is the total cost function per unit time, E(s, Δ), Δ = S − s. In stationary analysis, this function is constructed through the limiting distribution of on-hand inventory, and it involves some renewal-theoretic elements. For Δ ≥ 0 given, E(s, Δ) turns out to be convex in s, so that the corresponding optimal reorder point, s1(Δ), can be characterized easily. However, E(s1(Δ), Δ) is not in general unimodal on Δ ≥ 0. This requires the use of complicated search routines in computations, as there is no guarantee that a local minimum is global.

Both for periodic and continuous review systems with constant lead times, full backlogging and linear holding and shortage costs, we prove in this paper that E′(s1(Δ), Δ) = 0, Δ ≥ 0, is both necessary and sufficient for a global minimum (E(s1(Δ), Δ) is pseudoconvex on Δ ≥ 0) if the underlying renewal function is concave. The optimal stationary policy can then be computed efficiently by a one-dimensional search routine. The renewal function in question is that of the renewal process of periodic demands in the periodic review model and of demand .sizes in the continuous review model.
Technical Note—The Expected Remaining Service Time in a Single Server Queue
Authors: Fakinos Demetrios
Published: November 2008

For the G/G/1 queueing system, let (pn), n = 0, 1, 2, …, and (rn), n = 0, 1, 2, … be the limiting probability distributions of the number of customers in the system, when the system is considered “at any time” and when it is considered at arrival epochs respectively. Also let bn (n = 1, 2, …) be the mean remaining duration of the service in progress at the epoch of an arrival which finds n customers in the system. In this note, a relation between the sequences (pn), (rn) and (bn) is given and it is used to provide alternative derivations for two well-known results in the theory of queues.
Operations Research and Capacity Expansion Problems: A Survey
Authors: Luss Hanan
Published: November 2008

Planning for the expansion of production capacity is of vital importance in many applications within the private and public sectors. Examples can be found in heavy process industries, communication networks, electrical power services, and water resource systems. In all of these applications, the expansion of production capacity requires the commitment of substantial capital resources over long periods of time. Capacity expansion planning consists primarily of determining future expansion times, sizes, and locations, as well as the types of production facilities. Since the late 1950s, operations research methodology has been used to develop various models and solution approaches suitable for different applications. In this paper, we attempt to unify the existing literature on capacity expansion problems, emphasizing modeling approaches, algorithmic solutions, and relevant applications. The paper includes an extensive list of references covering a broad spectrum of capacity expansion problems.
A Multivariate New Better than Used Class Derived from a Shock Model
Authors: El-Neweihi Emad , Proschan Frank , Sethuraman Jayaram
Published: November 2008

We introduce a new class of multivariate new better than used (MNBU) life distributions based on a shock model similar to that yielding the Marshall-Olkin multivariate exponential distribution. Let T1, …, TM be independent new better than used (NBU) life lengths. Let F̄(t1, …, tn) be the joint survival function of minI∈A1 T1, I = 1, …, n, where A1, …, An are nonempty subsets of {1, …, M} and Ur=1n A1 = {1, …, M} F̄(t1, …, tn) is said to be a MNBU survival function. Basic properties of MNBU survival functions are derived. Comparisons and relationships of this new class of MNBU survival functions are developed with earlier classes.
Model Building Techniques for the Correction of End Effects in Multistage Convex Programs
Authors: Grinold Richard C.
Published: November 2008

This paper considers model building procedures that can be used to reduce end effects in multistage planning models. In particular, it emphasizes some problems that are peculiar to energy planning applications. The paper presents and compares four methods for mitigating end effects. It concludes that one of these four methods, the dual equilibrium procedure, is best. The major drawback of the dual equilibrium procedure is its lack of simplicity. If it is to be widely used, then it must be widely understood.
The Response Times of Priority Classes under Preemptive Resume in M/M/m Queues
Authors: Buzen J. P. , Bondi A. B.
Published: November 2008

Expressions are derived for the mean response times of each priority level in a multiserver M/M/m queue operating under preemptive resume scheduling. Exact results are obtained for cases where all priorities have the same mean service times; approximate results are obtained for the more general case where mean service times may differ. The results hold for any number of servers and any number of classes. For each priority level, it is assumed that arrivals are Poisson and service times are exponentially distributed.
Technical Note—A Polynomial Simplex Method for the Assignment Problem
Authors: Hung Ming S.
Published: November 2008

We present a polynomial primal simplex algorithm for the assignment problem. For n × n assignment problem with integer cost coefficients, the algorithm generates at most n3 ln ▵ bases prior to reach the optimal basis, where ▵ is the difference in objective value between an initial extreme point and the optimal extreme point.
Facility Locations with the Manhattan Metric in the Presence of Barriers to Travel
Authors: Larson Richard C. , Sadiq Ghazala
Published: November 2008

This paper considers the optimal location of p facilities in the plane, under the assumption that all travel occurs according to the Manhattan (or rectilinear or I1) metric in the presence of impenetrable barriers to travel. Facility users are distributed over a finite set of demand points, with the weight of each point proportional to its demand intensity. Each demand point is assigned to the closest facility. The objective is to locate facilities so as to minimize average Manhattan travel distance to a random demand. We show that an optimal set of facility locations can be drawn from a finite set of candidate points, all of which are easy to determine.
Complexity of the Project Sequencing Problem
Authors: Akileswaran V. , Hazen G. B. , Morin T. L.
Published: November 2008

This paper analyzes the computational complexity of the project sequencing problem. Specifically, we prove that the general decision problem is NP-complete, but note that an important special case is solvable in polynomial time.
Resource Allocation with Tree Constraints
Authors: Mjelde K. M.
Published: November 2008

We extend Zipkin's variant of the Luss and Gupta algorithm for the allocation of a single resource to activities described by concave return functions, to handle additional constraints imposed upon the total allocations to certain subsets of activities, and to subsets of these subsets, and so on. We determine computational times for certain return functions and extensions to problems with an objective function defined by the difference or the ratio of return and cost, and to problems with several resources.
Simple Dependent Pairs of Exponential and Uniform Random Variables
Authors: Lawrance A. J. , Lewis P. A. W.
Published: November 2008

The accurate characterization of input processes for simulation models can require the representation of dependencies among input values. Results are presented on the generation of dependent exponential and uniform pairs of random variates. A random-coefficient linear function of two independent exponential variables yielding a third exponential variable is used in the construction of simple, dependent pairs of exponential variables. To model negative dependency, the constructions employ antithetic exponential variables. By employing negative exponentiation, the constructions yield simple multiplicative-based models for dependent uniform pairs. The ranges of dependency allowable in the models are assessed by correlation calculations, both of the product moment and Spearman types. Broad ranges within the theoretically allowable ranges are found. Because of their simplicity, all models are particularly suitable for simulation and are free of point and line concentrations of probabilities.
Technical Note—On Reconciling Conflicting Goals: Applications of Multiobjective Programming
Authors: Hahn Robert W.
Published: November 2008

This paper examines the problem of identifying cost-effective solutions to problems with multiple objectives. The traditional approach has been to minimize costs subject to feasibility constraints and a set of targets. In contrast, a multiobjective programming approach treats the objectives as choice variables and cost as a parameter. To illustrate the two approaches, we analyze the problem of achieving environmental objectives. The comparison reveals that the traditional cost-minimizing approach can generate solutions that are inefficient, in the sense that greater emission reductions could have been attained at the same cost. Because the solution sets to the two problems may differ, we derive conditions under which the two approaches yield a similar set of results.
Surrogate Dual Multiplier Search Procedures in Integer Programming
Authors: Karwan Mark H. , Rardin Ronald L.
Published: November 2008

Search procedures for optimal Lagrange multipliers are highly developed and provide good bounds in branch and bound procedures that have led to the successful application of Lagrangean duality in integer programming. Although the surrogate dual generally provides a better objective bound, there has been little development of surrogate multiplier search procedures. This paper develops and empirically analyzes several surrogate multiplier search procedures. Results indicate that the procedures can produce possibly superior bounds in an amount of time comparable to other techniques. Our discussion also highlights the similarity of the procedures to some well known Lagrangean search techniques.
The Randomization Technique as a Modeling Tool and Solution Procedure for Transient Markov Processes
Authors: Gross Donald , Miller Douglas R.
Published: November 2008

We present a randomization procedure for computing transient solutions to discrete state space, continuous time Markov processes. This procedure computes transient state probabilities. It is based on a construction relating a continuous time Markov process to a discrete time Markov chain. Modifications and extensions of the randomization method allow for computation of distributions of first passage times and sojourn times in Markov processes, and also the computation of expected cumulative occupancy times and expected number of events occurring during a time interval. Several implementations of the randomization procedure are discussed. In particular we present an implementation for a general class of Markov processes that can be described in terms of state space (S), event set (E), rate vectors (R), and target vectors (T)—abbreviated as SERT. This general approach can handle systems whose state spaces are quite large, if they have sparse generators.
A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
Authors: Faaland Bruce
Published: November 2008

We solve a simple class of linear programming problems with tree-structured constraint matrices. Our procedure separates the problem into a sequence of continuous knapsack problems, each of which requires linear time to solve, for total solution time no worse than proportional to the number of nonzero entries in the original constraint matrix. The model arises in portfolio selection, advertising, and inventory and production planning.
Inspection Policies for Fault Location
Authors: Butler David A. , Lieberman Gerald J.
Published: November 2008

When a system fails it may not be obvious which components are at fault. Locating faulty components to be replaced may require a series of inspections each of which reveals the state (functioning/failed) of one of the components. The order in which components are inspected and replaced can greatly affect the cost to restore the system to an operating condition. This paper investigates inspection sequences for complex coherent systems.
Some Reliability Applications of the Variability Ordering
Authors: Ross Sheldon M. , Schechner Zvi
Published: November 2008

The random variable X is said to be more variable than Y if E[f(X)] ≥ E[f(Y)] for all increasing convex functions f. We prove a preservation property of this ordering under random sized sums, and then apply it to branching processes and shock models. We also give applications of this ordering to a population survival and to a Poisson shock model.
Estimating a Survival Curve when New Is Better Than Used
Authors: Boyles Russell A. , Samaniego Francisco J.
Published: November 2008

Let F be a distribution function on (0, ∞), and let S = 1 − F be its corresponding survival function. F is New Better than Used (NBU) if S(x)S(y) ≥ S(x + y) for all x and y. Let Sn(x) be the empirical survival function based on a random sample of size n from an NBU distribution function F. This paper studies the estimator Ŝn(x) defined as sup{Sn(x + y)/Sn(y)}, where the supremum is taken over all y for which Sn(y) > 0. We show that Ŝn is an NBU survival curve, and that it is strongly uniformly consistent for S when the underlying distribution has compact support (for example, when sampling is subject to type I censoring). Moreover, in such problems, we show that the rate of convergence of Ŝn is optimal.
Technical Note—A Class of Stochastic Mathematical Programs with Correlated Scale Parameters in the Objective and Right-Hand Side
Authors: Soyster A. L. , Foley R. D. , Murphy F. H.
Published: November 2008

This note studies a class of stochastic programs with scale parameters in the objective function and right-hand side. Linear programs are an important special case of this class. The scale parameters are a pair of jointly distributed random variables. The basic issue addressed is the type of biases introduced by replacing the random variables by their expected values. As one would expect, the covariance between the random variables is of central importance. Depending upon the sign of the covariance, the objective value of the program, in which the random variables are replaced by their expected values, is greater or lesser than the expected objective function value of the stochastic program.
The Optimal Search for a Moving Target When the Search Path Is Constrained
Authors: Eagle James N.
Published: November 2008

A search is conducted for a target moving in discrete time among a finite number of cells according to a known Markov process. The searcher must choose one cell in which to search in each time period. The set of cells available for search depends upon the cell chosen in the last time period. The problem is to find a searcher path, i.e., a sequence of search cells, that maximizes the probability of detecting the target in a fixed number of time periods. We formulate the problem as a partially observable Markov decision process and present a finite time horizon POMDP solution technique which is simpler than the standard linear programming methods.
Technical Note—A Langrangian Algorithm for the Multiple Choice Integer Program
Authors: Bean James C.
Published: November 2008

In the Multiple Choice Integer Program, the binary variables are partitioned into generalized upper bounding sets (or special ordered sets). We solve this problem using a branch-and-bound scheme designed to take advantage of this structure. The basic procedure is enhanced by solving a Lagrangean problem as an approximation. Further, we use a variable reduction technique to eliminate many of the variables prior to problem solution. Computational experience is promising for randomly generated problems, scheduling problems, and budgeting problems tested.
Explicit and Iterative Numerical Approaches to Solving Queueing Models
Authors: Snyder Patricia M. , Stewart William J.
Published: November 2008

This paper considers two approaches to the numerical solution of single node queueing models. Both approaches use a phase-type distribution to model very general service processes. The first approach is explicit and sometimes can exploit the structure of certain balance equations to reduce the global balance equations from a set of second order difference equations to a set of first order difference equations. This reduction permits the steady-state probability distribution to be written explicitly as a function of the model parameters. The second approach, due to Neuts, uses the fact that most queues that have a matrix-geometric steady-state probability distribution can be solved by means of a recursive technique. We compare the approaches and present a theorem that specifies necessary conditions for the computation of an explicit solution. A number of examples are provided.
Further Results on Queues with Partial Correlation
Authors: Hadidi Nasser
Published: November 2008

As a sequel to the author's and Conolly and Choo's articles, this paper further investigates the effects of positive correlation between the underlying processes in queueing models. Having established that the waiting time distribution is hyperexponential for a certain service interarrival joint density, we examined the sensitivity of this distribution to the value of the correlation coefficient r(0 < r < 1). Since the extreme cases of r = 0 (conventional models) and r = 1 have long been known, we are able to illustrate the convergence of the waiting time density and respective moments to their limiting values.
Technical Note—Construction of Difficult Linearly Constrained Concave Minimization Problems
Authors: Kalantari Bahman
Published: November 2008

Given a polytope and an arbitrary subset of its vertices, we show how to construct a differentiable concave function that assumes any arbitrary value (within a specified ε-tolerance) at each vertex of the subset, with each vertex in the subset a strong local constrained minimum. We also show how this construction method can be used to generate test problems for linearly constrained concave minimization algorithms.
Optimal Supply of a Depletable Resource with a Backstop Technology: Heal's Theorem Revisited
Authors: Oren Shmuel S. , Powell Stephen G.
Published: November 2008

Heal's theorem states that if the extraction cost of a depletable resource increases with cumulative extraction, and if a backstop technology exists, the user cost of the depletable resource declines to zero at the date of exhaustion. In this paper, we first present a simple method for proving this proposition, using a social planning model that determines the optimal rates both of extraction of the depletable resource and of production of the backstop technology. We then present two examples that show how this method can be used to solve more difficult problems in the theory of resource economics. The first example involves learning-by-doing in the backstop sector; that is, backstop costs decline with cumulative production. The second example involves uncertainty of backstop costs.
Minimizing Weighted Completion Times with Deadlines
Authors: Posner Marc E.
Published: November 2008

We examine a one-machine scheduling problem whose objective is to minimize the weighted sum of completion times, subject to deadline constraints. We synthesize and extend current known theory, and derive precedence relations between jobs. These relationships, along with tight new bounding criteria, are incorporated in a branch and bound solution procedure.
Technical Note—The Stochastic Discrete Dynamic Lot Size Problem: An Open-Loop Solution
Authors: Lasserre J. B. , Bes C. , Roubellat F.
Published: November 2008

We investigate the stochastic dynamic lot size model, taking into account probabilistic constraints on the state variable. Our approach is to obtain an open-loop solution by solving a new equivalent deterministic dynamic lot size problem with new parameters. We also discuss characteristics of the new equivalent deterministic problem and note, in particular, that the new formulation preserves concavity or convexity.
Technical Note—A Note on the Stochastic Shortest Route Problem
Authors: Kamburowski Jerzy
Published: November 2008

An optimality index for choosing the shortest route in an acyclic, stochastic network has recently been proposed. The present note identifies certain anomalies in using that index and proposes another optimality index. The results of using these indices are compared in a simple example.
Bounding the Project Completion Time Distribution in PERT Networks
Authors: Dodin Bajis
Published: November 2008

We consider the PERT model of a project composed of activities whose durations are random variables with known distributions. For the situations in which the activity durations are completely independent, we present a new method for obtaining a probability distribution function that bounds the exact probability distribution of the project completion time from below. The bounding distribution can be used to obtain an upper bound on the mean completion time of the project. We also prove and illustrate that this bounding distribution is better (tighter) than any of the existing lower bounds, implying that the corresponding upper bound on the mean completion time is tighter than any of the existing upper bounds.
The Optimality of Unbalancing Both Workloads and Machine Group Sizes in Closed Queueing Networks of Multiserver Queues
Authors: Stecke Kathryn E. , Solberg James J.
Published: November 2008

Using a closed queueing network model, we explore the consequences of varying workloads among multiserver queues that may be of unequal size. In addition, we solve the problem of assigning servers of similar types to the queues in the network to maximize expected throughput.

We show that (1) unbalanced configurations of assigned servers are superior to balanced ones, and (2) unbalanced workloads are better than balanced ones. We find that there can be significant differences in system throughput from balanced versus unbalanced configurations/workloads. Finally, we discuss applications to planning problems of flexible manufacturing systems.
Testing the Adequacy of Markov Chain and Mover-Stayer Models as Representations of Credit Behavior
Authors: Frydman Halina , Kallberg Jarl G. , Kao Duen-Li
Published: November 2008

We summarize methodology for testing the compatibility of discrete time stochastic processes—stationary and nonstationary Markov chains and an extension, the mover-stayer model—with longitudinal data from an unknown empirical process. We apply this methodology to determine the suitability of these models to represent the payment behavior of a sample of retail revolving credit accounts. We are led to reject stationary and also nonstationary Markov chain models for our data and for our state space definition in favor of the mover-stayer model. The mover-stayer model, in contrast to Markov chains, incorporates a simple form of population heterogeneity. Stationary Markov chains have been used extensively in finance literature to model payment behavior of credit accounts. Our empirical study suggests, however, that stationary Markov chains may not appropriately model payment behavior. It also indicates that incorporating heterogeneity in modeling payment behavior may be more important than incorporing nonstationarity.
Optimal Flows in Networks with Multiple Sources and Sinks, with Applications to Oil and Gas Lease Investment Programs
Authors: Federgruen Awi , Groenevelt Henry
Published: November 2008

In the classical maximal flow problem, the objective is to maximize the supply to a single sink in a capacitated network. In this paper we consider general capacitated networks with multiple sinks: the objective is to optimize a general “concave” preference relation on the set of feasible supply vectors. We show that an optimal solution can be obtained by a marginal allocation procedure. An efficient implementation results in an adaptation of the augmenting path algorithm. We also discuss an application of the procedure for an investment company that deals in oil and gas ventures.
Production Planning of Style Goods with High Setup Costs and Forecast Revisions
Authors: Bitran Gabriel R. , Haas Elizabeth A. , Matsuo Hirofumi
Published: November 2008

In this paper we study a problem, common to a wide variety of manufacturing companies, of determining the production schedule of style goods, such as clothing and consumer durables, under capacity constraints. Demand for items is stochastic and occurs in the last season of the planning horizon. Demand estimates are revised in each period. We exploit the problem's two-level hierarchical structure, which is characterized by families and items. Production changeover costs from one family to another are high, compared to other costs. However, changeover costs between items in the same family are negligible. We first formulate this problem as a difficult-to-solve stochastic mixed integer programming problem. Then, exploiting the problem's hierarchical structure, we formulate a deterministic, mixed integer programming problem and solve it by means of an algorithm that provides an approximate solution. A lower bound is obtained by applying generalized linear programming to the approximate problem. We illustrate the procedure using the disguised data of a consumer electronics company. The computational results demonstrate the effectiveness of the proposed approach in a practical setting.
Technical Note—The Complexity of the Optimal Searcher Path Problem
Authors: Trummel K. E. , Weisinger J. R.
Published: November 2008

In this note we show that the problem of finding an optimal searcher path that maximizes the probability of detecting a stationary target by the end of a fixed time is NP-complete. We also demonstrate that the problem of finding a path that minimizes mean time to detection is NP-hard.
Comments on “On the Optimal Choice of Sizes” by Peter Tryfos
Authors: Pentico David W.
Published: November 2008

Comments on Carr, C. R., C. W. Howe. 1962. Optimal service policies and finite time horizons. Mgmt. Sci. 9 126–140.
OR Practice—Solving Complex Chemical Equilibria Using a Geometric-Programming Based Technique
Authors: Wall Thomas Wayne , Greening Doran , Woolsey R. E. D.
Published: November 2008

Determining the composition of a chemical system at equilibrium is an important problem that arises in many fields of science and engineering. For complex equilibria, the use of a digital computer is required. The chemist often finds the use of current computer codes an inefficient and frustrating experience. This paper presents a globally convergent algorithm for the solution of chemical equilibrium problems. This algorithm has been made both efficient and easy to use and is now employed successfully by chemists on important problems. It is based on the application of geometric programming principles to solve systems of nonlinear equations. Although presented in a form that can be quickly understood by the practitioner, the methodology is mathematically rigorous. Computer programs that require no familiarity with the details of the methodology were developed and extensively tested. These programs can be used as general research tools for investigating the solution of nonlinear equations in areas other than chemistry.
Network Models of Spatial Oligopoly with an Application to Deregulation of Electricity Generation
Authors: Hobbs Benjamin F.
Published: November 2008

Because of the existence of transmission costs and significant scale economies in power production, deregulation of electricity generation would lead to spatial oligopolistic markets. This paper uses linear programs to obtain short-run spatial price equilibria for a deregulated bulk power market in upstate New York. These models, unlike most previous models of imperfect competition, capture spatial variations in production costs and demand functions. We present two models. One calculates a Nash-Bertrand equilibrium, in which each firm believes that rivals will not react to price changes. This equilibrium represents the most intense level of competition to be expected. The other model yields limit prices that are designed to discourage new firms from entering the market.
A Queue with Starter and a Queue with Vacations: Delay Analysis by Decomposition
Authors: Levy Hanoch , Kleinrock Leonard
Published: November 2008

This paper analyzes both a queueing system that incurs a start-up delay whenever an idle period ends and one in which the server takes vacation periods. We show that the delay distribution in the queue with starter is composed of the direct sum of two independent variables: (1) the delay in the equivalent queue without starter, and (2) the additional delay suffered due to the starter's presence. Using this decomposition property, we easily derive the distribution of the delay suffered in the system with starter. This analysis is done for systems (both discrete and continuous time) whose interarrival times possess the memoryless property. Using this approach, we then analyze the M/G/1 system with vacation periods. First, we show that the M/G/1 with vacations can be considered as a special case of the M/G/1 with starter, so that the delay in the M/G/1 with vacations can be easily found by using the formula for the delay of the M/G/1 with starter. Second, using geometric arguments, we explain why the additional delay in the vacation system is distributed as the residual life of the vacation period.
Uniformization and Hybrid Simulation/Analytic Models of Renewal Processes
Authors: Shanthikumar J. George
Published: November 2008

In this paper we demonstrate the use of uniformization in the simulation of renewal processes. Using uniformization, we represent the continuous random variable of interest as the first passage time of a continuous-time stochastic process associated with a Poisson process. We then use this result to develop a hybrid simulation/analytic method to model renewal processes. The estimators obtained from the hybrid simulation/analytic models have lower variance than the variance of the estimators of the traditional simulation models. We also discuss the possible impact of this method on the future of simulation methodology.
Optimal Sequencing by Modular Decomposition: Polynomial Algorithms
Authors: Sidney Jeffrey B. , Steiner George
Published: November 2008

We show that the combination of dynamic programming with partial-order decomposition algorithms enables us to solve sequencing problems in polynomial time for substantially larger classes of precedence constraints than previously realized. The algorithm's efficiency depends on the maximum number of jobs that are not related by the precedence constraints in certain subsets of the jobs. We also demonstrate how to modify this general algorithm lo take advantage of special problem characteristics.
Policy Bounds for Markov Decision Processes
Authors: Lovejoy William S.
Published: November 2008

This paper demonstrates how a Markov decision process (MDP) can be approximated to generate a policy bound, i.e., a function that bounds the optimal policy from below or from above for all states. We present sufficient conditions for several computationally attractive approximations to generate rigorous policy bounds. These approximations include approximating the optimal value function, replacing the original MDP with a separable approximate MDP, and approximating a stochastic MDP with its deterministic counterpart. An example from the field of fisheries management demonstrates the practical applicability of the results.
Generalized Mathematical Programming for Optimal Replacement in a Semi-Markov Shock Model
Authors: Mizuno Norihiro
Published: November 2008

We analyze a semi-Markovian decision process for optimal replacement of a device in a shock model, using a generalized mathematical programming approach. By means of a simple proof, we obtain a weak sufficient condition for the existence of an optimal control-limit replacement policy. We also present a convergent algorithm to find an optimal replacement policy.
Tenant Assignment Models
Authors: Kaplan Edward H.
Published: November 2008

Public housing authorities must implement tenant assignment policies aimed at providing affordable, decent housing for low income households. We consider the implications of such assignment policies by presenting analytic forms for the mean and variance of applicant waiting times that account for varying requirements for housing, applicant dropout, and priority assignment schemes, including transfers and standard scoring methods. We also consider a simple model of project demographics.