On a generalized graph coloring/batch scheduling problem
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
TypeCommunication / Conférence
Conference titleMultidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2007)
MetadataShow full item record
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 / KeywordsBatch Scheduling; Algorithmics
Showing items related by title and author.