We consider a scheduling problem in
which a bounded number of jobs can be processed
simultaneously by a single machine. The input is a
set of n jobs J = {J1, . . . , Jn}. Each job, Jj, is
associated with an interval [sj, cj ] along which it
should be processed. Also given is the parallelism
parameter g ? 1, which is the maximal number of
jobs that can be processed simultaneously by a single
machine. Each machine operates along a contiguous
time interval, called its busy interval, which contains
all the intervals corresponding to the jobs it processes.
The goal is to assign the jobs to machines such that
the total busy time of the machines is minimized.
The problem is known to be NP-hard already for
g = 2. We present a 4-approximation algorithm for
general instances, and approximation algorithms with
improved ratios for instances with bounded lengths,
for instances where any two intervals intersect, and
for instances where no interval is properly contained
in another. Our study has important application in
optimizing the switching costs of optical networks.