This paper deals with a single-machine scheduling problem with the objective to minimize the total completion time of jobs subjects to two maintenance constraints. The first maintenance constraint is that the machine will be stopped for maintenance after a periodic interval, and the second one is the constraint on the maximum number of jobs continuously processed. Four methods are used to solve the constrained single-machine scheduling problem. To solve small-scale problems, one binary integer programming model is first proposed, then pruning rules are formulated according to the properties of optimal solutions, and the corresponding branch and bound algorithm is proposed. The genetic algorithm is used to find the near-optimal solutions for medium-scale and large-scale problems. Dynamic genetic algorithm is proposed by adopting the dynamic mutation method to alleviate the precocity problem which is a phenomenon that cannot be ignored in the genetic algorithm. Finally, computational experiments are carried out to evaluate the performance of the proposed algorithms.