💻 computer science

A Block-Guided Artificial Bee Colony Algorithm for Distributed Assembly Flowshop Scheduling with Sequence-Dependent Setup Times

This paper proposes a Block-Guided Artificial Bee Colony (BG-ABC) algorithm that integrates an idle-aware block compression mechanism, a Sliding Window Upper Confidence Bound 1 (SW-UCB1) adaptive operator selection, and a critical job-focused local search to effectively minimize the makespan for the Distributed Assembly Permutation Flowshop Scheduling Problem with Sequence-Dependent Setup Times (DAPFSP-SDST).

Original authors: Ji-Feng Xu, Hong-Bo Song

Published 2026-10-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ji-Feng Xu, Hong-Bo Song

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

In the vast, interconnected world of modern manufacturing, the journey of a product often begins not in a single factory, but across a network of specialized facilities scattered around the globe. Imagine a car being built where the engines are made in one country, the electronics in another, and the final assembly happens in a third. This distributed approach offers flexibility and efficiency, but it creates a massive logistical puzzle. The challenge lies in deciding which factory should build which part, in what order those parts should be processed, and finally, how to bring them all together for assembly. Complicating this further is the reality that machines are not always ready to work immediately; they require time to clean, change tools, or adjust fixtures between tasks. The time needed for this preparation often depends entirely on which job was just finished and which one is coming next. This "sequence-dependent" nature means that a small change in the order of work can ripple through the entire system, drastically altering how long it takes to finish everything. Solving this puzzle is critical for industries ranging from automotive to furniture, as finding the most efficient schedule directly impacts costs, delivery times, and the ability to meet customer demand.

Researchers Ji-Feng Xu and Hong-Bo Song have tackled this complex scheduling problem by developing a new computational method that mimics the foraging behavior of honeybees to find the best possible production schedules. Their approach, designed specifically for scenarios where setup times vary based on the order of jobs, focuses on minimizing the total time required to complete all products, known as the makespan. The team observed that in the most efficient schedules, certain pairs of products consistently appear next to each other because they require the least amount of setup time and leave no idle waiting time for the assembly machine. To leverage this, they created a system that identifies these ideal pairs and locks them together into fixed "blocks," treating them as single units during the search for a solution. This strategy effectively shrinks the enormous number of possible schedules down to a much smaller, more manageable set, allowing the computer to focus its energy on the most promising arrangements rather than wasting time on unlikely combinations.

However, locking these blocks together carries a risk: the algorithm might get stuck in a local optimum, missing a better solution that requires breaking a block apart. To prevent this, the researchers embedded a dynamic selection system into the algorithm's "employed bee" phase. This system acts like a smart manager that watches which search strategies are working best in the current moment and shifts its attention accordingly, rather than sticking to a rigid plan. When the algorithm gets stuck, a "scout bee" mechanism steps in to dissolve the locked blocks and rebuild the schedule from scratch, ensuring the search continues to explore new possibilities. Furthermore, the researchers realized that not every part of the schedule needs the same level of attention. They directed the algorithm to focus its detailed search efforts only on the specific sequence of jobs that are causing bottlenecks, ignoring parts of the schedule that are already running smoothly. This targeted approach saves significant computing power, allowing the system to evaluate more potential solutions in the same amount of time.

The team tested their new method, which they call the Block-Guided Artificial Bee Colony algorithm, against a wide range of standard benchmark problems used by researchers in the field. These tests involved thousands of different scenarios with varying numbers of factories, machines, and products. The results showed that their method consistently outperformed existing state-of-the-art algorithms, finding schedules that were significantly shorter in duration. By combining the efficiency of grouping ideal product pairs with the adaptability of a bee-inspired search, the researchers demonstrated a robust way to handle the intricate coordination required in modern supply chains. Their work suggests that by understanding the specific structural patterns of these scheduling problems, it is possible to design intelligent tools that make complex global manufacturing networks run more smoothly and efficiently.

Technical Summary: A Block-Guided Artificial Bee Colony Algorithm for Distributed Assembly Flowshop Scheduling with Sequence-Dependent Setup Times

Problem Definition
This paper addresses the Distributed Assembly Permutation Flowshop Scheduling Problem with Sequence-Dependent Setup Times (DAPFSP-SDST). The problem models a multi-stage supply chain where $n$ jobs are processed across $f$ identical factories, each containing $m$ machines in a flowshop configuration. Upon completion, jobs are transported to a centralized facility to be assembled into $d$ products on a single assembly machine. The objective is to minimize the makespan ( $C_{max}$ ).

A critical complexity of this problem is the inclusion of Sequence-Dependent Setup Times (SDST) in both the manufacturing and assembly stages. In the manufacturing stage, setup times depend on consecutive jobs within a factory; in the assembly stage, they depend on consecutive products. The problem is identified as strongly NP-hard, requiring the simultaneous optimization of job-to-factory assignment, job sequencing within factories, and product assembly sequencing.

Methodology: The BG-ABC Algorithm
The authors propose a Block-Guided Artificial Bee Colony (BG-ABC) algorithm. The design is grounded in the observation that minimizing makespan is equivalent to minimizing the sum of total assembly setup times (TSTA) and total assembly idle times (TITA). High-quality solutions frequently exhibit adjacent product pairs that simultaneously achieve minimal SDST and zero assembly idle time.

The algorithm integrates four specific mechanisms into the standard ABC framework:

Idle-Aware Block Compression:
The algorithm identifies "compressible blocks," defined as consecutive product pairs $(\pi_l, \pi_{l+1})$ where $\pi_{l+1}$ is the SDST-minimal successor of $\pi_l$ and the idle time between them is zero. These pairs are locked into atomic blocks. The search space is reduced from permutations of individual products to permutations of these blocks, significantly shrinking the dimensionality of the search space while preserving promising structural patterns.
Adaptive Operator Selection (SW-UCB1):
In the employed bee phase, the algorithm operates on the compressed block sequence using three neighborhood operators: Swap, Insertion, and Inversion. To dynamically select the most effective operator as the search progresses, a Sliding Window Upper Confidence Bound 1 (SW-UCB1) scheme is employed. This mechanism tracks the recent rewards of each operator within a sliding window, allowing the algorithm to adapt its search strategy without the complex parameter tuning required by Q-learning.
Critical Job Subsequence (CJS) Local Search:
In the onlooker bee phase, local search is restricted to the "Critical Job Subsequence" (CJS). Based on the observation that idle times for products appearing after the last positive idle time cannot be reduced further, the algorithm focuses computational effort only on the prefix of the product sequence (the Critical Product Sequence) that contains positive idle times. A two-level evaluation strategy is used: a fast partial evaluation of the first $K$ products filters candidates before a full makespan evaluation is triggered, reducing computational overhead.
Refinement-and-Reconstruction (Scout Bee Phase):
To counteract the risk of premature convergence caused by block compression, a scout bee mechanism is implemented. If an individual stagnates beyond a threshold $\theta$ , the algorithm first attempts a targeted refinement using neighborhood descent on non-critical products and the CJS. If no improvement is found, the algorithm performs a structural reset: it dissolves the locked blocks, randomly permutes the remaining products, and shuffles job orders within products, thereby restoring structural diversity and escaping local optima.

Key Contributions
The paper claims four primary contributions:

Structural Insight: The proposal of an idle-aware block compression mechanism that locks SDST-minimal, zero-idle product pairs into atomic blocks, effectively reducing the search space dimensionality.
Adaptive Selection: The integration of the SW-UCB1 scheme to dynamically select neighborhood operators based on recent performance, enhancing search adaptability.
Focused Exploitation: The restriction of local search to the Critical Job Subsequence combined with a two-level evaluation strategy, which concentrates computational resources on the bottleneck regions of the schedule.
Stagnation Management: The design of a refinement-and-reconstruction mechanism in the scout bee phase that specifically targets the stagnation risks introduced by block compression.

Experimental Results
The algorithm was evaluated on 540 benchmark instances derived from the DAPFSP-SDST dataset by Hatami et al. [7], covering various problem scales ( $n \in \{100, 200\}$ , $m \in \{5, 10, 20\}$ , $f \in \{4, 6, 8\}$ , $d \in \{30, 40, 50\}$ ).

Comparison: BG-ABC was compared against four state-of-the-art algorithms: Iterated Greedy (IG), Genetic Programming Hyper-Heuristic (GP-HH), Novel Biogeography-Based Optimization (NBBO), and Two-Stage Heuristic Algorithm (TSHA).
Performance: BG-ABC achieved the lowest Average Relative Percentage Deviation (ARPD) of -1.95%, significantly outperforming TSHA (-1.28%), NBBO (-1.32%), GP-HH (-0.49%), and IG (0.81%). Statistical analysis using the Friedman test and Bonferroni-Dunn post-hoc test confirmed that BG-ABC's superiority is statistically significant at both 95% and 99% confidence levels.
Ablation Study: Variants of BG-ABC lacking specific components (block compression, adaptive selection, CJS search, or guided reconstruction) were tested. The full BG-ABC significantly outperformed all variants, confirming that each component is non-redundant and contributes to the overall performance.

Significance and Claims
The paper asserts that the BG-ABC algorithm provides a practical and robust intelligent optimization tool for multi-stage supply chain environments. Its significance lies in successfully embedding problem-specific structural insights (specifically the relationship between SDST, idle time, and block formation) into a population-based metaheuristic. By balancing search depth and computational cost through block compression and focused local search, the algorithm overcomes the limitations of single-descent heuristics (like TSHA) and generic metaheuristics that fail to fully exploit the specific properties of the DAPFSP-SDST. The authors conclude that the proposed method effectively improves operational efficiency and decision-making in distributed assembly systems.

More like this