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 $\mathcal{J}= \{J_1, \ldots , J_n \}$. Each job, $J_j$, is associated with an interval $[s_j, c_j]$ along which it should be processed. Also given is the parallelism parameter $g \ge 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 {\em 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.

Minimizing Total Busy Time in Parallel Scheduling with Application to Optical Networks

Gianpiero Monaco;Luca Moscardelli;
2010-01-01

Abstract

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 $\mathcal{J}= \{J_1, \ldots , J_n \}$. Each job, $J_j$, is associated with an interval $[s_j, c_j]$ along which it should be processed. Also given is the parallelism parameter $g \ge 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 {\em 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.
File in questo prodotto:
File Dimensione Formato  
busy.pdf

Solo gestori archivio

Tipologia: PDF editoriale
Dimensione 405.48 kB
Formato Adobe PDF
405.48 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11564/175062
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 43
  • ???jsp.display-item.citation.isi??? 36
social impact