System Design LLDCase Studies

Elevator System Design

LevelAdvanced

Duration120 mins

TopicCase Studies

4 / 6

Scheduling Algorithms: FCFS and SCAN

The Optimization Challenge

With entities defined and state machines designed, we now face the most intellectually challenging aspect of elevator system design: scheduling algorithms. The scheduling algorithm determines which elevator serves which request and in what order—decisions that dramatically impact user experience.

A poorly chosen algorithm can lead to:

Starvation: Some passengers wait indefinitely
Inefficiency: Elevators travel more distance than necessary
Poor fairness: Some floors consistently get worse service
Convoy effect: All elevators cluster together

Conversely, a well-designed algorithm minimizes average wait time, ensures fairness, and makes efficient use of elevator capacity. This is where LLD meets algorithm design.

What You Will Master

By the end of this page, you will be able to:

• Analyze FCFS (First-Come-First-Served) and understand its limitations • Implement SCAN (Elevator Algorithm) and its variants (LOOK, C-SCAN) • Apply the Strategy Pattern to make algorithms interchangeable • Evaluate algorithm trade-offs for different traffic patterns • Design dispatch logic for multi-elevator systems

FCFS: First-Come-First-Served

First-Come-First-Served (FCFS) is the simplest scheduling algorithm: requests are served in the exact order they arrive. It's the algorithm you'd implement if you weren't thinking about optimization at all.

How FCFS Works:

Maintain a queue of pending requests
When elevator becomes available, take the oldest request
Go to that floor, serve the request
Repeat

Example Scenario:

Elevator at floor 5. Requests arrive in order: Floor 2, Floor 15, Floor 3, Floor 14.

FCFS path: 5 → 2 → 15 → 3 → 14

Total floors traveled: 3 + 13 + 12 + 11 = 39 floors

FCFS Implementation
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class FCFSScheduler implements SchedulingStrategy {
  private requestQueue: Request[] = [];
  
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    // For single elevator: simply return the one elevator
    // For multiple elevators: find the idle or soonest-available one
    const available = elevators.filter(e => 
      e.getState() !== ElevatorState.MAINTENANCE
    );
    
    if (available.length === 0) return null;
    
    // Prefer idle elevators
    const idle = available.find(e => e.getState() === ElevatorState.IDLE);
    if (idle) return idle;
    
    // Otherwise, assign to elevator with shortest queue (basic fairness)
    return available.reduce((best, current) => 
      current.getQueueLength() < best.getQueueLength() ? current : best
    );
  }
  
  getNextDestination(currentFloor: Floor, queue: Request[]): Request | null {
    // FCFS: return the oldest request (first in queue)
    return queue[0] ?? null;
  }
  
  addRequest(request: Request): void {
    this.requestQueue.push(request);
  }
  
  orderDestinations(
    currentFloor: number,
    currentDirection: Direction,
    requests: Request[]
  ): Request[] {
    // FCFS doesn't reorder - keep original order
    return [...requests];
  }
}

Analysis of FCFS:

FCFS Advantages

•Simple to implement: Just a queue
•Fair in arrival order: First to request = first served
•No starvation: Every request eventually served
•Predictable: Easy to reason about

FCFS Disadvantages

•Highly inefficient: Constant direction changes
•Long seek times: Elevator oscillates unnecessarily
•Poor throughput: Serves fewer requests per hour
•Ignores position: Nearby requests have no priority

FCFS is Almost Never Used

Real elevator systems never use pure FCFS. It's presented here for educational purposes—to understand why we need smarter algorithms. In the example above, FCFS traveled 39 floors. We'll see SCAN reduce this dramatically.

SCAN: The Elevator Algorithm

SCAN, also known as the Elevator Algorithm, mimics how physical elevators have always worked: travel in one direction serving all requests along the way, then reverse direction.

How SCAN Works:

Travel in the current direction
Stop at each floor that has a request in this direction
Continue to the end of the building (or last request)
Reverse direction
Repeat

Example Scenario (Same as FCFS):

Elevator at floor 5, traveling UP. Requests: Floor 2, Floor 15, Floor 3, Floor 14.

SCAN path: 5 → 14 → 15 (reach top) → 19 (top) → 3 → 2

Actually, optimized SCAN: 5 → 14 → 15 → reverse → 3 → 2

Total: 10 + 1 + 12 + 1 = 24 floors (vs FCFS's 39)

That's 38% less travel!

Converting Mermaid diagram...

SCAN Algorithm Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class SCANScheduler implements SchedulingStrategy {
  
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    const available = elevators.filter(e => 
      e.getState() !== ElevatorState.MAINTENANCE
    );
    
    if (available.length === 0) return null;
    
    // Find elevator that can serve this request most efficiently
    let bestElevator: Elevator | null = null;
    let bestScore = Infinity;
    
    for (const elevator of available) {
      const score = this.calculateScore(elevator, request);
      if (score < bestScore) {
        bestScore = score;
        bestElevator = elevator;
      }
    }
    
    return bestElevator;
  }
  
  private calculateScore(elevator: Elevator, request: Request): number {
    const currentFloor = elevator.getCurrentFloor().getFloorNumber();
    const targetFloor = request.floor.getFloorNumber();
    const direction = elevator.getDirection();
    
    // If elevator is idle, score is just distance
    if (direction === Direction.IDLE) {
      return Math.abs(targetFloor - currentFloor);
    }
    
    const isAbove = targetFloor > currentFloor;
    const isBelow = targetFloor < currentFloor;
    
    // If request is in current direction of travel, low score
    if (direction === Direction.UP && isAbove) {
      return targetFloor - currentFloor;
    }
    if (direction === Direction.DOWN && isBelow) {
      return currentFloor - targetFloor;
    }
    
    // Request is behind or requires direction change
    // Higher score - will be served after current direction completes
    const maxFloor = 19; // Building height
    
    if (direction === Direction.UP) {
      // Must go to top, then come back down
      return (maxFloor - currentFloor) + (maxFloor - targetFloor);
    } else {
      // Must go to bottom, then come back up
      return currentFloor + targetFloor;
    }
  }
  
  orderDestinations(
    currentFloor: number,
    currentDirection: Direction,
    requests: Request[]
  ): Request[] {
    if (requests.length === 0) return [];
    
    // Separate requests by direction relative to current floor
    const above = requests.filter(r => 
      r.floor.getFloorNumber() > currentFloor
    );
    const below = requests.filter(r => 
      r.floor.getFloorNumber() < currentFloor
    );
    const same = requests.filter(r => 
      r.floor.getFloorNumber() === currentFloor
    );
    
    // Sort each group
    above.sort((a, b) => 
      a.floor.getFloorNumber() - b.floor.getFloorNumber()
    );
    below.sort((a, b) => 
      b.floor.getFloorNumber() - a.floor.getFloorNumber()
    );
    
    // SCAN order based on current direction
    if (currentDirection === Direction.UP || currentDirection === Direction.IDLE) {
      // Go up first, then down
      return [...same, ...above, ...below.reverse()];
    } else {
      // Go down first, then up
      return [...same, ...below, ...above.reverse()];
    }
  }
  
  getNextDestination(currentFloor: Floor, queue: Request[]): Request | null {
    // Queue is already ordered by orderDestinations
    return queue[0] ?? null;
  }
}

SCAN Variants: LOOK and C-SCAN

The basic SCAN algorithm can be improved with variants that address specific inefficiencies.

LOOK Algorithm:

SCAN always travels to the end of the building before reversing. LOOK is smarter—it only goes as far as the last request in the current direction, then reverses immediately.

Example:

Building has 20 floors. Elevator at floor 5, going UP. Requests at floors 8, 12.

SCAN: 5 → 8 → 12 → 19 (top) → reverse
LOOK: 5 → 8 → 12 → reverse

LOOK saves 7 floors of unnecessary travel!

LOOK Algorithm
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class LOOKScheduler extends SCANScheduler {
  
  orderDestinations(
    currentFloor: number,
    currentDirection: Direction,
    requests: Request[]
  ): Request[] {
    if (requests.length === 0) return [];
    
    const above = requests
      .filter(r => r.floor.getFloorNumber() > currentFloor)
      .sort((a, b) => a.floor.getFloorNumber() - b.floor.getFloorNumber());
    
    const below = requests
      .filter(r => r.floor.getFloorNumber() < currentFloor)
      .sort((a, b) => b.floor.getFloorNumber() - a.floor.getFloorNumber());
    
    const same = requests.filter(r => 
      r.floor.getFloorNumber() === currentFloor
    );
    
    // LOOK: Only go as far as the furthest request in current direction
    // Then immediately reverse (unlike SCAN which goes to building end)
    if (currentDirection === Direction.UP || currentDirection === Direction.IDLE) {
      // Serve all above, then all below (closest first when going down)
      return [...same, ...above, ...below];
    } else {
      return [...same, ...below, ...above];
    }
  }
  
  // Override score calculation for tighter estimates
  protected calculateScore(elevator: Elevator, request: Request): number {
    const currentFloor = elevator.getCurrentFloor().getFloorNumber();
    const targetFloor = request.floor.getFloorNumber();
    const direction = elevator.getDirection();
    const queue = elevator.getDestinationQueue();
    
    if (direction === Direction.IDLE) {
      return Math.abs(targetFloor - currentFloor);
    }
    
    // Find the furthest floor in current direction
    const floorsInDirection = queue
      .map(r => r.floor.getFloorNumber())
      .filter(f => direction === Direction.UP ? f > currentFloor : f < currentFloor);
    
    const furthest = direction === Direction.UP
      ? Math.max(...floorsInDirection, currentFloor)
      : Math.min(...floorsInDirection, currentFloor);
    
    const isInDirection = direction === Direction.UP
      ? targetFloor > currentFloor
      : targetFloor < currentFloor;
    
    if (isInDirection) {
      return Math.abs(targetFloor - currentFloor);
    }
    
    // Must complete current direction, then reverse
    const distanceToEnd = Math.abs(furthest - currentFloor);
    const distanceFromEndToTarget = Math.abs(furthest - targetFloor);
    return distanceToEnd + distanceFromEndToTarget;
  }
}

C-SCAN (Circular SCAN):

C-SCAN addresses fairness concerns with SCAN. In basic SCAN, floors near the extremes get served twice as often (once going up, once going down). C-SCAN provides more uniform wait times.

How C-SCAN Works:

Travel in one direction only (e.g., always UP for serving)
When reaching the top, immediately return to the bottom WITHOUT serving
Resume serving from the bottom going UP

This treats the floors as a circular list, ensuring every floor has equal priority.

Algorithm Comparison
Algorithm	Seek Behavior	Fairness	Efficiency	Best For
FCFS	Random (order of arrival)	By arrival time	Poor	Never (educational only)
SCAN	Sweep end-to-end	Moderate (favors middle)	Good	General buildings
LOOK	Sweep to last request	Moderate	Very Good	Most real elevators
C-SCAN	Circular sweep	Excellent (uniform)	Good	High-traffic buildings
C-LOOK	Circular to last request	Very Good	Excellent	Best overall

Real-World Algorithm Choice

Most modern elevator systems use LOOK or C-LOOK with additional heuristics. Pure algorithms are starting points—production systems add logic for rush hours, VIP service, energy efficiency, and group coordination. The Strategy Pattern makes these enhancements plug-and-play.

Multi-Elevator Dispatch Strategies

With multiple elevators, scheduling becomes two-dimensional:

Elevator Selection: Which elevator should handle a new hall call?
Request Ordering: What order should that elevator visit its destinations?

We've covered ordering (SCAN/LOOK). Now let's focus on dispatch strategies—selecting the best elevator for each request.

Dispatch Strategy Goals:

Minimize wait time for the requesting passenger
Balance load across all elevators
Avoid convoy effect (all elevators clustered together)
Consider future requests (anticipation)

Common Dispatch Strategies

•Nearest Elevator: Assign to the closest physically idle elevator
•Shortest Queue: Assign to elevator with fewest pending requests
•Earliest Arrival: Estimate arrival time; pick the elevator that arrives first
•Sector/Zone: Dedicate specific elevators to floor ranges
•Traffic-Adaptive: Adjust strategy based on current traffic patterns

Multi-Elevator Dispatch
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
interface DispatchStrategy {
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null;
}
 
// Strategy 1: Nearest Idle Elevator
class NearestIdleDispatch implements DispatchStrategy {
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    const targetFloor = request.floor.getFloorNumber();
    
    // Filter to available elevators
    const available = elevators.filter(e => 
      e.getState() !== ElevatorState.MAINTENANCE
    );
    
    // Prefer idle elevators, find nearest
    const idle = available.filter(e => e.getState() === ElevatorState.IDLE);
    
    if (idle.length > 0) {
      return idle.reduce((nearest, current) => {
        const nearestDist = Math.abs(
          nearest.getCurrentFloor().getFloorNumber() - targetFloor
        );
        const currentDist = Math.abs(
          current.getCurrentFloor().getFloorNumber() - targetFloor
        );
        return currentDist < nearestDist ? current : nearest;
      });
    }
    
    // No idle elevators, assign to one with shortest queue
    return this.shortestQueueFallback(available);
  }
  
  private shortestQueueFallback(elevators: Elevator[]): Elevator | null {
    if (elevators.length === 0) return null;
    return elevators.reduce((best, current) =>
      current.getQueueLength() < best.getQueueLength() ? current : best
    );
  }
}
 
// Strategy 2: Earliest Arrival Time
class EarliestArrivalDispatch implements DispatchStrategy {
  private readonly floorTravelTime: number = 2000; // ms per floor
  private readonly doorOperationTime: number = 5000; // ms per stop
  
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    const available = elevators.filter(e => 
      e.getState() !== ElevatorState.MAINTENANCE
    );
    
    if (available.length === 0) return null;
    
    let bestElevator: Elevator | null = null;
    let shortestTime = Infinity;
    
    for (const elevator of available) {
      const arrivalTime = this.estimateArrivalTime(elevator, request);
      if (arrivalTime < shortestTime) {
        shortestTime = arrivalTime;
        bestElevator = elevator;
      }
    }
    
    return bestElevator;
  }
  
  private estimateArrivalTime(elevator: Elevator, request: Request): number {
    const currentFloor = elevator.getCurrentFloor().getFloorNumber();
    const targetFloor = request.floor.getFloorNumber();
    const direction = elevator.getDirection();
    const queue = elevator.getDestinationQueue();
    
    if (direction === Direction.IDLE) {
      // Direct travel
      return Math.abs(targetFloor - currentFloor) * this.floorTravelTime;
    }
    
    // Count stops between current position and target
    let floorsToTravel = 0;
    let stopsOnWay = 0;
    
    if (this.isOnTheWay(currentFloor, targetFloor, direction, queue)) {
      // Target is in current direction, count intermediate stops
      const intermediateStops = queue.filter(r => {
        const f = r.floor.getFloorNumber();
        if (direction === Direction.UP) {
          return f > currentFloor && f < targetFloor;
        } else {
          return f < currentFloor && f > targetFloor;
        }
      });
      
      floorsToTravel = Math.abs(targetFloor - currentFloor);
      stopsOnWay = intermediateStops.length;
    } else {
      // Must complete current sweep first
      const furthestInDirection = this.getFurthestFloor(
        currentFloor, direction, queue
      );
      floorsToTravel = Math.abs(furthestInDirection - currentFloor) +
                       Math.abs(furthestInDirection - targetFloor);
      stopsOnWay = queue.length;
    }
    
    return (floorsToTravel * this.floorTravelTime) + 
           (stopsOnWay * this.doorOperationTime);
  }
  
  private isOnTheWay(
    current: number, 
    target: number, 
    direction: Direction,
    queue: Request[]
  ): boolean {
    if (direction === Direction.UP && target > current) {
      return true;
    }
    if (direction === Direction.DOWN && target < current) {
      return true;
    }
    return false;
  }
  
  private getFurthestFloor(
    current: number,
    direction: Direction,
    queue: Request[]
  ): number {
    const floors = queue.map(r => r.floor.getFloorNumber());
    if (direction === Direction.UP) {
      return Math.max(...floors, current);
    } else {
      return Math.min(...floors, current);
    }
  }
}
 
// Strategy 3: Zone-Based Dispatch
class ZoneDispatch implements DispatchStrategy {
  private zones: Map<number, number[]> = new Map(); // elevatorId -> [floors]
  
  constructor(numElevators: number, numFloors: number) {
    // Divide floors among elevators
    const floorsPerZone = Math.ceil(numFloors / numElevators);
    
    for (let i = 0; i < numElevators; i++) {
      const zoneStart = i * floorsPerZone;
      const zoneEnd = Math.min((i + 1) * floorsPerZone - 1, numFloors - 1);
      const floors = Array.from(
        { length: zoneEnd - zoneStart + 1 }, 
        (_, j) => zoneStart + j
      );
      this.zones.set(i, floors);
    }
  }
  
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    const targetFloor = request.floor.getFloorNumber();
    
    // Find elevator responsible for this floor
    for (const elevator of elevators) {
      const zone = this.zones.get(elevator.id);
      if (zone && zone.includes(targetFloor)) {
        if (elevator.getState() !== ElevatorState.MAINTENANCE) {
          return elevator;
        }
      }
    }
    
    // Zone elevator unavailable, fall back to nearest
    const nearestDispatch = new NearestIdleDispatch();
    return nearestDispatch.selectElevator(request, elevators);
  }
}

Dispatch is Active Research

Elevator dispatch optimization is an active research area. Modern systems use machine learning to predict traffic patterns and pre-position elevators. The core insight: dispatching based on estimated arrival time (not just distance) leads to significantly better average wait times.

The Strategy Pattern for Algorithms

We've implemented multiple scheduling algorithms (FCFS, SCAN, LOOK) and dispatch strategies (Nearest, Earliest Arrival, Zone). The Strategy Pattern is the perfect fit for making these interchangeable at runtime.

Strategy Pattern Benefits:

Family of algorithms: Define a common interface for all scheduling strategies
Runtime selection: Change algorithm without code changes
Testability: Test each strategy in isolation
Extensibility: Add new algorithms without modifying existing code
Configuration-driven: Building managers choose the strategy for their needs

Strategy Pattern Integration
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// Strategy interface for scheduling
interface SchedulingStrategy {
  // Select elevator for a new hall call
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null;
  
  // Order destinations for an elevator's queue
  orderDestinations(
    currentFloor: number,
    currentDirection: Direction,
    requests: Request[]
  ): Request[];
  
  // Get next destination from ordered queue
  getNextDestination(currentFloor: Floor, queue: Request[]): Request | null;
}
 
// Strategy factory for configuration-driven instantiation
class SchedulingStrategyFactory {
  static create(algorithmName: string, config?: BuildingConfig): SchedulingStrategy {
    switch (algorithmName.toUpperCase()) {
      case 'FCFS':
        return new FCFSScheduler();
      case 'SCAN':
        return new SCANScheduler();
      case 'LOOK':
        return new LOOKScheduler();
      case 'C-SCAN':
        return new CSCANScheduler();
      case 'C-LOOK':
        return new CLOOKScheduler();
      default:
        console.warn(`Unknown algorithm ${algorithmName}, defaulting to LOOK`);
        return new LOOKScheduler();
    }
  }
}
 
// Controller uses strategy via interface
class ElevatorController {
  private schedulingStrategy: SchedulingStrategy;
  private dispatchStrategy: DispatchStrategy;
  
  constructor(
    numFloors: number,
    numElevators: number,
    schedulingAlgorithm: string = 'LOOK',
    dispatchAlgorithm: string = 'EARLIEST_ARRIVAL'
  ) {
    this.schedulingStrategy = SchedulingStrategyFactory.create(schedulingAlgorithm);
    this.dispatchStrategy = this.createDispatchStrategy(dispatchAlgorithm);
    // ... initialize elevators and floors
  }
  
  private createDispatchStrategy(name: string): DispatchStrategy {
    switch (name.toUpperCase()) {
      case 'NEAREST':
        return new NearestIdleDispatch();
      case 'EARLIEST_ARRIVAL':
        return new EarliestArrivalDispatch();
      case 'ZONE':
        return new ZoneDispatch(this.elevators.length, this.floors.length);
      default:
        return new EarliestArrivalDispatch();
    }
  }
  
  // Strategy can be changed at runtime
  setSchedulingStrategy(strategy: SchedulingStrategy): void {
    this.schedulingStrategy = strategy;
    console.log('Scheduling strategy updated');
  }
  
  setDispatchStrategy(strategy: DispatchStrategy): void {
    this.dispatchStrategy = strategy;
    console.log('Dispatch strategy updated');
  }
  
  handleHallCall(floorNumber: number, direction: Direction): void {
    const floor = this.getFloor(floorNumber);
    const request = Request.createHallCall(floor, direction);
    
    // Use dispatch strategy to select elevator
    const elevator = this.dispatchStrategy.selectElevator(
      request, 
      this.getAvailableElevators()
    );
    
    if (elevator) {
      request.assign(elevator);
      elevator.addDestination(request);
      
      // Use scheduling strategy to reorder elevator's queue
      const orderedQueue = this.schedulingStrategy.orderDestinations(
        elevator.getCurrentFloor().getFloorNumber(),
        elevator.getDirection(),
        elevator.getDestinationQueue()
      );
      elevator.setDestinationQueue(orderedQueue);
    }
  }
}

Configuration in Production

Real elevator systems are configured at installation time. The Strategy Pattern allows building managers to specify 'algorithm: LOOK' in configuration. Some systems even switch algorithms based on time of day—SCAN during peak hours for throughput, simpler algorithms at night for energy savings.

Performance Analysis and Trade-offs

Choosing an algorithm requires understanding trade-offs. Let's analyze how each performs under different conditions.

Key Metrics:

Average Wait Time (AWT): Time from button press to elevator arrival
Average Journey Time (AJT): Time from button press to reaching destination
Throughput: Passengers served per hour
Fairness: Variance in wait times across floors
Energy Efficiency: Distance traveled per passenger

Algorithm Performance by Traffic Pattern
Algorithm	Low Traffic	Up-Peak (Morning)	Down-Peak (Evening)	Interfloor
FCFS	Poor	Very Poor	Very Poor	Poor
SCAN	Good	Very Good	Good	Good
LOOK	Very Good	Excellent	Very Good	Very Good
C-SCAN	Good	Good	Good	Excellent (fairest)
C-LOOK	Excellent	Excellent	Excellent	Excellent

Traffic Pattern Analysis:

Up-Peak (Morning rush):

Most passengers going FROM ground TO upper floors
SCAN/LOOK excel because one sweep up serves many requests
Zone dispatch helps by dedicating some elevators to high floors

Down-Peak (Evening rush):

Opposite pattern: upper floors TO ground
Similar to up-peak but reversed
Some systems "park" elevators on upper floors anticipating this

Interfloor (Normal business hours):

Random distribution of trips
C-LOOK provides best fairness (no floor is starved)
LOOK still efficient for individual wait times

Weekend/Night:

Very low traffic
Simple algorithms sufficient
Can optimize for energy (park at ground, power-save mode)

Performance Metrics Collection
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Metrics collector for algorithm evaluation
class ElevatorMetrics {
  private requests: Map<number, RequestMetrics> = new Map();
  
  recordRequestCreated(request: Request): void {
    this.requests.set(request.id, {
      createdAt: Date.now(),
      floor: request.floor.getFloorNumber(),
      direction: request.direction,
    });
  }
  
  recordElevatorArrived(requestId: number): void {
    const metrics = this.requests.get(requestId);
    if (metrics) {
      metrics.elevatorArrivedAt = Date.now();
      metrics.waitTime = metrics.elevatorArrivedAt - metrics.createdAt;
    }
  }
  
  recordRequestCompleted(requestId: number): void {
    const metrics = this.requests.get(requestId);
    if (metrics) {
      metrics.completedAt = Date.now();
      metrics.journeyTime = metrics.completedAt - metrics.createdAt;
    }
  }
  
  getAverageWaitTime(): number {
    const completed = [...this.requests.values()]
      .filter(m => m.waitTime !== undefined);
    
    if (completed.length === 0) return 0;
    
    const totalWait = completed.reduce((sum, m) => sum + m.waitTime!, 0);
    return totalWait / completed.length;
  }
  
  getAverageJourneyTime(): number {
    const completed = [...this.requests.values()]
      .filter(m => m.journeyTime !== undefined);
    
    if (completed.length === 0) return 0;
    
    const totalJourney = completed.reduce((sum, m) => sum + m.journeyTime!, 0);
    return totalJourney / completed.length;
  }
  
  getWaitTimeByFloor(): Map<number, number> {
    const byFloor = new Map<number, number[]>();
    
    for (const metrics of this.requests.values()) {
      if (metrics.waitTime !== undefined) {
        const floor = metrics.floor;
        if (!byFloor.has(floor)) byFloor.set(floor, []);
        byFloor.get(floor)!.push(metrics.waitTime);
      }
    }
    
    const averages = new Map<number, number>();
    for (const [floor, times] of byFloor) {
      averages.set(floor, times.reduce((a, b) => a + b, 0) / times.length);
    }
    return averages;
  }
  
  getThroughput(windowMs: number = 3600000): number {
    const now = Date.now();
    const recent = [...this.requests.values()]
      .filter(m => m.completedAt && (now - m.completedAt < windowMs));
    
    return recent.length;
  }
}
 
interface RequestMetrics {
  createdAt: number;
  floor: number;
  direction: Direction | null;
  elevatorArrivedAt?: number;
  completedAt?: number;
  waitTime?: number;
  journeyTime?: number;
}

Summary and Path Forward

Scheduling Algorithms Mastered:

We've explored the core algorithms that turn a simple elevator into an efficient transportation system:

Key Accomplishments

•FCFS Analysis: Understood why simple arrival-order processing fails at scale
•SCAN/LOOK Implementation: Built direction-aware scheduling that minimizes travel distance
•C-SCAN/C-LOOK: Learned circular variants for improved fairness across floors
•Multi-Elevator Dispatch: Implemented strategies for selecting which elevator serves each request
•Strategy Pattern: Made algorithms interchangeable for configuration-driven behavior
•Performance Metrics: Built systems to measure wait time, throughput, and fairness

What's Next:

With entities, state machines, and algorithms complete, we now bring everything together. The next page covers:

Pattern integration: How State, Strategy, and Observer patterns work in harmony
Clean Architecture: Organizing the code for maintainability
Event-driven coordination: How components communicate

This synthesis demonstrates how individual patterns combine into a cohesive, production-ready system.

Scheduling Design Complete

You now understand the algorithms that power elevator systems. The key insight: scheduling is about trade-offs. LOOK optimizes individual wait time; C-LOOK adds fairness. Understanding these trade-offs is what distinguishes senior engineers from juniors.

4 / 6

Loading learning content...

System Design LLDCase Studies

Elevator System Design

LevelAdvanced

Duration120 mins

TopicCase Studies

4 / 6

Scheduling Algorithms: FCFS and SCAN

The Optimization Challenge

A poorly chosen algorithm can lead to:

Starvation: Some passengers wait indefinitely
Inefficiency: Elevators travel more distance than necessary
Poor fairness: Some floors consistently get worse service
Convoy effect: All elevators cluster together

Conversely, a well-designed algorithm minimizes average wait time, ensures fairness, and makes efficient use of elevator capacity. This is where LLD meets algorithm design.

What You Will Master

By the end of this page, you will be able to:

FCFS: First-Come-First-Served

How FCFS Works:

Maintain a queue of pending requests
When elevator becomes available, take the oldest request
Go to that floor, serve the request
Repeat

Example Scenario:

Elevator at floor 5. Requests arrive in order: Floor 2, Floor 15, Floor 3, Floor 14.

FCFS path: 5 → 2 → 15 → 3 → 14

Total floors traveled: 3 + 13 + 12 + 11 = 39 floors

FCFS Implementation
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class FCFSScheduler implements SchedulingStrategy {
  private requestQueue: Request[] = [];
  
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    // For single elevator: simply return the one elevator
    // For multiple elevators: find the idle or soonest-available one
    const available = elevators.filter(e => 
      e.getState() !== ElevatorState.MAINTENANCE
    );
    
    if (available.length === 0) return null;
    
    // Prefer idle elevators
    const idle = available.find(e => e.getState() === ElevatorState.IDLE);
    if (idle) return idle;
    
    // Otherwise, assign to elevator with shortest queue (basic fairness)
    return available.reduce((best, current) => 
      current.getQueueLength() < best.getQueueLength() ? current : best
    );
  }
  
  getNextDestination(currentFloor: Floor, queue: Request[]): Request | null {
    // FCFS: return the oldest request (first in queue)
    return queue[0] ?? null;
  }
  
  addRequest(request: Request): void {
    this.requestQueue.push(request);
  }
  
  orderDestinations(
    currentFloor: number,
    currentDirection: Direction,
    requests: Request[]
  ): Request[] {
    // FCFS doesn't reorder - keep original order
    return [...requests];
  }
}

Analysis of FCFS:

FCFS Advantages

•Simple to implement: Just a queue
•Fair in arrival order: First to request = first served
•No starvation: Every request eventually served
•Predictable: Easy to reason about

FCFS Disadvantages

•Highly inefficient: Constant direction changes
•Long seek times: Elevator oscillates unnecessarily
•Poor throughput: Serves fewer requests per hour
•Ignores position: Nearby requests have no priority

FCFS is Almost Never Used

SCAN: The Elevator Algorithm

SCAN, also known as the Elevator Algorithm, mimics how physical elevators have always worked: travel in one direction serving all requests along the way, then reverse direction.

How SCAN Works:

Travel in the current direction
Stop at each floor that has a request in this direction
Continue to the end of the building (or last request)
Reverse direction
Repeat

Example Scenario (Same as FCFS):

Elevator at floor 5, traveling UP. Requests: Floor 2, Floor 15, Floor 3, Floor 14.

SCAN path: 5 → 14 → 15 (reach top) → 19 (top) → 3 → 2

Actually, optimized SCAN: 5 → 14 → 15 → reverse → 3 → 2

Total: 10 + 1 + 12 + 1 = 24 floors (vs FCFS's 39)

That's 38% less travel!

Converting Mermaid diagram...

SCAN Algorithm Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class SCANScheduler implements SchedulingStrategy {
  
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    const available = elevators.filter(e => 
      e.getState() !== ElevatorState.MAINTENANCE
    );
    
    if (available.length === 0) return null;
    
    // Find elevator that can serve this request most efficiently
    let bestElevator: Elevator | null = null;
    let bestScore = Infinity;
    
    for (const elevator of available) {
      const score = this.calculateScore(elevator, request);
      if (score < bestScore) {
        bestScore = score;
        bestElevator = elevator;
      }
    }
    
    return bestElevator;
  }
  
  private calculateScore(elevator: Elevator, request: Request): number {
    const currentFloor = elevator.getCurrentFloor().getFloorNumber();
    const targetFloor = request.floor.getFloorNumber();
    const direction = elevator.getDirection();
    
    // If elevator is idle, score is just distance
    if (direction === Direction.IDLE) {
      return Math.abs(targetFloor - currentFloor);
    }
    
    const isAbove = targetFloor > currentFloor;
    const isBelow = targetFloor < currentFloor;
    
    // If request is in current direction of travel, low score
    if (direction === Direction.UP && isAbove) {
      return targetFloor - currentFloor;
    }
    if (direction === Direction.DOWN && isBelow) {
      return currentFloor - targetFloor;
    }
    
    // Request is behind or requires direction change
    // Higher score - will be served after current direction completes
    const maxFloor = 19; // Building height
    
    if (direction === Direction.UP) {
      // Must go to top, then come back down
      return (maxFloor - currentFloor) + (maxFloor - targetFloor);
    } else {
      // Must go to bottom, then come back up
      return currentFloor + targetFloor;
    }
  }
  
  orderDestinations(
    currentFloor: number,
    currentDirection: Direction,
    requests: Request[]
  ): Request[] {
    if (requests.length === 0) return [];
    
    // Separate requests by direction relative to current floor
    const above = requests.filter(r => 
      r.floor.getFloorNumber() > currentFloor
    );
    const below = requests.filter(r => 
      r.floor.getFloorNumber() < currentFloor
    );
    const same = requests.filter(r => 
      r.floor.getFloorNumber() === currentFloor
    );
    
    // Sort each group
    above.sort((a, b) => 
      a.floor.getFloorNumber() - b.floor.getFloorNumber()
    );
    below.sort((a, b) => 
      b.floor.getFloorNumber() - a.floor.getFloorNumber()
    );
    
    // SCAN order based on current direction
    if (currentDirection === Direction.UP || currentDirection === Direction.IDLE) {
      // Go up first, then down
      return [...same, ...above, ...below.reverse()];
    } else {
      // Go down first, then up
      return [...same, ...below, ...above.reverse()];
    }
  }
  
  getNextDestination(currentFloor: Floor, queue: Request[]): Request | null {
    // Queue is already ordered by orderDestinations
    return queue[0] ?? null;
  }
}

SCAN Variants: LOOK and C-SCAN

The basic SCAN algorithm can be improved with variants that address specific inefficiencies.

LOOK Algorithm:

SCAN always travels to the end of the building before reversing. LOOK is smarter—it only goes as far as the last request in the current direction, then reverses immediately.

Example:

Building has 20 floors. Elevator at floor 5, going UP. Requests at floors 8, 12.

SCAN: 5 → 8 → 12 → 19 (top) → reverse
LOOK: 5 → 8 → 12 → reverse

LOOK saves 7 floors of unnecessary travel!

LOOK Algorithm
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class LOOKScheduler extends SCANScheduler {
  
  orderDestinations(
    currentFloor: number,
    currentDirection: Direction,
    requests: Request[]
  ): Request[] {
    if (requests.length === 0) return [];
    
    const above = requests
      .filter(r => r.floor.getFloorNumber() > currentFloor)
      .sort((a, b) => a.floor.getFloorNumber() - b.floor.getFloorNumber());
    
    const below = requests
      .filter(r => r.floor.getFloorNumber() < currentFloor)
      .sort((a, b) => b.floor.getFloorNumber() - a.floor.getFloorNumber());
    
    const same = requests.filter(r => 
      r.floor.getFloorNumber() === currentFloor
    );
    
    // LOOK: Only go as far as the furthest request in current direction
    // Then immediately reverse (unlike SCAN which goes to building end)
    if (currentDirection === Direction.UP || currentDirection === Direction.IDLE) {
      // Serve all above, then all below (closest first when going down)
      return [...same, ...above, ...below];
    } else {
      return [...same, ...below, ...above];
    }
  }
  
  // Override score calculation for tighter estimates
  protected calculateScore(elevator: Elevator, request: Request): number {
    const currentFloor = elevator.getCurrentFloor().getFloorNumber();
    const targetFloor = request.floor.getFloorNumber();
    const direction = elevator.getDirection();
    const queue = elevator.getDestinationQueue();
    
    if (direction === Direction.IDLE) {
      return Math.abs(targetFloor - currentFloor);
    }
    
    // Find the furthest floor in current direction
    const floorsInDirection = queue
      .map(r => r.floor.getFloorNumber())
      .filter(f => direction === Direction.UP ? f > currentFloor : f < currentFloor);
    
    const furthest = direction === Direction.UP
      ? Math.max(...floorsInDirection, currentFloor)
      : Math.min(...floorsInDirection, currentFloor);
    
    const isInDirection = direction === Direction.UP
      ? targetFloor > currentFloor
      : targetFloor < currentFloor;
    
    if (isInDirection) {
      return Math.abs(targetFloor - currentFloor);
    }
    
    // Must complete current direction, then reverse
    const distanceToEnd = Math.abs(furthest - currentFloor);
    const distanceFromEndToTarget = Math.abs(furthest - targetFloor);
    return distanceToEnd + distanceFromEndToTarget;
  }
}

C-SCAN (Circular SCAN):

C-SCAN addresses fairness concerns with SCAN. In basic SCAN, floors near the extremes get served twice as often (once going up, once going down). C-SCAN provides more uniform wait times.

How C-SCAN Works:

Travel in one direction only (e.g., always UP for serving)
When reaching the top, immediately return to the bottom WITHOUT serving
Resume serving from the bottom going UP

This treats the floors as a circular list, ensuring every floor has equal priority.

Algorithm Comparison
Algorithm	Seek Behavior	Fairness	Efficiency	Best For
FCFS	Random (order of arrival)	By arrival time	Poor	Never (educational only)
SCAN	Sweep end-to-end	Moderate (favors middle)	Good	General buildings
LOOK	Sweep to last request	Moderate	Very Good	Most real elevators
C-SCAN	Circular sweep	Excellent (uniform)	Good	High-traffic buildings
C-LOOK	Circular to last request	Very Good	Excellent	Best overall

Real-World Algorithm Choice

Multi-Elevator Dispatch Strategies

With multiple elevators, scheduling becomes two-dimensional:

Elevator Selection: Which elevator should handle a new hall call?
Request Ordering: What order should that elevator visit its destinations?

We've covered ordering (SCAN/LOOK). Now let's focus on dispatch strategies—selecting the best elevator for each request.

Dispatch Strategy Goals:

Minimize wait time for the requesting passenger
Balance load across all elevators
Avoid convoy effect (all elevators clustered together)
Consider future requests (anticipation)

Common Dispatch Strategies

•Nearest Elevator: Assign to the closest physically idle elevator
•Shortest Queue: Assign to elevator with fewest pending requests
•Earliest Arrival: Estimate arrival time; pick the elevator that arrives first
•Sector/Zone: Dedicate specific elevators to floor ranges
•Traffic-Adaptive: Adjust strategy based on current traffic patterns

Multi-Elevator Dispatch
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
interface DispatchStrategy {
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null;
}
 
// Strategy 1: Nearest Idle Elevator
class NearestIdleDispatch implements DispatchStrategy {
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    const targetFloor = request.floor.getFloorNumber();
    
    // Filter to available elevators
    const available = elevators.filter(e => 
      e.getState() !== ElevatorState.MAINTENANCE
    );
    
    // Prefer idle elevators, find nearest
    const idle = available.filter(e => e.getState() === ElevatorState.IDLE);
    
    if (idle.length > 0) {
      return idle.reduce((nearest, current) => {
        const nearestDist = Math.abs(
          nearest.getCurrentFloor().getFloorNumber() - targetFloor
        );
        const currentDist = Math.abs(
          current.getCurrentFloor().getFloorNumber() - targetFloor
        );
        return currentDist < nearestDist ? current : nearest;
      });
    }
    
    // No idle elevators, assign to one with shortest queue
    return this.shortestQueueFallback(available);
  }
  
  private shortestQueueFallback(elevators: Elevator[]): Elevator | null {
    if (elevators.length === 0) return null;
    return elevators.reduce((best, current) =>
      current.getQueueLength() < best.getQueueLength() ? current : best
    );
  }
}
 
// Strategy 2: Earliest Arrival Time
class EarliestArrivalDispatch implements DispatchStrategy {
  private readonly floorTravelTime: number = 2000; // ms per floor
  private readonly doorOperationTime: number = 5000; // ms per stop
  
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    const available = elevators.filter(e => 
      e.getState() !== ElevatorState.MAINTENANCE
    );
    
    if (available.length === 0) return null;
    
    let bestElevator: Elevator | null = null;
    let shortestTime = Infinity;
    
    for (const elevator of available) {
      const arrivalTime = this.estimateArrivalTime(elevator, request);
      if (arrivalTime < shortestTime) {
        shortestTime = arrivalTime;
        bestElevator = elevator;
      }
    }
    
    return bestElevator;
  }
  
  private estimateArrivalTime(elevator: Elevator, request: Request): number {
    const currentFloor = elevator.getCurrentFloor().getFloorNumber();
    const targetFloor = request.floor.getFloorNumber();
    const direction = elevator.getDirection();
    const queue = elevator.getDestinationQueue();
    
    if (direction === Direction.IDLE) {
      // Direct travel
      return Math.abs(targetFloor - currentFloor) * this.floorTravelTime;
    }
    
    // Count stops between current position and target
    let floorsToTravel = 0;
    let stopsOnWay = 0;
    
    if (this.isOnTheWay(currentFloor, targetFloor, direction, queue)) {
      // Target is in current direction, count intermediate stops
      const intermediateStops = queue.filter(r => {
        const f = r.floor.getFloorNumber();
        if (direction === Direction.UP) {
          return f > currentFloor && f < targetFloor;
        } else {
          return f < currentFloor && f > targetFloor;
        }
      });
      
      floorsToTravel = Math.abs(targetFloor - currentFloor);
      stopsOnWay = intermediateStops.length;
    } else {
      // Must complete current sweep first
      const furthestInDirection = this.getFurthestFloor(
        currentFloor, direction, queue
      );
      floorsToTravel = Math.abs(furthestInDirection - currentFloor) +
                       Math.abs(furthestInDirection - targetFloor);
      stopsOnWay = queue.length;
    }
    
    return (floorsToTravel * this.floorTravelTime) + 
           (stopsOnWay * this.doorOperationTime);
  }
  
  private isOnTheWay(
    current: number, 
    target: number, 
    direction: Direction,
    queue: Request[]
  ): boolean {
    if (direction === Direction.UP && target > current) {
      return true;
    }
    if (direction === Direction.DOWN && target < current) {
      return true;
    }
    return false;
  }
  
  private getFurthestFloor(
    current: number,
    direction: Direction,
    queue: Request[]
  ): number {
    const floors = queue.map(r => r.floor.getFloorNumber());
    if (direction === Direction.UP) {
      return Math.max(...floors, current);
    } else {
      return Math.min(...floors, current);
    }
  }
}
 
// Strategy 3: Zone-Based Dispatch
class ZoneDispatch implements DispatchStrategy {
  private zones: Map<number, number[]> = new Map(); // elevatorId -> [floors]
  
  constructor(numElevators: number, numFloors: number) {
    // Divide floors among elevators
    const floorsPerZone = Math.ceil(numFloors / numElevators);
    
    for (let i = 0; i < numElevators; i++) {
      const zoneStart = i * floorsPerZone;
      const zoneEnd = Math.min((i + 1) * floorsPerZone - 1, numFloors - 1);
      const floors = Array.from(
        { length: zoneEnd - zoneStart + 1 }, 
        (_, j) => zoneStart + j
      );
      this.zones.set(i, floors);
    }
  }
  
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null {
    const targetFloor = request.floor.getFloorNumber();
    
    // Find elevator responsible for this floor
    for (const elevator of elevators) {
      const zone = this.zones.get(elevator.id);
      if (zone && zone.includes(targetFloor)) {
        if (elevator.getState() !== ElevatorState.MAINTENANCE) {
          return elevator;
        }
      }
    }
    
    // Zone elevator unavailable, fall back to nearest
    const nearestDispatch = new NearestIdleDispatch();
    return nearestDispatch.selectElevator(request, elevators);
  }
}

Dispatch is Active Research

The Strategy Pattern for Algorithms

Strategy Pattern Benefits:

Family of algorithms: Define a common interface for all scheduling strategies
Runtime selection: Change algorithm without code changes
Testability: Test each strategy in isolation
Extensibility: Add new algorithms without modifying existing code
Configuration-driven: Building managers choose the strategy for their needs

Strategy Pattern Integration
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// Strategy interface for scheduling
interface SchedulingStrategy {
  // Select elevator for a new hall call
  selectElevator(request: Request, elevators: Elevator[]): Elevator | null;
  
  // Order destinations for an elevator's queue
  orderDestinations(
    currentFloor: number,
    currentDirection: Direction,
    requests: Request[]
  ): Request[];
  
  // Get next destination from ordered queue
  getNextDestination(currentFloor: Floor, queue: Request[]): Request | null;
}
 
// Strategy factory for configuration-driven instantiation
class SchedulingStrategyFactory {
  static create(algorithmName: string, config?: BuildingConfig): SchedulingStrategy {
    switch (algorithmName.toUpperCase()) {
      case 'FCFS':
        return new FCFSScheduler();
      case 'SCAN':
        return new SCANScheduler();
      case 'LOOK':
        return new LOOKScheduler();
      case 'C-SCAN':
        return new CSCANScheduler();
      case 'C-LOOK':
        return new CLOOKScheduler();
      default:
        console.warn(`Unknown algorithm ${algorithmName}, defaulting to LOOK`);
        return new LOOKScheduler();
    }
  }
}
 
// Controller uses strategy via interface
class ElevatorController {
  private schedulingStrategy: SchedulingStrategy;
  private dispatchStrategy: DispatchStrategy;
  
  constructor(
    numFloors: number,
    numElevators: number,
    schedulingAlgorithm: string = 'LOOK',
    dispatchAlgorithm: string = 'EARLIEST_ARRIVAL'
  ) {
    this.schedulingStrategy = SchedulingStrategyFactory.create(schedulingAlgorithm);
    this.dispatchStrategy = this.createDispatchStrategy(dispatchAlgorithm);
    // ... initialize elevators and floors
  }
  
  private createDispatchStrategy(name: string): DispatchStrategy {
    switch (name.toUpperCase()) {
      case 'NEAREST':
        return new NearestIdleDispatch();
      case 'EARLIEST_ARRIVAL':
        return new EarliestArrivalDispatch();
      case 'ZONE':
        return new ZoneDispatch(this.elevators.length, this.floors.length);
      default:
        return new EarliestArrivalDispatch();
    }
  }
  
  // Strategy can be changed at runtime
  setSchedulingStrategy(strategy: SchedulingStrategy): void {
    this.schedulingStrategy = strategy;
    console.log('Scheduling strategy updated');
  }
  
  setDispatchStrategy(strategy: DispatchStrategy): void {
    this.dispatchStrategy = strategy;
    console.log('Dispatch strategy updated');
  }
  
  handleHallCall(floorNumber: number, direction: Direction): void {
    const floor = this.getFloor(floorNumber);
    const request = Request.createHallCall(floor, direction);
    
    // Use dispatch strategy to select elevator
    const elevator = this.dispatchStrategy.selectElevator(
      request, 
      this.getAvailableElevators()
    );
    
    if (elevator) {
      request.assign(elevator);
      elevator.addDestination(request);
      
      // Use scheduling strategy to reorder elevator's queue
      const orderedQueue = this.schedulingStrategy.orderDestinations(
        elevator.getCurrentFloor().getFloorNumber(),
        elevator.getDirection(),
        elevator.getDestinationQueue()
      );
      elevator.setDestinationQueue(orderedQueue);
    }
  }
}

Configuration in Production

Performance Analysis and Trade-offs

Choosing an algorithm requires understanding trade-offs. Let's analyze how each performs under different conditions.

Key Metrics:

Average Wait Time (AWT): Time from button press to elevator arrival
Average Journey Time (AJT): Time from button press to reaching destination
Throughput: Passengers served per hour
Fairness: Variance in wait times across floors
Energy Efficiency: Distance traveled per passenger

Algorithm Performance by Traffic Pattern
Algorithm	Low Traffic	Up-Peak (Morning)	Down-Peak (Evening)	Interfloor
FCFS	Poor	Very Poor	Very Poor	Poor
SCAN	Good	Very Good	Good	Good
LOOK	Very Good	Excellent	Very Good	Very Good
C-SCAN	Good	Good	Good	Excellent (fairest)
C-LOOK	Excellent	Excellent	Excellent	Excellent

Traffic Pattern Analysis:

Up-Peak (Morning rush):

Most passengers going FROM ground TO upper floors
SCAN/LOOK excel because one sweep up serves many requests
Zone dispatch helps by dedicating some elevators to high floors

Down-Peak (Evening rush):

Opposite pattern: upper floors TO ground
Similar to up-peak but reversed
Some systems "park" elevators on upper floors anticipating this

Interfloor (Normal business hours):

Random distribution of trips
C-LOOK provides best fairness (no floor is starved)
LOOK still efficient for individual wait times

Weekend/Night:

Very low traffic
Simple algorithms sufficient
Can optimize for energy (park at ground, power-save mode)

Performance Metrics Collection
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Metrics collector for algorithm evaluation
class ElevatorMetrics {
  private requests: Map<number, RequestMetrics> = new Map();
  
  recordRequestCreated(request: Request): void {
    this.requests.set(request.id, {
      createdAt: Date.now(),
      floor: request.floor.getFloorNumber(),
      direction: request.direction,
    });
  }
  
  recordElevatorArrived(requestId: number): void {
    const metrics = this.requests.get(requestId);
    if (metrics) {
      metrics.elevatorArrivedAt = Date.now();
      metrics.waitTime = metrics.elevatorArrivedAt - metrics.createdAt;
    }
  }
  
  recordRequestCompleted(requestId: number): void {
    const metrics = this.requests.get(requestId);
    if (metrics) {
      metrics.completedAt = Date.now();
      metrics.journeyTime = metrics.completedAt - metrics.createdAt;
    }
  }
  
  getAverageWaitTime(): number {
    const completed = [...this.requests.values()]
      .filter(m => m.waitTime !== undefined);
    
    if (completed.length === 0) return 0;
    
    const totalWait = completed.reduce((sum, m) => sum + m.waitTime!, 0);
    return totalWait / completed.length;
  }
  
  getAverageJourneyTime(): number {
    const completed = [...this.requests.values()]
      .filter(m => m.journeyTime !== undefined);
    
    if (completed.length === 0) return 0;
    
    const totalJourney = completed.reduce((sum, m) => sum + m.journeyTime!, 0);
    return totalJourney / completed.length;
  }
  
  getWaitTimeByFloor(): Map<number, number> {
    const byFloor = new Map<number, number[]>();
    
    for (const metrics of this.requests.values()) {
      if (metrics.waitTime !== undefined) {
        const floor = metrics.floor;
        if (!byFloor.has(floor)) byFloor.set(floor, []);
        byFloor.get(floor)!.push(metrics.waitTime);
      }
    }
    
    const averages = new Map<number, number>();
    for (const [floor, times] of byFloor) {
      averages.set(floor, times.reduce((a, b) => a + b, 0) / times.length);
    }
    return averages;
  }
  
  getThroughput(windowMs: number = 3600000): number {
    const now = Date.now();
    const recent = [...this.requests.values()]
      .filter(m => m.completedAt && (now - m.completedAt < windowMs));
    
    return recent.length;
  }
}
 
interface RequestMetrics {
  createdAt: number;
  floor: number;
  direction: Direction | null;
  elevatorArrivedAt?: number;
  completedAt?: number;
  waitTime?: number;
  journeyTime?: number;
}

Summary and Path Forward

Scheduling Algorithms Mastered:

We've explored the core algorithms that turn a simple elevator into an efficient transportation system:

Key Accomplishments

•FCFS Analysis: Understood why simple arrival-order processing fails at scale
•SCAN/LOOK Implementation: Built direction-aware scheduling that minimizes travel distance
•C-SCAN/C-LOOK: Learned circular variants for improved fairness across floors
•Multi-Elevator Dispatch: Implemented strategies for selecting which elevator serves each request
•Strategy Pattern: Made algorithms interchangeable for configuration-driven behavior
•Performance Metrics: Built systems to measure wait time, throughput, and fairness

What's Next:

With entities, state machines, and algorithms complete, we now bring everything together. The next page covers:

Pattern integration: How State, Strategy, and Observer patterns work in harmony
Clean Architecture: Organizing the code for maintainability
Event-driven coordination: How components communicate

This synthesis demonstrates how individual patterns combine into a cohesive, production-ready system.

Scheduling Design Complete

4 / 6