The optimal allocation of replicas to a homogeneous or heterogeneous set of processors is derived for parallel tempering simulations on multiprocessor machines. In the general case, it is possible without substantially increasing wall clock time to achieve nearly perfect utilization of CPU time. Random fluctuations in the execution time of each replica do not significantly degrade the performance of the scheduler.