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

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

2 Citationer (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.

OriginalsprogEngelsk
TidsskriftEngineering Optimization
Vol/bind54
Udgave nummer8
Sider (fra-til)1426-1440
Antal sider15
ISSN0305-215X
DOI
StatusUdgivet - 2022

Bibliografisk note

Funding Information:
This research was partially funded by Airbus Defence & Space.

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

Fingeraftryk

Dyk ned i forskningsemnerne om 'Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity'. Sammen danner de et unikt fingeraftryk.

Citationsformater