Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity. Issue 8 (3rd August 2022)

• Record Type: Journal Article
• Authors: El Yafrani, Mohamed; Sung, Inkyung; Krach, Bernhard; Katsilieris, Fotios; Nielsen, Peter
• Is Part Of: Engineering optimization. Volume 54:Issue 8(2022)
• Page Start: 1426
• Page End: 1440
• Publication Date: 2022-08-03
• Subjects: Generalized assignment problem -- iterative local search -- real-time decision-making -- resource-independent task profits -- identical resource capacity; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2021.1940991
• Languages: English
• ISSNs: 0305-215X

Abstract

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.