Please use this identifier to cite or link to this item: https://hdl.handle.net/11147/8790
Title: Scalable parallel implementation of migrating birds optimization for the multi-objective task allocation problem
Authors: Öz, Dindar
Öz, Işıl
Öz, Işıl
Izmir Institute of Technology. Computer Engineering
Keywords: Parallel algorithm
Combinatorial optimization
Task allocation problem
Migrating birds optimization
Issue Date: Mar-2021
Publisher: Springer Verlag
Abstract: As the distributed computing systems have been widely used in many research and industrial areas, the problem of allocating tasks to available processors in the system efficiently has been an important concern. Since the problem is proven to be NP-hard, heuristic-based optimization techniques have been proposed to solve the task allocation problem. Particularly, the current cloud-based systems have been grown massively requiring multiple features like lower cost, higher reliability, and higher throughput; therefore, the problem has become more challenging and approximate methods have gained more importance. Migrating birds optimization (MBO) algorithm offers successful solutions, especially for quadratic assignment problems. Inspired by the movement of the birds, it exhibits good results by its population-based approach . Since the algorithm needs to deal with many individuals in the population, and the neighbor solution generation phase takes substantial time for large problem instances, we need parallelism to have execution time improvements and make the algorithm practical for large-scale problems. In this work, we propose a scalable parallel implementation of the MBO algorithm, PMBO, for the multi-objective task allocation problem. We redesigned the implementation of the MBO algorithm so that its computationally heavy independent tasks are executed concurrently in separate threads. We compare our implementation with three parallel island-based approaches. The experimental results demonstrate that our implementation exhibits substantial solution quality improvements for difficult problem instances as the computing resources, namely parallelism, increase. Our scalability analysis also presents that higher parallelism levels offer larger solution improvement for the PMBO over the island-based parallel implementations on very hard problem instances.
URI: https://doi.org/10.1007/s11227-020-03369-w
https://hdl.handle.net/11147/8790
ISSN: 0920-8542
1573-0484
Appears in Collections:Computer Engineering / Bilgisayar Mühendisliği
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Files in This Item:
File SizeFormat 
Öz-Öz2021_Article_Scalable.pdf
  Until 2024-01-01
1.86 MBAdobe PDFView/Open    Request a copy
Show full item record

CORE Recommender

WEB OF SCIENCETM
Citations

2
checked on Sep 18, 2021

Page view(s)

36
checked on Sep 20, 2021

Google ScholarTM

Check

Altmetric


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.