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 deals with systems (such as electronic devices and corporations) that are designed to accomplish multiple goals and whose internal structures are characterized by networks of interacting component parts. Each component of such a system is typically associated with a probability of failure, while each system goal is associated with a reward value. Failure of any network component may ultimately result in the inability to achieve one or more goals and force the forfeiture of the associated rewards. A basic problem in component-system design is to determine how the expectation of total reward may be maximized through the cost-limited acquisition of redundant (backup) components. This paper provides a formal statement of this redundancy-optimization problem and argues that the problem may not be solved easily by standard linear or integer programming techniques. It introduces an algorithm to solve this problem, proves its convergence, and presents computational results taken from a battery of test problems and an algorithm-efficiency study based on these tests. [ABSTRACT FROM AUTHOR]

This paper treats the optimal location of nuclear-power plants in the Pacific Northwest with respect to capital-construction, operating, and transmission costs. It presents a mathematical formulation of this two-product (peak and energy power) plant-location problem, using the simplex method in conjunction with a branch-and-bound process, and indicates a check procedure using Vogel's approximation method in conjunction with an algorithm for solving the transportation problem and a branch-and-bound process. The paper gives results for demand-growth rates of 4, 5, 6 and 7 percent and alternative designs and their costs. It also discusses the stability of the optimal solution. [ABSTRACT FROM AUTHOR]

This paper develops a new cutting plane for primal integer programming. This cut, when it exists and is used as pivot row, has the property that the minimum of the simplex evaluators of the next tableau is strictly larger (by an integer) than the minimum for the current tableau. The paper gives a sufficient condition in the form of a linear program for the existence of such a cut, and proposes an algorithm for generating such cuts. It also presents two additional sufficient conditions. The process of cut generation is then imbedded into a convergent primal algorithm to be used in an attempt to overcome the proof-of-optimality problem experienced with the primal algorithm. [ABSTRACT FROM AUTHOR]

This paper investigates the optimal allocation of the marketing budget within the marketing-mix decision variables so that sales (or profit) is maximized in a planning horizon. Since the influence of marketing mix variables upon sales are, in reality, nonlinear and interactive, a geometric programming algorithm is used that solves this problem. A procedure to estimate a functional of sales on the marketing mix and environmental variables utilizing the experienced judgments of the firm's executives and the raw data is provided. The derived functional is later optimized by the Geometric Programming algorithm under a constraint set consisting of budget and strategy restrictions imposed by a firm's marketing environment, and conditions under which the optimal solution is either local or global are identified. An empirical application for a large midwestern brewery is provided which utilizes and illustrates both the estimation an optimization procedures. [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 introduces a generalization of the frequently discussed problem of finding the optimum redundancy that maximizes the reliability of a network of components. Past work has restricted consideration to arrangements of redundant components called series-parallel networks. This paper allows a much broader class of arrangements called series-parallelseries networks. It is important to consider such arrangements for realistic situations in which components have more than one failure mode, or the combination of parallel paths introduces a failure probability. A dynamic programming algorithm is used to solve the more general problem for the case in which there are no constraints on the optimum solution. The algorithm is extended to handle multiple constraints using dominance and a variety of elimination methods to reduce the storage required in a compurer implementation of the algorithm. Problems with as many as 15 serial components and three constraints have been solved with reasonable digital computer computation times. [ABSTRACT FROM AUTHOR]

This paper develops a new algorithm for solving the general nonlinear programming problem that melds the flexible simplex search of NELDER AND MEAD with various additional rules to take care of equality and/or inequality constraints. The set of violated inequalities and equalities is lumped into one inequality constraint loosely satisfied during the early progress of the optimization and more closely satisfied during its final stages. To permit this type of search, the method sets up a special tolerance criterion, a function that does not depend on either the values of the objective function or the values of the constraints. The new algorithm has solved successfully a number of problems that have been proposed in the literature as test problems. Finally, to indicate the algorithm's capabilities, the paper describes an example composed of a linear objective function of twenty-four variables subject to fourteen nonlinear equalities and thirty inequalities. [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 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 analyzes the problem of balancing resource capacity utilization against the costs of user delay or inventory investment. Instead of formulating algorithms to solve more classical versions of the problem, this paper describes ways that organizations can drop the cost curve prior to applying an optimizing algorithm. This is done by classifying the techniques and giving examples from organizations which have faced serious smoothing problems. Other organizations can improve their coat performance by adopting some of these techniques. [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 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]

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.

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]

Two dynamic economic lot size production systems are analyzed in this paper, the first being a single product model with backlogging and the second a multi-echelon model. In each model the objective is to find a production schedule that minimizes the total production and inventory costs. A key conceptual difficulty is that the mathematically perplexing problem of minimizing a concave function is being considered, it is shown that both models are naturally represented via single source networks. The network formulations reveal the underlying structure of the models, and facilitate development of efficient dynamic programming algorithms for calculating the optimal production schedules. [ABSTRACT FROM AUTHOR]

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 presents an algorithm for the solution of dynamic programming problems requiring the determination of optimal policies for the control of a special class of stochastic processes when the time horizon of the planning period is at infinity. These processes can be mathematically described as discrete time parameter Markov chains with a finite number of states which have been "embedded" in continuous time in the sense that the time between transitions is a random variable whose probability distribution depends only on the states between which the transition takes place. Such processes are called Markov-renewal processes. The Markov processes considered by R. A. Howard in [1] are really two special cases of this somewhat wider class of stochastic processes. In these two special cases, the algorithm of this paper is identical with Howard's. In fact, with only slight modification, Howard's algorithm can be extended to this wider class of stochastic processes. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to illustrate some applications of the functional equation technique of the theory of dynamic programming to a general class of problems arising in the study of networks, particularly those arising in transportation theory. [ABSTRACT FROM AUTHOR]

In this paper, it is shown that the "caterer" problem, a problem in mathematical economics and logistics which has been discussed by Jacobs, Gaddum, Hoffman and Sokolowsky, and Prager, can be reduced to the problem of determining the maximum of the linear form Ln = ∑I=1nv1, subject to a series of constraints of the form V1 ≦ b1, v1 +v2 ≦ b2, v1 + v2 +v3 ≦ b2, ߪ, v1 + v2 + … + vK ≦ bK, v2 + v3 + … + vK+1 ≦ bK+1, …, vb-h+1 + … + Vn ≦ bn, 0 ≦ rI, I = 1, 2, … , n, under an assumption concerning the nonaccumulation of dirty laundry. This maximization problem is solved explicitly, using the functional equation technique of dynamic programming. [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 presents an algorithm for the global maximization of a convex function subject to linear inequality constraints. It is computationally finite and is designed to converge rapidly on problems in which there are few local optima or the global optimum is significantly better than most of the other local optima. [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]

A multi-stage linear program is defined with linking variables that connect consecutive stages. Optimality conditions for the composite problem are partitioned into local and linking conditions. When the Dantzig-Wolfe decomposition scheme is applied with the first stage as the master, the subproblem is also a MLP with one less stage. The same decomposition is then applied to the subproblem, giving rise to a nested decomposition scheme, in which each stage acts as a master for the following stage and a subproblem for the preceding. Optimizing a single stage problem results in satisfying the "local" optimality conditions. A very general rule is given for selecting the next subproblem to optimize, and finite convergence to a solution satisfying all linking conditions is demonstrated. Procedures for extracting the optimal primal solution at the end of the main algorithm and for initialization are given. Particular rules for selecting the next subproblem and for generating additional proposal vectors are discussed. Finally, it is shown how a variety of problems may be restructured as multi-stage linear programs to which this algorithm may be applied, and some computational experience is reported. [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]

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 presents a realistic chemical-process optimization problem in detail, and notes the fact of its equivalence to the general nonlinear programming problem. The eight equality constraints that arise are handled by algebraic substitution, and the resulting four-variable problem is solved by a modified form of the Davidon-Fletcher-Powell algorithm. Details of the method are presented (including a FORTRAN computer program), and results of two typical cases are summarized. [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 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]

This paper presents an iterative algorithm that allows the solution of the following problem to be obtained to any desired degree of accuracy: choose s,,A, for i=1, -.., rs to minimize &Sigma[supi−n][subi&minus1]c[subi](8[subi]) subject to Σ[supi;−n][subi−1]e[subi](8[subi])≥ ε for arbitrary given real ε c[subi], e[sub1], and finite A[subi], i=1, ..., n. In particular, the sets {(c[subi](ϒ), e[subi](ϒ)): ϒεA[subi] need not be convex. The procedure offers considerable computational advantage over alternative means of obtaining the desired solution. The technique uses a pair of Lagrange multipliers for the single constraint. This pair of Lagrangians induces a partial ordering among the set of all (8[sub1], ..., 8[subn]). The desired solution is found among the maximal elements under this ordering for appropriate choices of the multipliers, and possible improvement in the solution is bounded in terms of other maximal elements. The set of all maximal elements, under the partial ordering, is generated by dynamic programming. [ABSTRACT FROM AUTHOR]

In deriving the well known cuts for cutting-plane methods in 0, 1 integer programming, the integer points outside the 0, 1 space can limit the parallel movement of the hyperplane of the cut toward the solution set. Furthermore it is unnecessarily restrictive to limit the movement of this hyperplane to parallel translations. This paper removes these two limitations in order to derive stronger cuts and reduce the total number of cuts required. Thus, it describes a method based on a special case of the knapsack function that replaces each cut or original constraint by a new inequality whose hyperplane passes through as many integer points in 0, 1 space as possible. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the set-covering problem (that is, min c'y:Ey±e, y±0,y, integer, where E is an m by n matrix of 1's and O's, and e is an m-vector of 1's). The special problem structure permits a rather efficient, yet simple, solution procedure that is basically a (0, 1) search of the single-branch type coupled with linear programming and a suboptimization technique. The algorithm has been found to be highly effective for a good number of relatively large problems. Problems from 30 to 905 variables with as many as 200 rows have been solved in less than 16 minutes on an IBM 360 Model 50 computer. The algorithm's effectiveness stems from an efficient suboptimization procedure, which constructs excellent integer solutions from the solutions to linear-programming subproblems. [ABSTRACT FROM AUTHOR]

This paper develops a model for the optimum allocation of fixed stockpiles of interceptors. Imbedded dynamic programming and successive approximations serve as the format for the computational scheme. This procedure leads to a local optimum solution in general and to the global optimum in certain instances. A method for determining upper bounds is included in the algorithm so that optimal stopping rules may be used to choose a final solution. [ABSTRACT FROM AUTHOR]

The convex hull of the feasible integer points to a given integer program is a convex polytope I. The feasible set obtained by relaxing the integrality requirements is another convex polytope L. Cutting-plane algorithms essentially try to remove part of L--I. Hence the more complicated the relationship between L and I, the more difficult (in some sense) the integer program. This paper shows one such complexity: specifically, we construct a series of programs such that I has arbitrarily many faces even though L is a triangle. We also indicate the existence of a large class of problems that exhibit the same behavior. [ABSTRACT FROM AUTHOR]

This paper deals with the solution to a discrete optimization problem by decomposition. It develops a criterion for ranking the decomposition procedures, discusses the properties of the optimal decompositions, and gives an algorithm for finding the best decomposition in the case of no storage limitation. [ABSTRACT FROM AUTHOR]

This paper considers the problem of determining the policy to be followed by each member of a team so as to optimize some over-all criterion function characterizing the objective of the team. The reasoning of dynamic programming is employed to formulate the optimization problem, and the discussion is couched in the terms of a classical network problem. The paper first formulates a simple bipartite network optimization and then presents a number of generalizations. Finally, it gives two slightly different computational solutions to an example bipartite optimization problem. [ABSTRACT FROM AUTHOR]

The main result of this paper is a group theoretic algorithm (GTIP2) for the integer programming problem. This algorithm is an extension of an algorithm from an earlier paper (part I). The algorithm in part I solves a group optimization problem derived from a given integer programming problem. The optimal solution to the group problem thereby obtained is an optimal solution to the integer programming problem if it is feasible. Unfortunately, an optimal solution to the group problem may yield an infeasible integer solution. The algorithm GTIP2 of this paper is an extension of the method of part I when it fails. In particular, GTIP2 employs a search procedure to find an optimal solution to the integer programming problem. The extent of the search is bounded by procedures derived from a variety of relevant group problems that are solved by the algorithm of part I. There is a discussion of the class of problems for which GTIP2 is primarily intended and the relation of GTIP2 to other algorithms is indicated. A numerical example and some partial computational results are included. [ABSTRACT FROM AUTHOR]

This paper considers the problem of optimum allocation of redundant elements in a simple series system (maximizing system reliability subject to several linear cost constraints). Under the approximation that the components of the redundancy vector can be treated as continuous variables, the paper formulates this optimization problem as a geometric programming problem, describes techniques for obtaining numerical solutions in general, and obtains asymptotic closed-form solutions. A standard numerical example is used to illustrate that the asymptotic solution, when suitably rounded, compares favorably with the discrete optimal solution. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm that will yield the minimum make-span sequence for n-jobs requiring processing through M-machines when no passing is allowed. Theoretical development utilizing combinatorial analysis and proof of sequence optimality precedes the algorithm and an example problem. [ABSTRACT FROM AUTHOR]

In this paper we develop an algorithm for allocating redundancy among subsystems so as to achieve maximum system reliability without exceeding any of several linear constraints on redundancy. The algorithm represents a generalization of the one developed by Kettelle for the case of a single constraint on redundancy, published in this JOURNAL in 1962. [ABSTRACT FROM AUTHOR]

The special class of linear programs described as network flow problems includes many of the special structure optimization problems in such areas as assignment, transportation, catering, warehousing, production scheduling, etc Besides the physical motivation of the flow description, this class of problems possesses conceptually simple, and computationally elegant, solution techniques originated by DANTZIG, FORD, FULKERSON, ET AL This paper describes a generalization of this class of problems to 'process-flow networks,' or 'flow with gains,' in which flow in any branches of the network may be multiplied by an arbitrary constant, called the branch gain, before leaving the branch and flowing into the remainder of the network This generalization permits the description of networks in which different kinds of flow may be converted one to another, without 'constant returns to scale' Among other interesting problems, this model includes the metalprocessing problem, the machine-loading problem, financial budgeting, aircraft routing, warehousing with 'breeding' or 'evaporation,' the two-equation capacitated linear program, etc The solution method here described and proved is a natural extension of Ford and Fulkerson's technique (or specialization of the primal-dual method) and retains much of the physical motivation and easy computational aspect of their technique, a direct starting solution is usually available, and optimization of the imbedded linear program (the restricted primal problem) can be accomplished without the use of the simplex technique Conceptually, the solution procedure consists of the following steps (1) Find the inerementally cheapest loop in the network that will absorb flow (2) Establish as much additional flow into the network along this route as possible (3) Repeat Steps (1) and (2) until the desired flow is established, or until infeasibility is discovered The solution technique includes a maximal-flow procedure and produces a 'min-cut... [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for determining the minimum cost schedule of tasks in a critical path network in which task cost-time curves may be concave. A computer program for the case of cost-time curves that are piecewise linear in two segments is described, and a numerical example is presented. [ABSTRACT FROM AUTHOR]

In this paper a search scheme for finding the maximum of a discrete objective function of several variables is proposed. The scheme is sequential and optimal in the sense that it determines the maximum with minimum number of measurements of the function. Unlike other sequential search techniques with this property the scheme places no condition on the number of possible maxima of the objective function. Instead it requires that some bounds on the rate of change of the function per each variable be known. The points at which measurements of the value of the objective function are to be taken are determined successively by maximization of an auxiliary function updated after each measurement. The algorithm is described in detail, and illustrated by two simple examples. [ABSTRACT FROM AUTHOR]