GPU-Based Hybrid Cellular Genetic Algorithm for Job-Shop Scheduling Problem

Abdelkader Amrane, Fatima Debbat and Khadidja Yahyaoui
Additional contact information
Abdelkader Amrane: Department of Computer Science, University Mustapha Stambouli of Mascara, Algeria
Fatima Debbat: Department of Computer Science, University Mustapha Stambouli of Mascara, Algeria
Khadidja Yahyaoui: Department of Computer Science, University Mustapha Stambouli of Mascara, Algeria

International Journal of Applied Metaheuristic Computing (IJAMC), 2021, vol. 12, issue 2, 1-15

Abstract: In task scheduling, the job-shop scheduling problem is notorious for being a combinatorial optimization problem; it is considered among the largest class of NP-hard problems. In this paper, a parallel implementation of hybrid cellular genetic algorithm is proposed in order to reach the best solutions at a minimum execution time. To avoid additional computation time and for real-time control, the fitness evaluation and genetic operations are entirely executed on a graphic processing unit in parallel; moreover, the chosen genetic representation, as well as the crossover, will always give a feasible solution. In this paper, a two-level scheme is proposed; the first and fastest uses several subpopulations in the same block, and the best solutions migrate between subpopulations. To achieve the optimal performance of the device and to reshape a more complex problem, a projection of the first on different blocks will make the second level. The proposed solution leads to speedups 18 times higher when compared to the best-performing algorithms.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/IJAMC.2021040101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jamc00:v:12:y:2021:i:2:p:1-15

Access Statistics for this article

International Journal of Applied Metaheuristic Computing (IJAMC) is currently edited by Peng-Yeng Yin

More articles in International Journal of Applied Metaheuristic Computing (IJAMC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().