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]

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]

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 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]

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 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]

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 discusses the problem at assigning facilities to locations. Several optimal and sub-optimal-yielding algorithms are discussed mentioning their desirable and undesirable features. A new heuristic algorithm is proposed. The proposed algorithm, combining features from other well known models, and programmed in Fortran IV is tested against existing methods. The results show that the algorithm is efficient, easy to run and is very competitive with other well-known methods. [ABSTRACT FROM AUTHOR]

This paper investigates the classical n-job, M-machine flow-shop scheduling problem under the assumption that jobs are processed on all machines in the same order. Based on the heuristic job-pairing technique and the decomposition strategy, a heuristic decomposition algorithm is developed which will generate at least a near-optimal schedule for the flow-shop scheduling problem. The proposed algorithm is compared to the existing decomposition approach and is found to be superior to Ashour's decomposition algorithm, both in increased solution quality and decreased computational time required to solve the problem. [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]

Copyright of INFOR is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of INFOR is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The objective of this paper is the construction of a branch-and-bound algorithm for computing minimum cost flows in capacitated networks when the cost of passing a flow over an arc is concave. The method is based on the equivalence of the general network flow problem to a network flow problem in a bipartite network of a special form. An optimal flow is found by implicit enumeration of the set of extremal flows in that network. [ABSTRACT FROM AUTHOR]

This paper presents a method for taking into account dependency among certain activities in PERT networks. The method presented can be used with the reduction algorithm presented by Hartley and Wortham [1]. The addition of dependency among the completion times for certain types of activities should be a valuable aid in sensitivity analyses of PERT networks. [ABSTRACT FROM AUTHOR]

This paper describes a simple algorithm for the solution of very large sequence problems without the use of a computer. It produces approximate solutions to the n job, m machine sequencing problem where no passing is considered and the criterion is minimum total elapsed time. Up to m-1 sequences may be found. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the solution of the knapsack problem. The method involves searching the nodes of a tree along a single branch at a time. The algorithm eliminates the computational drawbacks inherent in the usual branch and bound schemes. [ABSTRACT FROM AUTHOR]

This paper considers an n-server queueing system with m customer classes distinguished by the reward associated with serving customers of that class. Our objective is to accept or reject customers so as to maximize the expected value of the rewards received over an infinite planning horizon. By making the assumptions of Poisson arrivals and a common exponential service time this problem can be formulated as an infinite horizon continuous time Markov decision problem. In §3 we customize the general algorithm for solving continuous time Markov decision problems to our queueing model. In §4 we obtain qualitative results about the form of the optimal policy. §6 reports the results of simulation tests which compare heuristic policies for our model when the service times associated with each customer class have arbitrary distributions. The ‘winning’ policy is based on a rather intricate theorem whose proof comprises §6. [ABSTRACT FROM AUTHOR]

There exists computational experience to the effect that search algorithms of the type introduced by Balas are frequently ineffective because of being tied to a rigid "natural" search origin. In this paper the dynamic relocation of the search origin to possibly more appropriate points is advocated. Details of such a procedure are given for the Simple Plant Location Problem. Computational improvements of, sometimes, a striking nature are presented. [ABSTRACT FROM AUTHOR]

Multi-level fixed-charge problems are mathematical optimization problems in which the separable portion of the objective function is the sum of piecewise continuous functions of a single variable. This paper describes a branch-and-bound algorithm that will find a global solution to this type of problem. The algorithm has the feature that a good feasible solution is generated at the start. Moreover, at each step of the algorithm an additional feasible solution may be generated for comparison with the best solution found previously. [ABSTRACT FROM AUTHOR]

Conditions which are necessary and sufficient for convergence of a nonlinear programming algorithm are stated. It is also shown that the convergence conditions can be easily applied to most programming algorithms. As examples, algorithms by Arrow, Hurwicz and Uzawa; Cauchy; Frank and Wolfe; and Newton-Raphson are proven to converge by direct application of the convergence conditions. Also the Topkis-Veinott convergence conditions for feasible direction algorithms are shown to be a special case of the conditions stated in this paper. [ABSTRACT FROM AUTHOR]

This paper considers the problem of scheduling m independent, immediately available tasks on n parallel processors. Each task has a waiting cost rate, that is a function of time, and a service time. There are no feasibility restrictions on the order in which the tasks are to be processed. An optimal scheduling rule is presented for the single processor scheduling of tasks with continuously discounted linear waiting costs. A dynamic programming algorithm has been developed for a wide class of parallel-processor problems. Linear waiting costs (with or without discounting), arbitrary processor use costs, and certain other costs are considered. In certain cases, the service time of a task may be a function of the processor that performs it. [ABSTRACT FROM AUTHOR]

The problem of scheduling n jobs on m identical processors has been introduced by R. McNaughton, but as yet no efficient algorithm has been found for determining an optimal sequencing of jobs. In this paper lower and upper bounds are given for the cost of an optimal schedule. Since the two bounds are not far apart, they may be helpful in practical scheduling problems. A procedure is described for obtaining a schedule which costs less than the given upper bound. [ABSTRACT FROM AUTHOR]