ASTEC 2009 Workshop/Summer school on Algorithms and Techniques for Scheduling on Clusters and Grids

Batch Scheduling of Conflicting jobs

The classic p-batch scheduling problem is to partition a set of jobs to batches, each to be processed simultaneously on set of parallel machines. Many real-life applications impose restrictions on the subsets of jobs that can be processed simultaneously. Such conflicts among the jobs are often modeled by an undirected conflict graph $G$, where each job is represented by a vertex. The length of a vertex is the processing time of the corresponding job, and the edges in the graph represent the conflicts between pairs of jobs. In each time period we can process a batch of jobs that forms an independent set in $G$. Indeed, finding a batch schedule for the jobs is equivalent to finding a proper batch coloring of the graph $G$, where each batch is assigned a distinct contiguous set of colors, whose size is equal to the maximum length of any vertex in the batch. In this talk I will survey known results for the above problem of batch scheduling with conflicts, considering three different measures: minimizing the makespan of the batch schedule, minimum sum of job completion times and minimum sum of batch completion times.

Based on papers with Leah Epstein, Magn\'{u}s Halld\'{o}rsson and Asaf Levin.