Search

The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.

This paper examines properties and interrelations of several concepts of generalized concavity. It shows that the class of functions that are both ‘generalized concave’ and ‘generalized convex’ is closely related to the class of monotone functions of a single variable. After excluding a certain small class of exceptions, the paper shows that, for arbitrary (perhaps not differentiable) functions, concave implies pseudoconcave, pseudoconcave implies strictly quasiconcave, and strictly quasiconcave implies quasiconcave. Several results characterizing the extreme values of generalized concave functions are given. [ABSTRACT FROM AUTHOR]

This paper considers the mathematical properties of chance constrained programming problems where the restriction is on the joint probability of a multivariate random event. One model that is considered arises when the right-hand side constants of the linear constraints are random. Another model treated here occurs when the coefficients of the linear programming variables are described by a multinormal distribution. It is shown that under certain restrictions both situations can be viewed as a deterministic nonlinear programming problem. Since most computational methods for solving nonlinear programming models require the constraints be concave, this paper explores whether the resultant problem meets the concavity assumption. For many probability laws of practical importance, the constraint in the first type of model is shown to violate concavity. However, a simple logarithmic transformation does produce a concave restriction for an important class of problems. The paper also surveys the `generalized linear programming' method for solving such problems when the logarithmic transformation is justified. For the second type model, the constraint is demonstrated to be nonconcave. [ABSTRACT FROM AUTHOR]

This paper deals with a nonstationary discrete-time Markov process whose transition probabilities vary periodically in time. Each transition results in a reward that varies within the same cycle as the transition matrix. For infinite processes a policy-iteration algorithm is developed that effectively determines an optimal policy maximizing the total discounted reward. The paper represents an extension of B. A. HOWARD'S policy-iteration technique for stationary Markov processes, A numerical example is given in which the developed iteration algorithm is demonstrated. [ABSTRACT FROM AUTHOR]

The multi-index transportation problem is defined and a summary of the algorithm described in an earlier paper is given. This paper discusses the theorems justifying the use of the algorithm and gives a necessary condition for the existence of a solution. It also describes the formulation of three special-structure linear-programming problems as examples of multi-index problems. The three problems discussed are the capacitated Hitchcock problem, transportation where there is more than one method of transport available, and the transformation of one type of multi-index problem into another. A final section describes problems that have restrictions in the form of inequalities. [ABSTRACT FROM AUTHOR]

A complementary programming problem is a linear programming problem with the additional restriction that xpxq=0 holds for each specified pair (xp, xq). This paper obtains constraints called C-cuts from the restriction xpxq=0, and uses them to facilitate the computation of the branch-and-bound procedure proposed in an earlier paper [Opns. Res. 19, 1523–1528 (1971)]. Some computational results are also reported. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm that will minimize the total processing time for a particular case of the n-job, m-machine scheduling problem. In many industrial processes, jobs are processed by a given sequence of machines. Often, once the processing of a job commences, the job must proceed immediately from one machine to the next without encountering any delays en route. The machine sequence need not be the same for all jobs. Because of this processing constraint that prohibits intermediate queues, most normal scheduling techniques are not applicable. This paper obtains a solution to this constrained scheduling problem by modeling it as a traveling-salesman problem; known solution techniques can then be employed. The paper solves a sample problem and discusses computational considerations. [ABSTRACT FROM AUTHOR]

This paper seeks here a minimum cost production plan over a finite number of time periods. There is a known demand requirement (stated in production hours) to be met in each period from current and previous hours of production (stored as inventory). A production policy consists of scheduled amounts of hours, some of which are costed at regular-time wage rates, the remainder costed at overtime rates. Expansion or contraction of the work force (stated in production hours) is charged against the period-to-period variations in regular-time employment. The fluctuations in overtime production do not incur such hiring and firing costs. The amount of overtime used, however, is constrained not to exceed a specified fraction of regular-time utilized in any period. We describe algorithms for finding an optimal policy under the assumption that all costs are described by linear functions and where demands are either monotonic increasing or decreasing in time. In addition to presenting the algorithms, we also examine certain planning horizon results implied by these algorithms. Specifically, we ascertain when optimal first period decisions can be made without knowing the precise values of all future demands and costs. [ABSTRACT FROM AUTHOR]

This paper approaches the assembly-line balancing problem as a sequencing problem involving precedence constraints that prohibit the occurrence of certain orderings. This approach permits the formulation of a dynamic programming algorithm for the exact solution of small assembly-line balancing problem. A generalization of this algorithm combined with a successive approximations technique is used for the solution of large problems. In addition, certain combinatorial problems associated with partially ordered sets are formulated and discussed in detail. These problems arise whenever sequencing problems with precedence constraints are treated by dynamic programming techniques. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for finding the K loopless paths that have the shortest lengths from one node to another node in a network. The significance of the new algorithm is that its computational upper bound increases only linearly with the value of K. Consequently, in general, the new algorithm is extremely efficient as compared with the algorithms proposed by Bock, Kantner, and Haynes [2], Pollack [7], [8], Clarke, Krikorian, and Rausan [3], Sakarovitch [9] and others. This paper first reviews the algorithms presently available for finding the K shortest loopless paths in terms of the computational effort and memory addresses they require. This is followed by the presentation of the new algorithm and its justification. Finally, the efficiency of the new algorithm is examined and compared with that of other algorithms. [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 presents a pseudo-boolean formulation of location problems based on a concept of a ‘dummy’ supply source activated outside a given distribution. First, it formulates a simple location problem as a pseudo-boolean function that can be optimized with existing boolean optimization algorithms. Later the formulation is extended to multidimensional location problems. Two such problems are analyzed: the first involves a distribution system with plants for production of different commodities; the second involves a distribution system with consumer demand and its pattern varying with time. [ABSTRACT FROM AUTHOR]

This paper considers the static flowshop-scheduling problem with the objective of minimizing, as a cost function, the mean job-completion time. Within the more general framework of combinatorial optimization problems, it defines a heuristic search technique--an approach that has been successful in the past in obtaining near-optimal solutions for problems that could not be solved exactly, either for lack of theory or because of exorbitant computational requirements. The paper presents a two-phase algorithm: The first phase searches among schedules with identical processing orders on all machines; the second refines the schedule by allowing passing. Results of computer study are presented for a large ensemble of pseudorandom problems, and for two particular problems previously cited in the literature. The method is shown to provide solutions that are exceptionally low in cost, and superior to those provided by sampling techniques in the cases for which comparison is possible. Computation time is also discussed and is given in machine-independent terms. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for solving resource-constrained network scheduling problems, a general class of problems that includes the classical job-shop-scheduling problem. It uses Lagrange multipliers to dualize the resource constraints, forming a Lagrangian problem in which the network constraints appear explicitly, while the resource constraints appear only in the Lagrangian function. Because the network constraints do not interact among jobs, the problem of minimizing the Lagrangian decomposes into a subproblem for each job. Algorithms are presented for solving these subproblems. Minimizing the Lagrangian with fixed multiplier values yields a lower bound on the cost of an optimal solution to the scheduling problem. The paper gives procedures for adjusting the multipliers iteratively to obtain strong bounds, and it develops a branch-and-bound algorithm that uses these bounds in the solution of the scheduling problem. Computational experience with this algorithm is discussed. [ABSTRACT FROM AUTHOR]

This paper presents new types of cutting-plane algorithms for integer-constrained optimization problems. The underlying idea of the method of enumerative cuts is to make use of an enumeration procedure in order to construct cutting planes that can be made arbitrarily deep. In recent publications, BALLAS and YOUNG have established in somewhat different contexts that valid cutting planes can be generated from the intersection of (basic) rays with adequately constructed hyperspheres. This paper introduces a family of polyhedra to replace the sphere; these polyhedra are not tangential to the hypersphere and produce cutting planes with particular characteristics that are discussed. Constructive procedures are sketched for generating step-by-step cutting planes that become deeper and deeper at every step, until the deepest cut is obtained. This construction often relies on a partial enumeration scheme of the set of integer solutions. [ABSTRACT FROM AUTHOR]

This paper studies the optimal operation of an M/G/1 queuing system with removable server and the following cost structure: a holding cost per customer in the system per unit time, a cost per unit time of keeping the server running, and fixed charges for turning the server on or off. The server can be turned on at arrival epochs or off at service-completion epochs. The paper characterizes an optimal policy for the infinite-horizon discounted problem, offers an optimality proof, and presents a computational algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes a general method of solution for problems, involving the allocation of jobs to machines and the sequencing of jobs on machines, in which a number of jobs, each consisting of a number of operations that may be performed on a given set of machines, is to be completed in some optimal fashion. Considering constraints on machine availability, job completion dates, and zoning, the paper demonstrates the underlying relation of a wide variety of machine-job problems with reference to their graphical representation, states a branch-and-bound method of solution, solves an illustrative example, and gives the mode of application to specific problems (for several of these the method reduces to methods published elsewhere). The algorithm represents not only a general framework of theoretical interest, but also a practical approach to certain specific problems. [ABSTRACT FROM AUTHOR]

One formulation of the machine sequencing problem is that of finding a minimaximal path in a disjunctive graph. This paper describes an implicit enumeration procedure that solves the problem by generating a sequence of circuit-free graphs and solving a slightly amended critical-path problem for each graph in the sequence. Each new term of the sequence is generated from an earlier one by complementing one disjunctive arc. The search tree is drastically cut down by the fact that the only disjunctive arcs that have to be considered for being complemented are those on a critical path. An evaluation of these candidates is used to direct the search at each stage, The procedure can start with any feasible schedule (like the one actually used in production, or generated by some heuristics), and gradually improve it. Thus one can possibly stop short of the optimum, with a reasonably 'good' feasible schedule. Storage requirements are limited to the data pertinent to the current node of the search tree. [ABSTRACT FROM AUTHOR]

This paper develops a methodology to evaluate various aspects of logistics supply support of space bases. It is assumed that there exists at the space base a schedule of operations that reflects the day-to-day living, build-up, and scientific experimental activities that are to be carried on. These activities, in turn, set a series of demands or requirements for products over a time spectrum. The supply system must deliver products so as to meet the amounts and times of the product requirements. Each product or module has an earliest and latest time by which it must be delivered. A mathematical model is developed that plans a series of trips, the dates at which each is to be sent, and the composition of the cargoes on each trip that satisfy the series of requirements over a time spectrum imposed by the activities at the space base. The series of trips are an expression of an efficient plan that simultaneously considers demands for different products at different future times and observes the various constraints of the system (e.g., cargo capacity of spaceships). The mathematical formulation of this scheduling problem is a simple non- linear discrete programming problem. An algorithm has been developed for its solution, and a description thereof is presented. The model is illustrated by showing how it would supply a long-term lunar base. Various uses of the model are described. [ABSTRACT FROM AUTHOR]

This paper summarizes experimental results from applying several computational methods for solving the classic three-machine scheduling model. The basic mathematical problem is to select an optimal permutation of a items, where the objective function employed is the total amount of processing time elapsing for the completion of all n items on three machines. The methods tested are integer linear programming, ordinary linear programming with answers rounded to integers, a heuristic algorithm, and random sampling. Throughout the experimentation n=6. A dual integer programming code is tested on six trial problems. Consideration is given to studying the phenomenon of input-form sensitivity. The results are not encouraging and confirm previous experimental evidence as to the strong effect of varying the input form. However, the addition of a powerful bound on the objective function has a significant beneficial effect on the convergence of the dual algorithm. A sampling study of the statistical characteristics of this model is made with 100 sets of data randomly generated. Frequency distributions of minimum and mean total processing time are tabulated and analyzed. On this same set of problems, a linear programming approach is examined for effectiveness in producing nearly optimal schedules. Such an approach tends to give answers that are better than would be obtained by a single permutation drawn at random, but the LP rounded solutions average about an 11 per cent increase over the optimal processing time. A heuristic algorithm based on Johnson's method is tested on 20 of the 100 eases and gives excellent results. Finally attention is turned to the method of randomly sampling the permutations, possibly applying a simple heuristic gradient method to improve each sampled schedule. A feature of this method is that elementary probability theory can be applied to yield corresponding statements about the accuracy guaranteed by the approach. [ABSTRACT FROM AUTHOR]

Because the payload that an airplane can carry is a function of the longest segment of its route and differs from route to routes the usual algorithms of network flow theory will not yield the optimum flow of payload. In this paper two network algorithms are described. They determine the route of maximum payload flow per hour of flight time and the maximum steady- state payload flow through a network with capacity constraints on the nodes,. [ABSTRACT FROM AUTHOR]

The 'explosion' problem is the problem of determining the required components from knowledge of demand for finished products. The 'netting' problem IS the problem of determining the net requirements of these components, for purposes of production or procurement from outside the firm, based on available inventory. This paper presents a simple algorithm which yields the 'netted explosion. 'The algorithm is suitable for digital computation in case of large inventories. [ABSTRACT FROM AUTHOR]

This paper studies the close relation between the Gass-Saaty parametric programming algorithm and the `primal-dual' procedures recently exploited by DANTZIG, FORD, AND FULKERSON lit is shown that the two procedures are equivalent The possibility of eliminating the two-phase character of the simplex method using these techniques is discussed Finally, the application of the techniques to problems with special structure is considered [ABSTRACT FROM AUTHOR]

This paper is concerned with the following problem in network synthesis. Suppose that we are given a network with real-valued capacities on each arc. There is a cost associated with each arc which is proportional to the magnitude of the arc capacity. We wish to determine new arc capacities such that the capacity of each cut in the new network differs from the capacity of the corresponding cut in the original network by a specified constant and such that the total cost is minimized. This problem is shown to be equivalent to solving a minimum cost flow problem on a related network. [ABSTRACT FROM AUTHOR]

Randomly-generated linear programming problems of three different types and five different sizes were solved by the criss-cross method and by the simplex method. One hundred problems of each type and size were solved, and the results are overwhelmingly favorable to the criss-cross method. An improvement to the criss-cross method used in these tests is given, and the extension of the results of the paper to variations of the criss-cross and simplex methods is discussed. [ABSTRACT FROM AUTHOR]

The paper considers a class of optimization problems. The problems are linear programming problems: maximize ex subject to Ax = b with the additional constraint that x must also be an extreme point of a second convex polyhedron Dx = d. X ≥ 0. A cutting-plane algorithm for solving such problems is presented. Two numerical examples are also included. [ABSTRACT FROM AUTHOR]

The author responds to the paper "The Loading Problem," by Eilon and Christofides. He focuses on suggesting a solution to the problem. The recommended solution involves a heuristic algorithm that allegedly requires fewer computations than the one proposed by Eilon and Christofides. It is suggested that the simpler algorithm offered by the author reaches mathematical optimization as often as the aforementioned algorithm. It is further proposed that the algorithm presented by Eilon and Christofides cannot be used to solve multi-dimensional programming problems. The author goes on to discuss a numerical analysis that can be used for the allocation of industrial resources. Related mathematical models are discussed in detail. A table comparing the results of the two algorithms is also presented.

This paper presents a model for determining how a central government can most efficiently allocate resources among other levels of government. The model explicitly includes the fact that lower levels of government can make independent decisions once they have been given resources by the central government. A key feature of the model is the mathematical formulation of the central government's objective of distributing resources efficiently, while at the same time being as fair as possible to all those receiving allocations. An algorithm for solving the model is presented along with a numerical example. [ABSTRACT FROM AUTHOR]

A framework of concepts is developed which helps to unify a substantial portion of the literature on large-scale mathematical programming. These concepts fall into two categories. The first category consists of problem manipulations that can be used to derive what are often referred to as "master" problems; the principal manipulations discussed are Projection, Inner Linearization, and Outer Linearization. The second category consists of solution strategies that can be used to solve the master problems, often with the result that "subproblems" arise which can then be solved by specialized algorithms. The Piecewise, Restriction, and Relaxation strategies are the principal ones discussed. Numerous algorithms found in the literature are classified according to the manipulation/strategy pattern they can be viewed as using, and the usefulness of the framework is demonstrated by using it (see Part II of this paper) to rederive a representative selection of algorithms. The material presented is listed in the following order: The first section is introductory in nature, and discusses types of large-scale problems, the scope of discussion and the literature, and the notation used. The second section, entitled "Problem Manipulation: Source of 'Master' Problems" covers the subjects of projection, inner linearization and outer linearization. The third section, "Solution Strategies: Source of 'Subproblems'," discusses piecewise strategy, restriction and relaxation. The fourth section is entitled "Synthesizing Known Algorithms from Manipulations and Strategies," and is followed by a concluding section and an extensive bibliography. [ABSTRACT FROM AUTHOR]

In this paper the Fiacco-McCormick SUMT technique is embedded in a class of inside-out algorithms. Convergence is demonstrated for the nonlinear programming problem under fairly general conditions and the algorithms are interpreted in a geometric structure. [ABSTRACT FROM AUTHOR]

The article presents an algorithm for solving a linear integer programming problem and describes the theoretical foundations for a new approach to integer programming. According to the authors, the approach may be described as an extension of the methods using enumeration, but by using a new, more powerful approach based on population statistics. The optimal solution to the integer programming problem in this paper is viewed as one of selecting the optimal function among a certain class of functions which map elements of one set into another. With this method in mind, the authors intend to view the different problems by characterizing the statistical structure of the associated finite class of maps.

The usefulness of integer programming as a tool of capital budgeting hinges on the development of an efficient solution technique. An algorithm based on partial enumeration has been developed by E. L. Lawler and M. D. Bell for solving integer linear programs with 0-1 decision variables; however their algorithm is not general enough to deal with all problems in which the objective function is quadratic. This paper extends Lawler and Bell's method so that it can be generally applied to integer quadratic programs. The new algorithm is illustrated by examples from capital budgeting. [ABSTRACT FROM AUTHOR]

This paper attempts to present the major methods, successful or interesting uses, and computational experience relating to integer or discrete programming problems. Included are descriptions of general algorithms for solving linear programs in integers, as well as some special purpose algorithms for use on highly structured problems. This reflects a belief, on the author's part, that various clever methods of enumeration and other specialized approaches are the most efficacious means existent by which to obtain solutions to practical problems. A serious try at gathering computational experience has been made—but facts are difficult to uncover. The paper is written with intent to enable readers to read selected sections without having to read the whole. [ABSTRACT FROM AUTHOR]

This paper treats the problem of locating a given number of interrelated physical facilities in a single- or multi-story building as an optimization model such that the weighted sum of the distances along orthogonal directions is minimized, and describes a constructive heuristic algorithm for the one-dimensional model. This linear placement algorithm is then extended to higher dimensions for placing uniform-size equipment modules at homogeneous fixed locations. The algorithm accommodates lower-bound constraints for the linear case efficiently and produces near-optimal solutions. Its significance, as demonstrated by comparison with some existing heuristic procedures, is that it has the capability of handling efficiently problems with large numbers of equal-size facilities whose solutions are computationally intractable using the present optimum-producing methods. [ABSTRACT FROM AUTHOR]

This paper gives counterexamples to: (1) Ritter's algorithm for the global maximization of a quadratic subject to linear inequality constraints, and (2) Tui's algorithm for the global minimization of a concave function subject to linear inequality constraints. [ABSTRACT FROM AUTHOR]

While Dantzig and Wolfe have formulated the decomposition algorithm as a computational device, it was subsequently recognized that the principle underlying the algorithm may also be utilized by a planning system to achieve a centralized planning within the framework of a decentralized organizational structure. This paper illustrates the workings of such a planning system and, at the same time, explores some of the problems connected with its actual implementation. The planning system under the study is called the decomposed planning system in order to distinguish it from either the centralized planning or the decentralized planning. [ABSTRACT FROM AUTHOR]

The algorithms of this paper solve problems of the ‘decomposition’ structure. It presents the basic framework for a class of algorithms, along with two possible versions. The basic algorithm generates a sequence of solutions that satisfy complementary slackness with a sequence of dual feasible solutions such that, when the linking constraints are satisfied, an optimum is obtained. Computational experience is reported for the first version in comparison with RSMFOR, a simplex program, on randomly generated problems and a three-period refinery model Using the number of nonzero multiplications as the bade for comparison, the results show the first version substantially better than the simplex method. The computational experience is discussed at some length. [ABSTRACT FROM AUTHOR]

This paper look at the maximal-flow-with-gains problem from a new point of view. We wish to discover the maximum output possible for any input. This approach leads naturally to a two-step parametric solution procedure: The step finds the maximum output far zero input, and resolves all difficulties with flow-generating loops; the second determines how the maximum output increases as input is increased. [ABSTRACT FROM AUTHOR]

This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric travelling-salesman problem. The procedure is based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems. The procedure produces optimum solutions for all problems tested, 'classical' problems appearing in the literature, as well as randomly generated test problems, up to 110 cities. Run times grow approximately as n² in absolute terms, a typical 100-city problem requires less than 25 seconds for one case (GE63S), end about three minutes to obtain the optimum with above 95 per cent confidence. [ABSTRACT FROM AUTHOR]

This paper connects some of the recent developments in concave and integer programming. In particular, it points out parallels between the work of HOANG TUI and R. D. YOUNG. From these methods, a finite algorithm for solving a special class of 0–1 integer programs is developed. Our approach contrasts with an earlier extension of Tui's method due to M. RAGHAVACHARI and general ‘intersection’ or ‘convexity’ cut approaches. [ABSTRACT FROM AUTHOR]

A new cluster-analysis method, the bond energy algorithm, has been developed recently; it operates upon a raw input object-object or object-attribute data array by permuting its rows and columns in order to find informative variable groups and their interrelations. This paper describes the algorithm and illustrates by several examples its use for both problem decomposition and data reorganization. [ABSTRACT FROM AUTHOR]

MILLER and WAGNER [Opns. Res. 13, 930–945 (1965)] define joint chance-constrained programming by specifying a set of consists that are joint probability measures of the extent to which constraint violations are permitted. For the special case of a random right-hand-side vector whose elements are independent random variables, they show that an equivalent deterministic concave program exists. The purpose of this paper is to generalize this result to a class of nonlinear chance-constrained programming models with joint constraints. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm that finds globally optimum flows in networks having nonlinear costs of arc flows, the flows being finite-dimensional vectors such as multicommodity flows. The algorithm is an extension of an idea of ALLSOP [Trans. Sci. 2, 1–13 (1968)] for minimizing total delays in a traffic network; it is also intimately related to results in nonserial dynamic programming. [ABSTRACT FROM AUTHOR]

This paper studies multistage mathematical programs with an arbitrary transient phase followed by an infinite stationary phase with linear constraints and objective. It presents conditions under which a derived linear program will determine an optimal solution to the infinite problem. These conditions are general and may be validated by simple algebraic tests (perhaps solving a finite linear program). No topological restrictions are placed on the model. [ABSTRACT FROM AUTHOR]

This paper treats the scheduling problem that has both precedence constraints (of a general form as in PERT-CPM problems) and resource constraints (of the form in the general job-shop scheduling problem). Preemptive-resume without changeover times is allowed. An efficient procedure for enumerating all active schedules is given. For the objective of minimizing the project length, a branch-and-bound algorithm is developed by adding a bounding procedure to the enumerative scheme. Computational experience is given. [ABSTRACT FROM AUTHOR]

This paper concerns finding a tight lower bound to the travelling-salesman problem, with the hope that all the different branch-and-bound algorithms for this problem can benefit from it. The bound is calculated by an iterative procedure with guaranteed convergence and is shown to require a computation time only about 9 per cent greater than the time required to solve an equivalent assignment problem. This new bound was tested on 14 sample problems and, on the average, found to be only 4.7 per cent below the optimum for symmetrical, and 3.8 per cent below the optimum for asymmetrical problems. [ABSTRACT FROM AUTHOR]

This paper develops an algorithm for solving an arborescence-structured production and inventory system. Arborescence structures model multi-echelon production systems in which each facility requires input from a unique immediate predecessor. Assuming known demands, and no backlogging, the objective is to schedule production over a finite planning horizon to minimize production and holding costs. The algorithm is applicable to systems in which, at all facilities with followers in the system, the production costs consist of a set-up charge plus linear costs and holding costs are linear. General costs are permitted at the lowest-echelon facilities (those without followers) with special computational efficiency resulting when these costs are concave. The algorithm exploits the known results on the structure of optimal policies in arborescence systems to decompose the problem into single-stage problems at each lowest-echelon facility. This decomposition is achieved by enumerating implicitly the feasible production set-up patterns at facilities with followers. As a result, the computational effort might increase exponentially with the number of facilities with followers, but is increasing only linearly with the number of lowest-echelon facilities in the system. [ABSTRACT FROM AUTHOR]

This paper uses the special structure of a (directed) acyclic network with positive gains to develop an extremely simple and powerful algorithm for maximal flow. Finiteness of the algorithm is achieved through a theorem characterizing basic solutions for this special network. [ABSTRACT FROM AUTHOR]