Different agents in the smart grid infrastructure (e.g., households, buildings, communities) consume energy with their own appliances, which may have adjustable usage schedules over a day, a month, a season or even a year. One of the major objectives of the smart grid is to flatten the demand load of numerous agents (viz. consumers), such that the peak load can be avoided and power supply can feed the demand load at anytime on the grid. To this end, we propose two Energy Consumption Scheduling (ECS) problems for the appliances held by different agents at the demand side to effectively facilitate load leveling. Specifically, we mathematically model the ECS problems as Mixed-Integer Programming (MIP) problems using the data collected from different agents (e.g., their appliances’ energy consumption in every time slot and the total number of required in-use time slots, specific preferences of the in-use time slots for their appliances). Furthermore, we propose a novel algorithm to efficiently and effectively solve the ECS problems with large-scale inputs (which are NP-hard). The experimental results demonstrate that our approach is significantly more efficient than standard benchmarks, such as CPLEX, while guaranteeing near-optimal outputs.