Abstract
Flexible Flow Shop (FFS) scheduling is a critical NP-hard problem in industrial manufacturing, particularly when scaled to hundreds of jobs. Traditional Genetic Algorithms (GAs) often suffer from premature convergence and high execution times in these large-scale scenarios. This paper introduces a Dual Heterogeneous Island Genetic Algorithm (DHIGA) that leverages hybrid multi-core CPU and GPU platforms. By running distinct GA models—a Cellular GA on GPUs and a Pseudo GA on CPUs—and linking them with an adaptive migration policy, the proposed approach achieves higher solution quality and greater stability than standalone parallel methods.
Introduction: The Challenge of Large-Scale Scheduling
The Flexible Flow Shop (FFS) scheduling problem involves routing jobs through multiple processing stages, where each stage offers several parallel machines. The primary objectives are typically minimizing the "make-span" (total completion time) and "tardiness" (lateness relative to due dates).
As the number of jobs increases (e.g., 300+), the search space grows exponentially, making FFS NP-hard. Genetic Algorithms are effective heuristics, but they face two significant hurdles at scale:
- Premature Convergence: The population may lose diversity too quickly, causing the algorithm to get trapped in local optima.
- Execution Time: The computational overhead for large populations becomes prohibitive on standard hardware.
Methodology: Dual Heterogeneous Islands
To address these challenges, the researchers developed a "Dual Island" model that embraces heterogeneity at both the algorithmic and hardware levels.
1. Algorithmic Diversity
The population is divided into two islands with contrasting evolutionary behaviors:
- Island A (Cellular GA): Individuals are organized on a 2D grid, restricting mating to immediate neighbors. This decentralized structure is highly effective at maintaining population diversity.
- Island B (Pseudo GA): This island employs a "complementary parent strategy" to enhance search capabilities, ensuring that diverse genetic traits are preserved throughout the evolution process.
2. Hardware Mapping and Optimization
The architecture is optimized for modern hybrid systems:
- GPU (CUDA): Island A's Cellular GA is mapped to the GPU. The algorithm's 2D grid structure aligns with GPU thread blocks, utilizing high-speed texture memory for efficient neighbor lookups.
- Multi-core CPU (OpenMP + SIMD): Island B's Pseudo GA runs on the CPU. To prevent the CPU from becoming a performance bottleneck, the authors implemented SIMD (Single Instruction, Multiple Data) vectorization (SSE2) to accelerate binary integer processing.
3. Penetration-Inspired Migration
Information exchange between islands is governed by a migration policy inspired by "penetration theory." Instead of fixed-interval swaps, the system adaptively determines the direction, rate, and timing of migration based on the fitness ratio between islands. This ensures that beneficial genes are shared without causing genetic drift that would homogenize the two distinct populations.
Experimental Results and Discussion
The DHIGA was evaluated using large-scale synthetic FFS instances featuring 300 jobs across 4 stages, with 2 machines per stage.
Key Findings
- Superior Solution Quality: The heterogeneous approach outperformed standalone parallel models, achieving a best fitness value of 306,500, compared to approximately 314,000 for individual parallel GAs.
- Enhanced Stability: The variance in results was significantly lower for the dual-island approach (2.0M) compared to the standalone Cellular GA (6.7M), indicating higher reliability.
- The "Elbow" Phenomenon: Convergence curves revealed sudden drops in error rates—referred to as "elbows"—coinciding with migration events. This confirms that the adaptive exchange of individuals successfully pushes the algorithm out of local optima.
- Hardware Balance: A critical insight was the necessity of SIMD optimization. Without it, the GPU would frequently idle while waiting for the CPU, highlighting that balancing computational power is as vital as the algorithm design itself.
Conclusion
The Dual Heterogeneous Island Genetic Algorithm provides a robust framework for solving massive scheduling problems by effectively utilizing hybrid hardware. By maintaining diversity through algorithmic heterogeneity and optimizing execution through hardware-specific mapping, the DHIGA offers a scalable solution for complex industrial scheduling. Future work may explore multi-island configurations and adaptation to dynamic environments.
Summary updated