Residential buildings energy cost optimization requires demand response (DR) scheduling when employing electric storage space heating in a market that hourly tariff electricity price is applied for customers. Thus, a suitable optimization algorithm for the thermal storage controller causes the household energy expenditure for heating purpose to be minimized. This study proposes greedy variable neighborhood algorithm (GVNA) that is composed of greedy algorithm and variable neighborhood search as the DR control algorithm. The case study outcomes illustrate that the daily heating electricity price decreases by 3,5 % to 11,4 % and monthly heating electricity cost reduces by 9 % to 20 % when employing different storage degrees from 10 % to 100 % of the total daily or monthly heat demand, respectively. Furthermore, this method enables both day-ahead and real-time scheduling of a residential thermal storage. Thus, GVNA can be a feasible approach at least for residential houses energy cost minimization problem due to its simplicity and small computational burden compared to other techniques in the literature.