This paper discusses construction of a model to minimize fleet-size required to operate a time-table subject to a maintenance constraint. The constraint requires that vehicles be provided maintenance at least once every two days at a specific location. A heuristic algorithm was devised which also attempts to take advantage of flexibility available in trip timings. The algorithm was applied to a problem faced by one of India's largest state road transport undertakings with encouraging results. Computational experience with the algorithm is described.