The project digraph specifies the
precedent relations.
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! If the next task on the priority list is not ready to be done
(because of precedence relation), then it cannot be assigned to a processor until the
precedence relations have been satisfied. For instance, if 
, then task Y cannot be assigned to a processor until task X is
complete no matter where it falls on the priority list.
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.
How to create a Priority List
In theory, we would solve a scheduling problem by creating the project digraph (specifying
the precedence relations), list all possible priority lists, and then see which priority
list(s) allow the project to be completed in the shortest amount of time. But, as
you can see, a project with even a relatively few tasks can result in a very large number
of priority lists. (Even with just 10 tasks, there are more than three million
priority lists.) Since it is often not practical (or possible, for that matter) to
analyze all possible priority lists, the remainder of this section will be devoted to
describing algorithms for generating priority lists (ones that we think will be
"close" to the optimal schedule).