Queueing, Scheduling & Network Flow Explorer

Analyze queueing systems with M/M/1 and M/M/c models, compare single-machine scheduling algorithms with interactive Gantt charts, and find maximum flow in directed networks using the Edmonds-Karp algorithm.

Model

Arrival rate (λ)(per unit time)Service rate (μ)(per server)

M/M/1 Queue Metrics

Utilization (ρ)

\rho = \lambda / \mu

60.0%

P(system empty)

P_0

0.4000

Avg queue length (Lq)

L_q = \rho^2 / (1 - \rho)

0.9000

Avg in system (L)

L = \\lambda \\cdot W

1.5000

Avg wait in queue (Wq)

W_q = L_q / \\lambda

0.3000 time units

Avg time in system (W)

W = W_q + 1/\\mu

0.5000 time units

P(waiting)

P_w = \rho

0.6000

Little's Law check $L = \lambda W$ = 3.0000 × 0.5000 = 1.5000 ≈ 1.5000

Reference Guide

M/M/1 Queue Formulas

The M/M/1 queue has Poisson arrivals (rate $\lambda$ ) and exponential service times (rate $\mu$ ) with a single server. The system is stable when $\rho = \lambda/\mu < 1$ .

L = \frac{\rho}{1 - \rho}, \quad L_q = \frac{\rho^2}{1 - \rho}

The average time a customer spends waiting in the queue and in the system overall are given by

W_q = \frac{\rho}{\mu - \lambda}, \quad W = \frac{1}{\mu - \lambda}

For M/M/c queues with $c$ servers, the Erlang-C formula gives the probability that an arriving customer must wait. Utilization per server becomes $\rho = \lambda / (c\mu)$ .

Little's Law (L = λW)

Little's Law is a fundamental theorem in queueing theory that holds for any stable system, regardless of arrival distribution, service distribution, or scheduling policy.

L = \lambda W

where $L$ is the average number of items in the system, $\lambda$ is the average arrival rate, and $W$ is the average time an item spends in the system.

This also applies to the queue alone

L_q = \lambda W_q

Little's Law is used in factory throughput analysis, software performance modeling, and hospital patient flow estimation.

Scheduling Algorithms

Single-machine scheduling optimizes different objectives depending on which rule is used.

SPT (Shortest Processing Time) minimizes average flow time $\bar{F} = \frac{1}{n}\sum_{j=1}^{n} C_j$ by processing the shortest jobs first.

EDD (Earliest Due Date) minimizes maximum lateness $L_{\max} = \max_j (C_j - d_j)$ by scheduling jobs with the nearest deadlines first.

WSPT (Weighted Shortest Job) minimizes total weighted completion time $\sum w_j C_j$ by sorting jobs in decreasing order of $w_j / p_j$ .

For a single machine, all algorithms produce the same makespan $C_{\max} = \sum p_j$ . The choice of rule depends on the optimization objective.

Max Flow / Min Cut

The max-flow problem finds the greatest amount of flow that can be sent from a source to a sink in a directed graph where each edge has a capacity constraint.

\text{max flow} = \text{min cut}

The Max-Flow Min-Cut Theorem states that the maximum flow equals the minimum total capacity of edges whose removal disconnects the source from the sink.

The Ford-Fulkerson method repeatedly finds augmenting paths in the residual graph and pushes flow along them. The Edmonds-Karp variant uses BFS, guaranteeing $O(VE^2)$ time complexity.

Applications include network routing, bipartite matching, transportation logistics, and image segmentation.