A major challenge to develop optimal strategies for allocation of flexible demand toward the smart grid paradigm is the uncertainty associated with the real-time price and electricity demand. This article presents a regret-based model and a novel iterative algorithm which solves the minimax regret optimization problem. This algorithms exhibits low computational burden compared with traditional linear programming methods and affords iterative convergence through updates of feasible power schedules, thus enabling a scalable parallel implementation for large device populations. Specifically, our approach seeks to minimize the induced worst-case regret over all price scenarios and solves the optimal charging strategy for the electrical devices. The convergence of the method and optimality of the computed solution is justified and some numerical simulations are discussed for the case of a single device operating under different types of price realizations and uncertainty bounds.