Randomized on-line scheduling on three processors

Randomized on-line scheduling on three processors

0.00 Avg rating—0 Votes
Article ID: iaor20043290
Country: Netherlands
Volume: 32
Issue: 2
Start Page Number: 152
End Page Number: 158
Publication Date: Mar 2004
Journal: Operations Research Letters
Authors:
Keywords: scheduling
Abstract:

We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for m=3 processors must be strictly greater than 27/19.

Reviews

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