7.2 Getting Started

To begin thinking about scheduling, let us consider an auto shop that is converting a car from gas to electric. A number of steps are involved. A time estimate for each task is given.

Task 1: Remove engine and gas parts (2 days)
Task 2: Steam clean the inside of the car (0.5 day)
Task 3: Buy an electric motor and speed controller (2 days for travel)
Task 4: Construct the part that connects the motor to the car’s transmission (1 day)
Task 5: Construct battery racks (2 days)
Task 6: Install the motor (0.5 day)
Task 7: Install the speed controller (0.5 day)
Task 8: Install the battery racks (0.5 day)
Task 9: Wire the electricity (1 day)

Some tasks have to be completed before others – we certainly can’t install the new motor before removing the old engine! There are some tasks, however, that can be worked on simultaneously by two different people, like constructing the battery racks and installing the motor.

To help us visualize the ordering of tasks, we will create a digraph.

For example, this digraph shows that Task 1, notated $T sub 1$ for compactness, needs to be completed before Task 2. The number in parentheses after the task name is the time required for the task.

The time it takes to complete this job will partially depend upon how many people are working on the project.

For simplicity, we are going to make the very big assumptions that every processor can do every task, that they all would take the same time to complete it, and that only one processor can work on a task at a time.

If we had only one processor working on this task, it is easy to determine the finishing time; just add up the individual times. We assume one person can’t work on two tasks at the same time, ignore things like drying times during which someone could work on another task. Scheduling with one processor, a possible schedule would look like this, with a finishing time of 10 days.

Schedule chart for one processor on a time axis from 0 to 10 days, gridded every half day. P sub 1 runs T sub 1 from 0 to 2, T sub 3 from 2 to 4, T sub 4 from 4 to 5, T sub 5 from 5 to 7, T sub 2 from 7 to 7.5, T sub 6 from 7.5 to 8, T sub 7 from 8 to 8.5, T sub 8 from 8.5 to 9 and T sub 9 from 9 to 10. There is no idle time and the finishing time is 10 days.

In this schedule, all the ordering requirements are met. This is certainly not the only possible schedule for one processor, but no other schedule could complete the job in less time. Because of this, this is an optimal schedule with optimal finishing time – there is nothing better.

For two processors, things become more interesting. For small digraphs like this, we probably could fiddle around and guess-and-check a pretty good schedule. Here would be a possibility:

Schedule chart for two processors on a time axis from 0 to 10 days. P sub 1 runs T sub 1 from 0 to 2, T sub 3 from 2 to 4, T sub 6 from 4 to 4.5 and T sub 9 from 4.5 to 5.5. P sub 2 runs T sub 5 from 0 to 2, T sub 4 from 2 to 3, T sub 2 from 3 to 3.5, T sub 8 from 3.5 to 4 and T sub 7 from 4 to 4.5, then sits idle from 4.5 to 5.5. Finishing time 5.5 days.

With two processors, the finishing time was reduced to 5.5 days. What was processor 2 doing during the last day? Nothing, because there were no tasks for the processor to do. This is called idle time.

Is this schedule optimal? Could it have been completed in 5 days? Because every other task had to be completed before task 9 could start, there would be no way that both processors could be busy during task 9, so it is not possible to create a shorter schedule.

So how long will it take if we use three processors? About $10 / 3 equals 3.33$ days? Again we will guess-and-check a schedule:

Schedule chart for three processors on a time axis from 0 to 10 days. P sub 1 runs T sub 1 from 0 to 2, T sub 2 from 2 to 2.5, T sub 6 from 2.5 to 3, T sub 8 from 3 to 3.5 and T sub 9 from 3.5 to 4.5. P sub 2 runs T sub 3 from 0 to 2, idles from 2 to 2.5, runs T sub 7 from 2.5 to 3 and then idles to the end. P sub 3 runs T sub 4 from 0 to 1 and T sub 5 from 1 to 3, then idles. Finishing time 4.5 days.

With three processors, the job still took 4.5 days. It is a little harder to tell whether this schedule is optimal. However, it might be helpful to notice that since Task 1, 2, 6, and 9 have to be completed sequentially, there is no way that this job could be completed in less than $2 + 0.5 + 0.5 + 1 = 4$ days, regardless of the number of processors. Four days is, for this digraph, the absolute minimum time to complete the job, called the critical time.

Definition

Critical Time

The critical time is the absolute minimum time to complete the job, regardless of the number of processors working on the tasks.

# Ch 7.2 - the gas-to-electric car conversion as data: task -> (days, prerequisites)
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
}
MAX_PROCESSORS = 5      # TRY IT: raise it. Where does hiring more people stop helping?
# TRY IT: give T5 (battery racks) a prerequisite of "T1" and re-run.

def critical_path(tasks):
    memo = {}
    def chain(t):                     # longest run of tasks ENDING at t
        if t not in memo:
            memo[t] = tasks[t][0] + max([chain(p) for p in tasks[t][1]] + [0])
        return memo[t]
    cur = max(tasks, key=chain)
    length, path = chain(cur), []
    while cur:
        path.append(cur)
        pres = tasks[cur][1]
        cur = max(pres, key=chain) if pres else None
    return length, list(reversed(path))

def schedule(tasks, procs, priority=None):
    priority = priority or list(tasks)
    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

work = sum(t for t, _ in TASKS.values())
ctime, path = critical_path(TASKS)
print(f"total work: {work} days - that is the finishing time with one person.")
print(f"critical path: {' -> '.join(path)} = {ctime} days, which no number of")
print("workers can ever beat.\n\nprocessors   finishing time   idle time")
for n in range(1, MAX_PROCESSORS + 1):
    fin, _ = schedule(TASKS, n)
    print(f"{n:>10}   {fin:>14}   {n * fin - work:>9}")
fin, log = schedule(TASKS, 2)
print("\nthe 2-processor schedule, task by task:")
for start, stop, p, t in sorted(log):
    print(f"   P{p + 1}   day {start:>4} to {stop:>4}   {t}")
print(f"\nThis run used the tasks in numerical order and finished in {fin} days.")
print("The book's hand-made 2-processor schedule finished in 5.5. Same tasks, same")
print("two workers - only the ORDER of choosing differed. That is section 7.3.")

Critical time can be determined by looking at the longest sequence of tasks in the digraph, called the critical path

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.