Scheduling in a Ring with Unit Capacity Links

Dartmouth Technical Report PCS-TR94-216

	Perry Fizzano
	Clifford Stein

Date:  1994

URL (compressed postscript): <http://www.cs.dartmouth.edu/reports/TR94-216.ps.Z> (60KB)

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR94-216.pdf> (152KB)

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.