Research Area: Metaheuristic Computing
The task assignment problem (TAP) is one of the standard combinatorial optimization problems (COPs) in the field of discrete optimization. TAP is known to be an NP-complete problem due to the difficulty to obtain the exact solution of it in polynomial time. Thus, it is essential to develop and/or propose an optimization algorithm to solve this problem. In TAPs, a set of tasks is assigned to a set of machines to both effectively minimize the communication and execution cost. This paper presents a modified Salp Swarm Algorithm (SSA), to solve not only task assignment problems but also, fundamental combinatorial optimization problems in engineering and real-world scientific domains. The modified salp algorithm takes place in the integration with the Local Refinement Heuristic (LRH) approach to enhance a given assignment along with operators. The modified algorithm is named Modified Salp Local Refinement Heuristic (MSLRH). To the best of our knowledge, this paper is the first of its kind to attempt using the SSA in task assignment problems. The MSLRH algorithm is tested on different benchmark datasets (tree structure and general graph), including various tasks and machines for each dataset. In addition, it compared with the most known meta-heuristic algorithms such as the Genetic Algorithm (GA), Particle Swarm Optimization (PSO) algorithm, and Jaya algorithm (JAYA) to investigate the effectiveness of the MSLRH algorithm in terms of average assignment allocation cost. From tree structure dataset (e.g., 200 tasks assigned to 8 machines), the proposed MSLRH algorithm has achieved a minimum average assignment cost better than GA by 62% and better than PSO and JAYA by 42%. From the general graph dataset (e.g., 209 tasks assigned to 16 machines), the proposed MSLRH algorithm has better results than other algorithms up to 60%. From various and extensive experimental results, the proposed algorithm has proven the effectiveness in solving the task assignment problem.
Keywords:
task assignment problem
combinatorial optimization problems
polynomial time
Local Refinement Heuristic
Genetic Algorithm
Particle Swarm Optimization
Jaya algorithm
Author(s) Name: Walaa H. El-Ashmawi, Ahmed F. Ali
Journal name: Applied Soft Computing
Conferrence name:
Publisher name: Elsevier
DOI: 10.1016/j.asoc.2020.106445
Volume Information: Volume 94
