The on-time arrival performance of vehicles at stops is a critical metric for both riders and city planners to evaluate the reliability of a transit system. However, it is a non-trivial task for transit agencies to adjust the existing bus schedule to optimize the on-time performance for the future. For example, severe weather conditions and special events in the city could slow down traffic and cause bus delay. Furthermore, the delay of previous trips may affect the initial departure time of consecutive trips
and generate accumulated delay. In this paper, we formulate the problem as a single-objective optimization task with constraints and propose a greedy algorithm and a genetic algorithm to generate bus schedules at timepoints that improves the bus ontime performance at timepoints which is indicated by whether the arrival delay is within the desired range. We use the Nashville bus system as a case study and simulate the optimization performance using historical data. The comparative analysis of the results identifies that delay patterns change over time and reveals the efficiency of the greedy and genetic algorithms.