Offline first fit scheduling in smart grids

In this paper we consider the problem of scheduling energy consumption loads in the setting of smart electric grids. Each load is characterized as a "job" by a start (arrival) time and a deadline by which a certain amount of electric energy must be delivered to the load. A job may be preemptable, i. e., it can be interrupted or non-preemptable. Specifically, we focus on scheduling a mixture of preemptable and non-preemptable jobs with the same arrival time and deadline with the goal of minimizing the peak power. We study and modify the first fit decreasing height algorithm of the strip packing problem for this purpose. We derive a performance bound for the algorithm and prove its tightness. We test the performance of the algorithm extensively on a variety of datasets including real life household data.