Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Time-Indexed Formulations for Machine Scheduling Problems: Column Generation

Time-Indexed Formulations for Machine Scheduling Problems: Column Generation 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png INFORMS Journal on Computing INFORMS

Time-Indexed Formulations for Machine Scheduling Problems: Column Generation

14 pages

Loading next page...
 
/lp/informs/time-indexed-formulations-for-machine-scheduling-problems-column-VbGbP4NjAo

References (18)

Publisher
INFORMS
Copyright
Copyright © INFORMS
Subject
Research Article
ISSN
1091-9856
eISSN
1526-5528
DOI
10.1287/ijoc.12.2.111.11896
Publisher site
See Article on Publisher Site

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.

Journal

INFORMS Journal on ComputingINFORMS

Published: May 1, 2000

Keywords: Keywords : scheduling ; time-indexed formulation ; dantiz-wolfe decompositon ; column generation

There are no references for this article.