Offline first-fit decreasing height scheduling of power loads

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 prove its asymptotic performance bound: $1.7OPT+1$ and its tightness. The heuristic results in at most one preemption per job, and it can be implemented with $O(nlogn+nq)$ time complexity where q is the number of non-preemptible jobs.