On a generalized graph coloring/batch scheduling problem

Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis

Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2007), On a generalized graph coloring/batch scheduling problem, Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2007), 2007-08, Paris, France

View/Open

generalized_batch.PDF (474.8Kb)

Type

Communication / Conférence

Date

2007

Conference title

Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2007)

Conference date

2007-08

Conference city

Paris

Conference country

France

Metadata

Show full item record

Author(s)

Lucarelli, Giorgio

Milis, Ioannis
Paschos, Vangelis

Abstract (EN)

We study a batch scheduling problem where jobs are no more independent but they are subject to (in)compatibility constraints described by an underlying graph. The problem is equiva- lent to a generalized weighted graph coloring problem. We study the frontier between polynomial and NP-variants of the problem as well as the approximability of NP-hard variants.

Subjects / Keywords

Batch Scheduling; Algorithmics