4
$\begingroup$

There are $n$ (non-recurring) jobs where each job $i$ has an arrival time $a_i$ and a duration $t_i$. All the jobs share a deadline length $d$ (deadline for each job is $a_i + d$). The problem is to find a (non-preemptive) scheduling time $s_i$ for each job on a single processor/machine such that the total number of missed deadlines is minimized (or maximize the number of on-time jobs).

So, even in cases where not all deadlines can be met, we want to find out the schedule that meets the maximum number of deadlines. Does this problem even have a polynomial solution? I tried a dynamic programming approach, but I can't really identify the subproblems.

For example, given this set of jobs (where each job is described by $(a_i, t_i)$): [(0, 50), (5, 20), (25, 40)] where $d = 60$, the best we can do is to meet 2/3 deadlines with a schedule like this: [(5,20), (25, 40), (65, 50)].

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – dkaeae May 15 at 12:09
1
$\begingroup$

For an optimal selection, one possible sequencing is always the one respecting the order of arrival time $S_0$. Another may be possible, but you can check that you always can do the switches to obtain $S_0$. This is due to the fact that all jobs have the same $d$.

Thus, your problem is equivalent to select the subset of jobs which do not overlap if they are executed as soon as possible in arrival time order.

Then you can do an approximative greedy algorithm considering jobs in increasing duration order. Counting the duration sorting, this has a $O(N \log(N))$ time complexity. It would generally give a very good result but might fail for example on $(a[i], t[i]) = [(0, 60), (30, 50), (60, 60)]$ with $d = 60$.

Or you can do a dynamic programming on $T$ array of $t(n)$, the soonest time at which $n$ jobs are achieved.

Initially, $T_0 = [0, +\infty, +\infty ..., +\infty]$, it has size $N+1$, the number of jobs (+ 0 index). The jobs are considered in increasing arrival time order. $T_k$ is the state of $T$ after considering $k^{th}$ job.

To keep track of the selection, you need an array $previous$ of size $N \times N$ and an array $lastElement$ of size $N$. All are initially filled with -1. $lastElements[i]$ tracks the index of the last added job for $T_{i+1}$. $previous[i][j]$ tracks the element added just before j for $T_{i+1}$.

Then the sub-problem is to compute $T_{k+1}$ from $T_{k}$.

This is the pseudo-code:

function next_job(T_last, a_k, t_k, d):

    T = T_last

    for i from 0 to N-1 do:
        if T_last[i] == +inf then break

        begin = max(a_k, T_last[i])
        end = begin + t_k

        if (end > a_k + d) then continue

        if (T[i+1] < end) then:

            T[i+1] = min(T[i+1], end)
            lastElement[i] = k
            if(i > 1) previous[i, k] = lastElement[i-1]
        end
    end

    return T

The final result is of course the largest $i$ such that $T[i]$ is not $+\infty$. It has a $O(N^2)$ overall time complexity.

To obtain the selection, you pick $elem0 = lastElement[i-1]$, then $elem1 = previous[i-1, elem0]$, then $elem2 = previous[i-2, elem1]$ and so on until you have your i elements.

Let's make a small example with $(a[i], t[i]) = [(0, 60), (10, 30), (50, 20)]$, $d=60$ :

  • $T_0 = [0, +\infty, +\infty, +\infty]$ => initialization
  • $T_1 = [0, 60, +\infty, +\infty]$ => one job may be achieved at time=60
  • $T_2 = [0, 40, +\infty, +\infty]$ => up to now only one job may be selected, but job (10, 30) took the place of (0, 60) as it can be achieved sooner.
  • $T_3 = [0, 40, 70, +\infty]$ => optimal solution selects 2 jobs.

At the end, $lastElements = [1, 2, -1]$ (starting job indexing at 0) and $previous = [[-1, -1, -1] [-1, -1, 1] [-1, -1, -1]]$. This let you track the optimal selection $\{1, 2\}$.

$\endgroup$
  • $\begingroup$ I can't really follow the logic here but I can see two problems: how do you know you should start the first job at time 0? What if the very first job arrives at time 5? Also, how do you keep track of the ordering of the jobs that your algorithm selects? $\endgroup$ – user6080524 May 15 at 14:36
  • $\begingroup$ Maybe I misunderstoofd what T represents. Can you explain for example how the very first job to schedule is selected? $\endgroup$ – user6080524 May 15 at 14:44
  • $\begingroup$ @user6080524: The DP initialisation just says 0 is the soonest time at which you can have achieved 0 job. If the first job start at 5, it will be taken in account at the line "begin = max(a_k, Tlast[i])". I will add the selection tracking. $\endgroup$ – Vince May 15 at 14:45
  • $\begingroup$ @user6080524 I added the selection tracking and a small example. Let me know it is clear enough. $\endgroup$ – Vince May 15 at 15:18

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.