Theoretical Paper
Journal of the Operational Research Society (2008) 59, 812–822; doi:10.1057/palgrave.jors.2602413 Published online 4 April 2007
A variable neighbourhood search algorithm for the constrained task allocation problem
- 1Universitat Politècnica de Catalunya (UPC), Barcelona, Spain
- 2University of Southampton, Southampton, UK
Correspondence: A Lusa, Research Institute IOC, Av. Diagonal 647 (edif. ETSEIB), p. 11, 08028 Barcelona, Spain. E-mail: amaia.lusa@upc.edu
Received March 2005; Accepted January 2007; Published online 4 April 2007.
Abstract
A variable neighbourhood search algorithm that employs new neighbourhoods is proposed for solving a task allocation problem whose main characteristics are: (i) each task requires a certain amount of resources and each processor has a capacity constraint which limits the total resource of the tasks that are assigned to it; (ii) the cost of solution includes fixed costs when using processors, task assignment costs, and communication costs between tasks assigned to different processors. A computational study shows that the algorithm performs well in terms of time and solution quality relative to other local search procedures that have been proposed.
Keywords:
task allocation problem, variable neighbourhood search, local search
