Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

7.3: Adding an algorithm

  • Page ID
    34213
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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

    Time 0: Mark ready tasks

    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:

    clipboard_e77fb190a3f596755cb0ed99767471a80.png

    We jump to the time when the next task completes, which is at time 2.

    Time 2: Both processors complete their tasks. We mark those tasks as complete. With Task 1 complete, Task 2 becomes ready:

    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}\)

    clipboard_ed931c39742cb3d6bfcc67592f093b557.png

    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}\)

    clipboard_e5f8d7915ae037b71ff7e5fa3c51f66de.png

    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}\)

    clipboard_e5d65817f8fa5dc929322c44dbfb1f85a.png

    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}\)

    clipboard_e00d40539291882f1466b3b9ba4fc17fc.png

    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})}\)

    clipboard_e7bc0f4b15e2eb217727706f983d188af.png

    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}\)

    sc3.svg

    Answer

    Time 0: Tasks 1, 4, and 7 are ready. Assign Tasks 1 and 4

    Time 9: Task 4 completes. Only task 7 is ready; assign task 7

    Time 10: Task 1 completes. Task 2 now ready. Assign task 2

    Time 17: Task 2 completes. Nothing is ready. Processor 1 idles

    Time 22: Task 7 completes. Tasks 5 and 8 are ready. Assign tasks 5 and 8

    Time 26: Task 8 completes. Task 9 is ready. Assign task 9

    Time 27: Task 5 completes. Tasks 3 and 6 are ready. Assign task 3

    Time 31: Task 3 completes. Assign task 6

    Time 35: Everything is done. Finishing time is 35 for this schedule.

    clipboard_eeee2de77e15748630b6197c99fed34fc.png

    It is important to note that the list processing algorithm itself does not influence the resulting schedule – the schedule is completely determined by the priority list followed. The list processing, while do-able by hand, could just as easily be executed by a computer. The interesting part of scheduling, then, is how to choose a priority list that will create the best possible schedule.


    7.3: Adding an algorithm is shared under a CC BY-SA 3.0 license and was authored, remixed, and/or curated by David Lippman via source content that was edited to conform to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.