Time-indexed formulations for machine scheduling problems: Column generation

Time-indexed formulations for machine scheduling problems have received a g reat deal of attention; not only do the linear programming relaxations prov ide strong lower bounds, but they are good guides for approximation algorit hms as well. Unfortunately, time-indexed formulations have one major disadv antage-their size. Even for relatively small instances the number of constr aints and the number of variables can be large. In this paper, we discuss h ow Dantzig-Wolfe decomposition techniques can be applied to alleviate, at l east partly, the difficulties associated with the size of time-indexed form ulations. In addition, we show that the application of these techniques sti ll allows the use of cut generation techniques.