Knowledge that Transforms

The usefulness of Lagrange multipliers for optimization in the presence of constraints is not limited to differentiable functions. They can be applied to problems of maximizing an arbitrary real valued objective function over any set whatever, subject to bounds on the values of any other finite collection of real valued functions denned on the same set. While the use of the Lagrange multipliers does not guarantee that a solution will necessarily be found for all problems, it is “fail-safe” in the sense that any solution found by their use is a true solution. Since the method is so simple compared to other available methods it is often worth trying first, and succeeds in a surprising fraction of cases. They are particularly well suited to the solution of problems of allocating limited resources among a set of independent activities.

In this paper, the methods for stock cutting outlined in an earlier paper in this Journal [Opns Res 9, 849–859 (1961)] are extended and adapted to the specific full-scale paper trim problem. The paper describes a new and faster knapsack method, experiments, and formulation changes. The experiments include ones used to evaluate speed-up devices and to explore a connection with integer programming. Other experiments give waste as a function of stock length, examine the effect of multiple stock lengths on waste, and the effect of a cutting knife limitation. The formulation changes discussed are (i) limitation on the number of cutting knives available, (n) balancing of multiple machine usage when orders are being filled from more than one machine, and (m) introduction of a rational objective function when customers' orders are not for fixed amounts, but rather for a range of amounts. The methods developed are also applicable to a variety of cutting problems outside of the paper industry.

This paper is a continuation of a previous one which investigates programming over a Markov-renewal process—in which the intervals between transitions of a system from state i to state j are independent samples from a distribution that may depend upon both i and j. Given a reward structure, and a decision mechanism that influences both the rewards and the Markov-renewal process, the problem is to select alternatives at each transition so as to maximize total expected reward. The first portion of the paper investigated various finite-return models. In this part of the paper, we investigate the infinite-return models, where it becomes necessary to consider only stationary policies that maximize the dominant term in the reward. It is then important to specify whether the limiting experiment is (I) undiscounted, with the number of transitions n → ∞, (II) undiscounted, with a time horizon t → ∞, or (III) discounted, infinite n or t, with discount factor a → 0. In each case, a limiting form for the total expected reward is shown, and an algorithm developed to maximize the rate of return. The problem of finding the optimal or near-optimal policies in the case of ties is still computationally unresolved. Extensions to nonergodic processes are indicated, and special results for the two-state process are presented. Finally, an example of machine maintenance and repair is used to illustrate the generality of the models and the special problems that may arise.