Urban public transportation agencies sometimes have to operate mixing vehicles of different sizes on their routes, due to resource limitations or historical reasons. Services with different passenger-carrying capacities are provided to passengers during a mixed-fleet operation. A fundamental question arising here is how to optimally deploy a given fleet of different bus sizes to provide services that minimize passenger waiting time. We formulate a mixed-fleet vehicle dispatching problem as a Mixed-Integer Nonlinear Programming (MINLP) model to optimize dispatching schemes (dispatching orders and times) when a given set of buses of different sizes are available to serve demand along a route. The objective is to minimize the average passenger waiting time under time-dependent demand volumes. Stochastic travel times between stops and vehicle capacity constraints (i.e., introducing extra waiting time due to denied boarding) are explicitly modeled. A Simulated Annealing (SA) algorithm coupled with a Monte Carlo simulation framework is developed to solve large real-world instances in the presence of stochastic travel times. Results show that, in addition to dispatching headway, bus dispatching sequence can strongly affect waiting times under a mixed-fleet operation. Indeed, with an optimal dispatching sequence, a more accurate adjustment of supply to demand is possible in accordance with time-dependent demand conditions, and the total savings in waiting time are mainly driven by a further reduction in the number of passengers left behind. The optimality of uneven dispatching headways stems from two elements: having a mixed fleet and having localized peaks on demand that make buses run full.