7.3 Adding an algorithm

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.

Note

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.

# Ch 7.3 - the List Processing Algorithm. The schedule is decided entirely by
# the priority list you hand it, so changing the list changes the answer.
TASKS = {
    "T1": (2.0, []),                     # remove engine and gas parts
    "T2": (0.5, ["T1"]),                 # steam clean the inside
    "T3": (2.0, []),                     # buy motor and speed controller
    "T4": (1.0, []),                     # build the motor-to-transmission part
    "T5": (2.0, []),                     # build the battery racks
    "T6": (0.5, ["T2", "T3", "T4"]),     # install the motor
    "T7": (0.5, ["T2", "T3"]),           # install the speed controller
    "T8": (0.5, ["T2", "T5"]),           # install the battery racks
    "T9": (1.0, ["T6", "T7", "T8"]),     # wire the electricity
}
PROCESSORS = 2
LISTS = {
    "the book's list": ["T1", "T3", "T4", "T5", "T6", "T7", "T8", "T2", "T9"],
    "plain numerical": ["T1", "T2", "T3", "T4", "T5", "T6", "T7", "T8", "T9"],
    "longest first":   ["T1", "T3", "T5", "T4", "T9", "T2", "T6", "T7", "T8"],
}
# TRY IT: add your own list, or move T2 to the very front of the book's list.

def schedule(tasks, procs, priority):
    done, running, now, log = {}, {}, 0.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=44):
    for p in range(procs):
        bar = [" "] * width
        for start, stop, q, t in log:
            if q != p:
                continue
            a = int(round(start / finish * width))
            b = max(a + 1, int(round(stop / finish * width)))
            label = t.center(b - a, "-")[:b - a]
            bar[a:b] = list(label)
        print(f"   P{p + 1} |{''.join(bar)}|")
    print(f"      0{' ' * (width - 1)}{finish}")

work = sum(t for t, _ in TASKS.values())
for name, priority in LISTS.items():
    finish, log = schedule(TASKS, PROCESSORS, priority)
    print(f"{name}: {', '.join(priority)}")
    print(f"   finishing time {finish} days, idle time {PROCESSORS * finish - work} days")
    gantt(log, finish, PROCESSORS)
    print()
print("Same tasks, same two workers, same algorithm - only the priority list moved.")

Example 1

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

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

Show solution

Time 0: Mark ready tasks

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

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

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

Schedule up to here:

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:

We assign the next ready task on the list, $T sub 4$ to $P sub 1$ , and $T sub 5$ to $P sub 2$ .

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

Since the next three tasks are not yet ready, we assign the next ready task, $T sub 2$ to $P sub 1$

Time 3.5: Processor 1 has completed $T sub 2$ . Completing $T sub 2$ causes $T sub 6$ and $T sub 7$ to become ready. We assign $T sub 6$ to $P sub 1$ .

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

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

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

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

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

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

Your Turn

Try it Now 1

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

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

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.

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.

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.