Search

The article presents a list of working papers related to management science. Some of the papers include "A Primal-Dual Surrogate Simplex Algorithm: Comparison with the Criss Cross Method," by R. S. Garfinkel and P. L. Yu, "Optimal Impulsive Trajectory Rendezvous Using Projection-Restoration," by W. A. Gruver, and "Asymptotic Normality of the Extremum of Certain Sample Functions," by P. K. Sen.

In this note we consider the validity of substituting a linear goal for a fractional goal in a mathematical program and provide a simple geometric interpretation that contrasts the essential differences between the two programs. [ABSTRACT FROM AUTHOR]

The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, for any given feasible flow, circuit flows of negative incremental costs. In the main theoretical result of this paper, it is proved that if at each stage, given a feasible nonoptimal flow X, the circuit flow with most negative incremental cost is added to X, linear convergence to the optimal solution will be obtained. In addition, this most negative incremental cost determines an upper bound on the difference in cost between the given feasible solution and the optimal. Based on these concepts, an algorithm, which preserves linear convergence, is presented to determine minimum cost flows in networks with convex costs in the arcs. Results of computer runs made for this algorithm are given. The special case of networks with linear costs is also considered. [ABSTRACT FROM AUTHOR]

Commentary is presented for an article published in the July 1960 issue of "Management Science," written by L. V. Kantorovich with an introductory note by T. C. Koopmans. According to the author, in his introduction Koopmans addresses in particular a linear programming problem and a matrix game presented by Kantorovich. Also presented is an interpretation of the article's treatment of decision variables and mathematical optimization. The author notes that the article presents algorithms that have been improved from their contemporary presentations.

Hub networks play an important role in many transportation and telecommunications systems. This paper introduces a new model called the hub arc location model. Rather than locate discrete hub facilities, this model locates hub arcs, which have reduced unit flow costs. Four special cases of the general hub arc location model are examined in detail. We provide motivation for the new models, and present examples and optimal solutions, using data for U.S. air passenger traffic. Results are used to compare optimal costs, hub locations, and hub arc locations with corresponding hub median optimal solutions. The results reveal interesting spatial patterns and help identify promising cities and regions for hubs. A companion paper (Campbell et al. 2005) presents integer programming formulations and solution algorithms for the new hub arc problems. It also provides details and computation times for these solution algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes and analyzes a periodic review inventory system with two replenishment modes. Regular orders are placed periodically following a base stock policy on inventory position, and arrive at the stocking location after a deterministic lead time. The location also has the option of placing emergency orders, characterized by a shorter lead time but higher acquisition cost, in case of imminent stock outs. Thus, at some appropriate time in the replenishment cycle, the necessity and size of an emergency order is determined according to a base stock policy on net stock. The timing of the emergency order is such that this order arrives and can be used to satisfy the demand in the time period just before the arrival of a regular order, when the likelihood of a stockout is highest. An approximate cost model is developed which can easily be optimized with respect to the order-up-to parameters. This model is used as the basis for a heuristic algorithm, which leads to solutions that are very close to the exact optimal solutions determined through simulation. It is shown that the proposed system offers substantial cost savings relative to a system without the emergency replenishment option. [ABSTRACT FROM AUTHOR]

This paper examines the effect of stochastic task times on the total operating costs of a continuously paced assembly line under the assumption that the line is stopped whenever at least one work station requires more time than allotted. A comprehensive stochastic cost function is integrated into an efficient balancing algorithm to enable an approximately minimum cost balance to be obtained. An experiment was conducted to determine the cost savings resulting from using the stochastic method as compared to two deterministic methods. The stochastic method of this paper produced lower cost balances in most cases studied. [ABSTRACT FROM AUTHOR]

We study in this paper dynamic equilibrium advertising strategies in a duopoly with asymmetric information structure and sequential play. The advertising model of Lanchester is used in a game where the relevant solution concept is feedback Stackelberg equilibrium, which is subgame perfect. An algorithm is devised for the computation of this equilibrium, and numerical results are reported and discussed. Using a data set from the cola market, we obtain the resulting advertising strategies and provide a comparison with closed-loop and open-loop Nash equilibria. [ABSTRACT FROM AUTHOR]

A companion paper (Campbell et al. 2005) introduces new hub arc location models and analyzes optimal solutions, with special attention to spatial pattens and relationships. This paper provides integer programming formulations and optimal solution algorithms for these problems. We describe two optimal solution approaches in detail and compare their performance, using standard hub location data sets. We present implementation details and show how algorithms can be fine tuned based on characteristics of the data. [ABSTRACT FROM AUTHOR]

Expert judgment is frequently used to assess parameter values of quantitative management science models, particularly in decision-making contexts. Experts can, however, only be expected to assess observable quantities, not abstract model parameters. This means that we need a method for translating expert assessed uncertainties on model outputs into uncertainties on model parameter values. This process is called probabilistic inversion. The probability distribution on model parameters obtained in this way can be used in a variety of ways, but in particular in an uncertainty analysis or as a Bayes prior. This paper discusses computational algorithms that have proven successful in various projects and gives examples from environmental modelling and banking. Those algorithms are given a theoretical basis by adopting a minimum information approach to modelling partial information. The role of minimum information is two-fold: It enables us to resolve the problem of nonuniqueness of distributions given the information we have, and it provides numerical stability to the algorithm by guaranteeing convergence properties. [ABSTRACT FROM AUTHOR]

This paper describes a hybrid method for solving the multi-commodity transportation and transshipment spatial equilibrium models. The method is basically a specialization of the block successive overrelaxation method for solving a linear complementarity problem with certain block structure and consists of solving a sequence of subproblems of the single-commodity type. These subproblems are solved by a special-purpose principal pivoting algorithm developed in an earlier paper. Under some mild conditions, convergence of the proposed method is established. Finally, computational experience of solving some fairly large randomly generated problems by the proposed hybrid method is presented. [ABSTRACT FROM AUTHOR]

New lock box solution techniques have recently been suggested by Stone and Nauss-Markland. This paper briefly discusses these new methodologies and shows how the algorithms can be combined into a third solution procedure which exploits the computational efficiency of the Stone heuristic and retains the optimizing property of the Nauss-Markland algorithm. [ABSTRACT FROM AUTHOR]

The most popular approach to developing mathematical models of organizational decision processes, the decomposition approach, begins with a mathematical statement of an ideal organizational problem and follows a process of decomposition to derive sub-problems solved by separate units at (possibly) different levels of the organization. Conversely, the composition approach starts with mathematical statements of the subproblems solved by the separate units and proceeds to develop a solution algorithm as a means of coordinating the activities of the separate units. A process of composition must then be followed if one is to discover the derived, organizational problem actually solved. This paper offers an operational definition of an organizational decision process and relates this process to the anatomy of mathematical models purported as being representative of it. Implications regarding the potential of the decision process models as tools of organizational design are explored. [ABSTRACT FROM AUTHOR]

In this paper we study a class of modified policy iteration algorithms for solving Markov decision problems. These correspond to performing policy evaluation by successive approximations. We discuss the relationship of these algorithms to Newton-Kantorovich iteration and demonstrate their covergence. We show that all of these algorithms converge at least as quickly as successive approximations and obtain estimates of their rates of convergence. An analysis of the computational requirements of these algorithms suggests that they may be appropriate for solving problems with either large numbers of actions, large numbers of states, sparse transition matrices, or small discount rates. These algorithms are compared to policy iteration, successive approximations, and Gauss-Seidel methods on large randomly generated test problems. [ABSTRACT FROM AUTHOR]

This paper, which is presented in two parts, is a contribution to the theory of fractional programming, i.e. maximization of quotients subject to constraints. In Part 1, duality theory for linear and concave-convex fractional programs is developed and related to recent results by Bector, Craven-Mond, Jagannathan, Sharma-Swarup, et al. Basic duality theorems of linear, quadratic and convex programming are extended. In Part II Dinkelbach's algorithm solving fractional programs is considered. The rate of convergence as well as a priori and a posteriori error estimates are determined. In view of these results the stopping rule of the algorithm is changed. Also the starting rule is modified using duality as introduced in Part I. Furthermore a second algorithm is proposed. In contrast to Dinkelbach's procedure the rate of convergence is still controllable. Error estimates are obtained too. [ABSTRACT FROM AUTHOR]

One of the most computationally useful ideas of the 1970s is the observation that many hard integer programming problems can be viewed as easy problems complicated by a relatively small set of side constraints. Dualizing the side constraints produces a Lagrangian problem that is easy to solve and whose optimal value is a lower bound (for minimization problems) on the optimal value of the original problem. The Lagrangian problem can thus be used in place of a linear programming relaxation to provide bounds in a branch and bound algorithm. This approach has led to dramatically improved algorithms for a number of important problems in the areas of routing, location, scheduling, assignment and set covering. This paper is a review of Lagrangian relaxation based on what has been learned in the last decade. [ABSTRACT FROM AUTHOR]

We demonstrate a numerically exact method for evaluating the time-dependent mean, variance, and higher- order moments of the number of entities in the multiclass [Pht/Pht/∞]K queueing network system, as well as at the individual network nodes. We allow for multiple, independent, time-dependent entity classes and develop time-dependent performance measures by entity class at the nodal and network levels. We also demonstrate a numerically exact method for evaluating the distribution function and moments of virtual sojourn time through the network for virtual entities, by entity class, arriving to the system at time t. We include an example using software that we have developed and have put in downloadable form in the Online Supplement to this paper on the journal's website. [ABSTRACT FROM AUTHOR]

In this paper, we present a branch-and-price method to solve special structured multistage stochastic integer programming problems. We validate our method on two different versions of a multistage stochastic batch-sizing problem (SBSP). One version adopts a recourse formulation, and the other is based on probabilistic constraints. Our algorithmic approach is applicable to both formulations. Our computational results suggest that both classes of problems can be solved using relatively few nodes of a branch-and-price tree. The success of our approach calls for extensions in methodology as well as applications. [ABSTRACT FROM AUTHOR]

Motivated by applications in freight handling and open-pit mining, Rhys, Balinski, and Picard studied the problems of selection and closure in papers published in Management Science in 1970 and 1976. They identified efficient algorithms based on linear programming and maximum-flow/minimum-cut procedures to solve these problems. This research has had major impact well beyond the initial applications, reaching across three decades and inspiring work on numerous applications and extensions. The extensions are nontrivial optimization problems that are of theoretical interest. The applications ranged from evolving technologies, image segmentation, revealed preferences, pricing, adjusting utilities for consistencies, just-in-time production, solving certain integer programs in polynomial time, and providing efficient 2-approximation algorithms for a wide variety of hard problems. A recent generalization to a convex objective function has even produced novel solutions to prediction and Bayesian estimation problems. This paper surveys the streams of research stimulated by these papers as an example of the impact of Management Science on the optimization field and an illustration of the far-reaching implications of good original research. [ABSTRACT FROM AUTHOR]

One of the basic assumptions of the classical dynamic lot-sizing model is that the aggregate demand of a given period must be satisfied in that period. Under this assumption, if backlogging is not allowed, then the demand of a given period cannot be delivered earlier or later than the period. If backlogging is allowed, the demand of a given period cannot be delivered earlier than the period, but it can be delivered later at the expense of a backordering cost. Like most mathematical models, the classical dynamic lot-sizing model is a simplified paraphrase of what might actually happen in real life. In most real-life applications, the customer offers a grace period--we call it a demand time window--during which a particular demand can be satisfied with no penalty. That is, in association with each demand, the customer specifies an acceptable earliest and a latest delivery time. The time interval characterized by the earliest and latest delivery dates of a demand represents the corresponding time window. This paper studies the dynamic lot-sizing problem with demand time windows and provides polynomial time algorithms for computing its solution. If backlogging is not allowed, the complexity of the proposed algorithm is O(T²) where T is the length of the planning horizon. When backlogging is allowed, the complexity of the proposed algorithm is O(T³). [ABSTRACT FROM AUTHOR]

In this paper, we focus on a useful modeling concept that is frequently ignored while formulating discrete optimization problems. Very often, there exists a natural symmetry inherent in the problem itself that, if propagated to the model, can hopelessly mire a branch-and-bound solver by burdening it to explore and eliminate such alternative symmetric solutions. We discuss three applications where such a symmetry arises: a telecommunications network design problem, a noise pollution problem, and a machine procurement and operation problem. For each case, we identify the indistinguishable objects in the model that create the problem symmetry and show how imposing certain decision hierarchies within the model significantly enhances its solvability, while using a popular modern-day commercial branch-and-cut software (CPLEX 6.5). [ABSTRACT FROM AUTHOR]

In order to discuss scheduling algorithms for time-sharing computer systems, this paper analyzes the M/G/1 queue under the well known round-robin (RR) discipline. Three models are considered: the constant-quantum RR model, the processor-shared (or zero-quantum RR) model, and the variable-quantum RR model. The paper proposes an effective calculating method for obtaining the expected response time under an arbitrary processing-time distribution with overhead. By the theoretical analysis, one can show how the response time is affected by the scheduling and processing-time distributions, as is demonstrated by some typical examples. [ABSTRACT FROM AUTHOR]

In an earlier paper [20] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions. [ABSTRACT FROM AUTHOR]

This paper considers "critical path" networks which are used for the planning and scheduling of projects that consist of well defined sequences of individual activities. When the number of activities is large, it becomes difficult to prepare a network for the project as one unit, and it may also be difficult to store the network in the high speed memory of a digital computer. Also, in the cases where there are two or more independent projects, which are weakly inter-related by common activities, the problem of efficient scheduling of all the projects becomes quite difficult. This paper presents a method to "tear" or "decompose" a project network into several subnetworks, schedule the subnetworks and then to put the subnetworks back together. A computational algorithm is first given for time-only networks; then two computational formulations are given for cost-time network of project subnetworks. The latter essentially generalize the algorithm due to Fulkerson, in order to handle piecewise linear, convex, cost-time curves for some or all of the activities. [ABSTRACT FROM AUTHOR]

This paper gives a detailed description of an algorithm for the solution of a specialized Linear Programming model, to be called the Machine Loading model. It is a generalization of the Transportation Problem, in that weighting factors are applied to the individual elements which form the row and column sums. For the Machine Loading model, the simplex method reduces to a specialized algorithm which generalizes the stepping stone method of the Transportation Problem [2], [3]. With the resulting generalized stepping stone method, it becomes practicable to solve many large-scale problems for which the direct application of the simplex method would be impracticable. The present paper is restricted to a discussion of the following topics: (I) the general characteristics of the model and its topological features; (ii) a detailed solution algorithm, including a consideration of degenerate cases and the use of a computer; (iii) a more restrictive capacitated model and the corresponding modifications to the solution algorithm; and (iv) the complete illustrative solution of a numerical example. The purpose is to aid interested readers in gaining familiarity with the algorithm and facility in the solution of numerical problems. No derivations or proofs will be included. [ABSTRACT FROM AUTHOR]

The purpose of the present paper is to extend the loop-technique of the stepping-stone algorithm to the generalized transportation problem. The main result (Theorem and Corollary of §6) is, that passing from a basic feasible solution to another one may always be carried out by constructing a simple symmetrical or a double loop (as defined in §2) and computing new values for the variables only along this path. The amount of computations needed for this turns out to be substantially reduced as compared to the usual way of solving the system of equations relating the new basis to the old one. [ABSTRACT FROM AUTHOR]

This paper investigates the effect upon performance in a service system, such as a telephone call center, of giving waiting customers state information. In particular, the paper studies two M/M/s/r queueing models with balking and reneging. For simplicity, it is assumed that each customer is willing to wait a fixed time before beginning service. However, customers differ, so the delay tolerances for successive customers are random. In particular, it is assumed that the delay tolerance of each customer is zero with probability beta, and is exponentially distributed with mean alpha[sup-1] conditional on the delay tolerance being positive. Let N be the number of customers found by an arrival. In Model 1, no state information is provided, so that if N is greater than or equal to s, the customer balks with probability beta; if the customer enters the system, he reneges after an exponentially distributed time with mean alpha[sup-1] if he has not begun service by that time. In Model 2, if N = s + k is greater than or equal to s, then the customer is told the system state k and the remaining service times of all customers in the system, so that he balks with probability beta + (1 - beta)(1 - q[subk]), where q[subk] = P(T > S[subk]), T is exponentially distributed with mean alpha[sup-1], S[subk] is the sum of k + 1 independent exponential random variables each with mean (s mu)[sup-1], and mu[sup-1] is the mean service time. In Model 2, all reneging is replaced by balking. The number of customers in the system for Model 1 is shown to be larger than that for Model 2 in the likelihood-ratio stochastic ordering. Thus, customers are more likely to be blocked in Model I and are more likely to be served without waiting in Model 2. Algorithms are also developed for computing important performance measures in these, and more general, birth-and-death models. [ABSTRACT FROM AUTHOR]

Recent research in the theory of algorithms has determined that many classical operations research problems are computationally related; i.e., an efficient algorithm for one implies the existence of efficient algorithms for everyone or a proof that one is inherently difficult implies they are all so. This paper presents a tutorial of this concept. In contrast to other surveys it does so by selecting a few problems (knapsack, traveling salesperson, multiprocessor scheduling, and flow shop) and carefully shows how they are related. References to most other problems of interest to operations researchers are given. The second part of this paper is a survey on the relatively recent progress in the study of approximation algorithms. These algorithms hold great promise for they work fast and in many cases are guaranteed to work well. Again the techniques for devising and analyzing these algorithms are explained through the continued use of these examples. [ABSTRACT FROM AUTHOR]

The problem of determining consistent and realistic reorder intervals in complex production-distribution environments was formulated as a large scale, nonlinear, integer programming problem by Maxwell and Muckstadt (1985). They show how the special structure of the problem permits its solution by a standard network flow algorithm. In this paper, we review the Maxwell-Muckstadt model, provide necessary and sufficient conditions that characterize the solution, and show that the optimal partition of nodes in the production-distribution network is invariant to an arbitrary scaling of the set-up and holding cost parameters. We consider two capacitated versions of the model: one with a single constrained work center, and the other with multiple constrained work centers. For single constraint problems, the invariance corollary provides a simple closed-form solution. For the multiple work center problem, the invariance corollary is exploited in the development of a Lagrange multiplier method of solution. The technique is illustrated by means of a small example problem and a problem taken from a real industrial setting. [ABSTRACT FROM AUTHOR]

Biomass conversion processes have the potential for satisfying approximately 25% of the national demand for methane gas. At the present time, very little analytical work has been done to optimally design and operate the production facilities associated with these processes. This study was motivated by the high cost of these systems and the attendant need for efficient operation. While in storage, biomass decays (exponentially) over time, and gas production declines (exponentially) with time. The basic operational problem is to determine the optimal residence times for batches in the anaerobic digester to maximize total production over a fixed planning horizon. This paper provides analysis to characterize the form of the optimal policy and presents an efficient algorithm for obtaining the solution. An example problem, based upon realistic biomass and digester data, is used to illustrate the algorithm as well as the behavior of the optimal solution. [ABSTRACT FROM AUTHOR]

This paper is concerned with the solution of linearly constrained zero-one quadratic programming problems. Problems of this kind arise in numerous economic, location decision, and strategic planning situations, including capital budgeting, facility location, quadratic assignment, media selection, and dynamic set covering. A new linearization technique is presented for this problem which is demonstrated to yield a tighter continuous or linear programming relaxation than is available through other methods. An implicit enumeration algorithm which uses Lagrangian relaxation, Benders' cutting planes, and local explorations is designed to exploit the strength of this linearization. Computational experience is provided to demonstrate the usefulness of the proposed linearization and algorithm. [ABSTRACT FROM AUTHOR]

In this paper, the joint problem of ordering and offering price discount by a supplier to his sole/major buyer is analyzed. The objective is to induce the buyer to alter his order schedule and size so that the supplier can benefit from lower set up, ordering, and inventory holding costs. We generalize the quantity discount pricing model of Monahan (1984) to: (1) explicitly incorporate constraints imposed on the amount of discount that can be offered; and (2) relax the implicit assumption of a lot-for-lot (or order-for-order) policy adopted by the supplier. An algorithm is developed to solve the suppliers joint ordering and price discount problem. [ABSTRACT FROM AUTHOR]

This paper presents multiperiod, multiple objective goal programming as an alternative to the more conventional hedge ratio approaches to financial futures hedging. The described model offers the potential benefits off (i) simultaneous achievement of multiple hedge-related objectives (i.e., minimization of transactions and margin opportunity costs; regulation of cash flow, and maximization of profits accruing from both the cash and futures positions); and (ii) periodic modification and updating of the futures position, as suggested by actual, observed prices and interest rates, throughout the hedging period. To assess its overall effectiveness, the model was applied to develop appropriate hedging strategies for three separate time periods, each representing a unique interest rate trend (i.e., upward movement, downward movement, and no change). Since real-world implementation of the model requires the use of forecast data, independent forecasts of both cash and futures prices were generated via (1) moving average, (2) exponential smoothing, and (3) random walk techniques. In progressing through each of the 13-week time periods, all forecasts were updated with the previous weeks' actual price data. Revised forecasts and actual price data were then incorporated into the model constraints on a weekly schedule. This approach, in essence, provided weekly futures activity recommendations based on the most recent price and interest rate developments observed at any point during the hedging period. The realized gains or losses were then compared to the previously-derived "perfect foresight" model results and to the traditional hedge ratio remits. This allowed for evaluation of the model's effectiveness under varying forecast methods and varying interest rate trends. The results show that the goal programming model outperformed other strategies in most cases. [ABSTRACT FROM AUTHOR]

This paper considers a one-machine scheduling problem where the objective is to minimize the sum of weighted completion times subject to release dates. A polynomial time algorithm is developed for the case when the jobs are clustered. The jobs in each cluster must be processed sequentially and the clusters are ordered. The insights developed are used in an efficient heuristic for the weighted completion time problem without clusters. Also, a class of release date problems is described for which the heuristic finds an optimal solution. [ABSTRACT FROM AUTHOR]

Most scheduling research has considered optimizing a single performance measure (criterion). In this paper we consider the problem of scheduling jobs on a single machine when the desirability of a schedule is evaluated using more than one performance measure. The procedures developed here can be used to construct trade-off curves among selected performance measures. The importance of the trade-off curve is that it provides the complete set of possibly optimal solutions for any objective function (cost function) involving only the selected performance measures. With this information, a manager can concentrate on selecting the most preferred schedule from the set. Algorithms are presented for the three two-criteria problems utilizing mean flow time, maximum tardiness, and number of tardy jobs and the three-criteria problem involving all of these criteria. Computational results for the four algorithms are provided. The most striking result is that the number of efficient solutions is very small in comparison to the number of permutation schedules for all three two-criteria problems and only modestly larger for the three-criteria problem. This has the managerial significance that, irrespective of the individual manager's specific trade-offs between the criteria, the number of possibly optimal schedules that need to be considered is relatively small. Several research directions on heuristic approaches, man-machine interactive approaches, computational efficiency, etc. are possible for the type of problem studied. The work reported here has the potential to stimulate research incorporating multiple performance measures in more complex scheduling models. [ABSTRACT FROM AUTHOR]

This paper gives optimality conditions to obtain a priori precedence relationships among some of the jobs in a single machine scheduling problem so as to curtail the enumeration while using branch-and-bound technique. The objective is to minimize a quadratic (or generalized quadratic) penalty function of job completion times. [ABSTRACT FROM AUTHOR]

An important aspect of the efficient design of an automatic transfer line is the ability to understand and predict the effects of the system parameters such as the size of the intermediate buffer storage space, the cycle times, failure times, repair times, and scrap rate, on the production rate of the transfer line. In this paper we develop an efficient algorithm to compute the production rate of a two-stage transfer line for different system parameters. The algorithm is developed assuming that the failure and repair times are geometrically distributed and that the units may be scrapped with a certain probability when the machine processing it fails. Using this algorithm, extensive numerical results are obtained. Based on these numerical results, the behavior of the transfer line is discussed and some interesting observations are reported which would be useful in the design of automatic transform lines. [ABSTRACT FROM AUTHOR]

Single server queues with batch arrivals are useful in the modeling of computer and communication systems amongst others. In this paper we give for a wide class of single server queues with batch arrivals a stable recursive method to compute state probabilities both at arrival and at arbitrary epochs. This class includes finite capacity models with state dependent Markovian input in which batches could be totally or partially rejected. The customers of a batch are served individually and the service time has a general distribution function. In particular, we discuss as application the computation of operating characteristics, such as rejection probability and probability of server idleness, for a finite capacity M/G/1 queue for which arriving customers are rejected if their waiting plus service times exceed the capacity of the system. [ABSTRACT FROM AUTHOR]

This paper presents a simplex-based solution procedure for the multiple objective linear fractional programming problem. By (1) departing slightly from the traditional notion of efficiency and (2) augmenting the feasible region as in goal programming, the solution procedure solves for all weakly efficient vertices of the augmented feasible region. The article discusses the difficulties that must be addressed in multiple objective linear fractional programming and motivates the solution algorithm that is developed. [ABSTRACT FROM AUTHOR]

The objective of the one-center model (single facility minimax location in the plane) is changed to be the maximum weighted number of demand points within a given weighted distance from the facility. The paper presents an O(n^2 log n) algorithm for the model along with some computational experience. [ABSTRACT FROM AUTHOR]

This paper describes a branch and bound approach for optimizing a media selection problem, namely, to choose the best set of mailing lists to maximize audience reach. Prompted by a national retailer's interest in more effective and efficient direct mail catalogue distribution, the algorithm exploits current heuristic approaches which improve computational efficiency. A numerical example and computational experience using actual data are discussed, along with extensions to other practical situations. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for deploying a crime directed patrol force. The optimization problem is formulated as the allocation of N patrol units among R high crime regions so as to maximize the weighted probability of a patrol intercept of a crime. The algorithm has full sensitivity analysis capabilities. This capability is critical because the model's input parameters include (1) crime weights, which in general will have a subjective component, (2) crime descriptive data, which are difficult to estimate, and (3) crime frequency data, which are likely to change with time. The paper presents an illustrative application of the algorithm. The resultant allocation is compared to a strategy which allocates patrol units in direct proportion to each region's total crime rate. The optimal allocation significantly increased the probability of an intercept. [ABSTRACT FROM AUTHOR]

In this paper we describe an integer programming algorithm for allocating limited resources to competing activities (jobs, tasks, etc.) of a project such that the completion time of the project is minimal among all possible completion times. Typical of such problems is the minimization of the completion time of projects of the PERT/CPM variety where limits on resource availability force the postponement of selected activities during project performance. Also included in this class of problems for which our procedure is applicable is the assignment Of jobs to machines such that the 'elapsed time for Completing all jobs (makespan) is a minimum over all possible job-machine assignments. The procedure developed consists of a systematic evaluation (enumeration) of all possible job finish times for each task in the project. To limit the number of task assignments which have to be explicitly evaluated, an artifice called a network cut is developed which removes from consideration the evaluation of job finish times which cannot lead to a reduced project completion time. Results reported demonstrate that the procedure developed is a reliable Optimization technique for projects consisting of up to 30-50 jobs and three different resource types. The procedure is particularly applicable in those instances in which computer primary storage is limited. Many of the mini-computers available today are capable of implementing our approach without extensive programming being required for writing to auxiliary storage, making the technique available to the project manager in those environments in which extensive computer resources for scheduling are not readily available. [ABSTRACT FROM AUTHOR]

One of the major contributions to the planning and management of Research and Development organizations is the evolution of methods for dealing with PERT-Cost or CPM-Cost problems. Classically however, variations of the critical path-cost (CPM-Cost) problem, arising when different cost duration relationships are assumed, have been mostly studied via techniques other than dynamic programming. If the precedence relations possess a serial structure, one can develop two essentially equivalent dynamic programming formulations, of the resource allocation variety, by minimizing either the project cost or the completion time. When nonserial precedence relationships are involved, this problem cannot be solved by routine invocation of conventional dynamic programming formulations or algorithms. The intent of this paper is to show that efficient nonserial dynamic programming formulations can be developed for several complex nonserial CPM-Cost problem situations. In particular, the project time minimization procedure results in less complex dynamic programming models and is thus employed in this paper. Three recent computational reduction techniques based primarily on the introduction of the artifice of pseudo-tasks and pseudo-stages are invoked to treat different variations of this essentially nonserial critical path-cost problem. Considerable savings in computational requirements are achieved by consolidating all phases preceding a junction node prior to the invocation of the dynamic programming procedure. The advantages of these approaches over existing mathematical programming methods include their ability to handle nonlinear cost functions and constraints, as well as their highly efficient parametrization capabilities. Further, the complexity of the dynamic programming formulation does not, unlike other methods, increase with the number of phases (tasks) but only with the degree in which the additional tasks change the structure of the precedence relations. [ABSTRACT FROM AUTHOR]

Many nonlinear programming algorithms utilize a one-dimensional search along directions generated by the algorithm. This paper describes a method for performing this search. The method finds 3 points which bracket the minimum, fits a quadratic through them to yield a fourth point, then fits successive cubics through 4 points, discarding one each time, until certain stop criteria are met. No gradient evaluations are required. Detailed flow charts of this procedure are given, and its performance is compared with that of 2 other algorithms. Eight test problems are used in this comparison, each solved using both exterior and interior penalty functions. The Davidon-Fletcher-Powell method is used to generate the search directions. Results show that the proposed procedure requires about ½ to ¾ the computer time of its nearest competitor, a procedure designed to be especially efficient when applied to penalty functions, and about &frac13 the time of the other competitor, the 2 point cubic search using derivatives. [ABSTRACT FROM AUTHOR]

This paper is intended to present a simple and quick method for obtaining approximate solutions to large scale zero-one programming problems. The method does not use enumeration. Instead, it assigns measures of preferability to zero-one variables that change the values of the variables from zero to one. The method yields very good approximate solutions to zero-one programming problems in dramatically short computation time. Even for problems involving more than a thousand zero-one variables the computation time is of little concern. The method is applicable not only to those problems associated with obtaining the optimal package of variables with the value one but also to a great variety of binary choice ("Yes-No") problems. [ABSTRACT FROM AUTHOR]

This paper considers fluid analogues for the standard linear programming problem and for a separable nonlinear programming problem. In the former case the usual duality results are demonstrated using the principle of minimum potential energy. In addition by examining the dynamics of the system a new method, referred to as the R-method, is derived for solving linear programmes, although it is not demonstrated that this has any computational advantages over the standard simplex method, except that degeneracy causes no problems. In the nonlinear case the weak Lagrangian principle is derived. The purpose of the paper is to demonstrate that analogue methods, while being impracticable as a physical method of solving optimisation problems, may give some insight into computational algorithms via dual energy concepts and/or dynamic behaviour. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to furnish a computational scheme for a class of programming problems with nonlinear constraints. The algorithm is sequential in nature, producing a sequence of feasible solutions whose limit points are optimal solutions of the original problem. Further, with a view to accelerating convergence we suggest two variants of the solution procedure. [ABSTRACT FROM AUTHOR]

A mean-variance portfolio selection model suitable for the small investor is formulated as a sequence of quadratic integer programming problems. The special structure of these quadratic problems is exploited in a partial enumeration algorithm which uses cutting planes to accelerate convergence. Computational experience is reported on problems ranging in size from fifteen to fifty variables. [ABSTRACT FROM AUTHOR]

This part of the paper introduces some possible implementations of Self-Scaling Variable Metric algorithms based on the theory presented in Part I. These implementations are analyzed theoretically and discussed qualitatively. A special class of SSVM algorithms is introduced, which has the additional property of being invariant under scaling of the objective function or of the variables. Experimental results are provided for a particular case of this class. This case has been tested in comparison to the DFP algorithm on a variety of functions with up to 50 variables. The results indicate that the new method has substantial advantage for functions with a large number of variables. [ABSTRACT FROM AUTHOR]