  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.
