An efficient algorithm for task allocation with the budget constraint
Date
2022
Authors
Li, Q.
Li, M.
Vo, B.Q.
Kowalczyk, R.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Expert Systems With Applications, 2022; 210(118279):1-13
Statement of Responsibility
Conference Name
Abstract
This paper studies a heterogeneous task allocation problem with the budget constraint. Existing works on task allocation mainly tackle this well-known NP-hard problem from an optimisation perspective. They have not been able to cater to the extra needs of scalability and robustness in large-scale systems. Furthermore, some general allocation mechanisms do not consider system budget and agent cost. Thus, they cannot guarantee to obtain valid solutions when the budget is constrained. This paper models the task allocation problem as a game whose players are the agents to be assigned to the teams working on the tasks, and align the task allocation objective (i.e., system optimality) with the game-theoretic solution concept of Nash equilibrium. Based on this formulation, a novel algorithm, called CF, is proposed in this paper.
CF searches for a valid Nash equilibrium solution using a greedy strategy that aims to improve system utility while takes into consideration of the overall system budget constraint. CF is a scalable, anytime, and monotonic algorithm, which in turn, makes it robust for the deployment in large-scale systems. CF can also be used as a local search algorithm for improving the quality of any existing valid allocation solution. Comprehensive empirical studies have been carried out in this paper to demonstrate that CF is effective in all budget states and achieves a solution quality better than the state-of-the-art algorithms.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2022 Elsevier Ltd