The Elevator Problem

The Elevator Problem is a classic scheduling and optimization challenge that models how multiple elevators coordinate to serve passengers efficiently. It demonstrates load balancing, scheduling algorithms, optimization trade-offs, and decentralized coordination. Unlike many concurrency problems, it focuses on real-time decision-making and multi-objective optimization.

The Scenario

A building has:

N elevators moving between floors
M floors
Passengers arriving at random floors with random destinations
Call buttons (up/down) on each floor
Destination buttons inside each elevator

The goals:

Minimize wait time - How long passengers wait for an elevator
Minimize travel time - How long the journey takes
Maximize throughput - Serve as many passengers as possible
Balance load - Distribute work evenly across elevators
Save energy - Minimize unnecessary movement

The challenges:

Elevators must coordinate without central controller
Must handle rush hour traffic patterns
Balance fairness vs efficiency
Decide: which elevator responds to which call?
Decide: which direction to go when requests exist in both?

The Algorithms

1. Nearest-First (First-Come-First-Served)

Respond to whichever call is physically closest
Pros: Simple, fair
Cons: Can lead to poor global efficiency

2. SCAN (Elevator Algorithm)

Move in one direction, serving all requests
Reverse direction at ends
Pros: Efficient, predictable
Cons: Can have high wait times at extremes

3. LOOK (Optimized SCAN)

Like SCAN but reverses before reaching the end
Only goes as far as highest/lowest request
Pros: More efficient than SCAN
Cons: Still can leave people waiting

4. Sectoring (Zone-Based)

Divide building into zones, assign elevators to zones
Pros: Balanced load, predictable service
Cons: Inflexible, can waste capacity

Real-World Applications

Elevator scheduling patterns appear everywhere:

Disk I/O scheduling: Head movement optimization (original SCAN algorithm use case)
Network packet scheduling: Quality of Service (QoS)
Task scheduling: CPU scheduler, job queues
Vehicle routing: Taxi/rideshare dispatch
Load balancing: Distributing requests across servers
Warehouse robotics: Robot dispatch and routing

State Diagram

stateDiagram-v2 [*] --> Idle Idle --> Moving: New request Moving --> Moving: Continue serving requests Moving --> DoorsOpen: Reached destination DoorsOpen --> Moving: More requests DoorsOpen --> Idle: No requests Moving --> ChangingDirection: No more requests in direction ChangingDirection --> Moving: Requests in opposite direction ChangingDirection --> Idle: No requests note right of Moving LOOK Algorithm: - Serve all requests in current direction - Reverse when no more ahead end note note right of Idle Dispatch Decision: - Calculate cost for each elevator - Assign to lowest cost - Consider: distance, direction, load end note

Elevator Movement Visualization

sequenceDiagram participant F5 as Floor 5 participant E1 as Elevator 1 participant F3 as Floor 3 participant F1 as Floor 1 participant E2 as Elevator 2 Note over F5,E2: T=0: E1 at Floor 3 going UP, E2 at Floor 1 IDLE F5->>E1: Call Down Note over E1: E1 cost: 2 floors Note over E2: E2 cost: 4 floors E1->>F5: E1 assigned (nearest) Note over F3: T=5: Passenger at F3 wants to go to F1 F3->>E1: Call Down Note over E1: E1 already going UP, will serve on way back E1->>F5: Arrives, picks up passenger E1->>F3: Serves F3 on way down E1->>F1: Completes journey

Implementation in Go

package main

import (
	"fmt"
	"math"
	"math/rand"
	"sync"
	"time"
)

type Direction int

const (
	DirectionIdle Direction = iota
	DirectionUp
	DirectionDown
)

func (d Direction) String() string {
	return []string{"IDLE", "UP", "DOWN"}[d]
}

// Request represents a passenger request
type Request struct {
	floor       int
	direction   Direction
	destination int // Only set after passenger boards
	timestamp   time.Time
}

// Elevator represents a single elevator
type Elevator struct {
	id              int
	currentFloor    int
	direction       Direction
	requests        []Request
	capacity        int
	passengers      int
	mu              sync.Mutex
	moving          bool
	floorsServed    int
	passengersServed int
}

func NewElevator(id, startFloor, capacity int) *Elevator {
	return &Elevator{
		id:           id,
		currentFloor: startFloor,
		direction:    DirectionIdle,
		requests:     make([]Request, 0),
		capacity:     capacity,
	}
}

// CalculateCost estimates the cost (time) to serve a request
func (e *Elevator) CalculateCost(floor int, direction Direction) int {
	e.mu.Lock()
	defer e.mu.Unlock()

	if e.direction == DirectionIdle {
		// Idle elevator - just distance
		return abs(e.currentFloor - floor)
	}

	if e.direction == direction {
		// Same direction - check if on the way
		if (direction == DirectionUp && floor >= e.currentFloor) ||
			(direction == DirectionDown && floor <= e.currentFloor) {
			// On the way - just distance
			return abs(e.currentFloor - floor)
		}
	}

	// Need to reverse - higher cost
	// Distance to farthest request + distance back to this floor
	farthest := e.getFarthestRequestInDirection()
	return abs(e.currentFloor-farthest) + abs(farthest-floor)
}

func (e *Elevator) getFarthestRequestInDirection() int {
	farthest := e.currentFloor

	for _, req := range e.requests {
		if e.direction == DirectionUp && req.floor > farthest {
			farthest = req.floor
		} else if e.direction == DirectionDown && req.floor < farthest {
			farthest = req.floor
		}
	}

	return farthest
}

// AssignRequest assigns a request to this elevator
func (e *Elevator) AssignRequest(req Request) {
	e.mu.Lock()
	defer e.mu.Unlock()

	e.requests = append(e.requests, req)

	// Set direction if idle
	if e.direction == DirectionIdle {
		if req.floor > e.currentFloor {
			e.direction = DirectionUp
		} else if req.floor < e.currentFloor {
			e.direction = DirectionDown
		}
	}

	fmt.Printf("[Elevator %d] 📝 Assigned request: Floor %d %s\n",
		e.id, req.floor, req.direction)
}

// Run executes the elevator's main loop using LOOK algorithm
func (e *Elevator) Run(done chan bool, wg *sync.WaitGroup) {
	defer wg.Done()

	ticker := time.NewTicker(500 * time.Millisecond) // Move every 500ms
	defer ticker.Stop()

	for {
		select {
		case <-done:
			return

		case <-ticker.C:
			e.move()
		}
	}
}

func (e *Elevator) move() {
	e.mu.Lock()
	defer e.mu.Unlock()

	if len(e.requests) == 0 {
		e.direction = DirectionIdle
		return
	}

	e.moving = true

	// LOOK algorithm: move in current direction
	if e.direction == DirectionUp {
		e.currentFloor++
	} else if e.direction == DirectionDown {
		e.currentFloor--
	}

	e.floorsServed++

	fmt.Printf("[Elevator %d] 🛗 Floor %d (%s) [Requests: %d, Passengers: %d/%d]\n",
		e.id, e.currentFloor, e.direction, len(e.requests), e.passengers, e.capacity)

	// Check for requests at current floor
	e.serveFloor()

	// Check if we need to change direction
	e.updateDirection()

	e.moving = false
}

func (e *Elevator) serveFloor() {
	// Pick up passengers waiting at this floor
	newRequests := make([]Request, 0)

	for _, req := range e.requests {
		if req.floor == e.currentFloor && req.direction == e.direction {
			// Passenger boards
			if e.passengers < e.capacity {
				e.passengers++
				e.passengersServed++

				fmt.Printf("[Elevator %d] 👤 Picked up passenger at floor %d (wait: %v)\n",
					e.id, e.currentFloor, time.Since(req.timestamp).Round(time.Millisecond))

				// Add destination request
				destReq := Request{
					floor:     req.destination,
					direction: DirectionIdle, // Internal request
				}
				newRequests = append(newRequests, destReq)
			} else {
				// Full - keep request for next elevator
				newRequests = append(newRequests, req)
			}
		} else if req.floor == e.currentFloor && req.direction == DirectionIdle {
			// Drop off passenger
			e.passengers--
			fmt.Printf("[Elevator %d] 🚪 Dropped off passenger at floor %d\n",
				e.id, e.currentFloor)
		} else {
			// Not at this floor yet
			newRequests = append(newRequests, req)
		}
	}

	e.requests = newRequests
}

func (e *Elevator) updateDirection() {
	// Check if there are more requests in current direction
	hasRequestsAhead := false

	for _, req := range e.requests {
		if e.direction == DirectionUp && req.floor > e.currentFloor {
			hasRequestsAhead = true
			break
		}
		if e.direction == DirectionDown && req.floor < e.currentFloor {
			hasRequestsAhead = true
			break
		}
	}

	if !hasRequestsAhead {
		// Reverse direction or go idle
		if e.direction == DirectionUp {
			// Check if requests below
			for _, req := range e.requests {
				if req.floor < e.currentFloor {
					e.direction = DirectionDown
					fmt.Printf("[Elevator %d] 🔄 Changing direction to DOWN\n", e.id)
					return
				}
			}
		} else if e.direction == DirectionDown {
			// Check if requests above
			for _, req := range e.requests {
				if req.floor > e.currentFloor {
					e.direction = DirectionUp
					fmt.Printf("[Elevator %d] 🔄 Changing direction to UP\n", e.id)
					return
				}
			}
		}

		// No requests in either direction
		if len(e.requests) == 0 {
			e.direction = DirectionIdle
		}
	}
}

// ElevatorSystem manages multiple elevators
type ElevatorSystem struct {
	elevators    []*Elevator
	numFloors    int
	mu           sync.Mutex
	totalRequests int
	totalWaitTime time.Duration
}

func NewElevatorSystem(numElevators, numFloors, capacity int) *ElevatorSystem {
	system := &ElevatorSystem{
		elevators: make([]*Elevator, numElevators),
		numFloors: numFloors,
	}

	// Distribute elevators across floors initially
	for i := 0; i < numElevators; i++ {
		startFloor := (numFloors / numElevators) * i
		system.elevators[i] = NewElevator(i, startFloor, capacity)
	}

	return system
}

// DispatchRequest finds the best elevator for a request (nearest-first strategy)
func (es *ElevatorSystem) DispatchRequest(req Request) {
	es.mu.Lock()
	defer es.mu.Unlock()

	es.totalRequests++

	// Find elevator with lowest cost
	bestElevator := es.elevators[0]
	bestCost := bestElevator.CalculateCost(req.floor, req.direction)

	for _, elevator := range es.elevators[1:] {
		cost := elevator.CalculateCost(req.floor, req.direction)
		if cost < bestCost {
			bestCost = cost
			bestElevator = elevator
		}
	}

	fmt.Printf("[Dispatch] 📡 Request floor %d %s → Elevator %d (cost: %d)\n",
		req.floor, req.direction, bestElevator.id, bestCost)

	bestElevator.AssignRequest(req)
}

// Run starts all elevators
func (es *ElevatorSystem) Run(done chan bool) {
	var wg sync.WaitGroup

	for _, elevator := range es.elevators {
		wg.Add(1)
		go elevator.Run(done, &wg)
	}

	wg.Wait()
}

// Stats prints system statistics
func (es *ElevatorSystem) Stats() {
	es.mu.Lock()
	defer es.mu.Unlock()

	fmt.Println("\n📊 Elevator System Statistics:")
	fmt.Printf("   Total requests processed: %d\n", es.totalRequests)

	totalFloorsServed := 0
	totalPassengers := 0

	for _, e := range es.elevators {
		e.mu.Lock()
		fmt.Printf("   Elevator %d:\n", e.id)
		fmt.Printf("     Final position: Floor %d\n", e.currentFloor)
		fmt.Printf("     Floors traveled: %d\n", e.floorsServed)
		fmt.Printf("     Passengers served: %d\n", e.passengersServed)
		totalFloorsServed += e.floorsServed
		totalPassengers += e.passengersServed
		e.mu.Unlock()
	}

	fmt.Printf("   Total floors traveled: %d\n", totalFloorsServed)
	fmt.Printf("   Total passengers served: %d\n", totalPassengers)
	fmt.Printf("   Avg floors per passenger: %.1f\n",
		float64(totalFloorsServed)/float64(totalPassengers))
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	fmt.Println("=== Elevator Scheduling Problem ===")
	fmt.Println("Multiple elevators serving a building\n")

	const (
		numElevators = 3
		numFloors    = 10
		capacity     = 4
		runtime      = 15 * time.Second
	)

	system := NewElevatorSystem(numElevators, numFloors, capacity)

	fmt.Printf("Configuration:\n")
	fmt.Printf("  Elevators: %d\n", numElevators)
	fmt.Printf("  Floors: %d\n", numFloors)
	fmt.Printf("  Capacity: %d passengers\n\n", capacity)

	done := make(chan bool)

	// Start elevators
	go system.Run(done)

	// Generate random passenger requests
	go func() {
		for i := 0; i < 20; i++ {
			time.Sleep(time.Duration(500+rand.Intn(1000)) * time.Millisecond)

			floor := rand.Intn(numFloors)
			destination := rand.Intn(numFloors)

			// Ensure destination != floor
			for destination == floor {
				destination = rand.Intn(numFloors)
			}

			var direction Direction
			if destination > floor {
				direction = DirectionUp
			} else {
				direction = DirectionDown
			}

			req := Request{
				floor:       floor,
				direction:   direction,
				destination: destination,
				timestamp:   time.Now(),
			}

			fmt.Printf("\n[Passenger %d] 🙋 Calling from floor %d to floor %d\n",
				i, floor, destination)

			system.DispatchRequest(req)
		}
	}()

	// Run for specified time
	time.Sleep(runtime)
	close(done)

	time.Sleep(500 * time.Millisecond)

	system.Stats()

	fmt.Println("\n✓ Simulation complete!")
}

How It Works

1. Cost-Based Dispatch

func (e *Elevator) CalculateCost(floor int, direction Direction) int {
    if e.direction == DirectionIdle {
        return abs(e.currentFloor - floor)  // Just distance
    }

    if sameDirection && onTheWay {
        return abs(e.currentFloor - floor)  // Low cost
    }

    // Need to reverse - high cost
    return distanceToFarthest + distanceBack
}

Each elevator calculates how “expensive” it would be to serve a request.

2. LOOK Algorithm

func (e *Elevator) move() {
    // Move in current direction
    if e.direction == DirectionUp {
        e.currentFloor++
    } else {
        e.currentFloor--
    }

    // Serve this floor
    e.serveFloor()

    // Check if should reverse
    if !hasRequestsAhead() {
        e.reverseDirection()
    }
}

Keep going in one direction until no more requests ahead.

3. Request Queuing

type Elevator struct {
    requests []Request  // All assigned requests
}

// Serve requests at current floor
func (e *Elevator) serveFloor() {
    for req in requests {
        if req.floor == currentFloor && req.direction == e.direction {
            pickUpPassenger()
        }
    }
}

4. Direction Management

func (e *Elevator) updateDirection() {
    if !hasRequestsAhead() {
        if hasRequestsBehind() {
            reverseDirection()
        } else {
            goIdle()
        }
    }
}

Advanced: Sectoring Strategy

package main

import (
	"fmt"
	"math"
)

type Zone struct {
	minFloor int
	maxFloor int
	elevator *Elevator
}

type SectoringSystem struct {
	zones     []Zone
	elevators []*Elevator
	numFloors int
}

func NewSectoringSystem(numElevators, numFloors, capacity int) *SectoringSystem {
	system := &SectoringSystem{
		zones:     make([]Zone, numElevators),
		elevators: make([]*Elevator, numElevators),
		numFloors: numFloors,
	}

	// Divide building into zones
	floorsPerZone := int(math.Ceil(float64(numFloors) / float64(numElevators)))

	for i := 0; i < numElevators; i++ {
		minFloor := i * floorsPerZone
		maxFloor := min((i+1)*floorsPerZone-1, numFloors-1)

		elevator := NewElevator(i, minFloor, capacity)
		system.elevators[i] = elevator

		system.zones[i] = Zone{
			minFloor: minFloor,
			maxFloor: maxFloor,
			elevator: elevator,
		}

		fmt.Printf("[Sectoring] Zone %d: Floors %d-%d (Elevator %d)\n",
			i, minFloor, maxFloor, i)
	}

	return system
}

func (ss *SectoringSystem) DispatchRequest(req Request) {
	// Find zone containing this floor
	for _, zone := range ss.zones {
		if req.floor >= zone.minFloor && req.floor <= zone.maxFloor {
			fmt.Printf("[Dispatch] Floor %d in Zone [%d-%d] → Elevator %d\n",
				req.floor, zone.minFloor, zone.maxFloor, zone.elevator.id)
			zone.elevator.AssignRequest(req)
			return
		}
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func RunSectoringExample() {
	fmt.Println("\n=== Sectoring Strategy ===")
	fmt.Println("Building divided into zones, each elevator serves one zone\n")

	system := NewSectoringSystem(3, 12, 4)

	// Requests are automatically routed to zone elevator
	requests := []Request{
		{floor: 2, direction: DirectionUp, destination: 5},   // Zone 0
		{floor: 6, direction: DirectionDown, destination: 4}, // Zone 1
		{floor: 9, direction: DirectionUp, destination: 11},  // Zone 2
	}

	fmt.Println("\nDispatching requests:")
	for i, req := range requests {
		fmt.Printf("\nPassenger %d:", i)
		system.DispatchRequest(req)
	}

	fmt.Println("\n✓ Sectoring example complete!")
}

func main() {
	RunSectoringExample()
}

Advanced: Group Elevator Dispatch

package main

import (
	"fmt"
	"sync"
)

// GroupDispatchSystem coordinates elevators to minimize global wait time
type GroupDispatchSystem struct {
	elevators []*Elevator
	mu        sync.Mutex
}

func NewGroupDispatchSystem(elevators []*Elevator) *GroupDispatchSystem {
	return &GroupDispatchSystem{
		elevators: elevators,
	}
}

// OptimalDispatch finds globally optimal assignment
func (gds *GroupDispatchSystem) OptimalDispatch(requests []Request) {
	gds.mu.Lock()
	defer gds.mu.Unlock()

	// For each request, find best elevator considering ALL pending requests
	for _, req := range requests {
		bestElevator := gds.findOptimalElevator(req)
		bestElevator.AssignRequest(req)
	}
}

func (gds *GroupDispatchSystem) findOptimalElevator(req Request) *Elevator {
	var bestElevator *Elevator
	minTotalCost := math.MaxInt32

	// Try assigning to each elevator and calculate total system cost
	for _, elevator := range gds.elevators {
		totalCost := gds.calculateSystemCost(elevator, req)

		if totalCost < minTotalCost {
			minTotalCost = totalCost
			bestElevator = elevator
		}
	}

	return bestElevator
}

func (gds *GroupDispatchSystem) calculateSystemCost(assignedElevator *Elevator, newReq Request) int {
	// Calculate total cost if we assign newReq to assignedElevator
	totalCost := 0

	for _, elevator := range gds.elevators {
		cost := 0

		if elevator == assignedElevator {
			// This elevator gets the new request
			cost = elevator.CalculateCost(newReq.floor, newReq.direction)
		} else {
			// Calculate cost for existing requests
			elevator.mu.Lock()
			for _, req := range elevator.requests {
				cost += elevator.CalculateCost(req.floor, req.direction)
			}
			elevator.mu.Unlock()
		}

		totalCost += cost
	}

	return totalCost
}

func RunGroupDispatchExample() {
	fmt.Println("\n=== Group Elevator Dispatch ===")
	fmt.Println("Optimize globally across all elevators\n")

	elevators := []*Elevator{
		NewElevator(0, 0, 4),
		NewElevator(1, 5, 4),
		NewElevator(2, 10, 4),
	}

	system := NewGroupDispatchSystem(elevators)

	// Batch of requests arrive simultaneously
	requests := []Request{
		{floor: 3, direction: DirectionUp, destination: 7},
		{floor: 8, direction: DirectionDown, destination: 2},
		{floor: 1, direction: DirectionUp, destination: 9},
	}

	fmt.Println("Finding optimal assignment for batch of requests...")
	system.OptimalDispatch(requests)

	fmt.Println("\n✓ Group dispatch example complete!")
}

func main() {
	RunGroupDispatchExample()
}

Key Go Patterns

1. Cost-Based Selection

bestElevator := elevators[0]
bestCost := elevators[0].CalculateCost(request)

for _, e := range elevators[1:] {
    cost := e.CalculateCost(request)
    if cost < bestCost {
        bestCost = cost
        bestElevator = e
    }
}

2. State Machine for Direction

type Direction int

const (
    DirectionIdle
    DirectionUp
    DirectionDown
)

func (e *Elevator) updateDirection() {
    // State transitions based on requests
}

3. Ticker for Periodic Movement

ticker := time.NewTicker(500 * time.Millisecond)

for {
    select {
    case <-ticker.C:
        e.move()  // Move one floor
    }
}

4. Request Queue with Filtering

newRequests := make([]Request, 0)

for _, req := range e.requests {
    if shouldKeep(req) {
        newRequests = append(newRequests, req)
    }
}

e.requests = newRequests

Performance Considerations

Algorithm Comparison

Algorithm	Avg Wait	Max Wait	Throughput	Fairness	Energy
Nearest-First	Medium	High	Medium	Low	High
SCAN	Low	Medium	High	Medium	Low
LOOK	Low	Low	High	Medium	Low
Sectoring	Medium	Low	Medium	High	Medium

Optimization Metrics

Average Wait Time: Sum of all wait times / number of passengers
Maximum Wait Time: Longest wait any passenger experienced
Total Travel Distance: Sum of all floors traveled by all elevators
Load Balance: Standard deviation of requests per elevator

Rush Hour Handling

// Detect rush hour patterns
if morningRushHour {
    // All elevators go to ground floor
    for _, e := range elevators {
        e.SetExpressMode(0) // Go to floor 0
    }
}

if eveningRushHour {
    // Distribute across building
    for i, e := range elevators {
        targetFloor := (numFloors / len(elevators)) * i
        e.SetExpressMode(targetFloor)
    }
}

Advantages of This Pattern

✓ Multi-objective optimization - Balance multiple goals ✓ Decentralized coordination - No single point of failure ✓ Adaptable - Handles different traffic patterns ✓ Scalable - Works with any number of elevators ✓ Realistic - Models real-world scheduling

When to Use

✓ Use when:

Multiple resources serve multiple requests
Need to optimize multiple objectives
Decentralized coordination preferred
Real-time decision making required

✗ Avoid when:

Single resource (no scheduling needed)
Central coordinator is better
Requests can’t be prioritized/reordered
Optimal solution required (NP-hard)

Variations

1. Express Elevators

type Elevator struct {
    isExpress bool
    expressFloors []int  // Only stops at these floors
}

2. Priority Passengers

type Request struct {
    priority int  // VIP, normal, low
}

// Serve high priority first

3. Predictive Dispatch

// Machine learning to predict demand
func (es *ElevatorSystem) PredictDemand(timeOfDay time.Time) []Request {
    // Historical patterns
    // Position elevators proactively
}

4. Double-Deck Elevators

type DoubleDeckElevator struct {
    lowerCar *Elevator
    upperCar *Elevator  // Always one floor above lower
}

Try It Yourself

Compare algorithms - Test SCAN vs LOOK vs Nearest-First
Add rush hour - Simulate morning/evening patterns
Implement priority - VIP passengers get faster service
Add express elevators - Some elevators skip floors
Measure metrics - Track wait time, travel time, energy
Optimize dispatch - Try different cost functions
Add building features - Lobby, parking, sky lobbies

The Elevator Problem: Scheduling and Load Balancing