  We consider offline scheduling algorithms that incorporate speed scaling to
address the bicriteria problem of minimizing energy consumption and a
scheduling metric. For makespan, we give linear-time algorithms to compute all
non-dominated solutions for the general uniprocessor problem and for the
multiprocessor problem when every job requires the same amount of work. We also
show that the multiprocessor problem becomes NP-hard when jobs can require
different amounts of work.
  For total flow, we show that the optimal flow corresponding to a particular
energy budget cannot be exactly computed on a machine supporting arithmetic and
the extraction of roots. This hardness result holds even when scheduling
equal-work jobs on a uniprocessor. We do, however, extend previous work by
Pruhs et al. to give an arbitrarily-good approximation for scheduling
equal-work jobs on a multiprocessor.
