Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
An LP-Based Hybrid Heuristic Procedure for the Generalized Assignment Problem with Special Ordered Sets
verfasst von : Alan P. French, John M. Wilson
Erschienen in: Hybrid Metaheuristics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 large values of
m
and
n
the NP-hard combinatorial problem GAPS2 becomes intractable for standard mathematical programming software such as CPLEX or XPRESS
MP
and it is unlikely that a proven optimal solution can be obtained. There is thus a need for heuristic algorithms to solve such problems. It will be shown how a combination of linear programming techniques and two heuristics forming a hybrid can be used to solve GAPS2. Good results, in terms of speed and accuracy, on large problem instances have been obtained. In particular when compared to an existing heuristic for GAPS2, the results look particularly promising.