  We study Nonpreemptive Peak Demand Minimization (NPDM) problem, where we are
given a set of jobs, specified by their processing times and energy
requirements. The goal is to schedule all jobs within a fixed time period such
that the peak load (the maximum total energy requirement at any time) is
minimized. This problem has recently received significant attention due to its
relevance in smart-grids. Theoretically, the problem is related to the
classical strip packing problem (SP). In SP, a given set of axis-aligned
rectangles must be packed into a fixed-width strip, such that the height of the
strip is minimized. NPDM can be modeled as strip packing with slicing and
stacking constraint: each rectangle may be cut vertically into multiple slices
and the slices may be packed into the strip as individual pieces. The stacking
constraint forbids solutions where two slices of the same rectangle are
intersected by the same vertical line. Nonpreemption enforces the slices to be
placed in contiguous horizontal locations (but may be placed at different
vertical locations).
  We obtain a $(5/3+\epsilon)$-approximation algorithm for the problem. We also
provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS)
which generates a schedule for almost all jobs with energy consumption
$(1+\epsilon)OPT$. The remaining jobs fit into a thin container of height $1$.
The previous best for NPDM was 2.7 approximation based on FFDH [Ranjan et al.
2015]. One of our key ideas is providing several new lower bounds on the
optimal solution of a geometric packing, which could be useful in other related
problems. These lower bounds help us to obtain approximative solutions based on
Steinberg's algorithm in many cases. In addition, we show how to split
schedules generated by the AEPTAS into few segments and to rearrange the
corresponding jobs to insert the thin container mentioned above.
