| Author: | Jason McCullough |
| Advisor: | Dr. Eric Torng |
| Email: | mccull29@msu.edu |
We consider the problem of scheduling jobs in a preemptive multiprocessor setting while optimizing the total (or average) flow time. Using conventional worst-case analysis, no effective on-line or polynomial-time off-line algorithm exists for this problem. We approach the problem from the perspective of resource augmentation. In this method the on-line algorithm is allowed more resources than the off-line algorithm to which it is compared. It has been shown that if the Shortest Remaining Processing Time (SRPT) algorithm is given m processors that are alpha times faster than the m processors given to the optimal off-line algorithm for alpha >= 2-1/m, SRPT achieves a flow time that is no larger than that of the optimal off-line algorithm on any input instance. We intend to extend these results to show that SRPT actually has a flow time that is alpha times smaller than the flow time of the optimal off-line algorithm on any input instance. That is, SRPT achieves an optimal speedup given sufficient extra resources.
Return to Workshop Listing