Time-indexed formulations for machine scheduling problems: Column generation

Time-indexed formulations for machine scheduling problems: Column generation

0.00 Avg rating0 Votes
Article ID: iaor20012323
Country: United States
Volume: 12
Issue: 2
Start Page Number: 111
End Page Number: 124
Publication Date: Mar 2000
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: programming: integer
Abstract:

Time-indexed formulations for machine scheduling problems have received a great deal of attention; not only do the linear programming relaxations provide strong lower bounds, but they are good guides for approximation algorithms as well. 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, at least partly, the difficulties associated with the size of time-indexed formulations. In addition, we show that the application of these techniques still allows the use of cut generation techniques.

Reviews

Required fields are marked *. Your email address will not be published.