In this paper, a novel schedulability analysis technique of real-time systems is presented. The developed approach is based on the consideration of the reachability graph of the (untimed) underlying Petri net of the studied model. The schedulability analysis is then conducted in two steps. Once a feasible firing sequence (called occurrence sequence) is highlighted, this sequence is then described under an algebraic form of type Ax ≤ b. The particular features of matrix A lead to a bimonotone linear inequality system. A bimonotone linear inequality is a linear inequality with at most two nonzero coefficients that are of opposite signs (if both different from zero). Thus, deciding whether a firing sequence is schedulable or not takes the form of the solution of a single-source shortest path problem which can be polynomially solved via the Bellman–Ford algorithm.