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 (ε). Algorithms with computation time bounds of O(1/ε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.