With the various detail pricing schemes designed by utilities and the development of the smart grid technologies, consumers are motivated and enabled to schedule their home appliances to save energy, reduce cost and help grid operation. This paper presents a novel Traversal-and-Pruning (TP) algorithm which schedules thermostatically controlled household loads to meet an optimization objective considering both payment and comfort settings. The novel TP algorithm is robust and a flexible method is developed to balance the optimality and speed of the algorithm. Simulation results show that an improved load schedule is obtained by the novel TP algorithm compared to an existing algorithm. (c) 2012 Elsevier Ltd. All rights reserved.