Residential, commercial, and industrial buildings have been reported to consume a large portion of the generated energy. With the introduction of smart grid and its energy optimization techniques, it is now possible to efficiently manage and control consumers’ energy usage to fulfil their demands with the existing energy generation infrastructure, which otherwise seems to be a backbreaking challenge. This paper presents an efficient energy management solution for buildings with a large number of thermostatic devices (air conditioners) that maintain the temperature of different thermal zones in a predefined range. The primary objective of this paper is to schedule the thermostatic devices in order to reduce total energy consumption by these devices when they are in operation for a very long duration of time, while maintaining the other constraints. We formulate it as a graph problem where minimum mean cycle will provide the desired solution. The proposed methodology ensures that at no point in time the power consumption goes beyond a certain peak power consumption limit. We also enhance the methodology to reduce peak load consumption. Furthermore, a fast greedy approach has been developed to efficiently scale up the aforementioned scheduling scheme for a large number of devices. Experimental results show that significant improvements can be obtained by the proposed approaches over existing algorithms in reducing average energy consumption.