Time-indexed formulations for machine scheduling problems : column generation

J.M. Akker, van den, C.A.J. Hurkens, M.W.P. Savelsbergh

Research output: Contribution to journalArticleAcademicpeer-review

122 Citations (Scopus)
2 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)111-124
JournalINFORMS Journal on Computing
Volume12
Issue number2
DOIs
Publication statusPublished - 2000

Fingerprint Dive into the research topics of 'Time-indexed formulations for machine scheduling problems : column generation'. Together they form a unique fingerprint.

Cite this