Affordable Access

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.

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

Statistics

Seen <100 times
0 Comments