Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

Time-Indexed Formulations and the Total Weighted Tardiness Problem

Time-Indexed Formulations and the Total Weighted Tardiness Problem Asolution approach based on the column-generation technique is presented for solving a time-indexed formulation of the total weighted tardiness problem. An acceleration strategy based on a decomposition of the time horizon into subperiods, where each subperiod is associated with a subproblem of the column-generation approach, is used to solve the linear relaxation. Branching strategies and dominance rules are also applied to find the optimal integer solution. Using this new approach, it is possible to solve to optimality 117 out of 125 open problems of the OR-Library. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png INFORMS Journal on Computing INFORMS

Time-Indexed Formulations and the Total Weighted Tardiness Problem

10 pages

Loading next page...
 
/lp/informs/time-indexed-formulations-and-the-total-weighted-tardiness-problem-Ze0ez0qg0H

References (33)

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

Abstract

Asolution approach based on the column-generation technique is presented for solving a time-indexed formulation of the total weighted tardiness problem. An acceleration strategy based on a decomposition of the time horizon into subperiods, where each subperiod is associated with a subproblem of the column-generation approach, is used to solve the linear relaxation. Branching strategies and dominance rules are also applied to find the optimal integer solution. Using this new approach, it is possible to solve to optimality 117 out of 125 open problems of the OR-Library.

Journal

INFORMS Journal on ComputingINFORMS

Published: Feb 1, 2008

Keywords: Keywords : time-indexed formulation ; single-machine scheduling problem ; Dantzig-Wolfe decomposition ; time-decomposition

There are no references for this article.