Generator maintenance scheduling (GMS) determines the outage periods of generating units in a one-year or two-year planning horizon for regular safety inspection. This paper introduces a new practical GMS for centralized electrical power systems in which, in contrary to previous studies, the outage periods are scheduled based on operational hours of units. Predefined minimum and maximum operating hours of units after a maintenance outage define the beginning and ending of their maintenance windows, respectively. In addition, unit commitment (UC) as a short-term planning is considered in the GMS with hourly time scale. Therefore, this problem becomes more complex than periodic maintenance scheduling. In this paper, a novel mixed-integer linear programming (MILP) model for the problem is developed. However, due to the problem intractability, two different solution algorithms on the basis of ant colony optimization (ACO) and simulated annealing (SA) are extended for the GMS problem. Both algorithms use some developed heuristics and feasibility rules, namely UC heuristic, for solving the UC problem. Numerical results indicate that the solution algorithms perform well compared to the exact solution of the MILP model obtained using CPLEX solver. Also, the solution algorithms as well as the UC heuristic are examined carefully. To demonstrate the performance of the proposed algorithms, two test systems containing 26 and 36 generating units are investigated.