%T Scheduling in a Ring with Unit Capacity Links
%A Perry Fizzano
%A Clifford Stein
%R Technical Report PCS-TR94-216
%I Dartmouth College, Computer Science
%C Hanover, NH
%D  1994
%U http://www.cs.dartmouth.edu/reports/TR94-216.ps.Z
%X
  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.