Cyclic Schedules and the Max-Plus Eigenvalue

λ as a function of one weight

What does x_j(k) mean?

x_j(k) is the time of the k-th firing of node j. The recurrence is a modeling choice — toggle the two readings and watch the arc badges on the graph above:

x(k+1)_j = max_i ( x_i(k) + Q̂_ij )

every arc advances the event index:
the (k+1)-st firing waits for the
k-th firings of all predecessors.

A_k = S_k + 3      B_k = S_k + 1
C_k = max(A_k + 2, B_k + 5)
D_k = max(A_k + 6, B_k + 4)
T_k = max(C_k + 2, D_k + 1)
S_(k+1) = T_k + 2   ← only this arc
                      advances the index

The cadence: one part per 12, or one per 3

Same graph, same weights. The serial reading finishes one job per 10 + 2 = 12 time units. The first-order reading pipelines: up to four jobs in flight — one per arc of the bottleneck cycle — so the long-run average is one completion every 12/4 = 3.