A task-scheduling problem
An interesting problem that can be solved using matroids is the problem of optimally scheduling unit-time tasks on a single processor, where each task has a deadline, along with a penalty that must be paid if the deadline is missed. The problem looks complicated, but it can be solved in a surprisingly simple manner using a greedy algorithm.
A unit-time task is a job, such as a program to be run on a computer, that requires exactly one unit of time to complete. Given a finite set S of unit-time tasks, a schedule for S is a permutation of S specifying the order in which these tasks are to be performed. The first task in the schedule begins at time 0 and finishes at time 1, the second task begins at time 1 and finishes at time 2, and so on.
The problem of scheduling unit-time tasks with deadlines and penalties for a single processor has the following inputs:
a set S = {a1, a2, ..., an} of n unit-time tasks;
a set of n integer deadlines d1, d2, ..., dn, such that each di satisfies 1 ≤ di ≤ n and task ai is supposed to finish by time di; and
a set of n nonnegative weights or penalties w1, w2, ..., wn, such that we incur a penalty of wi if task ai is not finished by time di and we incur no penalty if a task finishes by its deadline.
We are asked to find a schedule for S that minimizes the total penalty incurred for missed deadlines.
The set A is independent.
For t = 0, 1, 2, ..., n, we have Nt (A) ≤ t.
If the tasks in A are scheduled in order of monotonically increasing deadlines, then no task is late.
Proof Clearly, if Nt (A) >; t for some t, then there is no way to make a schedule with no late tasks for set A, because there are more than t tasks to finish before time t. Therefore, (1) implies (2). If (2) holds, then (3) must follow: there is no way to "get stuck" when scheduling the tasks in order of monotonically increasing deadlines, since (2) implies that the ith largest deadline is at most i. Finally, (3) trivially implies (1).
Using property 2 of Lemma 16.12, we can easily compute whether or not a given set of tasks is independent.
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.
Theorem 16.13: If S is a set of unit-time tasks with deadlines, andℓ is the set of all independent sets of tasks, then the corresponding system (S,ℓ) is a matroid.
Proof Every subset of an independent set of tasks is certainly independent. To prove the exchange property, suppose that B and A are independent sets of tasks and that |B| >; |A|. Let k be the largest t such that Nt (B) ≤ Nt (A). (Such a value of t exists, since N0(A) = N0(B) = 0.) Since Nn(B) = |B| and Nn(A) = |A|, but |B| >; |A|, we must have that k < n and that Nj(B) >; Nj(A) for all j in the range k 1 ≤ j ≤ n. Therefore, B contains more tasks with deadline k 1 than A does. Let ai be a task in B - A with deadline k 1. Let A′ = A ∪ {ai}.
We now show that A′ must be independent by using property 2 of Lemma 16.12. For 0 ≤ t ≤ k, we have Nt (A′) = Nt (A) ≤ t, since A is independent. For k < t = n, we have Nt (A′) ≤ Nt (B) ≤ t, since B is independent. Therefore, A′ is independent, completing our proof that (S,ℓ) is a matroid.