TERMINOLOGY

The Processors
Processors are the "workers" that do the work.
The word 'processor' itself carries an important connotation; namely, processors need not be people.
A processor could be an integrated circuit, a robot, a machine, a computer, an ATM, or even a person.
Notationally, we will use P₁ , P₂ , P₃ ,  . . .  , P_N  to represent the set of N processors available to do a job.

The Tasks
Tasks (or jobs) are the individual 'pieces' of work.
For our purposes, we will define a task as a unit of work that can't (by nature or by specification) be broken down into smaller units of work and is always carried out by a single processor.

The Processing Times
Every task has a processing time.
It is the amount of uninterrupted time required to carry out the task.
There is a serious complication here.  In many situations it may be the case that the processing time varies depending on which processor carries out the task or that some processors cannot carry out the task at all.
We will only deal with scheduling problems for which we can always assume that:
(1) each processor can carry out each task and
(2) the processing time for a task is the same for all processors and
(3) once a task is started, the processor must execute it without interruption.
Notationally, we may indicate the processing time for a task by putting it in parentheses after the name of the task, e.g., if task A can be completed in 5 hours, we might write 'A(5)'.

The Precedence Relations
These are restrictions on the order in which the tasks can be carried out.
We will use to indicate that task X must precede (come before) task Y.
Of course, if task Y must precede task X, we will write .
If there are no precedence requirements between task X and task Y (X can come before Y or Y can come before X), then we say that the two tasks are independent.
Precedence Relations are transitive.  This simply means that if     and  , then .  Or, in other words, if task X precedes task Y and task Y precedes task Z, then task X must also precede task Z.

Project
The entire set of tasks to be completed.

Critical Time (of a Project)
The minimum time required to complete the project.

Finishing Time (of a Project)
The actual time required to complete the project.

Schedule
A plan that specifies, for each task in a project, when the task will be done and by which processor.

Scheduling Algorithm
A systematic plan for creating schedules for projects.

Priority List
A list of all the tasks in the order in which the scheduler would prefer to see the tasks done.
Keep in mind that this is just a PREFERENCE!  The order of tasks on the priority list is followed UNLESS it causes a violation of the precedence relations.   Precedence relations override the priority list, but other than that, tasks are assigned to processors according to the priority list.

Optimal Schedule
A schedule with the minimum possible finishing time.
Or, in other words, an optmal schedule for a project is one for which the finishing time is equal to the critical time.

DIGRAPHS
If tasks are represented by vertices and precedence relations are represented by arrows pointing from one vertex to another, then the essence of a scheduling problem can be displayed visually by a graph known as a directed graph (digraph, for short).

This digraph represents a project consisting of four tasks: task A (takes 3 hours), task Q (takes 2 hours), task X (takes 4 hours), and task F (takes 2 hours).  The arrows reflect the precedence relations; namely, task X must precede (come before) tasks A & F and task Q must precede tasks X & A.

When dealing with ordinary graphs, the line segments connecting vertices were called edges.  For digraphs, the arrows connecting edges will be called arcs.   Just think of arcs as edges with arrows.

In the language of digraphs, is read "X is incident to Y" or "Y is incident from X."

For ordinary graphs, we defined the degree of a vertex.  For digraphs, we define the indegree of a vertex to be the number of arrows pointing in toward the vertex and the outdegree of a vertex to be the number of arrows pointing out away from the vertex.

In a digraph, a path from vertex A to vertex B is a sequence of arcs starting at A and ending at B in which no arc is repeated and each vertex in the sequence is incident to (precedes) the next one.

In a digraph, a cycle is a path that starts and ends at the same vertex.
A digraph that represents a scheduling problem CANNOT have a cycle.

Project Digraphs

Schedulers often take digraphs representing scheduling problems (for example, the one above) and modify them slightly so that they have "ficticious" START and END tasks of 0 time duration (as shown below).

Notice that the START vertex has arrows pointing away from it toward all tasks that could be the first task (as determined by the precedence relations).  Any vertex with an indegree of 0 could be the first task of the project.
And, the END vertex has arrows pointing toward it away from all tasks that could be the last task (as determined by the precedence relations).  Any vertex with an outdegree of 0 could be the last task of the project.

The Priority List
The Priority List specifies the preferred order in which the tasks should be done.
Precedence relations override the priority list, but other than that, tasks are assigned to processors according to the priority list.

How to assign tasks to processors for a given Priority List
· If all processors are busy, wait.
· If a processor is free, assign the first ready task on the priority list to a free processor.  Continue assigning ready tasks, in order, from the priority list until there are no free processors.  Remember, only ready tasks can be assigned!

The Number of Different Priority Lists Possible for a Project
For a project consisting of M tasks, the total number of different priority lists possible is given by M! = 1 x 2 x 3 x ... x M.
For instance, for a project with 5 tasks, there are 5! = 1(2)(3)(4)(5) = 120 different priority lists possible.

SCHEDULING ALGORITHMS (Algorithms for creating Priority Lists.)

Decreasing-Time Algorithm
(The Decreasing-Time Algorithm (DTA) is based on a seemingly simple strategy:  Do the longer jobs first and save the shorter jobs for last.)

Create a Priority List by listing the tasks in decreasing order of processing times (longest task first, shortest task last).  Tasks with equal processing times can be listed in any order.   A Priority List created by the DTA is often called a decreasing-time list.

A Problem with the Decreasing-Time Algorithm
The DTA ignores any information in the project digraph that might indicate that one or more tasks should be done early rather than late.

Critical-Path Algorithm

Preliminaries

Critical Path for X
For a vertex, X, of a project digraph, the critical path for X is the path from X to the END that has the longest total sum of processing times.

Critical Time for X
The actual total processing time in the critical path for vertex X is called the critical time for X.

Critical Path (for the Project)
The critical path for the project, or just critical path for short, is the critical path for the START vertex of the project.

Critical Time (for the Project)
The critical time for the project, or just critical time for short, is the critical time for the START vertex of the project.
A project can never be finished in less than the critical time for the project.

The Backflow Algorithm
(allows us to find the critical path and time for each vertex of a project digraph)
Note: We will indicate critical times for the vertices of a project digraph using square brackets to distinguish them from processing times (for which we use parentheses).

1. Begin at the END vertex of the project digraph and assign it a critical time of zero.
2. Move backwards to each vertex that is incident to (having an arrow pointing to) END and assign it a critical time.
   Note: For vertices incident to (having an arrow pointing to) END, the critical time is the same as the processing time.
3. For each of the vertices in Step 2, move backwards again to each vertex that is incident to (precedes) it and assign it a critical time.
   Note: For each of these vertices, the critical time is its processing time added to the LARGEST critical time of the vertices incident from (having an arrow pointing away from) that vertex.
4. Continue this process until each vertex of the project digraph has a critical time.
   Note: The critical time for each vertex is its processing time added to the LARGEST critical time of the vertices incident from (having an arrow pointing away from) that vertex.

Critical-Path Algorithm (based on a strategy similar to that of the Decreasing-Time Algorithm:
Do the jobs with the largest critical times first and save the jobs with shorter critical times for last.
(The DTA does the jobs with the largest processing times first.))

Create a Priority List by listing the tasks in decreasing order of critical times.  Tasks with equal critcal times can be listed in any order.  A Priority List created by the CPA is often called a critical-path list.

Although the Critical-Path Algorithm is generally better than the Decreasing-Time Algorithm, neither is guaranteed to produce an optimal schedule.   In fact, no efficient scheduling algorithm is presently known that always gives an optimal schedule.  However, the Critical-Path Algorithm is the best general-purpose scheduling algorithm currently known.

Scheduling with Independent Tasks

• When all tasks are independent (there are no precedence relations), tasks can always be assigned to the processors as they become free in exactly the order given by the Priority List.  So, there is no need to analyze a project digraph before assigning tasks to processors for a scheduling problem consisting of independent tasks.
• When all tasks are independent (there are no precedence relations), the decreasing-time list and the critical-path list are exactly the same.  This means, of course, that the Decreasing-Time Algorithm (DTA) is the same as the Critical-Path Algorithm (CPA).  So, there is no need to go to the extra trouble of calculating critical times in order to apply the CPA to a scheduling problem consisting of independent tasks.

Back