A dual heterogeneous island genetic algorithm for solving large size flexible flow shop scheduling problems on hybrid multicore CPU and GPU platforms

DOI10.1155/2019/1713636MaRDI QIDQ2298113zbMATH OpenOpenAlexFDO

Authors Jia Luo, Didier El Baz

Publication date 20 February 2020

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1903.10722

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Abstract: The flexible flow shop scheduling problem is an NP-hard problem and it requires significant resolution time to find optimal or even adequate solutions when dealing with large size instances. Thus, this paper proposes a dual island genetic algorithm consisting of a parallel cellular model and a parallel pseudo model. This is a two-level parallelization highly consistent with the underlying architecture and is well suited for parallelizing inside or between GPUs and a multi-core CPU. At the higher level, the efficiency of island GAs is improved by exploring new regions within the search space utilizing different methods. In the meantime, the cellular model keeps the population diversity by decentralization and the pseudo model enhances the search ability by the complementary parent strategy at the lower level. To encourage the information sharing between islands, a penetration inspired migration policy is designed which sets the topology, the rate, the interval and the strategy adaptively. Finally, the proposed method is tested on some large size flexible flow shop scheduling instances in comparison with other parallel algorithms. The computational results show that it cannot only obtain competitive results but also reduces execution time.

Review text

Summary: The flexible flow shop scheduling problem is an NP-hard problem and it requires significant resolution time to find optimal or even adequate solutions when dealing with large size instances. Thus, this paper proposes a dual island genetic algorithm consisting of a parallel cellular model and a parallel pseudo-model. This is a two-level parallelization highly consistent with the underlying architectures and is well suited for parallelizing inside or between GPUs and a multicore CPU. At the higher level, the efficiency of the island GA is improved by exploring new regions within the search space utilizing different methods. In the meantime, the cellular model keeps the population diversity by decentralization and the pseudo-model enhances the search ability by the complementary parent strategy at the lower level. To encourage the information sharing between islands, a penetration inspired migration policy is designed which sets the topology, the rate, the interval, and the strategy adaptively. Finally, the proposed method is tested on some large size flexible flow shop scheduling instances in comparison with other parallel algorithms. The computational results show that it not only can obtain competitive results but also reduces execution time.

Recommendations

• Parallel Processing and Applied Mathematics
• Flexible job shop problem -- parallel tabu search algorithm for multi-GPU
• Parallel genetic algorithms with migration for the hybrid flow shop scheduling problem
• Solving flexible job shop scheduling problem by genetic algorithm
• An effective new island model genetic algorithm for job shop scheduling problem

Cites work

• A mixed-precision algorithm for the solution of Lyapunov equations on hybrid CPU-GPU platforms
• A novel parallel quantum genetic algorithm for stochastic job shop scheduling
• An effective new island model genetic algorithm for job shop scheduling problem
• Cellular genetic algorithm on graphic processing units
• Heterogeneous computing and parallel genetic algorithms.
• Optimal synthesis of mechanisms with genetic algorithms
• Two-Stage, Hybrid Flowshop Scheduling Problem

Cited in

(1)

• Flexible job shop problem -- parallel tabu search algorithm for multi-GPU

Describes a project that uses

Uses Software

• CUDA

This page was built for publication: A dual heterogeneous island genetic algorithm for solving large size flexible flow shop scheduling problems on hybrid multicore CPU and GPU platforms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2298113)