Knowledge that Transforms

Two different kinds of heavy-traffic limit theorems have been proved for s-server queues. The first kind involves a sequence of queueing systems having a fixed number of servers with an associated sequence of traffic intensities that converges to the critical value of one from below. The second kind, which is often not thought of as heavy traffic, involves a sequence of queueing systems in which the associated sequences of arrival rates and numbers of servers go to infinity while the service time distributions and the traffic intensities remain fixed, with the traffic intensities being less than the critical value of one. In each case the sequence of random variables depicting the steady-state number of customers waiting or being served diverges to infinity but converges to a nondegenerate limit after appropriate normalization. However, in an important respect neither procedure adequately represents a typical queueing system in practice because in the (heavy-traffic) limit an arriving customer is either almost certain to be delayed (first procedure) or almost certain not to be delayed (second procedure). Hence, we consider a sequence of (GI/M/S) systems in which the traffic intensities converge to one from below, the arrival rates and the numbers of servers go to infinity, but the steady-state probabilities that all servers are busy are held fixed. The limits in this case are hybrids of the limits in the other two cases. Numerical comparisons indicate that the resulting approximation is better than the earlier ones for many-server systems operating at typically encountered loads.

This paper proposes methodology for improving the performance of Benders decomposition when applied to mixed integer programs. It introduces a new technique for accelerating the convergence of the algorithm and theory for distinguishing “good” model formulations of a problem that has distinct but equivalent mixed integer programming representations. The acceleration technique is based upon selecting judiciously from the alternate optima of the Benders subproblem to generate strong or pareto-optimal cuts. This methodology also applies to a much broader class of optimization algorithms that includes Dantzig-Wolfe decomposition for linear and nonlinear programs and related “cutting plane” type algorithms that arise in resource directive and price decomposition. When specialized to network location problems, this cut generation technique leads to very efficient algorithms that exploit the underlying structure of these models. In discussing the “proper” formulation of mixed integer programs, we suggest criteria for comparing various mixed integer formulations of a problem and for choosing formulations that can provide stronger cuts for Benders decomposition. From this discussion intimate connections between the previously disparate viewpoints of strong Benders cuts and tight linear programming relaxations of integer programs emerge.

Production scheduling can be defined as the allocation of available production resources over time to best satisfy some set of criteria. Typically, the scheduling problem involves a set of tasks to be performed, and the criteria may involve both tradeoffs between early and late completion of a task, and between holding inventory for the task and frequent production changeovers. The intent of this paper is to present a broad classification for various scheduling problems, to review important theoretical developments for these problem classes, and to contrast the currently available theory with the practice of production scheduling. This paper will highlight problem areas for which there is both a significant discrepancy between practice and theory, and for which the practice corresponds closely to the theory.

A new approach to the one-dimensional cutting stock problem is described and compared to the classical model for which Gilmore and Gomory have developed a special column-generation technique. The new model is characterized by a dynamic use of simply structured cutting patterns. Nevertheless, it enables the representation of complex combinations of cuts. It can be advantageous in practical applications where many different stock lengths or a relatively large number of order lengths have to be dealt with. The new approach is applied to a real problem where the “trim loss” is not valueless, since it can be used for further demands arising in later planning periods.