BRCE: bi-roles co-evolution for energy-efficient distributed heterogeneous permutation flow shop scheduling with flexible machine speed

Kuihua Huang, Rui Li, Wenyin Gong, Rui Wang, Heng WeiComplex 2023 · DOI

TL;DR

Researchers have developed BRCE (Bi-Roles Co-Evolution), a novel algorithm that optimizes distributed manufacturing schedules by splitting its search population into "producers" (explorers) and "consumers" (exploiters). By combining specialized local search strategies with a smart energy-saving tactic that slows down non-critical machines, BRCE significantly outperforms current state-of-the-art algorithms in reducing both production time and energy consumption.

The Challenge: Distributed Heterogeneous Scheduling

In the era of globalized production, jobs are often distributed across multiple factories—a setup known as Distributed Permutation Flow Shop Scheduling (DPFSP). This paper tackles a particularly complex version: DHPFSP-FMS.

  1. Heterogeneous (H): Unlike many models that assume every factory is identical, this model acknowledges that machines in different factories have different capabilities and processing times.
  2. Flexible Machine Speed (FMS): Modern machines allow operators to adjust speeds. Faster speeds reduce the makespan (total production time) but exponentially increase Total Energy Consumption (TEC).

The goal is to find the "Pareto front"—the set of optimal trade-offs where speed cannot be improved without increasing energy use. Existing algorithms often get stuck in "local optima," missing the most efficient solutions.

An example of a distributed scheduling solution across two factories, illustrating the assignment of operations to machines over time.

Methods: The BRCE Framework

The core innovation is the Bi-Roles Co-evolution (BRCE) framework, which mimics a biological producer-consumer relationship to balance computation:

  • The Producer Swarm: Focuses on "global search." It explores the wide landscape of possible schedules to maintain high genetic diversity, preventing the algorithm from narrowing its focus too early.
  • The Consumer Swarm: Focuses on "local search." It "absorbs" high-quality solutions from the producers and applies intense, problem-specific refinements to polish them.
Flowchart of the Bi-Roles Co-Evolution (BRCE) algorithm, showing the interaction between the Producer and Consumer swarms.

Key Algorithmic Strategies

  • Heuristic Initialization: Rather than starting randomly, BRCE uses three rules (Maximum Speed, Minimum Speed, and Balance Load) to ensure the initial population covers the full spectrum of the speed-vs-energy trade-off.
  • Knowledge-Driven Local Search: Five specific neighborhood structures target the "critical path" of production—the sequence of jobs that determines the final completion time.
  • Energy-Saving Strategy: Once a schedule is determined, the algorithm identifies "idle gaps" where a machine is waiting. It then calculates if it can slow down the previous operation to fill that gap, reducing energy use without delaying the overall project.

Key Results and Insights

The authors compared BRCE against four major algorithms (NSGA-II, MOEA/D, PMMA, and KCA) using 22 new instances based on the classic Taillard benchmark.

  • Superior Performance: BRCE achieved the highest Hypervolume (HV) in almost all instances, meaning it found a more diverse and higher-quality set of optimal solutions.
  • Statistical Significance: Using the Friedman rank test, BRCE ranked 1st for both Hypervolume and Spread.
  • The "Free" Energy Lunch: The authors proved that slowing down machines during non-critical operations is a "win-win"—it lowers energy consumption without affecting the makespan.

Future Directions

While BRCE is highly effective, future work will explore Distributed Assembly problems, where parts from different factories are assembled at a final destination. Additionally, the researchers aim to account for dynamic environments (e.g., machine breakdowns) and social impacts like worker fatigue alongside energy and time.

Summary updated

Abstract

Abstract Distributed manufacturing is the mainstream model to accelerate production. However, the heterogeneous production environment makes engineer hard to find the optimal scheduling. This work investigates the energy-efficient distributed heterogeneous permutation flow scheduling problem with flexible machine speed (DHPFSP-FMS) with minimizing makespan and energy consumption simultaneously. In DHPFSP-FMS, the local search misleads the population falling into local optima which reduces the convergence and diversity. To solve this problem, a bi-roles co-evolutionary algorithm is proposed which contains the following improvements: First, the global search and local search is divided into two swarms producer and consumer to balance computation. Second, three heuristic rules are designed to get a high-quality initialization population. Next, five problem-based local search strategies are designed to accelerate converging. Then, an efficient energy-saving strategy is presented to save energy. Finally, to verify the performance of the proposed algorithm, 22 instances are generated based on the Taillard benchmark, and a number of numerical experiments are adopted. The experiment results state that our algorithm is superior to the state-of-arts and more efficient for DHPFSP-FMS.
BibTeX
@inproceedings{huang2023brce,
  author = {Kuihua Huang and Rui Li and Wenyin Gong and Rui Wang and Heng Wei},
  title = {{BRCE: bi-roles co-evolution for energy-efficient distributed heterogeneous permutation flow shop scheduling with flexible machine speed}},
  booktitle = {Complex},
  year = {2023},
  doi = {10.1007/s40747-023-00984-x},
}
Figure