# SEMI-ONLINE MACHINE COVERING

Authors
Disciplines
• Computer Science

## Abstract

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.

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

Apr 24, 2014

## Optimal semi-online preemptive algorithms for mach...

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