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.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Engineering Optimization |
Vol/bind | 54 |
Udgave nummer | 8 |
Sider (fra-til) | 1426-1440 |
Antal sider | 15 |
ISSN | 0305-215X |
DOI | |
Status | Udgivet - 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.Forskningsdatasæt
-
Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity
El Yafrani, M. (Bidrager), Sung, I. (Ophavsperson), Krach, B. (Ophavsperson), Katsilieris, F. (Ophavsperson) & Nielsen, P. (Ophavsperson), Taylor & Francis, 8 jul. 2021
DOI: 10.6084/m9.figshare.14931913, https://tandf.figshare.com/articles/journal_contribution/Analysis_of_a_local_search_heuristic_for_the_generalized_assignment_problem_with_resource-independent_task_profits_and_identical_resource_capacity/14931913
Datasæt
-
Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity
El Yafrani, M. (Bidrager), Sung, I. (Ophavsperson), Krach, B. (Ophavsperson), Katsilieris, F. (Ophavsperson) & Nielsen, P. (Ophavsperson), Taylor & Francis, 2021
DOI: 10.6084/m9.figshare.14931913.v1, https://tandf.figshare.com/articles/journal_contribution/Analysis_of_a_local_search_heuristic_for_the_generalized_assignment_problem_with_resource-independent_task_profits_and_identical_resource_capacity/14931913/1
Datasæt