BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR94-216
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Scheduling in a Ring with Unit Capacity Links
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Fizzano, Perry
AUTHOR:: Stein, Clifford
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-216.ps.Z
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR94-216.pdf
ABSTRACT::
 We consider the problem of scheduling unit-sized jobs on a ring of
processors with the objective of minimizing the completion time of the
last job.  Unlike much previous work we place restrictions on the
capacity of the network links connecting processors.  We give a
polynomial time centralized algorithm that produces optimal length
schedules.  We also give a simple distributed 2-approximation
algorithm.
END:: ncstrl.dartmouthcs//TR94-216