A Bigger Scheduling Problem - Scheduling & the Critical Path

Three jobs sharing three machines turn scheduling into a resource problem: eight tasks, each pinned to one machine with an exact duration, parsed from the real model file the external solver reads. No solving happens yet.

highlighted = computed this step

The instance

There are 3 jobs, 3 machines, and 8 tasks in total; each task is pinned to one machine with an exact integer duration. Why: this is the real model the external solver reads, parsed from its model file at build time, not hand-typed into the lesson.

\text{tasks}=8

A new dimension: machines

Unlike the pinned activity DAG of the earlier chapters — whose honesty line already says no resource limits — tasks now compete for machines: a machine runs one task at a time. Why: the DAG model orders tasks inside one project, but it cannot represent two jobs needing the same machine at the same time.

\text{one machine, one task at a time}

The horizon

The solver searches integer times from 0 to 21, and the horizon equals the sum of all durations, 21 — the schedule where everything runs back to back. Why: an upper bound that loose is always safe, and this lesson presents the instance only; solving comes next.

\text{horizon}=21

Diagram note

The table lists one row per task, J1 through J3, with the machine column numbering the machines M1 through M3; those labels are the vocabulary this chapter uses everywhere. Pixel positions are rounded for layout; every number shown is exact.

\text{parsed instance, not typed}