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.
And, since scheduling is not much of an issue when there is only one processor, we will concern ourselves only with cases for which the number of processors is 2 or more.

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.
A task could be wiring a house, installing a hard drive, baking a cake, or inspecting a hazardous waste disposal site.
For scheduling purposes, tasks must be specified in advance.  For instance, wiring a house might be scheduled as a 16 hour task for a single electrician or perhaps as two separate 7 hour tasks that could be done by two electricians.  The important thing is that a task, once specified, cannot be further sub-divided during the actual scheduling process.

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.
If task X is putting on your socks, task Y is putting on your shoes, and task Z is putting on your shirt, then  since you should always put on your socks before putting on your shoes.   However, tasks X and Z are independent since it doesn't matter whether you put on your socks before your shirt or your shirt before your socks.  Similarly, Y and Z 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.

Back