<p>Parallel Assembly Sequence Planning (PASP) can be categorized into synchronous PASP (sPASP) and asynchronous PASP (aPASP) according to the way operation time progresses. Among these, aPASP allows assembly operations to start as soon as precedence constraints are satisfied, thereby providing greater flexibility and reducing idle time. However, research on aPASP remains relatively limited. Accordingly, this study focuses on aPASP with robot-dependent processing times, with the objective of minimizing the makespan. Furthermore, assembly direction change time and tool change preparation time are incorporated into the assembly timeline, which improves realism relative to simplified aPASP models. To effectively solve this problem, this study employs Adaptive Trend Optimization (ATO). ATO calculates a trend factor based on the solution’s convergence status and uses it to dynamically adjust the block search range. Finally, four test instances are used to validate the performance of ATO, and its results are compared with those of Particle Swarm Optimization (PSO), Genetic Algorithm-Precedence Preservative Crossover (GA-PPX), Ant Colony Optimization (ACO), and Artificial Bee Colony (ABC). The experimental results indicate that ATO achieves the best solution quality for aPASP across the tested instances.</p>