## Scheduling Jobs Before Shut Down

##### Abstract

Distributed systems execute background or alternative jobs while waiting
for data or requests to arrive from another processor. In those cases, the
following shut-down scheduling problem arises: given a set of jobs of
known processing time, schedule them on m machines so as to maximize the
total weight of jobs completed before an initially unknown deadline. We
will present optimally competitive deterministic and randomized algorithms
for shut-down scheduling. Our deterministic algorithm is parameterized by
the number of machines m. Its competitive ratio increases as the number of
machines decreases, but it is optimal for any given choice of m. Such
family of deterministic algorithm can be translated into a family of
randomized algorithms that use progressively less randomization and that
are optimal for the given amount of randomization. Hence, we establish a
precise trade-off between amount of randomization and competitive ratios.
Distributed systems execute background or alternative jobs while waiting
for data or requests to arrive from another processor. In those cases, the
following <em>shut-down scheduling problem</em> arises: given a set of
jobs of known processing time, schedule them on <em>m</em> machines so as
to maximize the total weight of jobs completed before an initially unknown
deadline. We will present optimally competitive deterministic and
randomized algorithms for shut-down scheduling. Our deterministic
algorithm is parameterized by the number of machines <em>m</em>. Its
competitive ratio increases as the number of machines decreases, but it is
optimal for any given choice of <em>m</em>. Such family of deterministic
algorithm can be translated into a family of randomized algorithms that
use progressively less randomization and that are optimal for the given
amount of randomization. Hence, we establish a precise trade-off between
amount of randomization and competitive ratios.
(Also cross-referenced as UMIACS-TR-99-72)

University of Maryland, College Park, MD 20742-7011 (301)314-1328.

Please send us your comments.