Weighted sum coloring in batch scheduling of conflicting jobs

Weighted sum coloring in batch scheduling of conflicting jobs

0.00 Avg rating0 Votes
Article ID: iaor200971610
Country: United States
Volume: 55
Issue: 4
Start Page Number: 643
End Page Number: 665
Publication Date: Dec 2009
Journal: Algorithmica
Authors: , , ,
Keywords: graphs
Abstract:

Motivated by applications in batch scheduling of jobs 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 a processing time p j , and an undirected intersection graph G=({1,…,n},E), with an edge (i,j) whenever the pair of jobs J i and J j cannot be processed in the same batch. We are to schedule the jobs in batches, where each batch completes its processing when the last job in the batch completes 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.

Reviews

Required fields are marked *. Your email address will not be published.