Affordable Access


  • Computer Science


This paper investigates two different semi-online versions of the machine covering, which is the problem of assigning a set of jobs to a system of m(m ≥ 3) identical parallel machines so as to maximize the earliest machine completion time. In the first case, we assume that the largest processing times is known in advance. In the second case, we assume that the total processing times of all jobs is known in advance. For each version we propose a semi-online algorithm and investigate its competitive ratio. The competitive ratio of each algorithm is $\frac{1}{m-1}$, which is shown to be the best possible competitive ratio for each semi-online problem.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

Semi-online machine covering for two uniform machi...

on Theoretical Computer Science Jan 01, 2009

Optimal semi-online algorithms for machine coverin...

on Theoretical Computer Science Jan 01, 2007

Optimal semi-online preemptive algorithms for mach...

on Theoretical Computer Science Jan 01, 2005
More articles like this..