An LP-based heuristic procedure for the generalized assignment problem with special ordered sets

An LP-based heuristic procedure for the generalized assignment problem with special ordered sets

0.00 Avg rating0 Votes
Article ID: iaor20083394
Country: United Kingdom
Volume: 34
Issue: 8
Start Page Number: 2359
End Page Number: 2369
Publication Date: Aug 2007
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

The generalized assignment problem with special ordered sets (GAPS2), is the problem of allocating n tasks to m time-periods, where each task must be assigned to a time-period, or shared between two consecutive time-periods. For reasonably large values of m and n the NP-hard combinatorial problem GAPS2 becomes intractable for standard mathematical programming software, hence there is a need for heuristic algorithms to solve such problems. It will be shown how an LP-based heuristic developed previously for the well-established generalized assignment problem can be modified and extended to solve GAPS2. Encouraging results, in terms of speed and accuracy, in particular when compared to an existing heuristic for GAPS2, are described.

Reviews

Required fields are marked *. Your email address will not be published.