To improve customer satisfaction and to perform production scheduling and equipment maintenance more efficiently, a single-machine scheduling problem with sequence-dependent setup times and two types of periodic maintenance is tackled. Firstly, two types of periodic maintenance are defined by different preventive maintenance effects, and a mixed integer programming model is formulated to minimize the total tardiness by taking into account the sequence-dependent setup times. Then, the valid inequalities are proposed to improve the model efficiency by analyzing the model structure. Then, an efficient multi-start algorithm is also designed for the solution, and five local search operators are designed for the search to avoid the algorithm falling into local optimum. Finally, computational experiments are performed to evaluate the effectiveness of the model and algorithm, as well as to analyze the sensitivity of parameters. The result shows that the trade-off between different maintenance types can reduce the total tardiness, and the total tardiness of two types of periodic maintenance is better than that of a single type of periodic maintenance. The result can provide decision support for manufacturing enterprises to make scheduling and maintenance plans.