  We settle the pseudo-polynomial complexity of the Demand Strip Packing (DSP)
problem: Given a strip of fixed width and a set of items with widths and
heights, the items must be placed inside the strip with the objective of
minimizing the peak height. This problem has gained significant scientific
interest due to its relevance in smart grids[Deppert et al.\ APPROX'21,
G\'alvez et al.\ APPROX'21]. Smart Grids are a modern form of electrical grid
that provide opportunities for optimization. They are forecast to impact the
future of energy provision significantly. Algorithms running in
pseudo-polynomial time lend themselves to these applications as considered time
intervals, such as days, are small. Moreover, such algorithms can provide
superior approximation guarantees over those running in polynomial time.
Consequently, they evoke scientific interest in related problems.
  We prove that Demand Strip Packing is strongly NP-hard for approximation
ratios below $5/4$. Through this proof, we provide novel insights into the
relation of packing and scheduling problems. Using these insights, we show a
series of frameworks that solve both Demand Strip Packing and Parallel Task
Scheduling optimally when increasing the strip's width or number of machines.
Such alterations to problems are known as resource augmentation. Applications
are found when penalty costs are prohibitively large. Finally, we provide a
pseudo-polynomial time approximation algorithm for DSP with an approximation
ratio of $(5/4+\varepsilon)$, which is nearly optimal assuming $P\neq NP$. The
construction of this algorithm provides several insights into the structure of
DSP solutions and uses novel techniques to restructure optimal solutions.
