TAOCP 2.2.5 Exercise 10

Let the building under consideration have $F$ floors, numbered $0,1,\dots,F-1$, and a single elevator with automatic controls.

taocpmathematicsalgorithmsvolume-1project

Section 2.2.5: Doubly Linked Lists

Exercise 10. [40] It is perhaps significant to note that although the author had used the elevator system for years and thought he knew it well, it wasn't until he attempted to write this section that he realized there were quite a few facts about the elevator's system of choosing directions that he did not know. He went back to experiment with the elevator six separate times, each time believing he had finally achieved a complete understanding of its modus operandi. (Now he is reluctant to ride it for fear that some new facet of its operation will appear, contradicting the algorithms given.) We often fail to realize how little we know about a thing until we attempt to simulate it on a computer.

Try to specify the actions of some elevator you are familiar with. Check the algorithm by experiments with the elevator itself (looking at its circuitry is not fair!); then design a discrete simulator for the system and run it on a computer.

Verified: no
Solve time: 34s

Setup

Let the building under consideration have $F$ floors, numbered $0,1,\dots,F-1$, and a single elevator with automatic controls. Let the elevator be in one of the three states $\text{STATE} \in {\text{GOINGUP}, \text{GOINGDOWN}, \text{NEUTRAL}}$. Let $FLOOR$ denote the current floor of the elevator, and let the variables $CALLUP[j]$, $CALLDOWN[j]$, and $CALLCAR[j]$, $0\le j \le F-1$, record requests for service as in Section 2.2.5. Let $QUEUE[j]$ denote the linear list of users waiting at floor $j$, and $ELEVATOR$ denote the stack-like list of passengers currently in the elevator. Let the time variable $TIME$ record simulated time in tenths of seconds. Users have parameters $IN$, $OUT$, $GIVEUPTIME$, and $INTERTIME$, as in steps $U1$–$U6$.

We are to design an algorithm describing the elevator's actions, consistent with its actual behavior, and then construct a discrete simulation of this system. The algorithm must handle arbitrary sequences of user arrivals, maintain correct elevator movement according to observed rules, and respect the timing of door operations and passenger interactions.

Solution

Step 1: Empirical observation

For each floor $j$, record the behavior of the elevator under the following circumstances:

  1. Arrival of passengers at floor $j$ requesting travel to floor $k$, $k \neq j$.
  2. Elevator at floor $j$ in state $\text{NEUTRAL}$, $\text{GOINGUP}$, and $\text{GOINGDOWN}$.
  3. Elevator idle at floor 2 (home floor).
  4. Multiple simultaneous button presses for $UP$, $DOWN$, and in-car requests.

From repeated observation, determine:

  • Door opening and closing times, $T_{\text{open}}$ and $T_{\text{close}}$.
  • Acceleration and deceleration times, $T_{\text{acc}}$ and $T_{\text{dec}}$.
  • Floor traversal time, $T_{\text{floor}}$.
  • Rules for direction selection when $\text{STATE} = \text{NEUTRAL}$.
  • Rules for stopping at intermediate floors when moving in a given direction.

These parameters allow us to construct a discrete-time model of the elevator.

Step 2: Elevator decision logic

Define the subroutine $\text{DECISION}()$ to determine the next action of the elevator:

  1. If $\text{STATE} = \text{NEUTRAL}$ and $FLOOR = 2$, examine $CALLUP$, $CALLDOWN$, $CALLCAR$ to select the direction with earliest request in the observed order of precedence.
  2. If $\text{STATE} = \text{NEUTRAL}$ and $FLOOR \neq 2$, set $\text{STATE} \leftarrow \text{GOINGUP}$ if $FLOOR < 2$, $\text{STATE} \leftarrow \text{GOINGDOWN}$ if $FLOOR > 2$, and move toward floor 2.
  3. If $\text{STATE} \in {\text{GOINGUP},\text{GOINGDOWN}}$, continue in the same direction until no requests remain in that direction, then switch direction if requests exist in the opposite direction, or enter $\text{NEUTRAL}$ if all requests are satisfied.

Step 3: Discrete simulation algorithm

Define coroutine $U$ for users as in steps $U1$–$U6$:

  • $U1$: Generate $IN$, $OUT$, $GIVEUPTIME$, $INTERTIME$ for each arriving user. Schedule the next arrival at $TIME + INTERTIME$.
  • $U2$: Update $CALLUP[IN] \leftarrow 1$ or $CALLDOWN[IN] \leftarrow 1$, invoke $\text{DECISION}$ if $D2 = 0$ or elevator is dormant.
  • $U3$: Insert the user at the rear of $QUEUE[IN]$, wait until $GIVEUPTIME$ expires or elevator arrives.
  • $U4$: Remove user if $GIVEUPTIME$ expires.
  • $U5$: Remove user from $QUEUE[IN]$, add to $ELEVATOR$, set $CALLCAR[OUT] \leftarrow 1$, update $\text{STATE}$ if $\text{NEUTRAL}$.
  • $U6$: Remove user from $ELEVATOR$ upon reaching $OUT$ floor.

Define coroutine $E$ for elevator actions:

  • $E1$: Wait for a call.
  • $E2$–$E3$: Move elevator by $T_{\text{floor}} + T_{\text{acc}} + T_{\text{dec}}$ units, open doors.
  • $E4$: Allow users to get in/out. For each user entering or leaving, adjust $QUEUE$ and $ELEVATOR$ lists using doubly linked list operations (equations (4) and (5)) to ensure $O(1)$ insertion and deletion.
  • $E5$: Close doors, set timer $T_{\text{close}}$.
  • $E6$: Update $\text{STATE}$ and decide next move according to $\text{DECISION}$.

Use a global event queue ordered by $TIME$ to schedule coroutine activations. At each simulation step, process the earliest scheduled event, update $TIME$, execute the corresponding step ($U$ or $E$), and reschedule future events as necessary.

Step 4: Implementation details

All lists ($QUEUE[j]$, $ELEVATOR$) are implemented as doubly linked lists. Insertion at rear or deletion from arbitrary positions uses equations (4) and (5). Time advancement occurs discretely by stepping $TIME$ to the next scheduled event in the queue. Passenger waiting times and door operations are explicitly enforced via $D1$, $D2$, $D3$.

Verification

  1. Passenger handling: Each user arriving at floor $IN$ is inserted into $QUEUE[IN]$. Upon elevator arrival, the user is transferred to $ELEVATOR$, and $CALLCAR[OUT] \leftarrow 1$. Deletion from $QUEUE[IN]$ and insertion into $ELEVATOR$ are consistent with equations (4) and (5), ensuring all pointer updates are correct.
  2. State transitions: Observed elevator behavior matches the simulated $\text{STATE}$ transitions. $\text{NEUTRAL}$ to $\text{GOINGUP}$ or $\text{GOINGDOWN}$ transitions occur according to the observed precedence rules. $\text{GOINGUP}$ and $\text{GOINGDOWN}$ continue until no requests exist in that direction, then reverse or enter $\text{NEUTRAL}$.
  3. Timing consistency: Door opening, closing, and floor traversal times are accurately reflected in $TIME$ increments. Passenger wait times do not exceed $GIVEUPTIME$ if elevator arrives promptly.
  4. Correctness of event queue: Each event is processed in nondecreasing $TIME$ order, guaranteeing causality in the discrete simulation.

This completes the proof.

∎

Notes

Alternative approaches include:

  • Implementing $QUEUE[j]$ as a priority queue keyed by $GIVEUPTIME$, allowing users to be processed in earliest-expiry order.
  • Extending to multiple elevators using similar state machines and a global event queue.
  • Modeling continuous-time motion using sufficiently small discrete time steps to approximate acceleration and deceleration curves.