A best online algorithm for unbounded parallel‐batch scheduling with restarts to minimize makespan

A best online algorithm for unbounded parallel‐batch scheduling with restarts to minimize makespan

0.00 Avg rating0 Votes
Article ID: iaor20116937
Volume: 14
Issue: 4
Start Page Number: 361
End Page Number: 369
Publication Date: Aug 2011
Journal: Journal of Scheduling
Authors: , , ,
Keywords: makespan, stochastic scheduling
Abstract:

We consider online scheduling with restarts in an unbounded parallel‐batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than ( 5 5 ) / 2 equ1 . We give an online algorithm for the considered problem with a competitive ratio ( 5 5 ) / 2 1.382 equ2 .

Reviews

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