Online Scheduling of Bounded Length Jobs to Maximize Throughput

Details Online Scheduling of Bounded Length Jobs to Maximize Throughput Online Scheduling of Bounded Length Jobs to Maximize Throughput

2009-02-12

arxiv.org/abs/0902.2209v3

Computer Science

Data Structures and Algorithms

Scientific paper

We consider an online scheduling problem, motivated by the issues present at the joints of networks using ATM and TCP/IP. Namely, IP packets have to broken down to small ATM cells and sent out before their deadlines, but cells corresponding to different packets can be interwoven. More formally, we consider the online scheduling problem with preemptions, where each job j is revealed at release time r_j, has processing time p_j, deadline d_j and weight w_j. A preempted job can be resumed at any time. The goal is to maximize the total weight of all jobs completed on time. Our main result are as follows: we prove that if all jobs have processing time exactly k, the deterministic competitive ratio is between 2.598 and 5, and when the processing times are at most k, the deterministic competitive ratio is Theta(k/log k).

Affiliated with

Also associated with

No associations

Rating

Online Scheduling of Bounded Length Jobs to Maximize Throughput 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 of Bounded Length Jobs to Maximize Throughput, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Scheduling of Bounded Length Jobs to Maximize Throughput will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-356795