Asset Details
Do you wish to reserve the book?
Centralized and distributed algorithms for network scheduling
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
Centralized and distributed algorithms for network scheduling
Do you wish to request the book?
Centralized and distributed algorithms for network scheduling
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Dissertation
Centralized and distributed algorithms for network scheduling
1995
Overview
In this dissertation we will examine centralized and distributed algorithms for network scheduling. The input to the network scheduling problem is a network of machines and a set of independent jobs such that each job originates on some machine in the network. A job may be processed on the machine it originated or it may be moved to another machine to be processed. Unlike many previous parallel machine scheduling models, our model accounts for communication between processors. If a job is moved from one processor to another processor it will incur a time delay. The delay is proportional to the distance between the two machines in the network. Another aspect of the network scheduling model is that each edge has a capacity which restricts the number of jobs that can be passed over it in one time step. We present two polynomial time centralized scheduling algorithms. One is for scheduling jobs optimally in a ring of processors with unit capacity edges. The other is for scheduling jobs optimally in arbitrary networks with infinite capacity edges. We also present three distributed approximation algorithms for network scheduling. All three of the distributed algorithms have extremely simple control structures and produce schedules with lengths that are within a small factor of optimal. The first of these results handles infinite capacity rings. We present a 4.22-approximation algorithm as well as provide simulation results that suggest the algorithm performs better than our analysis implies. Furthermore, we give a lower bound on the performance of any distributed scheduling algorithm for rings with infinite capacity links. The next algorithm we present is a simple d-approximation algorithm for scheduling jobs in d-regular networks with unit capacity links. We also show how to improve the analysis for rings; the improved analysis reduces the approximation factor to 5/3. The final algorithm is also for unit capacity networks and is very similar to the algorithm for d-regular networks. We prove that this algorithm is an O(log m)-approximation algorithm for arbitrary m machine networks given that the optimal schedule length is sufficiently large.
