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

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.

Keywords:

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

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Data availability: the data for the problem instances generated are openly available at https://doi.org/10.17632/njyxh337cc.1.

Additional information

Funding

This research was partially funded by Airbus Defence & Space.