Scheduling algorithm to minimize the number of late jobs

Question

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)].

Answer 1

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\}$.