2006 | OriginalPaper | Buchkapitel
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs
verfasst von : Leah Epstein, Magnús M. Halldórsson, Asaf Levin, Hadas Shachnai
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Motivated by applications in batch scheduling of interval jobs, processes in manufacturing systems and distributed computing, we study two related problems. Given is a set of jobs {
J
1
,...,
J
n
}, where
J
j
has the processing time
p
j
, and an undirected intersection graph
G
=({ 1,2,...,
n
},
E
); there is an edge (
i
,
j
) ∈
E
if the pair of jobs
J
i
and
J
j
cannot be processed in the same batch. At any period of time, we can process a
batch
of jobs that forms an independent set in
G
. The batch completes its processing when the last job in the batch completes its execution. The goal is to minimize the sum of job completion times. Our two problems differ in the definition of
completion time
of a job within a given batch. In the first variant, a job completes its execution when its batch is completed, whereas in the second variant, a job completes execution when its own processing is completed.
For the first variant, we show that an adaptation of the greedy set cover algorithm gives a 4-approximation for perfect graphs. For the second variant, we give new or improved approximations for a number of different classes of graphs. The algorithms are of widely different genres (LP, greedy, subgraph covering), yet they curiously share a common feature in their use of
randomized geometric partitioning
.