Introduction

You press the call button and wait. Somewhere above you, a small computer is making a decision about which car should come for you, and it has to make it without knowing who will press a button in the next ten seconds. That is elevator scheduling, and it is a textbook example of an online problem: the input arrives piece by piece and every decision is final before the rest of the input is known.

The simplest idea is first come, first served: take the oldest call and send a car. It is fair and it is dreadful, because the car crosses the building for one person while a dozen others are waiting on the floors it passes.

The classic fix is the elevator algorithm, known in operating systems as SCAN. A car keeps moving in one direction and stops at every floor where somebody wants to get on (going that way) or off; only when nothing remains ahead does it reverse. The variant that turns around at the last pending request instead of the end of the shaft is called LOOK. The same policy schedules the read/write arm of a hard disk: Peter Denning analysed these disk policies (FCFS, SCAN and relatives) in 1967, in his paper "Effects of Scheduling on File Memory Operations".

LOOK for one car, moving in direction d
while there are pending stops:
    if a stop exists ahead in direction d:
        move one floor in direction d
        if someone leaves here, or someone going d waits here: open doors
    else:
        reverse d

With several cars the problem grows a second layer: the dispatcher must also decide which car takes each call. Modern buildings go one step further with destination dispatch, where passengers type their floor in the lobby before entering. Schindler introduced the first practical system of this kind, Miconic 10, in 1992.

Run the Building

Below is a twelve-floor building (floor 0 is the lobby). Blue dots are people waiting to go up, orange dots people waiting to go down, and each car shows its direction and how many passengers it carries (capacity 8). Choose a traffic pattern, a policy and a number of cars, then press Play.

<!-- Controls: traffic pattern, dispatch policy, number of cars and the random seed. -->
<div class="row">
  <label>Traffic <select id="preset">
    <option value="up">Up-peak (morning)</option>
    <option value="lunch">Lunch</option>
    <option value="down">Down-peak (evening)</option>
    <option value="rand">Random</option>
  </select></label>
  <label>Policy <select id="policy">
    <option value="fcfs">First come, first served</option>
    <option value="nearest">Nearest car</option>
    <option value="collective" selected>Collective (SCAN/LOOK)</option>
    <option value="destination">Destination dispatch</option>
  </select></label>
</div>
<div class="row">
  <label>Cars <select id="cars"><option>1</option><option>2</option><option selected>3</option><option>4</option></select></label>
  <label>Seed <input id="seed" type="number" value="7" min="1" max="99999"></label>
  <button id="newseed" type="button" class="ghost">New seed</button>
  <label>Speed <select id="speed"><option value="2">x2</option><option value="5" selected>x5</option><option value="20">x20</option></select></label>
</div>
<p class="hint" id="phint"></p>
<div class="row">
  <button id="play" type="button">Play</button>
  <button id="reset" type="button" class="ghost">Reset</button>
  <button id="cmp" type="button" class="accent">Compare all policies</button>
</div>
<canvas id="cv" height="268" aria-label="A 12-floor building with elevator cars moving in shafts"></canvas>
<div class="legend"><span class="up">&#9679;</span> waiting to go up <span class="dn">&#9679;</span> waiting to go down</div>
<div class="status" id="status"></div>
<div id="out"></div>

/* Colour tokens with a dark-mode variant. */
:root { --fg:#222; --muted:#555; --bg:#fff; --line:#cdd9e3; --pane:#f1f5f9; --accent:#1d3557; --car:#457b9d; --open:#2a9d8f; --up:#2563eb; --dn:#e07a1f; --bar:#bcd0e3; --best:#0a7d33; }
@media (prefers-color-scheme: dark) {
  :root { --fg:#e6edf3; --muted:#9fb0c0; --bg:#10161d; --line:#2c3a48; --pane:#18212b; --accent:#7fb2e5; --car:#5b9bd0; --open:#3fc1b0; --up:#6ea0ff; --dn:#f0a04b; --bar:#2f4a63; --best:#5fd08a; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 2px; font-size: 14px; }
.row { display: flex; flex-wrap: wrap; gap: .45rem .7rem; align-items: center; margin: 0 0 .45rem; }
label { font-size: .82rem; color: var(--muted); display: flex; align-items: center; gap: .3rem; }
select, input { font: 600 13px system-ui, sans-serif; color: var(--fg); background: var(--pane); border: 1px solid var(--line); border-radius: 6px; padding: .3rem .4rem; max-width: 100%; }
input { width: 5.2rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid var(--accent); background: var(--accent); color: var(--bg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--accent); }
button.accent { background: var(--open); border-color: var(--open); color: #06231f; }
.hint { font-size: .8rem; color: var(--muted); margin: 0 0 .5rem; line-height: 1.4; min-height: 2.2em; }
canvas { width: 100%; height: 268px; display: block; background: var(--pane); border: 1px solid var(--line); border-radius: 8px; }
.legend { font-size: .75rem; color: var(--muted); margin: .25rem 0; }
.legend .up { color: var(--up); } .legend .dn { color: var(--dn); }
.status { font-size: .85rem; font-weight: 600; margin: .3rem 0; min-height: 1.3em; }
table { width: 100%; border-collapse: collapse; font-size: .8rem; margin-top: .4rem; }
caption { text-align: left; font-size: .78rem; color: var(--muted); padding-bottom: .3rem; }
th, td { text-align: left; padding: .3rem .35rem; border-bottom: 1px solid var(--line); }
th { color: var(--muted); font-weight: 600; }
td.m { position: relative; min-width: 64px; }
td.m .bar { position: absolute; left: 0; top: 3px; bottom: 3px; background: var(--bar); border-radius: 3px; }
td.m span { position: relative; font-variant-numeric: tabular-nums; padding-left: 3px; }
td.best span { color: var(--best); font-weight: 700; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Building and simulation parameters (times in seconds).
const FLOORS = 12, CAP = 8, T_FLOOR = 2, T_DWELL = 3, DURATION = 600, T_MAX = 12000;
// Traffic presets: arrivals per minute and the mix [from lobby, to lobby, between floors].
const PRESETS = {
  up:    { rate: 18, mix: [0.9, 0, 0.1] },
  lunch: { rate: 14, mix: [0.35, 0.35, 0.3] },
  down:  { rate: 18, mix: [0, 0.9, 0.1] },
  rand:  { rate: 12, mix: [0, 0, 1] }
};
const POLICIES = ['fcfs', 'nearest', 'collective', 'destination'];

// Small seeded random generator (mulberry32), so every policy sees identical traffic.
function rng(seed) {
  let a = seed >>> 0;
  return function () {
    a = (a + 0x6D2B79F5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

// Poisson arrivals over ten minutes with the chosen origin/destination mix.
function makeTraffic(name, seed) {
  const P = PRESETS[name], r = rng(seed), out = [];
  let t = 0;
  for (;;) {
    t += -Math.log(1 - r()) * 60 / P.rate;
    if (t >= DURATION) break;
    const u = r();
    let from, to;
    if (u < P.mix[0]) { from = 0; to = 1 + Math.floor(r() * (FLOORS - 1)); }
    else if (u < P.mix[0] + P.mix[1]) { to = 0; from = 1 + Math.floor(r() * (FLOORS - 1)); }
    else { from = Math.floor(r() * FLOORS); do { to = Math.floor(r() * FLOORS); } while (to === from); }
    out.push({ id: out.length, t: Math.ceil(t), from: from, to: to, dir: to > from ? 1 : -1, board: -1, drop: -1 });
  }
  return out;
}

function mkCar(id) {
  return { id: id, floor: 0, dir: 0, mode: 0, prog: 0, timer: 0, onboard: [], queue: [] };
}

// Is there a stop strictly beyond this floor in the given direction?
function ahead(car, f, dir) {
  for (const p of car.onboard) if ((p.to - f) * dir > 0) return true;
  for (const p of car.queue) if ((p.from - f) * dir > 0) return true;
  return false;
}

// Stop if someone leaves here, or someone going our way (or nobody beyond) waits here.
function wantStop(car) {
  const f = car.floor;
  if (car.onboard.some(p => p.to === f)) return true;
  if (car.onboard.length >= CAP) return false;
  const more = ahead(car, f, car.dir);
  return car.queue.some(p => p.from === f && (car.dir === 0 || p.dir === car.dir || !more));
}

function doStop(car, now) {
  const f = car.floor;
  let n = 0;
  car.onboard = car.onboard.filter(p => { if (p.to === f) { p.drop = now; n++; return false; } return true; });
  const more = ahead(car, f, car.dir);
  const rest = [];
  for (const p of car.queue) {
    if (p.from === f && car.onboard.length < CAP && (car.dir === 0 || p.dir === car.dir || !more)) {
      p.board = now; car.onboard.push(p); n++;
    } else rest.push(p);
  }
  car.queue = rest;
  car.mode = 2;
  car.timer = T_DWELL + Math.ceil(n / 2);
}

function decide(car, now) {
  if (wantStop(car)) { doStop(car, now); return; }
  const f = car.floor, tg = [];
  car.onboard.forEach(p => tg.push(p.to));
  car.queue.forEach(p => tg.push(p.from));
  const up = tg.some(x => x > f), dn = tg.some(x => x < f);
  if (car.dir > 0 && !up) car.dir = dn ? -1 : 0;
  if (car.dir < 0 && !dn) car.dir = up ? 1 : 0;
  if (car.dir === 0) {
    if (up && dn) {
      let du = 99, dd = 99;
      tg.forEach(x => { if (x > f) du = Math.min(du, x - f); if (x < f) dd = Math.min(dd, f - x); });
      car.dir = du <= dd ? 1 : -1;
    } else car.dir = up ? 1 : dn ? -1 : 0;
  }
  if (car.dir === 0) { car.mode = 0; return; }
  car.mode = 1; car.prog = 0;
}

function stepCar(car, now) {
  if (car.mode === 2) { car.timer--; if (car.timer <= 0) decide(car, now); }
  else if (car.mode === 1) {
    car.prog++;
    if (car.prog >= T_FLOOR) { car.floor += car.dir; car.prog = 0; decide(car, now); }
  } else decide(car, now);
}

// Forecast: replay a copy of the car on its current list of passengers and record the times.
function plan(car, extra, now, ghost) {
  const map = new Map();
  const cp = p => { const q = Object.assign({}, p); map.set(p.id, q); return q; };
  const c = {
    id: car.id, floor: car.floor, dir: car.dir, mode: car.mode, prog: car.prog, timer: car.timer,
    onboard: car.onboard.map(cp),
    queue: car.queue.concat(extra ? [extra] : []).map(cp)
  };
  if (ghost) c.queue.forEach(q => { q.to = Math.max(0, Math.min(FLOORS - 1, q.from + 3 * q.dir)); });
  let t = now, guard = 0;
  while ((c.onboard.length || c.queue.length) && guard++ < 600) { t++; stepCar(c, t); }
  return map;
}

function assign(S, p) {
  const cars = S.cars;
  let best = 0, bc = Infinity;
  cars.forEach((car, i) => {
    let cost;
    if (S.policy === 'nearest') {
      cost = Math.abs(car.floor - p.from) * 10 + car.queue.length + car.onboard.length;
    } else if (S.policy === 'collective') {
      // Collective: choose the car that minimises waiting time, destinations unknown (assume about 3 floors).
      const a = plan(car, null, S.t, true), b = plan(car, p, S.t, true);
      cost = b.get(p.id).board - S.t;
      car.queue.forEach(q => { cost += b.get(q.id).board - a.get(q.id).board; });
    } else {
      // Destination dispatch: choose the car that adds least to the total journey time of everyone.
      const a = plan(car, null, S.t, false), b = plan(car, p, S.t, false);
      cost = b.get(p.id).drop - S.t;
      car.queue.concat(car.onboard).forEach(q => { cost += b.get(q.id).drop - a.get(q.id).drop; });
    }
    cost += i * 1e-6;
    if (cost < bc) { bc = cost; best = i; }
  });
  cars[best].queue.push(p);
}

function makeSim(traffic, policy, nCars) {
  const cars = [];
  for (let i = 0; i < nCars; i++) cars.push(mkCar(i));
  return { t: 0, policy: policy, cars: cars, all: traffic.map(p => Object.assign({}, p)), next: 0, waiting: [], done: 0 };
}

function tick(S) {
  S.t++;
  while (S.next < S.all.length && S.all[S.next].t <= S.t) {
    const p = S.all[S.next++];
    if (S.policy === 'fcfs') S.waiting.push(p); else assign(S, p);
  }
  if (S.policy === 'fcfs') {
    while (S.waiting.length) {
      const p = S.waiting[0];
      let best = null;
      for (const car of S.cars) {
        if (car.queue.length || car.onboard.length) continue;
        if (!best || Math.abs(car.floor - p.from) < Math.abs(best.floor - p.from)) best = car;
      }
      if (!best) break;
      best.queue.push(S.waiting.shift());
    }
  }
  for (const car of S.cars) stepCar(car, S.t);
  S.done = 0;
  for (const p of S.all) if (p.drop >= 0) S.done++;
}

function finished(S) { return S.next >= S.all.length && S.done >= S.all.length; }

function runAll(traffic, policy, nCars) {
  const S = makeSim(traffic, policy, nCars);
  while (!finished(S) && S.t < T_MAX) tick(S);
  return S;
}

function stats(S) {
  let w = 0, j = 0, mx = 0, n = 0;
  for (const p of S.all) if (p.drop >= 0) { n++; w += p.board - p.t; j += p.drop - p.t; mx = Math.max(mx, p.board - p.t); }
  return { n: n, total: S.all.length, wait: n ? w / n : 0, journey: n ? j / n : 0, max: mx, end: S.t };
}

// User interface: drawing, controls and the comparison table.
const $ = id => document.getElementById(id);
const NAMES = { fcfs: "First come, first served", nearest: "Nearest car", collective: "Collective (SCAN/LOOK)", destination: "Destination dispatch" };
const HINTS = { fcfs: "One passenger per trip: the oldest waiting passenger is given to a free car, which carries only that person. No sharing at all.", nearest: "Each call is given to the car that is closest right now; every car then sweeps up and down serving its own list.", collective: "Calls go to the car that can reach them soonest. Cars sweep in one direction, stopping for everyone going that way (LOOK). Destinations are unknown until people board.", destination: "People key in their floor in the lobby, so the dispatcher knows every destination and picks the car that adds least to everyone's journey time." };
let S = null, timer = null, playing = false, acc = 0;

function params() {
  return { preset: $('preset').value, policy: $('policy').value, n: +$('cars').value,
           seed: Math.max(1, Math.floor(+$('seed').value) || 1), speed: +$('speed').value };
}

function waitingAt() {
  const w = [];
  for (let f = 0; f < FLOORS; f++) w.push([0, 0]);
  for (const p of S.all) if (p.t <= S.t && p.board < 0) w[p.from][p.dir > 0 ? 0 : 1]++;
  return w;
}

function draw() {
  const cv = $('cv'), g = cv.getContext('2d');
  const W = cv.clientWidth || 340, H = 268;
  cv.width = W; cv.height = H;
  const css = n => getComputedStyle(document.documentElement).getPropertyValue(n).trim();
  const fg = css('--muted'), line = css('--line'), car = css('--car'), open = css('--open'), up = css('--up'), dn = css('--dn');
  const RH = (H - 4) / FLOORS, x0 = 100, n = S.cars.length, sw = (W - 6 - x0) / n;
  const yTop = f => 2 + (FLOORS - 1 - f) * RH;
  g.font = '11px system-ui, sans-serif'; g.textBaseline = 'middle';
  const w = waitingAt();
  for (let f = 0; f < FLOORS; f++) {
    const y = yTop(f);
    g.strokeStyle = line; g.beginPath(); g.moveTo(0, y + RH); g.lineTo(W, y + RH); g.stroke();
    g.fillStyle = fg; g.textAlign = 'right'; g.fillText(String(f), 20, y + RH / 2);
    let cx = 28;
    for (let k = 0; k < 2; k++) {
      const c = w[f][k];
      g.fillStyle = k === 0 ? up : dn;
      for (let i = 0; i < Math.min(c, 4); i++) { g.beginPath(); g.arc(cx + 4, y + RH / 2, 3.2, 0, 6.3); g.fill(); cx += 8; }
      if (c > 4) { g.textAlign = 'left'; g.fillText('+' + (c - 4), cx, y + RH / 2); cx += 18; }
      cx += 4;
    }
  }
  for (let i = 0; i < n; i++) {
    const c = S.cars[i], sx = x0 + i * sw;
    g.fillStyle = css('--bar'); g.globalAlpha = 0.35; g.fillRect(sx + 2, 2, sw - 4, H - 4); g.globalAlpha = 1;
    const pos = c.floor + (c.mode === 1 ? c.dir * c.prog / T_FLOOR : 0);
    const cw = Math.min(sw - 8, 46), ch = RH - 3;
    const cx = sx + (sw - cw) / 2, cy = yTop(pos) + 1.5;
    g.fillStyle = c.mode === 2 ? open : car;
    g.fillRect(cx, cy, cw, ch);
    g.fillStyle = '#fff'; g.textAlign = 'center'; g.font = 'bold 11px system-ui, sans-serif';
    g.fillText((c.dir > 0 ? '▲' : c.dir < 0 ? '▼' : '·') + c.onboard.length, cx + cw / 2, cy + ch / 2);
    g.font = '11px system-ui, sans-serif';
  }
}

function fmt1(v) { return v.toFixed(1); }

function updStatus() {
  let waitN = 0;
  for (const p of S.all) if (p.t <= S.t && p.board < 0) waitN++;
  let txt = fmt("t = %t% s - waiting: %w% - delivered: %d% of %n%", { t: S.t, w: waitN, d: S.done, n: S.all.length });
  if (finished(S)) {
    const s = stats(S);
    txt += ' ' + fmt("Finished: average wait %w% s, average journey %j% s, longest wait %m% s.", { w: fmt1(s.wait), j: fmt1(s.journey), m: s.max });
  }
  $('status').textContent = txt;
}

function stopTimer() { playing = false; if (timer) clearInterval(timer); timer = null; $('play').textContent = "Play"; }

function reset() {
  stopTimer();
  const q = params();
  S = makeSim(makeTraffic(q.preset, q.seed), q.policy, q.n);
  $('out').innerHTML = '';
  $('phint').textContent = HINTS[q.policy];
  draw(); updStatus();
}

function play() {
  if (playing) { stopTimer(); return; }
  if (finished(S) || S.t >= T_MAX) reset();
  playing = true; $('play').textContent = "Pause";
  timer = setInterval(() => {
    acc += params().speed * 0.05;
    while (acc >= 1) { acc -= 1; if (!finished(S) && S.t < T_MAX) tick(S); }
    draw(); updStatus();
    if (finished(S) || S.t >= T_MAX) stopTimer();
  }, 50);
}

// Run every policy on the same traffic and tabulate the three metrics.
function compare() {
  stopTimer();
  const q = params(), tr = makeTraffic(q.preset, q.seed);
  const rows = POLICIES.map(p => ({ p: p, s: stats(runAll(tr, p, q.n)) }));
  const mx = k => Math.max.apply(null, rows.map(r => r.s[k]));
  const mn = k => Math.min.apply(null, rows.map(r => r.s[k]));
  const cell = (r, k) => {
    const v = r.s[k], pct = mx(k) > 0 ? Math.round(100 * v / mx(k)) : 0;
    return '<td class="m' + (v === mn(k) ? ' best' : '') + '"><div class="bar" style="width:' + pct + '%"></div><span>' + fmt1(v) + ' s</span></td>';
  };
  let h = '<table><caption>' + fmt("Same traffic (%n% passengers, seed %seed%) and %c% car(s) under every policy. Bold green = best in column.", { n: tr.length, c: q.n, seed: q.seed }) + '</caption>';
  h += '<tr><th>Policy</th><th>Avg wait</th><th>Avg journey</th><th>Max wait</th></tr>';
  for (const r of rows) h += '<tr><td>' + NAMES[r.p] + '</td>' + cell(r, 'wait') + cell(r, 'journey') + cell(r, 'max') + '</tr>';
  $('out').innerHTML = h + '</table>';
}

['preset', 'policy', 'cars', 'seed'].forEach(id => $(id).addEventListener('change', reset));
$('newseed').addEventListener('click', () => { $('seed').value = 1 + Math.floor(Math.random() * 9999); reset(); });
$('play').addEventListener('click', play);
$('reset').addEventListener('click', reset);
$('cmp').addEventListener('click', compare);
window.addEventListener('resize', () => { if (S) draw(); });
reset();
Result
Console

The real experiment is the button Compare all policies. It replays the same passengers, generated from the seed you see, under all four policies, and reports three numbers: the average wait (call to boarding), the average journey (call to arrival) and the longest wait anyone endured. Try these:

  • Up-peak with one car: the queue explodes whatever the policy. Add cars and watch the gap between FCFS and the rest.
  • Up-peak with three or four cars: compare collective with destination dispatch. Destination dispatch packs people with similar floors into the same car, so cars make fewer stops and the journey column improves.
  • Random traffic: the differences shrink, because no single flow dominates.
  • Change the seed a few times. A single run can mislead; a pattern that survives many seeds is real.

The Real Complexity

Single car, no capacity limit. Let the building have FF floors, let a car take tft_f seconds per floor and tdt_d seconds per stop. One full LOOK cycle (up, then down) covers at most 2(F−1)2(F-1) floors and makes at most FF stops in each direction, so

Tcycle≤2(F−1) tf+2F td.T_{\text{cycle}} \le 2(F-1)\,t_f + 2F\,t_d .

Every request is served within one cycle, so the waiting time is bounded by TcycleT_{\text{cycle}} and no request starves. That guarantee is exactly what FCFS-by-proximity policies such as shortest-seek-first lack. The price is variance: a call placed just after the car has passed waits almost a full cycle, which is why a floor at the far end can be treated worse than the middle.

How many stops? If NN passengers board at the lobby and each picks a destination uniformly among the F−1F-1 upper floors, the expected number of distinct floors where the car must stop is

S=(F−1)[1−(1−1F−1)N].S = (F-1)\left[1 - \left(1 - \frac{1}{F-1}\right)^{N}\right].

For F=12F = 12 and a full car of N=8N = 8 this gives S≈5.9S \approx 5.9 stops. Destination dispatch attacks this number directly: by grouping passengers with nearby destinations in one car, it lowers the stops per trip.

Complexity of dispatching itself. FCFS and nearest-car need O(k)O(k) work per call for kk cars. The cost-based dispatchers in the simulator replay each car's plan to predict times, which costs roughly O(k⋅H)O(k \cdot H) per call for a forecast horizon of HH seconds, in O(k+m)O(k + m) memory for mm active passengers.

Why optimal is out of reach. Scheduling a vehicle to carry people between given pickup and drop-off points is the dial-a-ride problem, which contains the travelling salesman problem and is NP-hard in general. In real life it is also online: the future requests are unknown, so the standard yardstick is competitive analysis, which compares an online policy with an offline optimum that sees the whole sequence in advance. Elevator control has been studied in exactly this setting (Ascheuer, Krumke and Rambau, 2000, for online dial-a-ride; Friese and Rambau, 2006, for multi-elevator systems).

Wait versus journey. The two metrics pull in different directions. Minimising the average wait sends the nearest car and boards as many people as possible; minimising journey time (wait plus ride) avoids stops that add to everyone's ride. Destination dispatch can optimise the second because it knows destinations before boarding. Which metric matters depends on the building: a lobby full of angry people is not the same problem as a stuffy cabin.

Where It Matters

Disk drives. The elevator algorithm is the ancestor of the sweep-style disk schedulers taught in every operating-systems course (SCAN, C-SCAN, LOOK). See the broader family in CPU scheduling and scheduling.

Traffic patterns. Engineers classify building traffic into up-peak (morning: almost everyone leaves the lobby), down-peak (evening: almost everyone goes to the lobby), lunch (heavy two-way flow) and interfloor (random trips between floors). A controller tuned for one can perform badly under another, which is why modern group controllers switch strategy by traffic mode.

Destination dispatch. Schindler's Miconic 10, introduced in 1992, was the first practical destination control system. Passengers key their floor in the lobby, and the display tells them which car to take. Grouping people by destination reduces intermediate stops, which most helps in up-peak traffic; manufacturers report large journey-time gains, but these depend on the building and the traffic.

Learning controllers. Elevator dispatching became a showcase for reinforcement learning. In 1996 (NIPS 8) Robert Crites and Andrew Barto trained a team of agents with a form of Q-learning in simulation, and their controller outperformed the best heuristic algorithms they compared against. The decision process behind it is a Markov decision process with a huge state space.

Online decisions in general. The tension between acting now and learning more later also appears in ski rental, the simplest online problem with a provable competitive ratio.

Conclusion

Elevator scheduling is a small problem that carries a big idea. A sweep policy like SCAN or LOOK gives a clean guarantee (nobody waits more than one cycle) with trivial computation. Adding cars, forecasts and destination information buys real improvements in journey time, but never perfection: the optimum would require knowing who walks into the lobby next.

So the next time the lift arrives just as the doors of the other one close, remember that nobody can promise you better than an online guess. A good policy is one whose guesses are rarely bad, and the simulator above lets you see how much a smarter guess is worth.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/elevator-scheduling/Content licensed under CC BY-NC 4.0.