

Up until now, we have been creating schedules by guess-and-check, which works well enough for small schedules, but would not work well with dozens or hundreds of tasks. To create a more procedural approach, we might begin by somehow creating a priority list. Once we have a priority list, we can begin scheduling using that list and the list processing algorithm.

Priority List

A priority list is a list of tasks given in the order in which we desire them to be completed.

The List Processing Algorithm turns a priority list into a schedule.

List Processing Algorithm

1. On the digraph or priority list, circle all tasks that are ready, meaning that all pre-requisite tasks have been completed.
2. Assign to each available processor, in order, the first ready task. Mark the task as in progress, perhaps by putting a single line through the task.
3. Move forward in time until a task is completed. Mark the task as completed, perhaps by crossing out the task. If any new tasks become ready, mark them as such.
4. Repeat until all tasks have been scheduled.

Example 2

Using our digraph from above, schedule it using the priority list below:

$$\mathrm{T}_{1}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$$

Solution

Priority list: $$({\mathrm{T}_{1}}), (\mathrm{T}_{3}), (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$$

We assign the first task, $$\mathrm{T}_{1}$$ to the first processor, $$\mathrm{P}_{1}$$, and the second ready task, $$\mathrm{T}_{3}$$, to the second processor. Making those assignments, we mark those tasks as in progress:

Priority list: $$\cancel{(\mathrm{T}_{1})}, \cancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$$

Schedule up to here:

Priority list: $$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$$

We assign the next ready task on the list, $$\mathrm{T}_{4}$$ to $$\mathrm{P}_{1}$$, and $$\mathrm{T}_{5}$$ to $$\mathrm{P}_{2}$$.

Priority list: $$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \cancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$$

Time 3: Processor 1 has completed $$\mathrm{T}_{4}$$. Completing $$\mathrm{T}_{4}$$ does not make any other tasks ready (note that all the rest require that $$\mathrm{T}_{2}$$ be completed first).

Priority list: $$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$$

Since the next three tasks are not yet ready, we assign the next ready task, $$\mathrm{T}_{2}$$ to $$\mathrm{P}_{1}$$

Priority list: $$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \cancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$$

Time 3.5: Processor 1 has completed $$\mathrm{T}_{2}$$. Completing $$\mathrm{T}_{2}$$ causes $$\mathrm{T}_{6}$$ and $$\mathrm{T}_{7}$$ to become ready. We assign $$\mathrm{T}_{6}$$ to $$\mathrm{P}_{1}$$.

Priority list: $$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \cancel{(\mathrm{T}_{6})}, (\mathrm{T}_{7}), \mathrm{T}_{8}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$$

Time 4: Both processors complete their tasks. The completion of $$\mathrm{T}_{5}$$ allows $$\mathrm{T}_{8}$$ to become ready. We assign $$\mathrm{T}_{7}$$ to $$\mathrm{P}_{1}$$ and $$\mathrm{T}_{8}$$ to $$\mathrm{P}_{2}$$.

Priority list: $$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \cancel{(\mathrm{T}_{7})}, \cancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$$

Time 4.5: Both processors complete their tasks. $$\mathrm{T}_{9}$$ becomes ready, and is assigned to $$\mathrm{P}_{1}$$. There is no ready task for $$\mathrm{P}_{2}$$ to work on, so $$\mathrm{P}_{2}$$ idles.

Priority list: $$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \xcancel{(\mathrm{T}_{7})}, \xcancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \cancel{(\mathrm{T}_{9})}$$

With the last task completed, we have a completed schedule, with finishing time 5.5 days.

Try it Now 1

Using the digraph below, create a schedule using the priority list:

$$\mathrm{T}_{1}, \mathrm{T}_{2}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{9}$$