The rule deciding who gets served next. First-come-first-served is one of several and it is a choice, not a default.
Week 1, The line starts here
Every term this course uses as though you already knew it, and the week you actually meet it.
There are twenty-three terms here, and you will meet them in roughly the order they are listed. Each one records the week it turns up in, so if a word on a lecture page is quietly doing work you cannot follow, the explanation should be here and it will be dated.
- Queue discipline
- Balking
Seeing the queue and deciding not to join it. Balkers never appear in your count, which is the first thing that will make your arrival rate wrong.
Week 1, The line starts here
- Reneging
Joining the queue and then leaving before being served. Distinct from balking, and much harder to spot from thirty metres away.
Week 1, The line starts here
- Little's LawL = λ W
Queue length equals arrival rate times time in the system. It holds for any stable queue regardless of discipline, and it lets you measure a wait you never timed.
Week 2, Little's Law
- Arrival rateλ
How many people join per unit time, averaged over a period you can state.
Week 2, Little's Law
- Stability
A queue that is neither growing without bound nor draining. Little's Law says nothing useful about an unstable one, and a backlog is an unstable one.
Week 2, Little's Law
- Utilisationρ
The fraction of capacity in use. Waiting time scales with the term it sits in, which goes to infinity as it approaches one.
Week 3, Variability is the tax
- Coefficient of variation
How uneven a set of service times is, relative to their mean. The number that separates a production line from a walk-in clinic.
Week 3, Variability is the tax
- Kingman's approximation
Waiting time as a utilisation term multiplied by a variability term. An approximation for a single-server queue, and usable if you say so.
Week 3, Variability is the tax
- Pooling
One line feeding several servers instead of one line each. Wins on mean wait and on variance at every load, and there are five real reasons not to do it.
Week 4, One line or many
- Serpentine queue
A single pooled line folded back on itself so it fits a room. The thing banks and airports changed to and supermarkets did not.
Week 4, One line or many
- Starvation
A job at the back never being served because shorter work keeps arriving in front of it. Borrowed from computing, and it happens to people as readily as to processes.
Week 5, Priority, and who pays for it
- Shortest-job-first
Serving the quickest customer next. Optimal for the mean wait, brutal for the longest job, and the most common unstated discipline at a counter.
Week 5, Priority, and who pays for it
- Triage
A priority queue that ranks people by how much the waiting will cost them, not by how badly off they are. The only widely used discipline that publishes its promises in minutes.
Week 6, Triage
- Invisible queue
A queue that publishes neither its length nor your position in it. You cannot balk from one, because leaving would be a decision made without information.
Week 7, The queues with no visible front
- Perceived wait
How long the wait felt. Reliably longer than the measured wait when the wait is unexplained, uncertain or unfair, and the gap is a finding rather than a failure of the customer.
Week 8, The felt wait
- Backpressure
Pushing the pressure back to whoever is producing work when the queue fills, rather than absorbing it in a longer line. The counter equivalent is a sign saying come back tomorrow.
Week 9, Machines that wait
- Ageing
Raising a job's priority the longer it has waited. Removes starvation without giving up shortest-job-first, and almost no human queue uses it.
Week 9, Machines that wait
- Admission control
Refusing work rather than queueing it. A feature, and weeks 5 and 6 are about who gets refused.
Week 9, Machines that wait
- Convoy effect
One slow job at the front serialising everything behind it, so throughput collapses well below capacity.
Week 10, When the queue is the hazard
- Bufferbloat
A queue growing unboundedly because somebody added memory instead of a limit. The system becomes unusable while every capacity metric still looks healthy.
Week 10, When the queue is the hazard
- Progressive crowd collapse
Density passing the threshold where individuals lose control of their footing and force travels through a crowd as a wave. A queueing failure, continuous with everything else here.
Week 10, When the queue is the hazard
- Market for position
Letting people pay to move forward. Does not remove waiting, converts it into money, and willingness to pay is not the same thing as need.
Week 11, Abolishing the queue
What is deliberately not here#
You will not find an entry for anything you could work out from the page in ten seconds, and there is nothing here for a term the course only uses once. A glossary that lists absolutely everything tends to be a glossary nobody opens twice.
There is also nothing here on queueing theory’s standard notation, meaning the A/B/C strings like M/M/1 and M/M/c. They only appear twice in week 4 and once in week 9, they are explained on the spot each time, and learning to read them fluently is not something this course is going to ask of you.