We propose a least laxity first (LLF) scheduling algorithm for a heterogeneous population of thermostatically controlled loads (TCL), aimed at providing regulation services for the power grid. TCLs periodically switch between on and off states in order to keep their monitored temperature in a certain comfort band. In our scheme, TCLs inform a central controller of their anticipated deadlines to switch states, allowing for their switching events to be scheduled. An LLF policy schedules these transitions to provide regulation with minimum deviation from the autonomous evolution of the TCLs. To manage large populations, we bundle requests with similar laxity values in a limited number of clusters, considerably reducing computational and communication costs, and preserving the privacy of participants.