The two-stage assembly flowshop scheduling problem with the objective of minimizing total tardiness recently has received the attention of researchers since it is applicable in real life situations. This problem has many applications including plastic manufacturing industry which is common in Gulf states. The literature review reveals that this problem, with the assumption of setup times being zero, has been considered in the literature and several heuristics have been proposed. However, the assumption is not applicable for some scheduling settings including plastic manufacturing. Thus, this research will address the scheduling problem of two-stage assembly flowshop with non-zero setup times to minimize total tardiness. Given that the problem is NP-hard, different heuristics, e.g., simulated annealing and genetic algorithm, will be proposed. Extensive computational experiments on randomly generated data will be conducted to assess the performance of the heuristics to be developed. The proposed heuristics will be compared with each other and with the existing heuristics in the literature for zero-setup times.