A Task-scheduling Problem

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 = {a₁, a₂, ..., a_n} of n unit-time tasks;

• a set of n integer deadlines d₁, d₂, ..., d_n, such that each d_i satisfies 1 ≤ d_i ≤ n and task a_i is supposed to finish by time d_i; and

• a set of n nonnegative weights or penalties w₁, w₂, ..., 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 finishes by its deadline.

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

• Consider a given schedule. We say that a task is late in this schedule if it finishes after its deadline. Otherwise, the task is early in the schedule. An arbitrary schedule can always be put into early-first form, in which the early tasks precede the late tasks. To see this, note that if some early task a_i follows some late task a_j, then we can switch the positions of a_i and a_j, and a_i will still be early and a_j will still be late.
• We similarly claim that an arbitrary schedule can always be put into canonical form, in which the early tasks precede the late tasks and the early tasks are scheduled in order of monotonically increasing deadlines. To do so, we put the schedule into early-first form. Then, as long as there are two early tasks a_i and a_j finishing at respective times k and k 1 in the schedule such that d_j < d_i, we swap the positions of a_i and a_j. Since a_j is early before the swap, k 1 ≤ d_j. Therefore, k 1 < d_i, and so a_i is still early after the swap. Task a_j is moved earlier in the schedule, so it also still early after the swap.
• The search for an optimal schedule thus reduces to finding a set A of tasks that are to be early in the optimal schedule. Once A is determined, we can create the actual schedule by listing the elements of A in order of monotonically increasing deadline, then listing the late tasks (i.e., S - A) in any order, producing a canonical ordering of the optimal schedule.
• We say that a set A of tasks is independent if there exists a schedule for these tasks such that no tasks are late. Clearly, the set of early tasks for a schedule forms an independent set of tasks. Letℓ denote the set of all independent sets of tasks.
• Consider the problem of determining whether a given set A of tasks is independent. For t = 0, 1, 2, ..., n, let N_t (A) denote the number of tasks in A whose deadline is t or earlier. Note that N₀(A) = 0 for any set A.

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.