💻 computer science

Joint Planning of Assembly Sequence Planning and Assembly Line Balancing Based on Improved Artificial Fish Swarm Algorithm

This paper proposes a Pareto hybrid artificial fish swarm algorithm that integrates improved feeding mechanisms and simulated annealing to simultaneously optimize assembly sequence planning and assembly line balancing by minimizing balancing loss, switching times, and beat time.

Original authors: YongGui Shi, Wei Zhang

Published 2026-07-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: YongGui Shi, Wei Zhang

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a busy factory assembly line, tasked with building a complex machine. You have two big headaches to solve at the same time:

The "Order of Operations" Puzzle (Assembly Sequence Planning): In what exact order should you screw, bolt, and snap the parts together? If you try to put the roof on before the walls, you're stuck. You need the perfect recipe.
The "Workload Balancing" Puzzle (Assembly Line Balancing): You have a team of workers (workstations). You need to hand out the tasks so that no one is sitting idle while another is drowning in work, and everyone finishes their shift at roughly the same time.

The problem is that these two puzzles are deeply connected. If you change the order of assembly, you might change how much work each person has to do. If you try to solve them separately, you might end up with a plan that looks good on paper but is a nightmare in reality.

This paper proposes a new way to solve both puzzles simultaneously using a clever computer algorithm inspired by nature.

The Problem: A "Combinatorial Explosion"

The authors explain that figuring out the best way to build a product is like trying to find a needle in a haystack, but the haystack keeps growing exponentially. If you have 20 parts, the number of possible ways to assemble them is astronomical. Traditional methods are either too slow (trying every single possibility) or too messy (getting stuck in a "local optimum," which is like finding a small hill and thinking it's the highest mountain).

The Solution: A "Smart Fish Swarm"

To tackle this, the authors created a Hybrid Artificial Fish Swarm Algorithm (HAFSA). Here is how they explain it using simple analogies:

The Fish School: Imagine a school of fish swimming in a pond. Each fish represents a possible solution (a specific plan for how to build the product).
Foraging (Finding Food): The fish swim around looking for "food," which represents a better, more efficient assembly plan. If a fish finds a spot with more food (a better plan), it swims there.
Swarming (Crowding): Fish also like to stick together in groups. If a fish sees a group of friends in a rich feeding area, it swims toward them. This helps the whole group find good solutions quickly.
The "Tail-Chasing" Behavior: If one fish finds a really great spot, the others chase after it.

The Catch: Sometimes, the fish get too comfortable in one spot and stop looking for better food elsewhere. They get stuck in a "local optimum."

The Innovation: Mixing in "Bird Hunting" (PSO)

To fix the fish getting stuck, the authors mixed in a technique from Particle Swarm Optimization (PSO), which is based on how birds hunt.

The Analogy: While the fish are swimming, the algorithm occasionally makes them "jump" or "fly" like birds. This introduces a bit of randomness and helps the school escape a small, mediocre pond and fly over to a potentially better lake.
The Pareto Idea: The algorithm doesn't just look for one perfect answer. Instead, it looks for a "menu of options" (a Pareto set). It finds plans that offer the best trade-offs between:
- Balance: Making sure no workstation is overloaded.
- Switching: Minimizing how often workers have to change tools or turn their bodies in different directions (which wastes time).
- Speed: Getting the job done as fast as possible.

How They Tested It

The researchers tested their new "Fish-Bird" algorithm on a real-world product assembly example involving 21 different parts. They compared their method against:

The standard "Fish" algorithm (AFSA).
The standard "Bird" algorithm (PSO).

The Results:

The Fish-Bird team won. Their hybrid algorithm found solutions that were just as fast as the others but required fewer tool changes and direction switches.
Efficiency: It reduced the total number of "switches" (changing tools or directions) from 24 (in the standard fish method) down to 22.
Balance: It kept the work evenly distributed among the workers, preventing bottlenecks.

The Bottom Line

The paper claims that by combining the "swarming" behavior of fish with the "jumping" ability of birds, and by using a smart map (called a "constraint matrix") to understand how parts fit together, they can generate better assembly plans faster. This helps factories save time, reduce wasted motion, and build products more efficiently without getting lost in the math.

Technical Summary: Joint Planning of Assembly Sequence Planning and Assembly Line Balancing Based on Improved Artificial Fish Swarm Algorithm

Problem Statement
The paper addresses the complex challenge of simultaneously optimizing Assembly Sequence Planning (ASP) and Assembly Line Balancing (ALB). These two problems are inherently coupled; ASP determines the optimal order of assembling components to minimize costs, while ALB assigns these tasks to workstations to minimize idle time and balance the line. Both are classified as Non-deterministic Polynomial Hard (NP-hard) problems with polynomial complexity. The authors note that optimizing these problems separately often leads to suboptimal overall system performance. Furthermore, existing methods for ASP often suffer from "combinatorial explosion" when using graph search, and traditional matrix generation methods can be time-consuming and inefficient for complex products. Additionally, many ALB studies fail to account for the dynamic changes in assembly tools and directions inherent in ASP, leading to balancing results that may be impractical in actual assembly processes.

Methodology
The proposed approach integrates ASP and ALB into a unified multi-objective optimization framework using a Hybrid Artificial Fish Swarm Algorithm (HAFSA). The methodology is structured in three main phases:

ASP Modeling via BOM and Constraint Matrix:
- Instead of relying solely on AND/OR graphs which cause combinatorial explosion, the authors construct a modular assembly constraint matrix based on the Bill of Materials (BOM) hierarchy diagram.
- The assembly constraint matrix ( $E(G)$ ) is defined using a directed graph where elements represent parts and values indicate priority and connection relationships (e.g., $1$ for direct connection before, $-1$ for after, $9$ for non-direct connection before, etc.).
- Sub-assembly Partitioning: An algorithm analyzes the BOM hierarchy to determine the independence of sub-assemblies. It iteratively checks column values in the constraint matrix; if a group of parts shows consistent non-positive or non-negative relationships with external parts, they are identified as independent sub-assemblies. If not, the algorithm peels off specific rows to create feasible independent modules.
- Internal Planning: Within each identified sub-assembly, a specific swapping and solidifying algorithm is used to generate feasible internal assembly sequences based on the constraint matrix values.
Multi-Objective Optimization Model:
The integrated model seeks to minimize three objective functions simultaneously:
- Workstation Time Balance: Minimizing the variance between the production rhythm ( $T_c$ ) and individual workstation times ( $T_m$ ).
- Switching Costs: Minimizing the total number of assembly tool changes and assembly direction changes between consecutive tasks.
- Maximum Workstation Time: Minimizing the cycle time (the maximum time among all workstations).
Hybrid Artificial Fish Swarm Algorithm (HAFSA):
To solve this multi-objective problem, the authors propose a HAFSA that combines the Artificial Fish Swarm Algorithm (AFSA) with Particle Swarm Optimization (PSO) and Pareto optimality concepts.
- Encoding/Decoding: Assembly tasks are encoded based on priority weights within sub-assemblies. Decoding assigns tasks to workstations sequentially, opening new workstations only when the cycle time constraint is exceeded.
- Pareto Solution Set: An external repository stores non-dominated solutions. A crowding distance mechanism is used to maintain diversity and manage the repository size.
- Algorithm Improvements:
  - Behavioral Logic: The algorithm follows a serial search order: tail-chasing, foraging, clustering, and random behavior.
  - PSO Integration: To prevent the algorithm from falling into local optima (a known weakness of standard AFSA), PSO operations are introduced. This includes using a Metropolis criterion (simulated annealing concept) to accept deteriorating solutions with a certain probability, allowing the search to escape local traps.
  - Dynamic Inertia: The "visual field" (search range) of the artificial fish is dynamically adjusted using an inertia weight ( $\omega$ ) inspired by PSO, starting with a large field for global exploration and narrowing for local convergence.

Key Contributions

Integrated Framework: The paper proposes a method to jointly plan ASP and ALB rather than treating them sequentially, acknowledging their interdependence.
Matrix-Based Sub-assembly Identification: A novel approach using the BOM hierarchy and assembly constraint matrix to automatically identify independent sub-assemblies, reducing the search space and avoiding combinatorial explosion.
HAFSA Algorithm: The development of a Pareto-based Hybrid Artificial Fish Swarm Algorithm that improves upon standard AFSA by incorporating PSO operations and simulated annealing principles to enhance global search capabilities and avoid local optima.
Multi-Objective Handling: The explicit inclusion of tool changes and direction changes as optimization objectives alongside traditional time balancing.

Results
The proposed method was validated using a case study of a specific product with 21 assembly tasks. The HAFSA (labeled AFSA&PSO) was compared against a standard Particle Swarm Optimization (PSO) algorithm and a standard Artificial Fish Swarm Algorithm (AFSA).

Workstation Balance: All three algorithms achieved the same maximum workstation operation time of 31 minutes. However, the inter-station balance value for HAFSA was 0.69, which was superior to the PSO result (0.75) and equal to the standard AFSA (0.69).
Switching Efficiency: The HAFSA achieved a total of 22 changes (tool + direction). This was equal to the PSO result (22) but significantly better than the standard AFSA, which resulted in 24 changes.
Conclusion from Data: The HAFSA demonstrated the ability to find a Pareto-optimal solution that balances station times effectively while minimizing the total number of operational switches, outperforming the standard AFSA in switch reduction and matching or exceeding PSO in balance metrics.

Significance and Claims
The paper claims that its primary significance lies in improving the efficiency and feasibility of joint ASP and ALB planning. By utilizing the BOM hierarchy to pre-process sub-assemblies, the method makes the search space more targeted, thereby improving solution efficiency and avoiding the generation of large numbers of infeasible solutions.

The authors assert that the proposed HAFSA is more effective than traditional AFSA and PSO algorithms for this specific multi-objective problem. The integration of PSO operations into the fish swarm behavior allows the algorithm to better escape local optima, resulting in higher-quality Pareto solutions. The study concludes that this integrated approach provides a more reasonable and efficient planning method for complex product assembly lines, particularly where tool and direction changes are critical cost factors.