Task-scheduling problem as a matroid

A task-scheduling problem as a matroid

An interesting problem that can be solved using matroid is the problem of optimally scheduling unit-time tasks on a single processor, where each task has a deadline, along with a penalty paid if the task misses its deadline.

            Given a finite set S of unit-time tasks, a schedule for S is a permutation of S specifying the order in which to perform these tasks.

            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 di; and

·         a set of n non negative weights or penalties w₁,w₂, . . . ,w_n, such that a penalty of w_i is incurred if task a_i is not finished by time d_i.

The problem is to find a schedule for S that minimizes the total penalty incurred for missed deadlines.

A task is said to be late in this schedule if it finishes after its deadline. Otherwise, the task is early in the schedule.

The search for an optimal schedule is to finding a set A of tasks that are early in the optimal schedule. Having found set A, create the actual schedule by listing the elements of A in order of monotonically increasing deadlines, then listing the late tasks (i.e., S - A) in any order, producing a canonical ordering of the optimal schedule.

The 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 because if the tasks in set A are scheduled in order of monotonically increasing deadlines then no task is late.

Theorem

Therefore, a greedy algorithm can be used to find a maximum-weight independent set of tasks A.

And according to theorem of correctness of greedy algorithm on matroids.

Example: