  We consider fundamental scheduling problems motivated by energy issues. In
this framework, we are given a set of jobs, each with a release time, deadline
and required processing length. The jobs need to be scheduled on a machine so
that at most g jobs are active at any given time. The duration for which a
machine is active (i.e., "on") is referred to as its active time. The goal is
to find a feasible schedule for all jobs, minimizing the total active time.
When preemption is allowed at integer time points, we show that a minimal
feasible schedule already yields a 3-approximation (and this bound is tight)
and we further improve this to a 2-approximation via LP rounding techniques.
Our second contribution is for the non-preemptive version of this problem.
However, since even asking if a feasible schedule on one machine exists is
NP-hard, we allow for an unbounded number of virtual machines, each having
capacity of g. This problem is known as the busy time problem in the literature
and a 4-approximation is known for this problem. We develop a new combinatorial
algorithm that gives a 3-approximation. Furthermore, we consider the preemptive
busy time problem, giving a simple and exact greedy algorithm when unbounded
parallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields an
algorithm that is 2-approximate.
