<p>As the structural complexity of mechanical products increases, traditional assembly sequence planning (ASP) methods become inefficient in identifying optimal assembly sequences. To address this challenge and enhance the automation and intelligence level of ASP, a parallel assembly sequence planning (PASP) methodology is proposed in this paper. First, an automated subassembly identification algorithm based on an integrated graph theory model (IGTM) is presented, utilizing a global rule matrix as input to generate an assembly hierarchy tree (AHT). Subsequently, a global non-orthogonal interference matrix is established along with an automatic derivation method for subassembly interferences. To optimize assembly sequences, a hybrid search strategy is proposed, including a global parallel search strategy based on tabu lists and a regional linear search strategy based on ant colony optimization (ACO) algorithm. Furthermore, a comprehensive evaluation index system is established to determine optimal assembly sequences. A case study demonstrates the assembly sequence planning of a machine gun using the proposed method. The effectiveness and advantages of the proposed method are also discussed through quantitative and qualitative comparisons with existing ASP methods.</p>