Residential HVAC control is a large untapped resource for providing regulation services to the grid. This paper presents a set of algorithms for controlling HVACs of a group of residential houses that a demand response aggregator can use to sell regulation service in the wholesale market. The focus is on the regulation market offered by the PJM RTO. Real-world regulation signals from PJM are used to simulate the performance and range of regulation services in a realistic scenario. After presenting the empirical counter example for why a universal optimal control strategy cannot exist for regulation, a set of heuristic algorithms is presented, which performs well in a range of test cases. The control mechanism involves a central controller communicating with smart thermostats of multiple residential houses to gather indoor temperature data, prioritizing them according to certain heuristics and sending on/off signals back to the thermostats to control the HVAC. The case studies indicate that the proposed heuristic algorithms can deliver the required regulation services, while adequately handling communication delays, different types of regulation signals and household’s thermal comfort requirements.