A time-indexed formulation for single-machine scheduling problems : column generation

Time-indexed formulations for single-machine scheduling problems have received a lot of attention, because the linear program relaxations provide strong bounds. Unfortunately, time-indexed formulations have one major disadvantage: their size. Even for relatively small instances the number of constraints and the number of variables can be large. In this paper, we discuss how Dantzig-Wolfe decomposition techniques can be applied to alleviate the dificulties associated with the size of time-indexed formulations and that the application of these techniques still allows the use of cut generation techniques