An improvement on the Migrating Birds Optimization with a problem-specific neighboring function for the multi-objective task allocation problem |
| |
| Affiliation: | 1. Department of Computer Science and Engineering, University of Dhaka, Bangladesh;2. ICube Laboratory, University of Strasbourg, France;1. School of Science & Technology, International Hellenic University, Thessaloniki, Greece;2. Department of Informatics, Aristotle University of Thessaloniki, Thessaloniki, Greece;3. Information Technologies Institute, Centre of Research & Technology Hellas, Thessaloniki, Greece;4. Ubitech Ltd., Athens, Greece;1. Tridimensional Technology Division, Center for Information Technology Renato Archer, Campinas-SP 13069-901, Brazil;2. Institute of Computing, University of Campinas, Campinas-SP 13083-852, Brazil;1. Department of Electrical and Computer Engineering, Curtin University, Australia;2. Digital Productivity Flagship of the Commonwealth Scientific and Industrial Research Organisation (CSIRO), Hobart, Australia;1. Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, China;2. Department of Computer Science and Software Engineering, Laval University, Canada;2. Telematics Engineering Department, University of Cauca, Sector Tulcán, Popayán, Colombia;3. System Engineering Department, University of Cauca, Sector Tulcán, Popayán, Colombia;4. Institute of Informatics, Federal University of Rio Grande do Sul (UFRGS), Porto Alegre, Brazil;5. Intelligent Management Systems Group, Foundation University of Popayán, Colombia\n |
| |
| Abstract: | Allocating tasks to processors is a well-known NP-Hard problem in distributed computing systems. Due to the lack of practicable exact solutions, it has been attracted by the researchers working on heuristic-based suboptimal search algorithms. With the recent inclusion of multiple objectives such as minimizing the cost, maximizing the throughput and maximizing the reliability, the problem gets even more complex and an efficient approximate method becomes more valuable. In this work, I propose a new solution for the multi-objective task allocation problem. My solution consists in designing a problem-specific neighboring function for an existing metaheuristic algorithm that is proven to be successful in quadratic assignment problems. The neighboring function, namely greedy reassignment with maximum release (GR-MR), provides a dynamic mechanism to switch the preference of the search between the exploration and exploitation. The experiments validate both that the quality of the solutions are close to the optimal and the proposed method performs significantly better comparing to three other metaheuristic algorithms. Neighboring functions being the common reusable components of metaheuristic algorithms, GR-MR can also be utilized by other metaheuristic-based solutions in the future. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
