Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
473998 | Computers & Operations Research | 2008 | 14 Pages |
Abstract
This paper studies the linear programming (LP) relaxation of xjtxjt-formulation of the single machine scheduling problem 1|rj|∑wjCj1|rj|∑wjCj. The Lagrangian relaxation approach is proposed to cope with the computational difficulties for large problems. Since it can still be time consuming if highly accurate LP relaxation is required, the effect of approximate solution is studied with respect to the αα-point heuristic. A two-stage proximal bundle algorithm is designed for the computation of the approximate solution. Results of numerical experiments show the efficiency of the proposed algorithm for large problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Han Yu Gu,