A queue (待ち行列), in the sense of a waiting line, is a model that treats a line waiting its turn for service in numerical terms, based on how arrivals come in and how they are served.
Arrive
Wait in line
Served at counter
Leave
When service ends they leave, and the next in line moves up to the counter.
4 / 4
Both the gaps between arrivals and the time needed to serve each one vary, so the average wait and line length are estimated with probability and statistics. The basic form has a single counter that serves arrivals first come, first served. The share of time the counter is busy is called utilization, and it is found by dividing the average service time by the average interarrival time.
AnalogyLike taking a number at a clinic's front desk and sitting in the waiting room until it is called. On busy days, both the crowd in the waiting room and the wait itself grow.
How to rememberQueuing theory began with research into how congested telephone exchange lines would get.
Exam points
Mix-upAs utilization (利用率) rises, waiting time does not creep up in proportion. As utilization approaches 1, waiting time shoots up.
Mix-upThe queuing model (待ち行列) is a tool for estimating congestion, and its purpose differs from the queue (キュー) data structure, which takes data out in the order it was put in.
An optimization problem (最適化問題) seeks, among the solutions that meet the conditions that must hold (constraints), the one (optimal solution) that makes a measure of goodness (objective function), such as maximum profit or minimum cost, as good as it can be.
What to decide
Constraints
Objective function
Optimal solution
Among the solutions that meet every constraint, the one with the largest total profit is the optimal solution.
4 / 4
When there are only a few candidate solutions, listing them all and comparing their objective function values reveals the optimal solution. When there are many, methods such as linear programming express the conditions and the goal as equations and solve them. Deciding the order in which to carry out jobs, or the order in which to visit several locations, are also examples of optimization problems.
AnalogyLike choosing what to pack so that your suitcase carries as many useful items as it can hold.
How to rememberThe English word optimization comes from the Latin optimus, meaning “best”. Whether the aim is a maximum or a minimum, both count as the “best”.
Exam points
ExamIn an optimization problem (最適化問題), write the constraints (制約条件) a solution must satisfy separately from the objective function (目的関数) to be minimized or maximized. Derive the constraints from the problem's premises, because adding a condition the premises do not state can push the true optimal solution (最適解) out of the candidates.
ExamWhen the order of stops along a route can be chosen freely, the shortest time comes from totaling the travel time for each candidate order and picking the smallest. Any order that includes an impassable leg is dropped from the candidates.
ExamTo order jobs that use two machines in the same sequence so that everything finishes soonest, look at the shortest usage time: if it is on the first machine, put that job at the front, and if it is on the second, put it at the end, then repeat with the rest (Johnson's rule, ジョンソン法).
An estimate of congestion (average wait and line length)
The best solution within the conditions
Core idea
Treat the variability of arrivals and service with probability
Build it from constraints and an objective function kept separate
Key points
A queuing model estimates the average wait and line length from the variability of arrivals and service.
With a single counter, utilization is the average service time divided by the average interarrival time, and as it nears 1 the waiting time climbs steeply.
An optimization problem searches, among solutions that meet the constraints, for the optimal solution with the best objective function value.
An optimization problem with few candidates can be solved by computing every candidate's value and comparing them.