State aggregation in dynamic programming — An application to scheduling of independent jobs on parallel processors

Exact dynamic programming formulations of capacity loading problems will, in general, involve a prohibitively large state space. This paper offers a methodology for aggregation of the state space when dealing with such problems. Instead of future costs with respect to a known state, we are considering the costs in the worst (or best) case with respect to the given aggregate information. We apply the technique to scheduling of independent jobs on parallel processors.