Efficient algorithms are developed optimizing an important class of capacity scheduling models. The specific problem considered can be simply described in terms of contracting for warehousing capacity. Contracts must be let for warehouse capacity over n time periods, with the minimum capacity to be provided in each time period being specified. Savings may be achieved by long-term leasing arrangements or by contracting at favorable periods of time, even though this creates idle capacity at certain time periods. A minimum cost solution to this problem is sought. The mathematical model also applies to problems of equipment replacement and overhaul, checkout, repair, and replacement of stochastically failing equipment, determination of economic lot size, product assortment, and deterministic batch queuing policies, labor-force planning, and multi-commodity warehouse decisions. For some of these problems, such as equipment replacement, the computing algorithms presented are even more efficient than schemes heretofore proposed for simpler versions of the same problem.