A DUAL-BASED HEURISTIC FOR THE CAPACITATED LOT SIZING PROBLEM (PRODUCTION SCHEDULING)

There are several features in multi-item manufacturing systems that make production planning more difficult than the problems usually addressed in the research literature. Three examples include: (1) the existence of bottleneck facilities used for production of several parts; (2) setup time that reduces available capacity; and (3) nonstationary demand which gives rise to waves of heavy utilization followed by troughs of light utilization, rendering the implied cost of setup time and other effects of capacity limits variable over the planning horizon. This research focuses on mathematical programming methods of accounting for capacity costs properly in this dynamic environment so that lot sizes and timing reflect the costs of setup, capacity and inventory.; First, the problem is formulated as a fixed charge mixed binary integar linear program. Next the capacity constraints are relaxed and moved to the objective function with Lagrange multipliers. The problem is thus decomposed into a series of uncapacitated single product lot size problems which are solved by dynamic programming. A modified subgradient optimization procedure is used to determine the costs of capacity. This approach directly produces dual solutions; a heuristic smoothing procedure constructs feasible primal solutions (production plans) which do not require overtime.; For problems without setup time, my algorithm found solutions that were better on average than the other algorithms tested (and faster than some comparable algorithms.) More importantly, the algorithm solves problems with setup time with equal ease. Problems with extremely tightly binding capacity constraints were much more difficult to solve than anticipated. Feasible solutions could not always be found for them. The most significant results for problems with setup time were that (1) the tightness of the capacity constraint, although not necessarily a good indicator of problem difficulty for problems without setup time, is a good indicator for problems with setup time; and (2) my algorithm solves larger problems better than smaller problems, although they are more time consuming to solve. This indicates that larger problems may be easier problems despite the greater computational effort they require.