Computation of approximate α-points for large scale single machine scheduling problem

Publication Type:
Journal Article
Citation:
Computers and Operations Research, 2008, 35 (10), pp. 3262 - 3275
Issue Date:
2008-10-01
Filename Description Size
Thumbnail2012007930OK.pdf232.3 kB
Adobe PDF
Full metadata record
This paper studies the linear programming (LP) relaxation of xjt-formulation of the single machine scheduling problem 1 | rj | ∑ wj Cj. 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. © 2007 Elsevier Ltd. All rights reserved.
Please use this identifier to cite or link to this item: