Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity

Mohamed El Yafrani, Inkyung Sung*, Bernhard Krach, Fotios Katsilieris, Peter Nielsen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

1 Citation (Scopus)

Abstract

In practice, allocating tasks to resources is often tackled in (near) real-time due to the latency of the task information and sudden task arrivals into a system. Therefore, the problem must be solved within a very short time budget, when tasks are urgent or idle resources are critical to the system's performance. Local search algorithms could be a good solution to this issue. These algorithms usually focus the search on limited solution areas by applying local updates on an incumbent solution. To investigate the feasibility and performance of applying a local search algorithm to resource allocation, a special case of the Generalized Assignment Problem (GAP) is modelled, where task profits are independent of the resources assigned and resources' capacities are identical. Then the performance of a local search algorithm to the target problems is examined empirically, characterizing the features of the GAP that make the problem hard for heuristics.

Original languageEnglish
JournalEngineering Optimization
Volume54
Issue number8
Pages (from-to)1426-1440
Number of pages15
ISSN0305-215X
DOIs
Publication statusPublished - 2022

Bibliographical note

Publisher Copyright:
© 2021 Informa UK Limited, trading as Taylor & Francis Group.

Keywords

  • Generalized assignment problem
  • identical resource capacity
  • iterative local search
  • real-time decision-making
  • resource-independent task profits

Fingerprint

Dive into the research topics of 'Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity'. Together they form a unique fingerprint.

Cite this