We investigate a fundamental object in operations research: the stability region of a randomly modulated scheduling problem. Specifically, we consider a queueing system comprising multiple queues and a single server, where the scheduling decisions are influenced by stationary random modulations of the queue capacities, evolving autonomously over a finite state space (which is essentially the model studied in \cite{shakkottai}). In this setting, we identify the stability problem with two structures arising, respectively, in combinatorial optimisation and convex geometry: a generalised network flow -- or network flow with gains -- and a cephoid -- the Minkowski sum of deGua simplices. These novel identifications yield: strongly polynomial algorithms for feasibility; new characterisations of the stability region -- explicit in some cases; and algorithms for computing its minimal descriptions. In the particular ON/OFF case (initially studied in \cite{tassiulas}), where the first identification reduces to a classical network flow, we present a unified framework tied together by the max-flow/min-cut theorem.