New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling.
In: INFORMS Journal on Computing, Jg. 21 (2009), Heft 1, S. 167-175
Online
academicJournal
Zugriff:
In one-machine scheduling, mixed-integer program time-indexed formulations are often used to provide very good lower bounds through Lagrangian relaxations. To get an improved lower bound, we add valid cuts to a time-indexed formulation and show we still have a Lagrangian relaxation that can be solved as a shortest path in a graph. Two branch-and-bound algorithms are then presented for the earliness-tardiness scheduling problem with either common or general due dates. In both cases, our algorithms outperform the previously published approaches. [ABSTRACT FROM AUTHOR]
Titel: |
New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling.
|
---|---|
Autor/in / Beteiligte Person: | Sourd, Francis |
Link: | |
Zeitschrift: | INFORMS Journal on Computing, Jg. 21 (2009), Heft 1, S. 167-175 |
Veröffentlichung: | 2009 |
Medientyp: | academicJournal |
ISSN: | 1091-9856 (print) |
DOI: | 10.1287/ijoc.1080.0287 |
Schlagwort: |
|
Sonstiges: |
|