7.4 Choosing a Priority List

We will explore two algorithms for selecting a priority list.

Decreasing time algorithm

The decreasing time algorithm takes the approach of trying to get the very long tasks out of the way as soon as possible by putting them first on the priority list.

Example 1

Consider the scheduling problem represented by the digraph below. Create a priority list using the decreasing time list algorithm, then use it to schedule for two processors using the list processing algorithm.

Show solution

To use the decreasing time list algorithm, we create our priority list by listing the tasks in order from longest task time to shortest task time. If there is a tie, we will list the task with smaller task number first (not for any good reason, but just for consistency).

For this digraph, the decreasing time algorithm would create a priority list of:

$T sub 6 open parenthesis 10 close parenthesis, T sub 3 open parenthesis 7 close parenthesis, T sub 10 open parenthesis 7 close parenthesis, T sub 1 open parenthesis 6 close parenthesis, T sub 5 open parenthesis 5 close parenthesis, T sub 4 open parenthesis 4 close parenthesis, T sub 7 open parenthesis 4 close parenthesis, T sub 2 open parenthesis 3 close parenthesis, T sub 8 open parenthesis 3 close parenthesis, T sub 9 open parenthesis 2 close parenthesis$

Once we have the priority list, we can create the schedule using the list processing algorithm. With two processors, we’d get:

Time 0: We identify ready tasks, and assign $T sub 3$ to $P sub 1$ and $T sub 1$ to $P sub 2$

Priority list: $T sub 6, open parenthesis T sub 3 close parenthesis crossed out, T sub 10, open parenthesis T sub 1 close parenthesis crossed out, T sub 5, open parenthesis T sub 4 close parenthesis, T sub 7, open parenthesis T sub 2 close parenthesis, T sub 8, T sub 9$

Time 6: $P sub 2$ completes $T sub 1$ . No new tasks become ready, so $T sub 4$ is assigned to $P sub 2$ .

Priority list: $T sub 6, open parenthesis T sub 3 close parenthesis crossed out, T sub 10, open parenthesis T sub 1 close parenthesis crossed out, T sub 5, open parenthesis T sub 4 close parenthesis crossed out, T sub 7, open parenthesis T sub 2 close parenthesis, T sub 8, T sub 9$

Time 7: $P sub 1$ completes $T sub 3$ . No new tasks become ready, so $T sub 2$ is assigned to $P sub 1$ .

Priority list: $T sub 6, open parenthesis T sub 3 close parenthesis crossed out, T sub 10, open parenthesis T sub 1 close parenthesis crossed out, T sub 5, open parenthesis T sub 4 close parenthesis crossed out, T sub 7, open parenthesis T sub 2 close parenthesis crossed out, T sub 8, T sub 9$

Time 10: Both processors complete their tasks. $T sub 6$ becomes ready, and is assigned to $P sub 1$ . No other tasks are ready, so $P sub 2$ idles.

Priority list: $T sub 6 crossed out, open parenthesis T sub 3 close parenthesis crossed out, T sub 10, open parenthesis T sub 1 close parenthesis crossed out, T sub 5, open parenthesis T sub 4 close parenthesis crossed out, T sub 7, open parenthesis T sub 2 close parenthesis crossed out, T sub 8, T sub 9$

Time 20: With $T sub 6$ complete, $T sub 5$ and $T sub 7$ become ready, and are assigned to $P sub 1$ and $P sub 2$ respectively.

Priority list: $open parenthesis T sub 6 close parenthesis crossed out, open parenthesis T sub 3 close parenthesis crossed out, T sub 10, open parenthesis T sub 1 close parenthesis crossed out, open parenthesis T sub 5 close parenthesis crossed out, open parenthesis T sub 4 close parenthesis crossed out, open parenthesis T sub 7 close parenthesis crossed out, open parenthesis T sub 2 close parenthesis crossed out, T sub 8, T sub 9$

Time 24: $P sub 2$ completes $T sub 7$ . No new items become ready, so $P sub 2$ idles.

Time 25: $P sub 1$ completes $T sub 5$ . $T sub 8$ and $T sub 9$ become ready, and are assigned.

Time 27: $T sub 9$ is completed. No items ready, so $P sub 2$ idles.

Time 28: $T sub 8$ is completed. $T sub 10$ becomes ready, and is assigned to $P sub 1$ .

Priority list: $open parenthesis T sub 6 close parenthesis crossed out, open parenthesis T sub 3 close parenthesis crossed out, open parenthesis T sub 10 close parenthesis crossed out, open parenthesis T sub 1 close parenthesis crossed out, open parenthesis T sub 5 close parenthesis crossed out, open parenthesis T sub 4 close parenthesis crossed out, open parenthesis T sub 7 close parenthesis crossed out, open parenthesis T sub 2 close parenthesis crossed out, open parenthesis T sub 8 close parenthesis crossed out, open parenthesis T sub 9 close parenthesis crossed out$

This is our completed schedule, with a finishing time of 35.

Using the decreasing time algorithm, the priority list led to a schedule with a finishing time of 35. Is this good? It certainly looks like there was a lot of idle time in this schedule. To get some idea how good or bad this schedule is, we could compute the critical time, the minimum time to complete the job. To find this, we look for the sequence of tasks with the highest total completion time. For this digraph that sequence would appear to be: $T sub 2, T sub 6, T sub 5, T sub 8, T sub 10,$ with total sequence time of 28. From this we can conclude that our schedule isn’t horrible, but there is a possibility that a better schedule exists.

Your Turn

Try it Now 2

Determine the priority list for the digraph from Try it Now 1 using the decreasing time algorithm.

Answer

$T sub 7, T sub 1, T sub 4, T sub 2, T sub 9, T sub 5, T sub 3, T sub 6, T sub 8$

Critical path algorithm

A sequence of tasks in the digraph is called a path. In the previous example, we saw that the critical path dictates the minimum completion time for a schedule. Perhaps, then, it would make sense to consider the critical path when creating our schedule. For example, in the last schedule, the processors began working on tasks 1 and 3 because they were longer tasks, but starting on task 2 earlier would have allowed work to begin on the long task 6 earlier.

The critical path algorithm allows you to create a priority list based on idea of critical paths.

I’m sure you can imagine that searching for the critical path every time you remove a task from the digraph would get really tiring, especially for a large digraph. In practice, the critical path algorithm is implementing by first working from the end backwards. This is called the backflow algorithm.

# Ch 7.4 - the backflow algorithm. Work backwards from the end of the digraph
# and label every task with its critical time: how long the job still has to run
# once that task starts.
TASKS = {                       # task: (time, prerequisites)
    "T1": (6, []),      "T2": (3, []),          "T3": (7, []),
    "T4": (4, []),      "T5": (5, ["T1", "T6"]), "T6": (10, ["T2"]),
    "T7": (4, ["T3", "T6"]), "T8": (3, ["T5", "T7"]),  "T9": (2, ["T5"]),
    "T10": (7, ["T5", "T7", "T8"]),
}
# TRY IT: change T6 from 10 to 2 and re-run. The critical path moves.

successors = {t: [s for s in TASKS if t in TASKS[s][1]] for t in TASKS}
critical, order = {}, []
while len(critical) < len(TASKS):
    for t in TASKS:
        if t in critical or any(s not in critical for s in successors[t]):
            continue
        critical[t] = TASKS[t][0] + max([critical[s] for s in successors[t]] + [0])
        order.append(t)

print("backflow, in the order the labels can be filled in:")
for t in order:
    downstream = successors[t]
    via = (f"{TASKS[t][0]} + {max(critical[s] for s in downstream)} "
           f"(through {max(downstream, key=lambda s: critical[s])})"
           if downstream else f"{TASKS[t][0]} + 0 (it feeds the end)")
    print(f"   critical time of {t:<4} = {via:<28} = {critical[t]}")

start = max(critical, key=lambda t: critical[t])
path, cur = [], start
while cur:
    path.append(cur)
    nxt = successors[cur]
    cur = max(nxt, key=lambda s: critical[s]) if nxt else None
print(f"\ncritical path: {' -> '.join(path)}")
print(f"critical time: {' + '.join(str(TASKS[t][0]) for t in path)} = {critical[start]}")
print(f"total work if one person did it all: {sum(t for t, _ in TASKS.values())}\n")

by_critical = sorted(TASKS, key=lambda t: (-critical[t], int(t[1:])))
by_time = sorted(TASKS, key=lambda t: (-TASKS[t][0], int(t[1:])))
print("critical path priority list :", ", ".join(by_critical))
print("decreasing time priority list:", ", ".join(by_time))
print("\nThe two lists disagree because a short task can still be the gate that")
print("holds up a very long chain behind it. Look at T2: only 3 units of work,")
print(f"but critical time {critical['T2']} - nothing else can finish until it does.")

Note

Backflow Algorithm

Introduce an “end” vertex, and assign it a time of 0, shown in [brackets]
Move backwards to every vertex that has an arrow to the end and assign it a critical time
From each of those vertices, move backwards and assign those vertices critical times. Notice that the critical time for the earlier vertex will be that task’s time plus the critical time for the later vertex.

Example: Consider this segment of digraph.

In this case, if T2 has already been determined to have a critical time of 10, then T1 will have a critical time of 5+10 = 15

If you have already assigned a critical time to a vertex, replace it only if the new time is larger.

Example: In the digraph below, T1 should be labeled with a critical time of 16, since it is the longer of 5+10 and 5+11.

4. Repeat until all vertices are labeled with their critical times

One you have completed the backflow algorithm, you can easily create the critical path priority list by using the critical times you just found.

This version of the Critical Path Algorithm will usually be the easier to implement.

Example 3

Applying this to our digraph from the earlier example, we start applying the backflow algorithm.

Show solution

We add an end vertex and give it a critical time of 0.

We then move back to $T sub 4, T sub 9,$ and $T sub 10$ , labeling them with their critical times

From each vertex marked with a critical time, we go back. $T sub 7$ , for example, will get labeled with a critical time 11 – the task time of 4 plus the critical time of 7 for $T sub 10$ . For $T sub 5$ , there are two paths to the end. We use the longer, labeling T₅ with critical time $5 + 7 = 12$ .

Continue the process until all vertices are labeled. Notice that the critical time for $T sub 5$ ended got replaced later with the even longer path through $T sub 8$ .

We can now quickly create the critical path priority list by listing the tasks in decreasing order of critical time:

Priority list: $T sub 2, T sub 6, T sub 1, T sub 3, T sub 5, T sub 7, T sub 8, T sub 10, T sub 4, T sub 9$

Applying this priority list using the list processing algorithm, we get the schedule:

In this particular case, we were able to achieve the minimum possible completion time with this schedule, suggesting that this schedule is optimal. This is certainly not always the case.

By observation, we can see that a much better schedule exists for the example above:

A better three processor schedule for the same tasks, boundary times 1, 3 and 9. P sub 1 runs T sub 1 from 0 to 1, T sub 6 from 1 to 3 and T sub 9 from 3 to 9. P sub 2 runs T sub 2 from 0 to 1, T sub 7 from 1 to 3 and T sub 5 from 3 to 9. P sub 3 runs T sub 3 from 0 to 1, T sub 8 from 1 to 3 and T sub 4 from 3 to 9. No processor is ever idle and the finishing time is 9.

In most cases the critical path algorithm will lead to a very good schedule. There are cases, like this, where it will not. Unfortunately, there is no known algorithm to always produce the optimal schedule.

# Ch 7.4 - decreasing time vs critical path, scheduled on N processors.
TASKS = {
    "T1": (6, []),      "T2": (3, []),           "T3": (7, []),
    "T4": (4, []),      "T5": (5, ["T1", "T6"]), "T6": (10, ["T2"]),
    "T7": (4, ["T3", "T6"]), "T8": (3, ["T5", "T7"]),  "T9": (2, ["T5"]),
    "T10": (7, ["T5", "T7", "T8"]),
}
PROCESSORS = 2      # TRY IT: 3, then 4. Does the critical path list stay ahead?

successors = {t: [s for s in TASKS if t in TASKS[s][1]] for t in TASKS}
critical = {}
while len(critical) < len(TASKS):
    for t in TASKS:
        if t not in critical and all(s in critical for s in successors[t]):
            critical[t] = TASKS[t][0] + max([critical[s] for s in successors[t]] + [0])

def schedule(procs, priority):
    done, running, now, log = {}, {}, 0, []
    while len(done) < len(TASKS):
        for p in range(procs):
            if p in running:
                continue
            live = [t for t, _ in running.values()]
            ready = [t for t in priority if t not in done and t not in live
                     and all(q in done for q in TASKS[t][1])]
            if ready:
                running[p] = (ready[0], now + TASKS[ready[0]][0])
                log.append((now, now + TASKS[ready[0]][0], p, ready[0]))
        now = min(f for _, f in running.values())
        for p in [p for p, (t, f) in running.items() if f <= now]:
            done[running.pop(p)[0]] = now
    return max(done.values()), log

def gantt(log, finish, procs, width=56):
    for p in range(procs):
        bar = [" "] * width
        for start, stop, q, t in log:
            if q == p:
                a = int(round(start / finish * width))
                b = max(a + 1, int(round(stop / finish * width)))
                bar[a:b] = list(t.center(b - a, "-")[:b - a])
        print(f"   P{p + 1} |{''.join(bar)}|")

work = sum(t for t, _ in TASKS.values())
best_possible = max(critical.values())
print(f"{len(TASKS)} tasks, {work} units of work, critical time {best_possible}.")
print(f"On {PROCESSORS} processors nothing can finish sooner than "
      f"max({best_possible}, {work}/{PROCESSORS} = {work / PROCESSORS:g}).\n")
lists = {
    "decreasing time": sorted(TASKS, key=lambda t: (-TASKS[t][0], int(t[1:]))),
    "critical path":   sorted(TASKS, key=lambda t: (-critical[t], int(t[1:]))),
}
for name, priority in lists.items():
    finish, log = schedule(PROCESSORS, priority)
    print(f"{name}: {', '.join(priority)}")
    print(f"   finishing time {finish}, idle time {PROCESSORS * finish - work}"
          + ("   <-- hits the critical time, so it is optimal"
             if finish == best_possible else ""))
    gantt(log, finish, PROCESSORS)
    print()
print("Getting the long jobs started early is not the same as getting the")
print("BLOCKING jobs started early, and only the second one is what matters.")

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.