Minimizing total busy time in parallel scheduling with application to optical networks

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