A FULLY POLYNOMIAL APPROXIMATION SCHEME FOR SINGLE-PRODUCT SCHEDULING IN A FINITE CAPACITY FACILITY.

This paper considers a version of the economic lot sizing problem for a single product produced in a facility of finite capacity over a finite time horizon with specifiable start and end conditions. A set of algorithms is presented that will approximate the optimal production schedule to a given allowable error (e). Algorithms with computation time bounds of O(l/e[sup 2]) are presented which allow for setups of finite length, setups with or without direct cash flow, quite general cost and demand functions, and a wide variety of production policy constraints. The procedures make no a priori assumptions about the form of the optimal solution. Numerical results are included. [ABSTRACT FROM AUTHOR]