This study deals with the two-stage assembly flowshop scheduling problem which is important for manufacturing environments where customer due dates must be satisfied. Classifying setup and processing times as separate improves machine utilization while reducing tardiness across due dates as tasks are handled by respective machines. We focus on minimizing mean tardiness which is essential for the reputation of the producer and customer satisfaction. We present two new algorithms and compare their performances with the algorithms in the literature for similar problems. It is also shown that a dominance relation, developed by using the mathematical formulation of the problem, greatly improves the efficiency of the initial solution. Through extensive computational simulations, we show that our hybrid simulated annealing algorithm outperforms the best existing algorithm in the literature, yielding a relative error of at least 40% lower on average. Furthermore, robustness tests were conducted with no setup times to assess the stability of our algorithms under diverse conditions. Results indicate that our newly proposed algorithm maintains high efficiency under both zero and non-zero setup time conditions. All the considered algorithms were compared under the same computation time, and statistical analysis were conducted to justify the results.