marimo-team/marimo-learn

1# /// script2# requires-python = ">=3.13"3# dependencies = [4#     "altair",5#     "asimpy",6#     "marimo",7#     "polars==1.24.0",8# ]9# ///10 11import marimo12 13__generated_with = "0.20.4"14app = marimo.App(width="medium")15 16 17@app.cell(hide_code=True)18def _():19    import marimo as mo20    import random21    import statistics22 23    import altair as alt24    import polars as pl25 26    from asimpy import Environment, Process, Resource27 28    return Environment, Process, Resource, alt, mo, pl, random, statistics29 30 31@app.cell(hide_code=True)32def _(mo):33    mo.md(r"""34    # Pooled vs. Separate Queues35 36    ## *Why Airports Switched to Single Lines*37 38    A facility has two identical servers. Customers arrive as a Poisson process and each needs one server for an exponentially distributed service time. Which queueing discipline should the facility use?39 40    - Separate queues: each server has its own dedicated line; customers randomly pick a line on arrival and cannot switch.41    - Pooled queue: a single shared line feeds whichever server becomes free first.42 43    It turns out that pooling the queues is always better, even though both systems have identical total arrival rate, identical per-server service rate, and identical utilization $\rho$. The pooled system consistently produces shorter mean wait times, often by a factor of two or more at moderate utilization. The reason is that separate queues waste servers' idle time. In separate queues, one server may be idle while customers wait in the other line. Pooling eliminates this mismatch: a free server always serves the next waiting customer.44 45    ### Why Separate Queues Persist46 47    Despite being provably worse, separate queues feel fairer because customers can see their progress. Single lines eliminate the anxiety of watching the other queue move faster, but historically customers resisted them until airlines and banks demonstrated the improvement empirically in the 1960s–70s.48    """)49    return50 51 52@app.cell(hide_code=True)53def _(mo):54    mo.md(r"""55    ## Implementation56 57    This tutorial explores this finding using two simulations run with identical random seeds:58 59    1. Pooled: `Resource(capacity=2)` with one arrival stream. The resource grants access to whichever capacity slot is free.60    2. Separate: two `Resource(capacity=1)` instances. Arrivals call `random.choice` to pick a server and cannot switch even if it is slower.61 62    The mean sojourn time is collected across a sweep of utilization levels $\rho$.63    """)64    return65 66 67@app.cell(hide_code=True)68def _(mo):69    sim_time_slider = mo.ui.slider(70        start=0,71        stop=100_000,72        step=1_000,73        value=20_000,74        label="Simulation time",75    )76 77    arrival_rate_slider = mo.ui.slider(78        start=0.5,79        stop=1.9,80        step=0.05,81        value=1.8,82        label="Arrival rate",83    )84 85    seed_input = mo.ui.number(86        value=192,87        step=1,88        label="Random seed",89    )90 91    run_button = mo.ui.run_button(label="Run simulation")92 93    mo.vstack([94        sim_time_slider,95        arrival_rate_slider,96        seed_input,97        run_button,98    ])99    return arrival_rate_slider, seed_input, sim_time_slider100 101 102@app.cell103def _(arrival_rate_slider, seed_input, sim_time_slider):104    SIM_TIME = int(sim_time_slider.value)105    ARRIVAL_RATE = float(arrival_rate_slider.value)106    SEED = int(seed_input.value)107    SERVICE_RATE = 1.0108    N_SERVERS = 2109    RHO = ARRIVAL_RATE / (N_SERVERS * SERVICE_RATE)110    return ARRIVAL_RATE, N_SERVERS, RHO, SEED, SERVICE_RATE, SIM_TIME111 112 113@app.cell114def _(Process, SERVICE_RATE, random):115    class Customer(Process):116        def init(self, server, sojourn_times):117            self.server = server118            self.sojourn_times = sojourn_times119 120        async def run(self):121            arrival = self.now122            async with self.server:123                await self.timeout(random.expovariate(SERVICE_RATE))124            self.sojourn_times.append(self.now - arrival)125 126    return (Customer,)127 128 129@app.cell130def _(Customer, Process, random):131    class PooledArrivals(Process):132        def init(self, arrival_rate, server, sojourn_times):133            self.arrival_rate = arrival_rate134            self.server = server135            self.sojourn_times = sojourn_times136 137        async def run(self):138            while True:139                await self.timeout(random.expovariate(self.arrival_rate))140                Customer(self._env, self.server, self.sojourn_times)141 142    return (PooledArrivals,)143 144 145@app.cell146def _(Customer, Process, random):147    class SeparateArrivals(Process):148        def init(self, arrival_rate, servers, sojourn_times):149            self.arrival_rate = arrival_rate150            self.servers = servers151            self.sojourn_times = sojourn_times152 153        async def run(self):154            while True:155                await self.timeout(random.expovariate(self.arrival_rate))156                server = random.choice(self.servers)157                Customer(self._env, server, self.sojourn_times)158 159    return (SeparateArrivals,)160 161 162@app.cell163def _(164    ARRIVAL_RATE,165    Environment,166    N_SERVERS,167    PooledArrivals,168    Resource,169    SEED,170    SIM_TIME,171    random,172    statistics,173):174    def run_pooled(arrival_rate=ARRIVAL_RATE):175        random.seed(SEED)176        sojourn_times = []177        env = Environment()178        shared_server = Resource(env, capacity=N_SERVERS)179        PooledArrivals(env, arrival_rate, shared_server, sojourn_times)180        env.run(until=SIM_TIME)181        return statistics.mean(sojourn_times)182 183    return (run_pooled,)184 185 186@app.cell187def _(188    ARRIVAL_RATE,189    Environment,190    N_SERVERS,191    Resource,192    SEED,193    SIM_TIME,194    SeparateArrivals,195    random,196    statistics,197):198    def run_separate(arrival_rate=ARRIVAL_RATE):199        random.seed(SEED)200        sojourn_times = []201        env = Environment()202        servers = [Resource(env, capacity=1) for _ in range(N_SERVERS)]203        SeparateArrivals(env, arrival_rate, servers, sojourn_times)204        env.run(until=SIM_TIME)205        return statistics.mean(sojourn_times)206 207    return (run_separate,)208 209 210@app.cell211def _(ARRIVAL_RATE, N_SERVERS, SERVICE_RATE, pl, run_pooled, run_separate):212    def sweep():213        sweep_rows = []214        for rho in [0.5, 0.6, 0.7, 0.8, 0.9]:215            rate = rho * N_SERVERS * SERVICE_RATE216            pw = run_pooled(arrival_rate=rate)217            sw = run_separate(arrival_rate=rate)218            sweep_rows.append({"rho": rho, "pooled_W": pw, "separate_W": sw, "ratio": sw / pw})219        return pl.DataFrame(sweep_rows)220 221    df_sweep = sweep()222    pooled_W = run_pooled(arrival_rate=ARRIVAL_RATE)223    separate_W = run_separate(arrival_rate=ARRIVAL_RATE)224    return df_sweep, pooled_W, separate_W225 226 227@app.cell(hide_code=True)228def _(N_SERVERS, RHO, SERVICE_RATE, mo, pooled_W, separate_W):229    mo.md(f"""230    ## Results231 232    {N_SERVERS} servers, service rate {SERVICE_RATE}, utilisation ρ = {RHO:.2f}233 234    At ρ = {RHO:.2f}: pooled W = {pooled_W:.3f}, separate W = {separate_W:.3f}235    — separate queues are **{separate_W / pooled_W:.2f}×** slower236    """)237    return238 239 240@app.cell241def _(df_sweep):242    df_sweep243    return244 245 246@app.cell247def _(alt, df_sweep):248    df_plot = df_sweep.unpivot(249        on=["pooled_W", "separate_W"], index="rho", variable_name="system", value_name="W"250    )251    chart = (252        alt.Chart(df_plot)253        .mark_line(point=True)254        .encode(255            x=alt.X("rho:Q", title="Utilization per server (ρ)"),256            y=alt.Y("W:Q", title="Mean sojourn time (W)"),257            color=alt.Color("system:N", title="Queue type"),258            tooltip=["rho:Q", "system:N", "W:Q"],259        )260        .properties(title="Pooled vs. Separate Queues: Mean Sojourn Time")261    )262    chart263    return264 265 266@app.cell(hide_code=True)267def _(mo):268    mo.md(r"""269    ## Understanding the Math270 271    ### Why pooling always wins272 273    Two separate M/M/1 queues each running at utilization $\rho$ have mean sojourn time $W_{\text{sep}} = 1/(\mu(1-\rho))$. A pooled M/M/2 queue with the same total arrival rate has strictly lower mean sojourn time for every value of $0 < \rho < 1$. The proof uses the [Erlang-C formula](https://en.wikipedia.org/wiki/Erlang_(unit)#Erlang_C_formula), but the intuition is simpler: pooling converts two independent random processes into one, and the combined queue can exploit any idle capacity instantly. At $\rho = 0.8$, separate queues give roughly twice the mean wait of a pooled queue.274 275    ### Connection to variance reduction276 277    Think of the service delivered in a time window by two separate servers as two independent random variables $X_1$ and $X_2$. Their average $(X_1 + X_2)/2$ has variance $\sigma^2/2$, which is half the variance of either component alone. Pooling achieves something similar: by combining demand into one stream served by both servers, the system smooths out random fluctuations. The pooled queue is, in effect, averaging over both servers' idle periods instead of locking each idle period to a single lane.278 279    ### Rule of thumb280 281    At $\rho = 0.8$, separate queues produce roughly double the mean wait of a pooled queue. This factor grows as $\rho$ increases, because the $(1-\rho)$ term in the denominator amplifies any wasted capacity. The lesson: whenever you can route demand flexibly to a shared resource, do it.282    """)283    return284 285 286if __name__ == "__main__":287    app.run()288