Turning Markov Chains Into Graphs Yields Exact Formulas for Production Line Performance

For nearly seventy years, engineers studying serial production lines have relied on numerical methods to estimate quantities such as throughput and machine utilization. Now a research team from the University of the Aegean and Aristotle University of Thessaloniki has developed a general algorithm that extracts exact, closed-form symbolic formulas for the stationary probabilities of any finite Markov chain, publishing the methodology in Frontiers in Manufacturing Technology. The work, led by Konstantinos S. Boulas, Georgios D. Dounias, and Chrissoleon T. Papadopoulos, transforms the transition matrix of a Markov chain into a weighted directed graph and then systematically enumerates a special class of graph structures called anti-arborescences to produce the stationary probabilities as ratios of polynomials in symbolic form.

Markov chains model systems whose future depends only on the present state, a memoryless property that keeps complexity low while capturing the dynamics of queues, production lines, maintenance systems, and supply chains. Traditionally, the stationary probabilities of such chains are obtained numerically by solving systems of linear algebraic equations. The new approach instead exploits a deep connection between Markov chains and graph theory: the transition matrix can be represented as a directed graph whose vertices are the system states and whose weighted edges encode the mean transition rates between states. The graph is entirely characterized by its adjacency matrix, establishing a direct correlation with the transition matrix of the underlying Markov process.

The mathematical heart of the method lies in the Markov Chain Tree Theorem. An anti-arborescence is a spanning tree of the directed graph in which all edges point toward a single final node, the root. Such a tree contains all N states of the system and exactly N minus 1 edges, making every state accessible from any other within at most N minus 1 transitions. Because the transitions along the edges are independent events, the probability of a given anti-arborescence equals the product of the transition probabilities of its edges. According to the theorem, the probability that the system occupies a particular state is the sum of the probabilities of all anti-arborescences ending at that state, normalized by the sum of the probabilities of all anti-arborescences in the graph.

These sums of products translate directly into polynomial algebra. Each anti-arborescence yields a spanning monomial, the product of its edge weights. The sum of all monomials ending at a state forms the spanning polynomial of that state, which becomes the numerator of the stationary probability. The sum of the spanning polynomials of all states forms the spanning polynomial of the graph, a common denominator shared by every stationary probability. When the edge weights are symbols rather than numbers, the result is an exact mathematical formula; when they are numbers, the same procedure delivers a numerical value. Crucially, no systems of linear equations or differential equations need to be solved at any point.

The algorithmic challenge is enumerating all anti-arborescences efficiently, because their number grows hyper-exponentially with graph size. For a complete directed graph with n vertices, Cayley’s formula shows that the number of spanning trees rooted at each vertex equals n raised to the power n minus 2. The team therefore adopted the algorithm of Gabow and Myers from 1978, which is optimal for listing all spanning trees rooted at a specific vertex of a directed graph. Since that algorithm finds trees growing away from a root rather than ending at one, the researchers first transpose the transition matrix, reversing the direction of every edge while preserving its weight. The Gabow and Myers procedure is then executed once for each of the N states.

A key technical innovation is the Relabeling procedure. Before each execution of the Gabow and Myers algorithm, the vertices of the graph are reordered according to a depth-first search starting from the state under consideration, and temporarily renamed with ascending numbers. The original graph remains untouched as a reference structure containing all state names and transition weights. Experiments with relatively large graphs showed that this relabeling does not change the output but reduces the number of manipulations needed to identify the bridge edge that serves as the stopping criterion of the enumeration, thereby cutting execution time. The effect is negligible for small graphs but becomes significant for larger systems.

The researchers validated the method on classic examples from operations research. Applying it to a three-machine production line without intermediate buffers, a system first analyzed by G. C. Hunt in 1956, the algorithm reproduced the polynomial structure of Hunt’s celebrated throughput formula and revealed its composition from the stationary probabilities of individual states. For a two-stage line with a one-slot buffer, the extracted symbolic formulas for maximum utilization and throughput matched Hunt’s general expressions exactly after algebraic simplification. Compared against the numerical MARKOV algorithm in the Prodline software across 196 balanced and unbalanced line configurations, the symbolic results agreed with a Mean Absolute Error of 2.82 times ten to the minus seven, while the equation-based evaluation completed in fractions of a second versus six minutes and forty-four seconds for the numerical method.

The discussion in the paper confronts the method’s limits candidly. The exact closed-form formulas grow exponentially in size as the number of states increases, restricting direct application to small systems. For a ten-stage production line, the team counted 6,765 states and 32,960 transitions, far fewer than the theoretical 45 million of a fully connected graph, yet still enough to make exhaustive enumeration impractical. The authors argue that these intricate formulas for small systems serve as building blocks for other methodologies, including decomposition techniques, simulation testing, and the generation of training data for artificial intelligence methods. Once a formula is found, its evaluation is dramatically faster than numerical solution and requires no special software.

Beyond manufacturing, the correlation between Markov chains and graphs opens research directions in discrete mathematics and artificial intelligence. The computation tree generated by the Gabow and Myers algorithm describes a non-deterministic Turing machine, and the resulting spanning polynomials amount to detailed operating instructions for a production line, describing every possible transition. The authors suggest that the exact symbolic answers could serve as benchmarking tests for robust computing systems, including quantum computers, comparing the time to find anti-arborescences and the accuracy of results against computational challenges that may not yet have been invented. The internal topology of the state graphs, whose real transition counts fall well below theoretical maxima, may also illuminate production phenomena such as the bowl phenomenon that carries significant economic impact.

This paper is Part I of a two-part work, describing the methodology in full. Part II, by the same team, demonstrates the efficacy of the approach in unveiling accurate closed-form formulas for very short serial production lines without buffers, extending Hunt’s results to three-station systems for all performance metrics for the first time in the literature and providing symbolic stationary probabilities for four-station systems. The authors indicate that future research will explore the role of spanning trees in transient conditions of Markov processes, absorption phenomena, first passage time probabilities, and graph decomposition, with applications extending to production lines, supply chains, and queueing networks.

Subject of Research: Markov chains and graph theory methodology for exact symbolic stationary probability extraction with application to production lines

Article Title: Extraction of exact symbolic stationary probability formulas for Markov chains with finite space with application to production lines. Part I: description of methodology

Article References: Extraction of exact symbolic stationary probability formulas for Markov chains with finite space with application to production lines. Part I: description of methodology. (n.d.). https://doi.org/10.3389/fmtec.2025.1439421

Image Credits: AI Generated

DOI: 10.3389/fmtec.2025.1439421

Keywords: Markov chains, graph theory, spanning trees, anti-arborescence, stationary probabilities, production lines, Extraction, exact, symbolic, stationary, probability, formulas