Production planning with time-dependent capacity bounds

In this paper, we examine the problem of finding minimum-cost production schedules that satisfy known demands over a finite planning horizon. A dynamic programming algorithm is developed to find these schedules for cases in which production in each period is constrained by a time-dependent capacity bound. The costs considered are production and inventory holding costs, and all cost functions are assumed to be nondecreasing and concave. The algorithm is an extension of Florian and Klein's method developed for problems in which capacity bounds are the same in all periods. Although the problem with time-dependent bounds is NP-complete, the algorithm is shown to be efficient when the capacity bounds are integer multiples of a common divisor and the largest multiplier is small. Hence, it is useful in applications in which production capacity is periodically increased by adding facilities of the same size.