Today, Scheduling problems have wide applications in many production and service systems. Most scheduling problems are based on the assumption that machine works continuously during the planning horizon. This assumption is not true in many production environments because the machine may not be available during one or more periods such as during maintenance operations. In this study assumed that the machine has a single unavailability interval and the starting time of this interval is a decision variable. They assumed that the maintenance period was specified in advance and time of maintenance, did not fall outside the maintenance period. In this thesis, single machine scheduling problems with flexible maintenance have been considered. First, the single machine scheduling problem with one flexible maintenance period and non-resumable jobs with the aim of minimizing maximum earliness is studied. The proposed problem is NP-hard. By proving a number of theorems, a heuristic procedure is developed to solve the problem. A branch-and-bound approach is also presented. Computational results for 3840 problem instances show that the branch-and-bound approach is capable of optimally solving 99.47% of the instances. Next, the single machine scheduling problem with one flexible maintenance period, non-resumable jobs, with the aim of minimizing the number of tardy jobs is considered. The proposed problem is NP-hard. An exact branch and bound approach is proposed for the problem. By proving a number of theorems and lemmas, a lower bound and some efficient dominance rules are developed. Moore and Hodjson's algorithm is developed for this problem and used to calculate the upper bound. Computational results for 3840 instances show that the branch and bound procedure is capable of optimally solving 99.34% of the instances.