On-line scheduling algorithms for a batch machine with finite capacity

On-line scheduling algorithms for a batch machine with finite capacity

0.00 Avg rating0 Votes
Article ID: iaor2006461
Country: Netherlands
Volume: 9
Issue: 2
Start Page Number: 167
End Page Number: 186
Publication Date: Mar 2005
Journal: Journal of Combinatorial Optimization
Authors: ,
Abstract:

We study the problem of on-line scheduling jobs with release dates on a batch machine of finite capacity with the objective of minimizing the makespan. We generalize several existing algorithms for the problem to a class of on-line algorithms that are 2-competitive for any arbitrary finite machine capacity. Then, we show that one of these generalized algorithms is in fact 7/4-competitive for machine capacity 2. This is the first on-line algorithm for a finite machine capacity with competitive ratio less than 2.

Reviews

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