3
$\begingroup$

Let $\mathcal{J} = \{J_1,...,J_n\}$ be a set of jobs with each $J_i = [a_i,r_i,d_i]$ where the job becomes available at its arrival time $a_i$, requires $r_i$ execution time and needs to be finished at its deadline $d_i$ (hard real time). Assume we have $m$ processors available.

Given the above, what scheduling algorithms are available to deal with this? I'm aware of a publication by Horn that gives a solution using flows; since that was in 1974 and flows are comparatively slow, I tried to find faster algorithms for this setting, but couldn't find any. The book on scheduling by Pinedo suggested in this answer on CS.SE mentions the setting and that it can be solved using flows, but unfortunately nothing else. Apart from these two sources, I have been unsuccessful.

Are there known algorithms to solve the above problem that are faster than flow networks on $\Theta(n)$ nodes?

Improve this question
$\endgroup$
4
  • $\begingroup$ Did you try a literature search (e.g., searching for papers that cite the Horn paper you mention)? $\endgroup$
    – D.W. ♦
    Oct 20 '14 at 0:57
  • $\begingroup$ I did, but couldn't find any more recent papers discussing this setting. It's mostly about tasks issuing jobs periodically, sporadically or aperiodically - basically online settings from what I could tell, about jobs that repeat with differing degrees of regularity. $\endgroup$
    – G. Bach
    Oct 20 '14 at 1:30
  • $\begingroup$ Why is Horn's solution "comparatively slow" (and compared to what?) Aren't the reduction and solving the resulting single-commodity network flow both polynomial time? If you're concerned about an $O(n^3)$ algorithm being too slow, there have been advances in solving network flow problems more efficiently since the 1970s (mostly by using clever data structures to reduce $O(n^2)$ subproblems to $O(n\lg n)$, I think). See for example, Ahuja, Magnati and Orlin, Network Flows, 1993. $\endgroup$
    – Wandering Logic
    Oct 20 '14 at 12:17
  • $\begingroup$ @WanderingLogic I'm aiming for something near-linear or quadratic at worst, and as far as I can tell, the best currently available flow algorithms are $\mathcal{O}(|V|\cdot|E|)$ which in this case would be $\mathcal{O}(n^3)$ since the constructed network has $\Theta(n^2)$ edges in the worst case. $\endgroup$
    – G. Bach
    Oct 20 '14 at 12:22
1
$\begingroup$

I think it is going to be tough to find a more efficient algorithm than the one you already have. You are getting close to requiring an online algorithm.

I think a lot is known about the online version of this problem. Take a look at:

Dertouzos and Mok: Multiprocessor On-Line Scheduing of Hard-Real-Time Tasks, IEEE T. Software Eng., 15(12):1497-1506, 1979.

It is known that least laxity first (also known as least slack first) scheduling is an optimal on-line greedy scheduling algorithm for the multiprocessor case only when all the $a_i$ are the same (basically: all the tasks arrive at the same time, but they have different execution times and deadlines.) Dertouzos and Mok show there is no online algorithm for the case that the $a_i$ are not known a-priori.

What I don't know is whether there is some least-slack-first algorithm similar to list scheduling. There must be a reference about this, but I haven't found it in the small amount I've looked just now. Slack is a dynamic quantity. At any time $t$ for any job $i$ it is the difference between $d_i -t$ and however much work is remaining to be done on job $i$. The slack of a job starts at the value $(d_i - a_i) - r_i$ and must be monotonically non-increasing. On imagines that one could take all the jobs, sort them by their initial slack value, and then greedily schedule them in that order, and that (for the case where the processors are identical, there are no precedence constraints, the jobs are all single-threaded, and arbitrary preemption and job migration are permitted and have no cost) you might be able to prove something concrete about it.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the reference - I have considered checking whether I can adapt any known algorithms before attempting to figure out something new, so pointing me in the (possibly) right direction here is appreciated! $\endgroup$
    – G. Bach
    Oct 20 '14 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.