Dynamic Linear Programs for Production Scheduling

Deterministic linear scheduling problems can often be formulated as linear programs with staircase coefficient matrix structure in which the linking blocks are identity matrices, since the activities that link successive time periods represent storage of goods. The solution technique proposed in this paper can be viewed as a nested decomposition approach in which primal- as well as dual-variable information is transmitter between master and subproblems.