Online Scheduling to Minimize the Maximum Delay Factor

Details Online Scheduling to Minimize the Maximum Delay Factor Online Scheduling to Minimize the Maximum Delay Factor

2008-07-11

arxiv.org/abs/0807.1891v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper two scheduling models are addressed. First is the standard model (unicast) where requests (or jobs) are independent. The other is the broadcast model where broadcasting a page can satisfy multiple outstanding requests for that page. We consider online scheduling of requests when they have deadlines. Unlike previous models, which mainly consider the objective of maximizing throughput while respecting deadlines, here we focus on scheduling all the given requests with the goal of minimizing the maximum {\em delay factor}.We prove strong lower bounds on the achievable competitive ratios for delay factor scheduling even with unit-time requests.For the unicast model we give algorithms that are $(1 + \eps)$-speed $O({1 \over \eps})$-competitive in both the single machine and multiple machine settings. In the broadcast model we give an algorithm for similar-sized pages that is $(2+ \eps)$-speed $O({1 \over \eps^2})$-competitive. For arbitrary page sizes we give an algorithm that is $(4+\eps)$-speed $O({1 \over \eps^2})$-competitive.

Affiliated with

Also associated with

No associations

Rating

Online Scheduling to Minimize the Maximum Delay Factor does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Online Scheduling to Minimize the Maximum Delay Factor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Scheduling to Minimize the Maximum Delay Factor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-576273