Excursions in Math Chapter 3: Scheduling Overview

The headings are links to examples.

Definitions

In scheduling problems, the vertices represent the tasks and each task has a completion time associated with it (we have weights associated with the vertices).

The edges represent which tasks must be completed before other tasks can be started.

A graph created like this is called an order requirement digraph.

A path consists of a set of vertices traversed through edges which join the tasks.

The path length is the sum of the weights of the vertices associated with the path.

A critical path is a path of longest length in the digraph. It represents the shortest possible time to finish the job, assuming you had an infinite number of processors available.

A priority list is a list of the tasks in which order you would like to do them. The priority list, in a sense, tells you how to read an order requirement digraph.

Independent tasks have an order requirement digraph which has no edges. Any task can be begun at any time in the scheduling process, since no task depends on other tasks. In this case, the priority list is all you need to create the schedule.

A schedule is a representation of how to schedule tasks on processors to complete a given job.

List Processing Algorithm

To create a schedule using the list processing algorithm, we need two things:

• an order requirement digraph, and
• a priority list for the tasks.

Changing either the order requirement digraph or the priority list will result in a different schedule. The schedule will also be different depending on how many processors we have at hand.

List Processing Algorithm:

• Assign the first available task to the first available processor.
• When a processor becomes available, we set it to work on the first task in the priority list which is ready. Ready means all tasks which needed to be completed before we started this task are done.

Critical Path Scheduling

In critical path scheduling, we are given an order requirement digraph but no priority list. We use critical path scheduling to create a priority list, then use the list processing algorithm to create the schedule.

Critical Path Scheduling

1. find a task that begins a critical path in the order requirement digraph. If there is a tie, choose the task with the lower number.
2. Place the task found in step 1 next on the list L.
3. Remove the task found in step 1, and all the edges attached to it, from the current order requirement digraph. This leaves a new order requirement digraph.
4. If there are no vertices left in the new order requirement digraph found in step 3, the procedure is complete and you have the priority list L. If there are vertices left, go to step 1.

The priority list found using critical path scheduling will hopefully produce a schedule which has an optimal or near optimal solution.

Decreasing Time List Algorithm

The decreasing time list algorithm creates a priority list for independent tasks by listing the tasks in order of decreasing time (this schedules long tasks first). The schedule is then created using the list processing algorithm.