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.

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

FLAMMINI, MICHELE
2010

Abstract

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.
Scheduling; Optical networks; Approximation algorithms
File in questo prodotto:
File Dimensione Formato  
2010_TheorComputSci_411_Flammini.pdf

accesso aperto

Descrizione: Versione PrePrint - Submitted
Tipologia: Documento in Pre-print
Licenza: Accesso gratuito
Dimensione 147.16 kB
Formato Adobe PDF
147.16 kB Adobe PDF Visualizza/Apri

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: http://hdl.handle.net/20.500.12571/2331
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 40
  • ???jsp.display-item.citation.isi??? 30
social impact