bluuebunny/crossref_metadata_2025 huggingface dataset:
Random Juror Selection from Multiple Lists
Authors: Kadane Joseph B. , Lehoczky John P.
Published: November 2008

We examine the selection of jurors' names from multiple source lists, using statistical and optimization methodology. Five plans for sampling at random from overlapping lists of names are analyzed for their probabilistic and cost properties. In each plan the probability of a name being selected is independent of which and how many lists it appears on. We consider the optimal ordering of the frames to minimize cost and develop a heuristic for solving this problem. Although the methods are discussed in terms of juror selection, the results apply to sampling from overlapping frames in any context. For instance, if lists of equipment are kept according to possible uses, with versatile equipment listed many times, the methods of this paper can be used to draw a random sample of equipment to check for readiness.
Pyramid and Semicube Decompositions of Multiattribute Utility Functions
Authors: Farquhar Peter H.
Published: November 2008

We apply the fractional hypercube decomposition theorem for multiattribute utility functions to the quasi-pyramid, the pyramid, and the semicube fractions. The resulting nonadditive utility models illustrate the broad range of decompositions that can be obtained with this fractional hypercube methodology. The pyramid decompositions have nonseparable interaction terms for each pair of attributes, whereas the semicube decomposition has nonseparable interaction terms for each proper subset of attributes. The computations and scaling illustrated here can be performed with other fractional hypercubes to produce various results between these two extremes.
Network Flows, Minimum Coverings, and the Four-Color Conjectures
Authors: Weinberger David B.
Published: November 2008

In this paper we use Fulkerson's antiblocking theory as a framework in which to explore certain combinatorial properties of network flows. In particular, we derive a surprising round-off result for a class of integer covering problems. When combined with Edmond's characterization of the matching polytope, our results yield an interesting proposition concerning the four-color conjecture. Our goal in presenting this proposition is not so much to propose a new approach to the famous conjecture as it is to present an interesting example of the interrelation of a number of seemingly diverse areas of combinatorics and combinatorial optimization—in particular, antiblocking and minimum coverings, integer network flows, edge matchings in graphs, and graph coloring.
Optimal Capacity Expansion with Inventory
Authors: Rao M. R.
Published: November 2008

In a given region over a finite time horizon, a known nondecreasing demand for a single commodity has to be satisfied by production in that period and/or by inventory from the previous period. There is no initial production capacity or inventory, but the capacity and production may be increased at the beginning of each discrete time period. We assume that the capacity and production are nondecreasing over the time periods. The total time discounted costs to be minimized include the capacity expansion, production, inventory carrying, and idle capacity costs, which are assumed to be concave. The problem is to determine an optimal capacity expansion and production schedule, together with the associated inventory carrying and idle capacity schedules. Based on some interesting properties of an optimal solution, we devise an efficient dynamic programming algorithm to solve this problem.
An Advanced Dual Basic Feasible Solution for a Class of Capacitated Generalized Networks
Authors: Hultz John , Klingman Darwin , Russell Robert
Published: November 2008

This paper presents a “one-pass” algorithm that determines an “advanced” dual basic feasible solution for a class of capacitated generalized network problems. Special cases in this class of problems include transportation and transshipment problems. We include computational results that show that this new start substantially improves the solution performance of the dual method for transportation and transshipment problems. In fact, a dual code employing this advanced start is found to be faster (in terms of total solution time) than the fastest out-of-kilter code SUPERK on highly rectangular transportation problems.
Stochastic Programs with Incomplete Information
Authors: Ben-Tal Aharon , Hochman Eithan
Published: November 2008

This paper treats a simple recourse problem. We consider the problem of reducing the feasible set into a smaller efficient set when partial information about the random parameters is known. We analyze some examples and give applications to stochastic programs with compete information.
Manpower Planning with Uncertain Requirements
Authors: Grinold Richard C.
Published: November 2008

This paper examines a longitudinal model of a manpower system. The demand for effective manpower is determined by the state of a finite Markov chain. There are delays in training effective manpower, and effective manpower is an input to the training process. Thus it is not always available to meet demand. We present an operational method for calculating optimal accession policies. This calculation can in turn be used to find the equilibrium operating rules for the system. The model is a useful device for measuring the impact of alternate assumptions about continuation rates, manpower utilization policies, demand levels, and transition probabilities in the demand process.
On Searching for Events of Limited Duration
Authors: Barnett Arnold
Published: November 2008

Given a set of events, an observer wishes to detect as many of these as possible. The events arise at several discrete points according to independent Poisson processes, and the lifetimes of individual occurrences are independent and identically distributed random variables. The specific problem is: given that the observer can only visit one point per unit time, in what sequence should he make his visits so as to maximize the steady-state fraction of events he detects? We obtain some results about the optimal search policy and find the best policy precisely in some circumstances.
Incorporating Component and System Test Data into the Same Assessment: A Bayesian Approach
Authors: Mastran David V.
Published: November 2008

On occasion, reliability analysts have test data gathered both at the component level of a multicomponent system and at the system level. When the system test data provide no information on component performance, classical statistical techniques in all but trivial cases do not allow using both sets of data. We present a Bayesian procedure that does allow using both sets. The procedure for attribute data makes use of a lemma that relates the moments of the prior and posterior distributions of reliability to the test data. The procedure for variables data assumes the time to failure distribution of each component is exponential.
Technical Note—Johnson's Three-Machine Flow-Shop Conjecture
Authors: Burns Fennell , Rooker John
Published: November 2008

In an epoch-setting paper on scheduling theory, Johnson determined an efficient algorithm for solving the two-stage flow-shop problem and two special cases of the three-stage problem. In his concluding remarks he suggested another special condition in which one would obtain a three-stage solution. We give an example to show that this conjecture is not quite true. A true statement is obtained, however, by only a slight strengthening of the original. The primary issue concerns the impact of the two-stage no-preference precedent rules on the three-stage problem.
Branch-and-Bound Strategies for Dynamic Programming
Authors: Morin Thomas L. , Marsten Roy E.
Published: November 2008

This paper shows how branch-and-bound methods can be used to reduce storage and, possibly, computational requirements in discrete dynamic programs. Relaxations and fathoming criteria are used to identify and to eliminate states whose corresponding subpolicies could not lead to optimal policies. The general dynamic programming/branch-and-bound approach is applied to the traveling-salesman problem and the nonlinear knapsack problem. Our computational experience demonstrates that the hybrid approach yields dramatic savings in both computer storage and computational requirements.
A Cotton Ginning Problem
Authors: Klingman Darwin , Randolph Paul H. , Fuller Stephen W.
Published: November 2008

This paper examines the plant location problem of the cotton-processing industry. In recent years the industry has experienced an excess gin plant capacity. By considering the transportation requirements from the farms to the gins, the gin costs, and the gin capabilities, we develop a model to determine which gins should be used for this seasonal product. A case study is used to illustrate the analysis and emphasis is placed on alternative formulations of the model.
On a General Solution of the Deterministic Lot Size Problem with Time-Proportional Demand
Authors: Resh Michael , Friedman Moshe , Barbosa Lineu C.
Published: November 2008

We reconsider the classical lot-size model with the assumption that demand rate is deterministic, starts at the origin, and linearly increases with time. Two relevant costs are involved: carrying cost and replenishment cost. The planning horizon is finite and known. The problem is to find the optimal schedule of replenishments, i.e., their number and the schedule of time intervals between consecutive orders. Mathematically, we have to find an integer m and the values of m continuous variables so as to minimize the total carrying and replenishments costs. We prove that for a givers number of replenishments m, there exists a unique vector of m time intervals that minimizes the total cost function. It is further shown that the total carrying cost obtained after substituting the optimal value of that vector is a convex function of m. The algorithm that determines the unique optimal value of m and the unique optimal scheduling of replenishments for m employs these mathematical results. Finally, we investigate the asymptotic properties of the model when the planning horizon is infinite.
An Integer Generalized Transportation Model for Optimal Job Assignment in Computer Networks
Authors: Balachandran V.
Published: November 2008

This paper investigates the assignment of tasks in a network of functionally similar computers. We formulate the problem by a periodic review model with Boolean variables. A computationally efficient, integer-generalized transportation model is applicable because of the existence of relative efficiencies of computers for jobs. Since a job is to be processed exclusively by one computer, we show that an optimal solution to this problem is a basic feasible solution to a slightly modified generalized transportation problem. A branch-and-bound solution procedure prevents possible splitting of a job among computers. We provide an algorithm and computational results.
The M/M/∞ Queue with Varying Arrival and Departure Rates
Authors: Collings T. , Stoneman C.
Published: November 2008

This paper derives the queue size distribution for infinite server queues with Poisson arrivals and exponential service times when the parameters of both distributions are allowed to vary with time. Both continuous and discrete variation are examined. Infinite server queues realistically describe those queues in which sufficient service capacity exists to prevent virtually any customer waiting time. Such queues are not uncommon in the health services, when a delay in service can sometimes mean death. Specifically, we discuss the queuing problem of an intensive care unit and show that it is unlikely that the hourly variation in the arrival rate of patients to the unit will significantly affect the number of beds occupied.
Technical Note—Finding Some Essential Characteristics of the Feasible Solutions for a Scheduling Problem
Authors: Erschler J. , Roubellat F. , Vernhes J. P.
Published: November 2008

This note is concerned with some essential characteristics of the feasible solutions for a job-shop scheduling problem in which the jobs are constrained by fixed starting times and due dates. These characteristics are related to the scheduling order of operations on each machine and to the fixed starting and completion times for each operation. We present the basic principles enabling one to define these characteristics and propose a procedure for finding them.
Technical Note—Exact Solutions of Inexact Linear Programs
Authors: Falk James E.
Published: November 2008

We address the problem of solving a linear program whose objective function coefficients are known only to lie in a given convex set. We seek a solution that is optimal against the worst possible realization of the objective function, i.e., a max-min solution. We present optimality criteria that characterize the desired solution and strengthen earlier results due to Soyster. The conditions are computationally implementable.
Markov Chain Model for Events Following Induced Abortion
Authors: Shachtman Richard H. , Hogue Carol J.
Published: November 2008

This paper presents a Markov chain model for investigating questions about the possible health-related consequences of induced abortion. The model evolved from epidemiologic research questions in conjunction with the criteria for Markov chain development. It has been developed to apply to data collected on 928 women who participated in an historical-prospective study conducted in Skopje, Yugoslavia. Formulas employing the transition probabilities may be used to answer specific questions of interest to epidemiologists, physicians, and health policy makers.
The Simple Plant-Location Problem under Uncertainty
Authors: Jucker James V. , Carlson Robert C.
Published: November 2008

There is a class of simple plant-location problems under uncertainty that can be decomposed into two simpler problems that can be solved sequentially with surprising ease. The salient characteristic of this class of problems is that for any demand generating region, one plant dominates all others as a supply source. We develop and discuss the conditions required for this dominance. The risk-averse nature of the firm is incorporated into this model with a mean-variance formulation of the objective function. The general formulation is particularized to four paradigms of firms characterized by a range of behavioral and market assumptions.
Implementation and Computational Study on an In-Core, Out-of-Core Primal Network Code
Authors: Karney D. , Klingman D.
Published: November 2008

This paper presents extensive computational experience with a special-purpose primal simplex code using the augmented threaded index method for solving capacitated and uncapacitated transshipment and transportation problems. This code is distinguished from other codes for solving such problems in that not all of the data resides in central memory simultaneously; thus, it is referred to as an in-core, out-of-core code. The major advantages of such a code over an in-core code are (1) it can solve problems that the latter can not solve because of central memory requirements; (2) even for problems that the latter can solve, it requires less central memory, which is critical for fast job processing on multiprogrammed computer systems; and (3) the code can also be used as an in-core code.

The design of such codes presents numerous computational difficulties in selecting the best starting and pivot procedures in order to minimize central as well as peripheral processing time. We present computational experience with various pivot, start and capacity buffer procedures, as well as different buffer sizes. Computational results are also provided for different types of network problems, including assignment, transportation, and minimum cost flow problems. These computational results are compared with in-core, out-of-kilter, negative cycle, and primal simplex network codes for problem sizes that these codes could solve.
A Research Bibliography in Stochastic Programming, 1955–1975
Authors: Stancu-Minasian I. M. , Wets M. J.
Published: November 2008

About 800 publications, reports, and articles dealing with stochastic programming are included in this bibliography. The references are classified in terms of their contents: formulation, applications, theory and computation, books and surveys.
Comparison of Some Algorithms for Solving the Group Theoretic Integer Programming Problem
Authors: Chen Der-San , Zionts Stanley
Published: November 2008

Gomory has shown that the group-theoretic problem associated with an integer programming problem can be treated as a shortest-route problem. Thus one may solve it by a standard shortest-route algorithm. However, because of the special properties of the constructed problem, one can simplify and modify the algorithm. This paper presents five such simplified algorithms and compares their computational results with the group-theoretic algorithms developed by Gomory, Hu, and Shapiro.
Analysis of a Standing Order Inventory System with Emergency Orders
Authors: Rosenshine Matthew , Obee Duncan
Published: November 2008

The advent of relatively sophisticated information systems has made it possible for many businesses that keep inventories to know their needs very rapidly. However, the producers of these inventories have not all made comparable advances in scheduling production to meet the rapidly changing orders placed by their increasingly sophisticated customers. As a result, leadtimes have been growing rather than decreasing. Since in most cases the company needing the inventory cannot control the leadtime, it must either accept it or look for ways to mitigate its effect. This paper evaluates one way to cope with the problem of large or growing leadtimes.
Cost Models for Stochastic Clearing Systems
Authors: Stidham Shaler
Published: November 2008

Stochastic clearing systems are characterized by a stochastic input process and an output mechanism that intermittently clears the system, i.e., instantaneously restores the net quantity in the system to zero. Asymptotic properties of such systems can be derived under weak probabilistic assumptions, the essential requirement being that limiting behavior can be determined by “averaging over a cycle,” as is the case, for example, with regenerative processes. In this paper we consider the problem of finding the optimal level, q, at which to clear when there are fixed clearing and variable holding costs. We also study a generalization of a clearing system in which the clearing operation restores the net quantity to a level m, which may be different from zero. Applications to bulk-service queues, demand-responsive public-service systems, and (s, S) inventory systems, among others, are discussed. The exact solutions that we obtain for the optimal clearing parameters are compared to those implied by deterministic approximations.
Technical Note—Minimax Procedure for a Class of Linear Programs under Uncertainty
Authors: Jagannathan R.
Published: November 2008

We consider a linear programming problem with random aij and bi elements that have known (finite) mean and variance, but whose distribution functions are otherwise unspecified. A minimax solution of the stochastic programming model is obtained by solving an equivalent deterministic convex programming problem. We derive these deterministic equivalents under different assumptions regarding the stochastic nature of the random parameters.
Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties
Authors: Sidney Jeffrey B.
Published: November 2008

We consider a single-machine job shop scheduling problem in which penalties occur for jobs that either commence before their target start times or are completed after their due dates. The objective is to minimize the maximum penalty, subject to restrictive assumptions on the target start times, the due dates, and the penalty functions. We present an algorithm for solving this problem, along with a method for generating alternative optima. The algorithm is generalized to cover the case in which the machine is available for only a limited time span.
National Development Planning Revisited
Authors: Ackoff Russell L.
Published: November 2008

We argue that the principal obstructions to national development of less-than-well-developed countries are cultural, not economic or technological. Furthermore, such countries tend to mistake activity for change, and self-imposed constraints for ones that are externally imposed. We propose concepts of development and planning that are intended to overcome these obstacles. The concepts involve an idealized redesign of the system planned for by all those who will be affected by it. A means for launching such a planning effort—a crusade for development—is suggested.
A Classified Bibliography of Research on Optimal Design and Control of Queues
Authors: Crabill Thomas B. , Gross Donald , Magazine Michael J.
Published: November 2008

This paper presents a classified bibliography organized into six sections—static design models, dynamic control models, models involving queue discipline control, miscellaneous models, tutorial and survey papers, and books that have specific portions devoted to design and control. Some of the above categories are further subdivided when appropriate, and explanations of the types of models in each category and subcategory precede the actual list of references. Papers that fall into more than one category are cross-referenced.
Individual versus Social Optimization in Exponential Congestion Systems
Authors: Lippman Steven A. , Stidham Shaler
Published: November 2008

We consider a stochastic congestion system modeled as a birth-death process. Customers arrive from a Poisson process. The departure rate when i customers are in the system is non-decreasing, concave, and bounded above in i. The cost structure consists of a linear holding cost and a random reward received when a customer enters the system. The system can be controlled by deciding which customers will enter. Our main result (extending those of Naor, Yechiali, and Knudsen) is that, with or without discounting and for a finite or infinite time horizon, the individually optimal rule calls for the customer to enter the system whenever the socially optimal rule does. We also study the properties of the optimal congestion toll, which induces customers acting in their own interest to follow a socially optimal rule.
Optimal Control of Single-Server Queuing Networks and Multi-Class M/G/1 Queues with Feedback
Authors: Tcha Dong-Wan , Pliska Stanley R.
Published: November 2008

We consider a queuing network with Poisson arrivals at each node. At each service completion epoch, a reward is received and the serviced customer changes nodes or leaves the system according to specified probabilities. In addition, linear holding costs are incurred. The problem is to schedule the server so as to maximize the expected discounted reward over an infinite planning horizon. This model is equivalent to a single-server, multi-class queuing system with feedback of the customers. We study two cases: general service times with a non-preemptive service discipline and exponential service times with a preemptive service discipline. For each case we show that a modified static policy of priority form is optimal and we provide an algorithm for computing an optimal policy.
Technical Note—Solving Integer Programming Problems by Aggregating Constraints
Authors: Kendall Kenneth E. , Zionts Stanley
Published: November 2008

Integer programming problems with bounded variables can be solved by combining the constraints into an equivalent single constraint. This note presents a refinement to earlier work that reduces the size of the coefficients in the equivalent constraint and points out advantages as well as computational considerations for solving problems by this method.
A Utility Function for Time Streams Having Inter-Period Dependencies
Authors: Bell David E.
Published: November 2008

A utility function that is separable over time cannot accurately reflect the preferences of a decision maker whose attitude toward risk in a given period of a time stream depends on the particular outcome in the previous and/or following period. In this paper we use conditional utility independence to give assumptions that do allow such preferences to be quantified. For a T-period time stream the result requires the assessment of T − 1 two-period utility functions and one scaling constant. If stationarity assumptions are appropriate, only one two-period utility function and two constants are required.
Estimation of Parameters of Zero-One Processes by Interval Sampling
Authors: Brown M. , Solomon H. , Stephens M. A.
Published: November 2008

We consider an alternating renewal process {X(t), t ≧ 0} with states 0 and 1. The periods in state 0 are exponentially distributed with parameter λ, and those in state 1 are exponential with parameter μ. The process is available for sampling only at time epochs that are multiples of a fixed number ▵. The object is to estimate λ and μ from the data. We consider estimation procedures for each of the following sets of data: (i) X(0), X(▵), …, X(n▵), where n is a fixed number of observations; (ii) X(0), X(▵), …, X(M▵), where M is the random number of observations required to have n complete 0-1 cycles.
Technical Note—A Note on the Near Optimality of “5-EOQ's Worth” Forecast Horizons
Authors: Schwarz Leroy B.
Published: November 2008

This note contributes analytical insight into Lundin and Morton's empirical observation concerning the near optimality of “5-EOQ's worth” forecast horizons. They observed that, using protective procedures, forecast horizons corresponding to 5-EOQ's supply guarantee a first-period decision no more than one percent above optimum in an infinite horizon, periodic review, deterministic production planning problem. This note presents similar analytical results for the corresponding infinite horizon, continuous review, deterministic model.
A Normative Methodology for Modeling Consumer Response to Innovation
Authors: Hauser John R. , Urban Glen L.
Published: November 2008

Consumer response determines the success or failure of new products and services. This paper proposes a methodology that integrates knowledge in the fields of psychometrics, utility theory, and stochastic choice theory to improve the design of new products and services. The methodology consists of a consumer response and a managerial design process. The design process is one of idea generation, evaluation, and refinement, while the consumer response is based on consumer measurement, models of the individual choice process, and aggregation of predictions of individual choices. The individual response model processes the consumer measures by first reducing them to an underlying set of perceptual dimensions. Then the measures of perception are combined to produce a scalar goodness measure for each choice alternative through a process called “compaction.” Next, homogeneous segments are defined based on similar preferences. The goodness measures for each consumer or segment are linked to probability of choice for the new products and services and for competing products and services. In each step theoretical, empirical, and statistical issues are identified. Various techniques are introduced and described for each phase. Selected techniques are demonstrated based on the survey data collected at MIT to support the design of a health maintenance organization (HMO) and in the consumer market to evaluate a new deodorant.
Bidding in Simultaneous Auctions with a Constraint on Exposure
Authors: Rothkopf Michael H.
Published: November 2008

We consider the problem of determining a profit maximizing set of sealed bids in simultaneous auctions that are independent except for a restriction on the total of all bids. Although the objective function is not concave, we show that a Lagrangian approach will often yield an optimal answer and, when it does not, will yield a good solution and a bound on possible further improvements. Characteristics of optimal sets of bids are proven. The methodology employed will be generally attractive for any problem that involves allocating a single resource among a large number of competing activities with convex-concave profit functions.
The Centers and Medians of a Graph
Authors: Minieka Edward
Published: November 2008

This paper extends previous results for calculating the centers and medians of a graph so that every point on every edge as well as all vertices are served.
Level Crossings in Point Processes Applied to Queues: Single-Server Case
Authors: Brill P. H. , Posner M. J. M.
Published: November 2008

This paper introduces a new methodology for obtaining the stationary waiting time distribution in single-server queues with Poisson arrivals. The basis of the method is the observation that the stationary density of the virtual waiting time can be interpreted as the long-run average rate of downcrossings of a level in a stochastic point process. Equating the total long-run average rates of downcrossings and upcrossings of a level then yields an integral equation for the waiting time density function, which is usually both a linear Volterra and a renewal-type integral equation. A technique for deriving and solving such equations is illustrated by means of detailed examples.
The Application of a Hankel Transformation to a Class of Circularly Symmetric Coverage Problems
Authors: Schroeter Gerhard
Published: November 2008

The expected coverage of a target with a circularly symmetric value density function by a circularly symmetric damage function, where the distance between their centers is a stochastic variable, is expressed in terms of Hankel transforms. In problems of this type, the Hankel transformation of order zero plays a role similar to that of the Fourier transformation in the case of ordinary convolution integrals. Several well-known singular results for circularly symmetric coverage problems are unified and generalized.
Technical Note—An Algorithm for the p-Median Problem
Authors: Narula Subhash C. , Ogbu Ugonnaya I. , Samuelsson Haakon M.
Published: November 2008

We present a branch-and-bound algorithm for solving the p-median problem. The bounds are obtained by solving the Lagrangian relaxation of the p-median problem using the subgradient optimization method. The proposed algorithm is simple, requires small core storage and computational time, and can be used for solving large problems. Comparative results are also reported.
Technical Note—On Converse Duality for a Nondifferentiable Programming Problem
Authors: Mond B.
Published: November 2008

Some authors have assumed that the Kuhn-Tucker constraint qualification is always satisfied in a mathematical programming problem in which the nonlinear constraints define a convex set with nonempty interior. That this assumption is incorrect is shown by counterexample.
An Offensive Earned-Run Average for Baseball
Authors: Cover Thomas M. , Keilers Carroll W.
Published: November 2008

This paper studies a baseball statistic that plays the role of an offensive earned-run average (OERA). The OERA of an individual is simply the number of earned runs per game that he would score if he batted in all nine positions in the line-up. Evaluation can be performed by hand by scoring the sequence of times at bat of a given batter. This statistic has the obvious natural interpretation and tends to evaluate strictly personal rather than team achievement. Some theoretical properties of this statistic are developed, and we give our answer to the question, “Who is the greatest hitter in baseball history?”
The Set-Covering Problem: A New Implicit Enumeration Algorithm
Authors: Etcheberry Javier
Published: November 2008

The set-covering problem is to minimize cx subject to Ax ≧ en over all binary n-vectors x. A is an m × n binary matrix and en is an n-vector of 1's. We develop a new implicit enumeration strategy to solve this problem. The branching strategy is similar to the row partitioning strategy used by other authors in the partitioning problem. Simple and sharp bounds are obtained by relaxing the constraints of the associated linear program by attaching nonnegative multipliers to them. Good multipliers are obtained by using the subgradient optimization technique. Computational experience shows that these bounds are at least one order of magnitude more efficient than the ones obtained by solving the associated linear program with the simplex method. Computational results with this new implicit enumeration algorithm are encouraging. Problems with as many as 50 constraints and 100 variables were solved in the order of 100 seconds of CPU time on an IBM 360-67.
The (S − 1, S) Inventory Model under Time Limit on Backorders
Authors: Das Chandrasekhar
Published: November 2008

Existing models of inventory control assume that when a stockout occurs customers either wait as long as necessary or not at all for the replenishment to arrive. This paper introduces a more realistic assumption—customers are assumed to wait a fixed amount of time before cancelling their orders. The new assumption is incorporated in the (S − 1, S) inventory model, which is appropriate for slow-moving items. Statistical and economic measures of performance for the model are developed on the basis of certain queuing results. We then use optimization techniques to derive a minimum-cost inventory policy with or without constraints on service levels. We also derive an optimal policy for trade-offs between inventory levels and replenishment rates and provide computational approaches.
Technical Note—A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges
Authors: Hong Saman , Padberg Manfred W.
Published: November 2008

We transform a multiple traveling salesman problem with fixed charges for the assignment of salesmen and with a symmetric cost matrix to a standard symmetric traveling salesman problem.
Technical Note—Bayesian Decision Making with Ordinal Information
Authors: Charnetski Johnnie R.
Published: November 2008

Conventional Bayesian decision-making models require decision makers to stipulate numerically, either directly or indirectly, a specific set of conditional densities (posterior distributions) on the state/ signal set. The method presented permits decision makers to use a Bayesian approach when only ordinal information, in the form of partial orders (possibly incomplete), exists concerning the likelihood of individual and/or joint state/signal occurrence. From the partial orders provided, the mean values of the reward functions may be statistically approximated and the choice of a best action selected. We present a variation of a well-known Bayesian decision problem.
Technical Note—An Eigenvector Condition for Markov Chain Lumpability
Authors: Barr D. R. , Thomas M. U.
Published: November 2008

Under certain conditions the state space of a discrete parameter Markov chain may be partitioned to form a smaller “lumped” chain that retains the Markov property. Existing statements of conditions on the transition matrix P of the original chain characterizing such lumpability are difficult to verify in practice, especially when the dimension of P is large. An alternate approach, based on the eigenvectors of P, is presented and illustrated with examples.
Technical Note—Cannibalization Policies for Multistate Systems
Authors: Khalifa David , Hottenstein Michael , Aggarwal Sumer
Published: November 2008

When spare parts are not available from conventional sources, cannibalization is often the only source of replacement. The interchange-ability of components, however, is restricted by part-type restrictions and by the cannibalization policy that is being followed. We investigate and compare the performance of six cannibalization policies, from no cannibalization to unrestricted cannibalization. Each policy is applied via computer simulation to fourteen distinctly defined machine configurations in which we manipulate the variable of the number of part-types.
Optimal Peremptory Challenges in Trials by Juries: A Bilateral Sequential Process
Authors: Roth Arthur , Kadane Joseph B. , Degroot Morris H.
Published: November 2008

This paper explores optimal strategies for the use of peremptory challenges in jury trials where the prospective jurors are examined and then either challenged or seated, one by one. We assume that the lawyers for each side do not necessarily agree about the probability that each prospective juror will vote for conviction, but that the assessment of each side is available to the other. The strategies we develop are optimal noncooperative sequential strategies in the sense that each side maximizes its expected utility at each stage under the assumption that both sides will continue to use these optimal strategies in all future decisions. Under certain regularity conditions we show that it is optimal to be the first side to decide whether to challenge any prospective juror. Necessary and sufficient conditions are given for an optimal strategy to be reversible, which means that it does not matter to either side whether it decides first or second. Specifically, the optimal strategy is reversible if the two sides always agree about the probability that each prospective juror will vote for conviction. We give an algorithm based on backward induction for finding the optimal strategies and discuss simple examples.
General Techniques for Combinatorial Approximation
Authors: Sahni Sartaj
Published: November 2008

This is a tutorial on general techniques for combinatorial approximation. In addition to covering known techniques, a new one is presented. These techniques generate fully polynomial time approximation schemes for a large number of NP-complete problems. Some of the problems they apply to are: 0-1 knapsack, integer knapsack, job sequencing with deadlines, minimizing weighted mean flow times, and optimal SPT schedules. We also present experimental results for the job sequencing with deadlines problem.
Simple Criteria for Optimal Portfolio Selection with Upper Bounds
Authors: Elton Edwin J. , Gruber Martin J. , Padberg Manfred W.
Published: November 2008

We present a new method for selecting optimal portfolios when upper-bound constraints on investments in individual stocks are present and when the variance-covariance matrix of returns possesses a special structure such as that implied by the standard single-index model. The method differs substantially from the usual nonlinear programming methods used in this context and allows the development of criteria that indicate important characteristics of a stock.
A Strategic Weapons Exchange Allocation Model
Authors: Bracken Jerome , Falk James E. , Miercort Frederic A.
Published: November 2008

We formulate a two-strike strategic weapons exchange, model as a max-min problem with the first striker's allocation affecting the second striker's feasible region. The max-min problem is shown to be equivalent to a separable, nonconvex program, to which an algorithm designed to locate an approximate global solution is then applied. The solution of three example problems is given.
A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times
Authors: Kise Hiroshi , Ibaraki Toshihide , Mine Hisashi
Published: November 2008

We consider a class of n-job one-machine scheduling problems with ready time r(i), processing time p(i), and due time d(i) for each job i. Preemption is not allowed, and precedence constraints among jobs are not assumed. For this problem we show that there is a 0(n2)-time algorithm to find a schedule that minimizes the number of tardy jobs, under the assumption that r(i) < r(j) implies d(i) ≤ d(j).
Scheduling to Minimize Maximum Cumulative Cost Subject to Series-Parallel Precedence Constraints
Authors: Abdel-Wahab H. M. , Kameda T.
Published: November 2008

Consider a set of events that are constrained by a certain precedence relation. Associated with each event is a cost (an integer), which may be interpreted as an additional number of resource units necessary for the event to occur (units are released if the cost is negative). It is desired to order the events into a single sequence in such a way that the maximum cumulative cost encountered (largest number of resource units used at one time) is minimized. It is known that this problem is in general NP-complete. For the special case where the precedence constraints can be represented by a series-parallel graph, we present an algorithm for finding an optimal schedule whose running time does not grow faster than the square of the number of events.
Technical Note—A New Proof of the Optimality of the Shortest Remaining Processing Time Discipline
Authors: Smith Donald R.
Published: November 2008

We present a new proof of the fact that for a work-conserving queue, the queuing discipline that always serves a job with the shortest remaining processing time minimizes the number of jobs in the system. A key feature of the proof is a definition of work dominance, allowing comparison of two systems based on the remaining service times of jobs present. Work dominance is both necessary and sufficient for stochastic comparison of the number of jobs present under identical but arbitrary arrival processes.
Complexity of Scheduling under Precedence Constraints
Authors: Lenstra J. K. , Rinnooy Kan A. H. G.
Published: November 2008

Precedence constraints between jobs that have to be respected in every feasible schedule generally increase the computational complexity of a scheduling problem. Occasionally, their introduction may turn a problem that is solvable within polynomial time into an NP-complete one, for which a good algorithm is highly unlikely to exist. We illustrate the use of these concepts by extending some typical NP-completeness results and simplifying their correctness proofs for scheduling problems involving precedence constraints.
Minimal Resources for Fixed and Variable Job Schedules
Authors: Gertsbakh Ilya , Stern Helman I.
Published: November 2008

We treat the following problem: There are n jobs with given processing times and an interval for each job's starting time. Each job must be processed, without interruption, on any one of an unlimited set of identical machines. A machine may process any job, but no more than one job at any point in time. We want to find the starting time of each job such that the number of machines required to process all jobs is minimal. In addition, the assignment of jobs to each machine must be found. If every job has a fixed starting time (the interval is a point), the problem is well-known as a special case of Dilworth's problem. We term it the fixed job schedule problem (FSP). When the job starting times are variable, the problem is referred to as the variable job schedule problem (VSP), for which no known exact solution procedure exists. We introduce the problems by reviewing previous solution methods to Dilworth's problem. We offer an approximate solution procedure for solving VSP based on the entropy principle of informational smoothing. We then formulate VSP as a pure integer programming problem and provide an exact algorithm. This algorithm examines a sequence of feasibility capacitated transportation problems with job splitting elimination side constraints. Our computational experience demonstrates the utility of the entropy approach.
The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
Authors: Picard Jean-Claude , Queyranne Maurice
Published: November 2008

The time-dependent traveling salesman problem may be stated as a scheduling problem in which n jobs have to be processed at minimum cost on a single machine. The set-up cost associated with each job depends not only on the job that precedes it, but also on its position (time) in the sequence. The optimization method described here combines finding shortest paths in an associated multipartite network with subgradient optimization and some branch-and-bound enumeration. Minimizing the tardiness costs in one-machine scheduling (in which the cost is a non-decreasing function of the completion time of each job) is then attacked by this method. A branch-and-bound algorithm is designed for this problem. It uses a related time-dependent traveling salesman problem to compute the required lower bounds. We give computational results for the weighted tardiness problem.
A Survey of Linear Cost Multicommodity Network Flows
Authors: Kennington Jeff L.
Published: November 2008

This exposition presents a state-of-the-art survey of results and algorithms for linear multicommodity network flow problems.
An Interactive Multiple-Objective Linear Programming Approach to a Problem in Forest Management
Authors: Steuer Ralph E. , Schuler Albert T.
Published: November 2008

In many situations it is under legislative mandate to manage publicly owned forest resources for multiple uses (e.g., timber production, hunting, grazing). The major obstacle that has been encountered in applying previously developed mathematical programming procedures to multiple-use forest management has been the difficulty in assessing the appropriate criterion weights required. To avoid the criterion weight estimation problem, an interactive multiple-objective linear programming approach, which does not require criterion weights of any kind, was developed in response to the needs of the multiple-use forest management problem. The procedure uses a combination of linear programming and vector-maximum techniques. At each iteration the cone generated by the gradients of the multiple objectives is contracted. On the last two iterations the most acceptable efficient extreme point is identified with the aid of a filtering device. As illustrated, the method has been applied to prepare preliminary management plans for a 10,000-acre sub-unit of a national forest.
Optimum Solution Structure for a Repairable Inventory Problem
Authors: Simpson Vincent P.
Published: November 2008

This paper proves that the optimum solution structure for an n-period repairable inventory problem is completely defined by three period dependent values: θn, the repair-up-to-level; δn, the purchase-up-to-level; and θn + ξn, the scrap-down-to-level. The specific problem examined includes fixed periodic reviews, instantaneous delivery of purchased and repaired units, backlogging of unsatisfied demand, random demand for serviceables, random return of repairables with any relationship being permitted between demand and returns and a convex differentiable cost function. The basic solution methodology is a backward dynamic programming technique in two dimensions with the Kuhn-Tucker saddle point theorems applied in each stage.
The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted Costs
Authors: Sondik Edward J.
Published: November 2008

This paper treats the discounted cost, optimal control problem for Markov processes with incomplete state information. The optimization approach for these partially observable Markov processes is a generalization of the well-known policy iteration technique for finding optimal stationary policies for completely observable Markov processes. The state space for the problem is the space of state occupancy probability distributions (the unit simplex). The development of the algorithm introduces several new ideas, including the class of finitely transient policies, which are shown to possess piecewise linear cost functions. The paper develops easily implemented approximations to stationary policies based on these finitely transient policies and shows that the concave hull of an approximation can be included in the well-known Howard policy improvement algorithm with subsequent convergence. The paper closes with a detailed example illustrating the application of the algorithm to the two-state partially observable Markov process.
Minimizing a Submodular Function on a Lattice
Authors: Topkis Donald M.
Published: November 2008

This paper gives general conditions under which a collection of optimization problems, with the objective function and the constraint set depending on a parameter, has optimal solutions that are an isotone function of the parameter. Relating to this, we present a theory that explores and elaborates on the problem of minimizing a submodular function on a lattice.