A task-scheduling problem as a matroid (CLRS book)

Question

I don't understand very well section 16.5 of the 3rd edition of the famous Introduction to Algorithms book, known as CLRS. It defines the problem of scheduling unit-time tasks with deadlines and penalties for a single processor with the following inputs:

• a set $S = {a_{1}, a_{2}, ..., a_{n}}$ of $n$ unit-time tasks
• a set of $n$ integer deadlines ${d_{1}, d_{2}, ..., d_{n}}$ such that each $d_{i}$ satisfies $1 \leq d_{i} \leq n$ and task $a_i$ is supposed to finish by time $d_i$
• a set of of $n$ nonnegative weights or penalties ${w_{1}, w_{2}, ..., w_{n}}$, such that we incur a penalty of $w_i$ if task $a_i$ is not finished by time $d_i$, and we incur no penalty if a task finished by its deadline.

And the following goal:

We wish to find a schedule for S that minimizes the total penalty incurred for missed deadlines.

NOTE: I'm aware that there are other posts here about similar problems (scheduling unit-time tasks with profit etc.), but I'm trying to understand this particular explanation, on the CLRS book.

So, I'll get now to the point. On the same page (444), where it explains the core idea, the book talks about the early-first form and the canonical form, without mentioning the penalties anymore: it talks exclusively about the deadlines (I'm not going to copy the whole text, I'm assuming that who answers the question owns the book).

My first question: because the whole reasoning does not mention penalties, it looks like to me it will work only if all the penalties are equal, which would be a different problem. I'm probably missing something here. But what? No matter how you order the tasks based on deadlines, you cannot possibly minimize the penalties without taking them into account. In other words, even if you hit 99/100 deadlines and missed the deadline for that one single task, its penalty might be bigger than the penalties of all the other tasks combined. I don't understand CRLS's logic, in this particular case.

My second question: on the next page (445), CLRS mentions the penalties in one place:

The problem of minimizing the sum of the penalties of the late tasks is the same as the problem of maximizing the sum of the penalties of the early tasks. The following theorem thus ensures that we can use the greedy algorithm to find an independent set A of tasks with the maximum total penalty.

And after that it mentions theorem 16.13 claiming substantially that $(S, I)$ is a matroid.

I believe I understand that, it makes sense. But, how can we determine in the first place the subset of the early tasks without taking into account the actual values of each $w_i$ penalty? In my understanding, that's not possible. I wouldn't dare claiming there's a mistake in the CLRS book, but that's my only theory at the moment. Very likely I'm wrong, but I cannot figure out why. On page 444, it mentions twice "monotonically increasing deadlines" but never anything like "monotonically decreasing penalties".

On the other side, I've done some research and I've read about variations of this problem with profits instead of penalties. I've understood that the tasks need to be ordered by monotonically decreasing profit. After doing that, we put each task as close to its deadline as possible, and move left only (= early) when the slot is already taken. That makes completely sense, because the profit is taken into account. If we consider penalties as negative profits, shouldn't the same logic apply? But, even with a different logic, how can we ignore the $w_i$ values?

Answer 1

I believe you are completely correct but mixed up two things from the book, namely the order in which the tasks are selected and the order in which the tasks are scheduled.

The greedy algorithm here indeed orders the task by their weights $w_i$ (as for every max-weight greedy algorithm on matroids). Given a set $A$ of tasks that are independent, i.e. they can somehow be scheduled so that no task is late, one way to schedule those tasks, such that none of them is late is by ordering those tasks (and only those, you omit the the tasks that are not in $A$) in increasing order of their due dates $d_j$.

Regarding your example with 99/100 tasks early: The one with the biggest weight (or penalty) is definitely one of the 99 tasks, as it is the first one to be selected by the greedy algorithm (unless its due date is non-positive). However, this task does not need to be the one that appears in the schedule first.

In essence, the order in which the greedy algorithm selects the tasks is not related to the order in which the tasks are scheduled.

Towards your second question: Whether a task is early only depends on its due date. The corresponding independence check for the matroid would work as follows:

1. The empty set is independent (no task is late).
2. Given set $A$ and task $a \notin A$, order all tasks in $A+a = [a_1, \ldots, a_m]$ by $d_j$ (such that $d_1 \leq \ldots \leq d_m$) and check for all $a_j \in A+a$ whether $j \leq d_j$ (as you have unit processing times).

The reason why this works, is subject of Lemma 16.12 (in the 3rd edition at least. the equivalence of three statements).