In this study, single machine scheduling with flexible maintenance is investigated with non-resumable jobs by minimizing the weighted number of tardy jobs. It is assumed that the machine stops for a constant interval time during the scheduling period to perform maintenance. In other words, the starting time of maintenance is the decision variable. By reviewing the literature, we noticed that this problem has not been studied yet. Initially, it is proved that the problem is NP-hard. Then, a mathematical model is proposed and solved by the GAMS software. Because of the long time for solving the problem with an exact method, we develop a heuristic algorithm. To evaluate the efficiency of the proposed algorithm, 696 test problems with different sizes of the problem in the range from 1 to 2000 jobs, are generated. The computational results demonstrate that the average error of solution is 10.93\%.