In this paper we consider a scheduling problem where the limited availability of machine results from maintenance. In many manufacturing systems, scheduling maintenance will result in some jobs being tardy and a larger total flow time is generated. Therefore, our objective is to find a schedule that minimizes the total flow time subject to minimum number of tardy jobs and periodic maintenance. In this paper, a branch-and-bound algorithm that utilizes several theorems is proposed to derive the optimal schedule. We also develop a heuristic to solve large sized problems. Computational results show that the presented heuristic is highly accurate and efficient.