Cyclic Schedules and the Max-Plus Eigenvalue
Close a one-shot schedule into a loop — a finished part releases the next job — and the schedule becomes a cyclic event system. Its behavior is governed by the max-plus recurrence
\[x(k+1)_j = \max_i \bigl( x_i(k) + \widehat{Q}_{ij} \bigr),\]
where \(x_j(k)\) is the time of the \(k\)-th firing of stage \(j\). After a transient, such a system is eventually periodic up to linear drift: the relative pattern of event times repeats while advancing at a fixed rate. That rate is an eigenvalue — the maximum cycle mean — and the cycle that attains it is the system’s bottleneck.
Tropical multiplication accumulates lag around the loop. The worst cycle sets the beat.
The explorer is a single self-contained HTML file. It runs entirely in your browser with no server, no network, and no dependencies — the Download offline HTML link gives you the same artifact to keep and open directly from disk.
What you can do
- Step the recurrence from a chosen initial vector and watch the transient lock onto the periodic regime \(x(k+4) = x(k) + 12\) — twelve time units every four events, a cadence of \(\lambda = 3\).
- Flip the chart to de-trended view \(x(k) - \lambda k\): the periodic regime becomes a flat repeating band, and the system’s drift disappears.
- Start from the eigenvector \(v = (0, 0, -2, 0, 3, 1)\) and see the special case: no transient, no wobble — \(x(k) = v + 3k\) exactly.
- Drag arc weights in the sensitivity view: watch the four cycle means, the eigenvalue, and the critical cycle respond. Speeding up an off-bottleneck arc changes nothing; slowing the transfer \(A \to D\) to 4 produces two co-critical cycles — the exact breakpoint in the piecewise-linear curve \(\lambda(w)\).
- Toggle the semantics view between the literal serial reading (one part per 12 time units) and the pipelined first-order reading (one per \(12/4 = 3\)): same graph, same weights, four jobs in flight.
This artifact covers the cyclic half of the story; the one-shot half — shortest paths, Bellman–Ford, and critical paths on the same graph — lives in the shortest-paths explorer.
Supporting information
This interactive page serves as supporting information for the tropical-algebra paper When Addition Becomes Optimization: Tropical Algebra, Paths, Schedules, and Semiring Computation (Sections 10–11: cyclic event systems and max-plus eigenvalues). It is designed to remain usable offline and to be archived alongside the paper.