A Scheduling Problem
Problem: Jobs arrive online (arrival time a_i, processing time p_i known at arrival time) and have to be scheduled with preemption on one machine. The stretch of a job is s_i = (c_i - a_i)/p_i where c_i is the completion time of job i. Design an online algorithm to minimize max-stretch, ie., max_i s_i.
What is known: Say d= (max_i p_i)/(min_i p_i). If there are three or more job sizes, the lower bound on the competitive ratio is roughly d^{1/3} and the best known upper bound is roughly d^{1/2}.
Why is it interesting: Stretch is a natural measure. Seems like one needs a new idea and that may yield a nice new scheduling algorithm useful to test in practice. Related sum-stretch optimization is nearly solved? This is because shortest-remaining-processing-time (SRPT) does pretty well for it and there are even results for minimizing weighted flow time, \sum_i w_i(c_i-a_i) for arbitrary weights by Chekuri, Khanna and Zhu, and later by others.
Social commentary: I was reminded of this problem because Cliff Stein and I were discussing work sometime ago, and the discussion was whether the pursuit of stretch optimization had been worthwhile for the scheduling algorithms community. That SRPT is a near-optimizer for sum-stretch is interesting, but says something about SRPT that has been known for a long time. Did we get any new algorithms, insights or hard challenges? This is the kind of discussion researchers have, reflecting on the past to see for example if this (roughly) 10 year old research direction has been impactful. While the outcome is unclear, there is a ray of hope --- the problem of minimizing the max-stretch have been encouraging: the known algorithms do give new ways to schedule and has found applications in web servers, file transfers over the net and systems, and there is a technically challenging open problem (stated above).
What is known: Say d= (max_i p_i)/(min_i p_i). If there are three or more job sizes, the lower bound on the competitive ratio is roughly d^{1/3} and the best known upper bound is roughly d^{1/2}.
Why is it interesting: Stretch is a natural measure. Seems like one needs a new idea and that may yield a nice new scheduling algorithm useful to test in practice. Related sum-stretch optimization is nearly solved? This is because shortest-remaining-processing-time (SRPT) does pretty well for it and there are even results for minimizing weighted flow time, \sum_i w_i(c_i-a_i) for arbitrary weights by Chekuri, Khanna and Zhu, and later by others.
Social commentary: I was reminded of this problem because Cliff Stein and I were discussing work sometime ago, and the discussion was whether the pursuit of stretch optimization had been worthwhile for the scheduling algorithms community. That SRPT is a near-optimizer for sum-stretch is interesting, but says something about SRPT that has been known for a long time. Did we get any new algorithms, insights or hard challenges? This is the kind of discussion researchers have, reflecting on the past to see for example if this (roughly) 10 year old research direction has been impactful. While the outcome is unclear, there is a ray of hope --- the problem of minimizing the max-stretch have been encouraging: the known algorithms do give new ways to schedule and has found applications in web servers, file transfers over the net and systems, and there is a technically challenging open problem (stated above).
posted by metoo at 1:17 AM
4 Comments:
My interest in scheduling problems
has evolved over the years. In
particular, for some of the
online problems, I feel that we
should look for positive results
and useful insights. Resource augmentation analysis shows that some of the lower bounds are not very robust.
In the online setting, max-stretch
seems too hard a measure for worst case competitive analysis if d is
large (as the lower bound shows).
Question is whether to focus our
efforts on improving the upper
and lower bounds for this or
change the setting and obtain
an algorithm that seems to make
sense and prove a good upper bound
in a restricted setting (either
resource augmentation or
input distribution). I would
focus on the latter.
Chandra
I would be interested in knowing more about upper bounds for online max-stretch optimization with resource augmentation and/or with appropriate input distribution. I have not thought about either and don't know if they are nontrivial, but will be great to get some new insight into this problem.
In the resource augmentation setting, it is known that Shortest Job First (SJF) is O(1/\epsilon) competitive for max-stretch with (1+\epsilon) speedup. Reference "Server Scheduling in the L_p Norm: A Rising Tide Lifts All Boats", Bansal and Pruhs, STOC 03.
Similar results (with a slightly worse competitive ratio) also hold for non-clairvoyant algorithms (i. e. when algorithm learns p_j only when the job j finishes). In particular, the algorithm Shortest Elapsed Time First (SETF), which at any time works on the job that has received least processing thus far is O(1/\epsilon^2) competitive.
These results extend (rather easily) to l_p norms of weighted flow time (and hence max-weighted flow time) in both clairvoyant and non-clairvoyant settings. These results can be found in the LATIN04 paper by Bansal and Pruhs.
Nikhil
A d^[1/2} lower bound was cliamed at the Luminy Scheduling conference:
http://www.cirm.univ-mrs.fr/
web.ang/liste_rencontre/Rencontres2006/
Tryst06/Tryst06.html
by Frédéric Vivien
(I think this was joint work with others). BTW, Muthu, just to let you know what you missed, this was where we went swimming after lunch each day:
http://perso.orange.fr/sebos31/
images/aix/calanque4.jpg
Kirk
Post a Comment
<< Home