BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR94-213
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Job Scheduling in Rings
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Fizzano, Perry
AUTHOR:: Stein, Clifford
AUTHOR:: Karger, David R.
AUTHOR:: Wein, Joel
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1994
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: Compressed Postscript at http://www.cs.dartmouth.edu/reports/TR94-213.ps.Z
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR94-213.pdf
ABSTRACT::
	We give distributed approximation algorithms for job
scheduling in a ring architecture. In contrast to almost all other
parallel scheduling models, the model we consider captures the
influence of the underlying communications network by specifying that
task migration from one processor to another takes time proportional
to the distance between those two processors in the network.  As a
result, our algorithms must balance both computational load and
communication time.
	The algorithms are simple, require no global control, and work
in a variety of settings.  All come with small constant-factor
approximation guarantees; the basic algorithm yields schedules of
length at most 4.22 times optimal.  We also give a lower bound on
the performance of any distributed algorithm some results for a simple
capacitated case, and the results of simulation experiments, which
give better results than our worst-case analysis.
END:: ncstrl.dartmouthcs//TR94-213